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

穷举法（蛮力法、暴力法）穷举法（蛮力法、暴力法）信息科学与工程学院信息科学与工程学院 计算机科学与技术计算机科学与技术 陈叶芳陈叶芳真分数递增序列真分数递增序列【例例】：求真分数递增序列求真分数递增序列统计统计分母分母在区间在区间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+;cn=i;dn=j;/找到一个最简真分数找到一个最简真分数真分数递增序列真分数递增序列for(i=1;i=n-1;i+)/冒泡排序冒泡排序for(j=1;jcj+1*dj)h=cj;cj=cj+1;cj+1=h;/分子分母同时交换分子分母同时交换 h=dj;dj=dj+1;dj+1=h;高斯8皇后问题在国际象棋的8*8方格的棋盘上如何放置8个皇后，使这8个皇后不能互相攻击，即任意两个皇后不允许处在同一横排、同一纵列，也不允许处在同一与棋盘边框呈45度角的斜线上。高斯8皇后问题一个解用一个8位数表示，第k个数字为j，表示第k行的第j格放置一个皇后高斯8皇后问题条件1.不允许出现在同一横排、同一纵列：要求8位数中数字位数中数字18各出现各出现1次次。因此解空间为12345678,87654321。数字18的排列为9的倍数？循环步长可优化为9。为了判断数字18在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(设jk)，即：|g(j)-g(k)|不等于j-kj-k代表什么？g(j)-g(k)代表什么？高斯8皇后问题int s,k,i,j,t,x,f9,g9;long a,y;s=0;for(a=12345678;a=87654321;a+=9)y=a;k=0;for(i=1;i0)x=y%10;fx=fx+;y=y/10;k+;gk=x;/分离各数字，用数组分离各数字，用数组f统计统计for(t=0,i=1;i=8;i+)if(fi!=1)t=1;/数字数字18出现不为出现不为1次，返回次，返回 if(t=1)continue;for(k=1;k=7;k+)for(j=k+1;j=8;j+)if(fabs(gj-gk)=j-k)t=1;if(t=1)continue;/45度斜线上，返回度斜线上，返回s+;/解个数统计解个数统计高斯8皇后问题