{
copy_num(1); /*复制分解的数字*/ if(!comp_num(2))
continue; /*若每列的前两位的组成与素数相矛盾，则试探下一个数*/ for(array[2][0]=0;array[2][0] copy_num(2); /*复制分解的数字*/ if(!comp_num(3)) continue; /*若每列的前三位的组成与素数相矛盾，则试探下一个数*/ for(i4=0;i4 array[3][0]=select[i4]; copy_num(3); /*复制分解的数字*/ for(flag=1,i=1;flag&&i<=4;i++) /*判断每列是否可逆素数*/ if(!find1(i))flag=0; if(flag&&find2()) /*判断对角线是否为可逆素数*/ { printf(\输出幻方矩阵*/ } } } } } int num(int number) /*判断是否可逆素数*/ { int j; if(!ok(number)) return 0; for(j=0;number>0;number/=10) /*将素数变为反序数*/ j=j*10+number; if(!ok(j)) return 0; /*判断反序数是否为素数*/ return 1; } int ok(int number) /*判断是否为素数*/ { int i,j; if(number%2==0) return 0; j=sqrt((double)number)+1; for(i=3;i<=j;i+=2) if(number%i==0) return 0; return 1; } void process(int i) /*将第i个整数分解为数字并存入数组*/ { int j,num; num=number[i][0]; for(j=4;j>=1;j–,num/=10) number[i][j]=num; } void copy_num(int i) /*将array[i][0]指向的素数的各位数字复制到array[i]中*/ { int j; for(j=1;j<=4;j++) array[i][j]=number[array[i][0>[j]; } int comp_num(int n) /*判断array中每列的前n位是否与可逆素数允许的前n位矛盾*/ { static int ii; /*用内部静态变量保存前一次查找到的元素下标*/ static int jj; /*ii:前一次查找前二位的下标，jj:前一次查找前三位的下标*/ int i,num,k,*p; /*p:指向对应的要使用的前一次下标ii或jj*/ int *pcount; /*pcount:指向要使用的临时数组数量的计数器*/ switch(n){ /*根据n的值选择对应的一组控制变量*/ case 2:pcount=&lcount[0];p=ⅈbreak; case 3:pcount=&lcount[1];p=&jj;break; default:return 0; } for(i=1;i<=4;i++) /*对四列分别进行处理*/ { for(num=0,k=0;k if(num<=larray[n-2][*p]) /*与前一次最后查找到的元素进行比较*/ for(;*p>=0&&num for(;p *p=0; return 0; } if(num!=larray[n-2][*p]) return 0; /*前n位不是可逆素数允许的值则返回0*/ } return 1; } int find1(int i) /*判断列方向是否是可逆素数*/ { int num,j; for(num=0,j=0;j<4;j++) num=num*10+array[j][i]; return find0(num); } int find2(void) /*判断对角线方向是否是可逆素数*/ { int num1,num2,i,j; for(num1=0,j=0;j<4;j++) num1=num1*10+array[j][j+1]; for(num2=0,j=0,i=4;j<4;j++,i–) num2=num2*10+array[j][i]; if(find0(num1)) return(find0(num2)); else return 0; } int find0(int num) /*查找是否为满足要求的可逆素数*/ { static int j; if(num<=number[j][0])for(;j>=0&&num void p_array(void) /*输出矩阵*/ { int i,j; for(i=0;i<4;i++) { for(j=1;j<=4;j++) printf(\printf(\} } *问题的进一步讨论 程序中大量技巧是用于尽早发现矛盾，减少循环次数，缩短运行时间。从实际效果看是相当不错的。但目前的程序仍然可以进一步优化。 当第四行设定了前三行后，尚未设定的行就没必要再使用穷举的方法，因为列方向设定好的三位数字已经限制了最后一个数字可能的取值，在可逆数中找出前三位数字与设定好的三位数字相同的素数。这些素数就是在这一列前面已设定好的三位数字的限制条件下可能的取值。此时每一列上只有不超过四个可能的取值。找出全部各列可能的取值(可能的四位可逆素数)，求出它们的交集。若交集为空，即没有共同的可能取值，则列间数据相互矛盾否满足则将交集中的数据填 入矩阵中就是题目的一个解。 算法可再进一步优化。先穷举一、二和四列的数据，然后用上面的算法来确定第三行的值，这样可进一步缩小穷举的范围，提高运行效率。 分析输出的结果。可以看出本题的基本解只有17种，每个解可通过旋转与反射获得同构的其它7个解，可以进一步改进程序，只输出17个基本解。 *思考题 用1到16构成一个四阶幻方，要求任意相邻两个方格中的数字之和均为素数。 36.百钱百鸡问题 中国古代数学家张丘建在他的《算经》中提出了著名的―百钱买百鸡问题‖：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？ *问题分析与算法设计 设鸡翁、鸡母、鸡雏的个数分别为x,y,z，题意给定共100钱要买百鸡，若全买公鸡最多买20只，显然x的值在0~20之间；同理，y的取值范围在0~33之间，可得到下面的不定方程： 5x+3y+z/3=100 x+y+z=100 所以此问题可归结为求这个不定方程的整数解。 由程序设计实现不定方程的求解与手工计算不同。在分析确定方程中未知数变化范围的前提下，可通过对未知数可变范围的穷举，验证方程在什么情况下成立，从而得到相应的解。 *程序说明与注释 #include int x,y,z,j=0; printf(\for(x=0;x<=20;x++) /*外层循环控制鸡翁数*/ for(y=0;y<=33;y++) /*内层循环控制鸡母数y在0~33变化*/ { z=100-x-y; /*内外层循环控制下，鸡雏数z的值受x,y的值的制约*/ if(z%3==0&&5*x+3*y+z/3==100) /*验证取z值的合理性及得到一组解的合理性*/ printf(\} } *运行结果 Follwing are possible plans to buy 100 fowls with 100 Yuan. 1:cock=0 hen=25 chicken=75 2:cock=4 hen=18 chicken=78 3:cock=8 hen=11 chicken=81 4:cock=12 hen=4 chicken=84 *问题的进一步讨论 这类求解不定方程总理的实现，各层循环的控制变量直接与方程未知数有关，且采用对未知数的 取值范上穷举和组合的方法来复盖可能得到的全部各组解。能否根据题意更合理的设置循环控制条件来减少这种穷举和组合的次数，提高程序的执行效率，请读者考虑 37.爱因斯坦的数学题 爱因斯坦出了一道这样的数学题：有一条长阶梯，若每步跨2阶，则最最后剩一阶，若每步跨3 阶，则最后剩2阶，若每步跨5阶，则最后剩4阶，若每步跨6阶则最后剩5阶。只有每次跨7阶，最后才正好一阶不剩。请问这条阶梯共有多少阶？ *问题分析与算法设计 根据题意，阶梯数满足下面一组同余式： x≡1 (mod2) x≡2 (mod3) x≡4 (mod5) x≡5 (mod6) x≡0 (mod7) *程序说明与注释 #include int i=1; /*i为所设的阶梯数*/ while(!((i%2==1)&&(i%3==2)&&(i%5==4)&&(i%6==5)&&(i%7==0))) ++i; /*满足一组同余式的判别*/ printf(\} *运行结果 Staris_number=119 *问题的进一步讨论 此题算法还可考虑求1、2、4、5的最小公倍数n，然后判t(t为n-1)≡0(mod7)是否成立，若不成立则t=t+n,再进行判别，直至选出满足条件的t值。请自行编写程序实现 38.换分币 用一元人民币兑换成1分、2分和5分硬币，共有多少种不同的兑换方法。 *问题分析与算法设计 根据题意设i,j,k分别为兑换的1分、2分、5分硬币所具有的钱数(分)，则i,j,k的值应满足： i+j+k=100 *程序说明与注释 #include int i,j,k,count=1; printf(\for(i=0;i<=100;i++) /*i为1分硬币钱数，可取值0,1，2…,100*/ for(j=0;j<=100-i;j+=2) /*j为2分硬币钱数，可取0值，2，4，…，100*/