C语言穷举-习题参考.ppt

《C语言穷举-习题参考.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、穷举法（蛮力法、暴力法）信息科学与工程学院计算机科学与技术陈叶芳真分数递增序列【例】：求真分数递增序列统计分母在区间[a,b]的最简真分数（分子小于分母，且分子分母无公因数）共有多少个？并求这些最简真分数升序序列中的第k项。（正整数a,b,k从键盘输入）升序排列后的第k项=c(k)/d(k)，数组c和d分别存储分子和分母在范围[a,b]内穷举分母j:对每一个分母j穷举分子:a,a+1,…,b1,2,…j-1若分子i与分母j存在大于1的公因数，非最简，则忽略；否则得一个最简真分数c(n)/d(n)。对最简序列排序最

2、简真分数n=0;//计数for(j=a;j<=b;j++)//穷举分母for(i=1;i<=j-1;i++)//穷举分子{for(t=0,u=2;u<=i;u++)if(j%u==0&&i%u==0){t=1;break;}//分子分母有公因数舍去if(t==0){n++;c[n]=i;d[n]=j;}//找到一个最简真分数}}真分数递增序列for(i=1;i<=n-1;i++)//冒泡排序for(j=1;j<=n-i;j++)if(c[j]*d[j+1]>c[j+1]*d[j]){h=c[j];c[j]=c[j

3、+1];c[j+1]=h;//分子分母同时交换h=d[j];d[j]=d[j+1];d[j+1]=h;}高斯8皇后问题在国际象棋的8*8方格的棋盘上如何放置8个皇后，使这8个皇后不能互相攻击，即任意两个皇后不允许处在同一横排、同一纵列，也不允许处在同一与棋盘边框呈45度角的斜线上。高斯8皇后问题一个解用一个8位数表示，第k个数字为j，表示第k行的第j格放置一个皇后高斯8皇后问题条件1.不允许出现在同一横排、同一纵列：要求8位数中数字1~8各出现1次。因此解空间为[12345678,87654321]。数字1~8的

4、排列为9的倍数？循环步长可优化为9。为了判断数字1~8在8位数中各出现1次，设置f数组，f(x)统计数字x的次数，若f(1)~f(8)均等于1，符合条件。否则测试下一数据。高斯8皇后问题条件2.不允许处在同一与棋盘边框45度角的斜线上，设置g数组，若8位数的第k个数字为x（g(k)=x），则要求第j个数字与第k个数字的绝对值不等于j-k(设j>k)，即：

5、g(j)-g(k)

6、不等于j-kj-k代表什么？g(j)-g(k)代表什么？高斯8皇后问题ints,k,i,j,t,x,f[9],g[9];longa,y;s=

7、0;for(a=12345678;a<=87654321;a+=9){y=a;k=0;for(i=1;i<=8;i++)f[i]=0;//统计数字i的次数while(y>0){x=y%10;f[x]=f[x]++;y=y/10;k++;g[k]=x;}//分离各数字，用数组f统计for(t=0,i=1;i<=8;i++)if(f[i]!=1)t=1;//数字1~8出现不为1次，返回if(t==1)continue;for(k=1;k<=7;k++)for(j=k+1;j<=8;j++)if(fabs(g[j]-g

8、[k])==j-k)t=1;if(t==1)continue;//45度斜线上，返回s++;//解个数统计}高斯8皇后问题