八皇后最简真分数.ppt

穷举法（蛮力法、暴力法） 信息科学与工程学院 计算机科学与技术 陈叶芳 真分数递增序列 【例】：求真分数递增序列 统计分母在区间[a,b]的最简真分数（分子小于分母，且分子分母无公因数）共有多少个？并求这些最简真分数升序序列中的第k项。（正整数a,b,k从键盘输入） 最简真分数 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==0i%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; } 高斯8皇后问题 在国际象棋的8*8方格的棋盘上如何放置8个皇后，使这8个皇后不能互相攻击，即任意两个皇后不允许处在同一横排、同一纵列，也不允许处在同一与棋盘边框呈45度角的斜线上。 高斯8皇后问题 一个解用一个8位数表示，第k个数字为j，表示第k行的第j格放置一个皇后 高斯8皇后问题 条件1.不允许出现在同一横排、同一纵列：要求8位数中数字1~8各出现1次。 高斯8皇后问题 条件2.不允许处在同一与棋盘边框45度角的斜线上，设置g数组，若8位数的第k个数字为x（g(k)=x），则要求第j个数字与第k个数字的绝对值不等于j-k(设jk)，即： |g(j)-g(k)|不等于j-k 高斯8皇后问题 int s,k,i,j,t,x,f[9],g[9]; long a,y; s=0; for(aaa+=9) { y=a; k=0; for(i=1;i=8;i++) f[i]=0; //统计数字i的次数 while(y0) {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皇后问题 * 升序排列后的第k项=c(k)/d(k)，数组c和d分别存储分子和分母 在范围[a,b]内穷举分母j: 对每一个分母j穷举分子: a,a+1,…,b 1,2,…j-1 若分子i与分母j存在大于1的公因数，非最简，则忽略；否则得一个最简真分数c(n)/d(n)。 对最简序列排序 因此解空间为87654321]。 数字1~8的排列为9的倍数？循环步长可优化为9。 为了判断数字1~8在8位数中各出现1次，设置f数组，f(x)统计数字x的次数，若f(1)~f(8)均等于1，符合条件。否则测试下一数据。 j-k代表什么？ g(j)-g(k)代表什么？