程序设计大赛 暴力求解法
一、 知识点
二、 题目应用
1．输入正整数n，按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中a~j恰好为数字0~9的一个排列，2<=n<=79。 样例输入：62
样例输出：79546 / 01283 = 62 94736 / 01528 = 62
【分析】
枚举0~9的所有排列？没这个必要。只需要枚举fghij就可以算出abcde，然后判断是否有所有数字都不相同即可。不仅程序简单，而且枚举量也从10！=3628800降低至不到1万。由此可见，即使采取暴力枚举，也是需要认真分析问题的。 #include
int a[11]; int k=0;
while(i!=0) //此程序最重要的地方也就是比较这十个数字各不相同，要用数组存起来 {
a[k++]=i; i/=10; }
while(j!=0)
{
a[k++]=j; j/=10; }
int flag;
if(k==9) flag=0; //有十个数，所以这里是9 int l;
for(k=0;k<10;k++)
for(l=k+1;l<10;l++)
if(!flag) //如果flag为0说明分母为四位，则第一位为0 if(a[k]==a[l]||a[k]==0) return 0; else if(flag)
if(a[k]==a[l]) return 0; return 1; }
int main(int argc, char *argv[]) {
int i,n,m;
scanf(\
for(i=1234;i<98765;i++) //i<=49876 {
m=i*n;
if(m>100000) break; else if(test(m,i)) {
printf(\ } }
return 0; }
2 最大乘积
输入n个元素组成的序列S，你需要找出一个乘积最大的连续子序列。如果这个最大的乘积不是整数，应输出-1(表示无解)。1<=n<=18, -10<=Si<=10。 样例输入： 3
2 4 -3 5
2 5 -1 2 -1 样例输出： 8 20
【分析】
连续子序列有两个要素：起点和终点，因此只需枚举起点和终点即可。由于每个元素的绝对值不超过10，一共又不超过18个元素，最大可能的乘积不会超过10^18，可以用
long long存下。 #include
{ int n, S[18];
while(scanf(\ { for(int i = 0; i < n; i++) scanf(\
int result[172], count = 0;
//result数组用来存各连续子序列的值，子序列的个数为n(n+1)/2
for(i = 0; i < n-1; i++) //求出各连续子序列的值，存在数组result中
{ result[count] = S[i];
for(int j = i+1; j < n; j++) { count++;
result[count] = result[count-1] * S[j]; }
count++; }
int mid = result[0]; //找出result中的最大值，为所求的值 for(i = 1; i < count; i++)
mid = (mid > result[i]) ? mid : result[i]; if(mid > 0)
printf(\ else
printf(\ }
return 0; }
3.分数拆分
输入正整数，找到所有的正整数x>=y，使得1/k=1/x+1/y
4．判断是否为双基回文数 S<106,比s大的最小的 #include
int fun(int x,int n) //将十进制的x转化为n进制，判断是否为回文数 {
int a[100],b[100]; int k=0;
for(int i=0;;i++)
{ a[i]=x%n; x=x/n;
if(x==0) break;
} k=i; int j;
for(j=k,i=0;j>=0;i++,j--) b[i]=a[j];
b[k+1]='\\0'; //求出x的n进制数 int flag=1;
for (i=0;;i++) {
if(i>(k/2)) break; if (b[i]!=b[k-i]) {
flag=0;break; } }
if(flag) return 1; //是n进制的回文数 else return 0; //不是 }
int main()
{ int n,k,flag,i;
while (scanf(\ {
for(;;n++) //枚举，找出最小的 { k=0;
flag = 0;
for(i=2;i<=10;i++) {
if(fun(n,i)) k++;
if(k>=2){flag=1; break;} }
if(flag){ printf(\
} }
return 0; }
4.子集二进制算法介绍：
若集合S包含n个元素x1， x2, ···, xn, 则用一种简介的表示S的子集的方法是，把它表示成由0和 1组成的串，其中，若xk 属于S，则串中的第K个元素为1，否则为0. 例如，若n = 3, 则8(= 23)个串及其对应的子集如下所示：
000 空集 100 {x1 }
001 {x3} 101 {x1, x3} 010 {x2} 110 {x1, x2}
011 {x2,x3 } 111 {x1, x2, x3} 通过这个列表，可以看出如何按照上面的次序来生成这些0-1串：先寻找最右边的0，把它变成1，然后把它右边的所有数字都变成0.
3. 问题 假金币
Gold Bar银行收到可靠消息：在M组金币中每组都有一个重量不同的假金币(其他金币的重量相同)。经济危机之后他们只有一台天平可用。用这台天平，可以称量出左边托盘中的物体是轻于、重于或等于右边托盘中的物体。
为了分别出假金币，银行职员将所有的金币编为1-N号。然后用天平称量不同的金币组合，每次仔细记载称量金币的编号和结果。
现在要求编写一个程序，帮助银行职员根据称量记录找出假金币的编号。 输入：
第一行为金币组数M，后面是每组金币情况。
第二行输入两个空格隔开的整数N和K，N是金币的总数(2<=N<=1000)，K是称量的次数(1<=K<=100)。随后的2K行记录称量的情况和结果，连续两行记录一次称量：第1行首先是Pi(1<=Pi<=N/2) ，表示两边托盘中放置的金币数目，随后是左边托盘中Pi个金币编号和右边托盘中Pi个金币编号，所有的数之间都由空格隔开；第2行用<，>，=和记录称量结果。
<表示左边托盘中的金币比右边的轻 >表示左边托盘中的金币比右边的重 =表示左右两边托盘中的金币一样重
输出
输出假金币的编号。如果根据称量记录无法确定假金币，输出0。 输入样例 1 5 3
2 1 2 3 4 <
1 1 4 =
1 2 5 = 输出样例 3
short jo(int j,int *s, char c) {
//函数判断假设j号金币是假的与称量结果是否矛盾 //s是称重记录，其第一个元素是砝码个数 //c是称量结果 m=s[0]<<1;
程序设计大赛 暴力求解
