c语言经典例题.doc

×8国际象棋盘上,有8个皇后,每个皇后占一格;要求皇后间不会出现相互“攻击”的现象,即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法。*问题分析与算法设计这是一个古老的具有代表性的问题,用计算机求解时的算法也很多,这里仅介绍一种。采用一维数组来进行处理。数组的下标i表示棋盘上的第i列,a[i]的值表示皇后在第i列所放的位置。如:a[1]=5,表示在棋盘的第一例的第五行放一个皇后。程序中首先假定a[1]=1,表示第一个皇后放在棋盘的第一列的第一行的位置上,然后试探第二列中皇后可能的位置,找到合适的位置后,再处理后续的各列,这样通过各列的反复试探,可以最终找出皇后的全部摆放方法。程序采用回溯法,算法的细节参看程序。*程序说明与注释#include<>#defineNUM8/*定义数组的大小*/inta[NUM+1];intmain(){inti,k,flag,not_finish=1,count=0;i=1;/*正在处理的元素下标,表示前i-1个元素已符合要求,正在处理第i个元素*/a[1]=1;/*为数组的第一个元素赋初值*/printf("Thepossibleconfigurationof8queensare:\n");while(not_finish)/*not_finish=1:处理尚未结束*/{while(not_finish&&i<=NUM)/*处理尚未结束且还没处理到第NUM个元素*/{for(flag=1,k=1;flag&&k<i;k++)/*判断是否有多个皇后在同一行*/if(a[k]==a[i])flag=0;for(k=1;flag&&k<i;k++)/*判断是否有多个皇后在同一对角线*/if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))flag=0;if(!flag)/*若存在矛盾不满足要求,需要重新设置第i个元素*/{if(a[i]==a[i-1])/*若a[i]的值已经经过一圈追上a[i-1]的值*/{i--;/*退回一步,重新试探处理前一个元素*/if(i>1&&a[i]==NUM)a[i]=1;/*当a[i]为NUM时将a[i]的值置1*/elseif(i==1&&a[i]==NUM)not_finish=0;/*当第一位的值达到NUM时结束*/elsea[i]++;/*将a[i]的值取下一个值*/}elseif(a[i]==NUM)a[i]=1;elsea[i]++;/*将a[i]的值取下一个值*/}elseif(++i<=NUM)if(a[i-1]==NUM)a[i]=1;/*若前一个元素的值为NUM则a[i]=1*/elsea[i]=a[i-1]+1;/*否则元素的值为前一个元素的下一个值*/}if(not_finish){++count;printf((count-1)%3?"[%2d]:":"\n[%2d]:",count);for(k=1;k<=NUM;k++)/*输出结果*/printf("%d",a[k]);if(a[NUM-1]<NUM)a[NUM-1]++;/*修改倒数第二位的值*/elsea[NUM-1]=1;i=NUM-1;/*开始寻找下一个足条件的解*/}}}例如:当n=4,m=8时,将得到如下5个数列:51114211331132212222按照条件使前一个元素的值一定大于等于当前元素的值,不断地向前推就可以解决问题。下面的程序允许用户选定M和N,输出满足条件的所有数列。输入m和n(20>=m>=n>0)求出满足以下方程的正整数数列i1,i2,...,in,使得:i1+i1+...+in=m,且i1>=i2...>=in。例如:当n=4,m=8时,将得到如下5个数列:51114211331132212222*问题分析与算法设计可将原题抽象为:将M分解为N个整数,且N个整数的和为M,i1>=i2>=...>=in。分解整数的方法很低多,由于题目中有"i1>=i2>=.....>=in,提示我们可先确定最右边in元素的值为1,然后按照条件使前一个元素的值一定大于等于当前元素的值,不断地向前推就可以解决问题。下面的程序允许用户选定M和N,输出满足条件的所有数列。*程序说明与注释#include<>#defineNUM10/*允许分解的最大元素数量*/inti[NUM];/*记录分解出的数值的数组*/intmain(){intsum,n,total,k,flag,count=0;printf("Pleaseenterrequriedterms(<=10):");scanf("%d",&n);printf("theirsum:");scanf("%d",&total);sum=0;/*当前从后