穷举法（蛮力法、暴力法）穷举法（蛮力法、暴力法）穷举法（蛮力法、暴力法）穷举法（蛮力法、暴力法）信息科学与工程学院计算机科学与技术陈叶芳信息科学与工程学院计算机科学与技术陈叶芳真分数递增序列【例】：求真分数递增序列•统计分母在区间[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)。对最简序列排序最简真分数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+1];c[j+1]=h;//分子分母同时交换h=d[j];d[j]=d[j+1];d[j+1]=h;}d[j]c[j]1]d[j1]c[j高斯8皇后问题•在国际象棋的8*8方格的棋盘上如何放置8个皇后，使这8个皇后不能互相攻击，即任意两个皇后不允许处在同一横排、同一纵列，也不允许处在同一与棋盘边框呈45度角的斜线上。高斯8皇后问题•一个解用一个8位数表示，第k个数字为j，表示第k行的第j格放置一个皇后高斯8皇后问题•条件1.不允许出现在同一横排、同一纵列：要求8位数中数字1~8各出现1次。•因此解空间为[12345678,87654321]。•数字1~8的排列为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)，即：•|g(j)-g(k)|不等于j-kj-k代表什么？g(j)-g(k)代表什么？高斯8皇后问题ints,k,i,j,t,x,f[9],g[9];longa,y;s=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[k])==j-k)t=1;if(t==1)continue;//45度斜线上，返回s++;//解个数统计}高斯8皇后问题
