计算智能作业4

计算智能作业4

上机报告

一。问题重述：

八后问题：八皇后问题要求在一个８×８的棋盘上放上８个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击．按照国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子．因此，八皇后问题等于要求八个皇后中的任意两个不能被放在同一行或同一列或同一斜线上。问共有多少种解法。

二。算法设计思路：

用循环递归循环来实现的，分别一一测试了每一种摆法，并把它拥有的92种变化表现出来。冲突问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态；对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第i个皇后占领了第j列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。用数组a[i]表示第i个皇后放置的列；i的范围：1—8;对角线数组：b[j](主对角线),c[j]（从对角线），根据程序的运行，去决定主从对角线是否放入皇后。

三。算法描述：

从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。回溯法即从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，不断“回溯”的寻找解的方法。使用数组实现回溯法的思想。当n>8时，便打印出结果。

改进：

考虑开发N皇后问题，添加一个int型的变量，程序一开始要求输入一个数(确定是几皇后问题)，输入后按下enter 后,输出各种解。主程序与八皇后的求解大体相同。

程序：

#include

#include

#include

#include

int QUEENS;

int iCount =0; //记录解的序号的全局变量。

intSite[100]; //记录皇后在各行上的放置位置的全局数组。

void Queen(intn,int QUEENS); //递归求解的函数。递归放置第n个皇后，程序的核心。

void Output(intQUEENS); //输出一个解，即一种没有冲突的放置方案。

int IsValid(intn); //判断第n个皇后放上去之后，是否合法，即是否无冲突。

void main()

{

system("title 32010072203--递归算法皇后问题 ");

int n,QUEENS;

printf("输入n(代表N皇后问题):");

scanf("%d",&n);

cout<

QUEENS=n;

printf(" 递归算法%d皇后的解法：\n",n);

cout<<" "<<"----------------------------------------"<

Queen(0,QUEENS); //从第0行开始递归试探。

}

void Queen(intn,int QUEENS)

{ int i;

if(n == QUEENS) //参数n从0开始，等于QUEENS时便试出了一个解，将它输出并回溯。

{ Output(QUEENS);

return;

}

for(i = 1 ; i <= QUEENS ; i++) //n还没到QUEENS，在第n行的各个列上依次试探。

{Site[n] = i; //在该行的第i列上放置皇后。

if(IsValid(n)) //如果放置没有冲突，就开始下一行的试探。

Queen(n + 1,QUEENS);

}

}

int IsValid(intn)

{ inti;

for(i = 0 ; i < n ; i++) //将第n个皇后的位置依次于前面n－1个皇后的位置比较。

{if(Site[i] == Site[n]) //两个皇后在同一列上，返回0。

return 0;

if(abs(Site[i] - Site[n]) == (n - i)) //两个皇后在同一对角线上，返回0。

return 0;

}

return 1; //没有冲突，返回1。

}

void Output(int QUEENS)

{

int i;

printf("No.%-5d", ++iCount); //输出序号。

for(i = 0 ; i 依次输出各个行上的皇后的位置，即所在的列数。

printf("%d" , Site[i]);

printf("\n");

}

四。时空效率：O(n^2+2n)=O(n^2)

五。遇到的问题与解决方法：

1.首先遇到的问题即因为不清楚国际象棋的规则，所以不知道怎样才是皇后互相不能攻击。然后查阅了象棋规则，了解到需要解决的问题即是使皇后互相不在同一行同一列同一斜线。先复习了下这段时间所学到的各种传统算法，然后选用了回溯法。由于弄明白程序算法是一样的，所以把八皇后改进为N皇后问题。实现用户自己输入N的算法。

2. 为解决皇后互相不在同一行同一列同一斜线这个问题，把棋盘的横坐标定为i，纵坐标定为j,i和j的取值范围是从１到８。当某个皇后占了位置(i,j)时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其它皇后了。用语句实现，可定义如下三个整型数组：a[8],b[15],c[24]。其中：

　　a[j-1]=1 第j列上无皇后

　　a[j-1]=0 第j列上有皇后

　　b[i+j-2]=1 (i,j)的对角线（左上至右下）无皇后

　　b[i+j-2]=0 (i,j)的对角线（左上至右下）有皇后

　　c[i-j+7]=1 (i,j)的对角线（右上至左下）无皇后

　　c[i-j+7]=0 (i,j)的对角线（右上至左下）有皇后

　

六。体会

这次把传统算法按照之前记的笔记，复习及总结了一遍。感觉把各种算法灵活运用到各种实际例题中还是很有难度的，所以每道题也都想了很长时间。这次没来得及把所有题都实现一遍，不过都有好好想一遍思路，等以后有时间还要再去实现。

七。其他题

1.邮票问题：设有n种不同面值的邮票，每封信规定最多能贴m张邮票，写出算法对于给定的n、m ，求出邮资的最大连续区间。（n=4，m=5时，区间为[1，71]）

分析：

本题即求在贴的邮票不多于n张的可满足条件的邮资集.集合问题的关键在于判定元素是否在集合中,对于本题而言,是判断某个邮资是否在贴不多于n张邮票可满足.这个判断问题可以用递归的方法解决.设当前考虑的邮资值为max,最多允许贴n张邮票,记为(max,n).如果首先贴一张面值为xi的邮票,那么剩下的问题是(max-xi,n-1)的问题.如果(max-xi,n-1)可解,那么(max,n)问题也可解.

这个递归的算法可以转化为递推的算法来解决.设piece[value]表示邮资为value时所需最少的邮票数, pieces[MAX]=min{pieces[MAX-x[i]]+1}.当pices[value]<=n时,问题(max,n)可解,否则无解.

程序：

#include

#include

using namespace std;

int main()

{

system("title 32010072203--邮票问题 ");

int x[100];//各种邮票的面值

int pieces[10000];//邮资为value时所需最少的邮票数,

int i,j,m,n,MAX,min;

printf("输入最多粘贴的邮票数n,邮票种数m,邮票的面值xi:");

while(cin>>n>>m)

{

for(i=1;i<=m;i++)

cin>>x[i];

min=x[1];

for(i=2;i<=m;i++)

{

if(x[i]

min=x[i];

}

memset(pieces,0,sizeof(pieces));

MAX=0; //若最大范围为空,则输出MAX=0

while(1)

{

MAX++;//计算邮资为MAX最少需要的邮票张数

for(i=1;i<=m;i++)

if( MAX-x[i]>=0)

{

if(pieces[MAX]==0)

pieces[MAX]=pieces[MAX-x[i]]+1;

if(pieces[MAX]>pieces[MAX-x[i]]+1)

pieces[MAX]=pieces[MAX-x[i]]+1;

}

//判断所需最少邮票张数是否超过n张

if(pieces[MAX]==0||pieces[MAX]>n) //若最大范围不为空,则把结果输出

{

cout<<"区间为【"<】"<

break;

}

}

}

return 0;

}

2.0-1背包问题：求从n种物品中选取若干物品装载容量为m的背包的最佳方案（x1，x2……xn）。其中第i个物品的重量为wi，价值为pi(i=1……n)。在åxiwi£m的前提下，最大。

贪心法

从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1).不能保证求得的最后解是最佳的；
2).不能用来求最大或最小解问题；
3).只能求满足某些约束条件的可行解的范围。
分析：

目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

故该题重点为每次选取单位容量价值最大的物品。

程序：

#include

#define max 100 //最多物品数

void sort (int n,float a[max],float b[max])//按价值密度排序

{

int j,h,k;

float t1,t2,t3,c[max];

for(k=1;k<=n;k++)

c[k]=a[k]/b[k];

for(h=1;h

for(j=1;j<=n-h;j++)

if(c[j]

{t1=a[j];a[j]=a[j+1];a[j+1]=t1;

t2=b[j];b[j]=b[j+1];b[j+1]=t2;

t3=c[j];c[j]=c[j+1];c[j+1]=t3;

}

}

void knapsack(int n,float limitw,floatv[max],float w[max],int x[max])

{float c1; //c1为背包剩余可装载重量

int i;

sort(n,v,w); //物品按价值密度排序

c1=limitw;

for(i=1;i<=n;i++)

{

if(w[i]>c1)break;

x[i]=1; //x[i]为1时，物品i在解中

c1=c1-w[i];

}

}

void main()

{

system("title 32010072203—0-1背包问题（贪心法） ");

int n,i,x[max];

float v[max],w[max],totalv=0,totalw=0,limitw;

cout<<"请输入n和limitw:";

cin>>n >>limitw;

for(i=1;i<=n;i++)

x[i]=0; //物品选择情况表初始化为0

cout<<"请依次输入物品的价值："<

for(i=1;i<=n;i++)

cin>>v[i];

cout<

cout<<"请依次输入物品的重量："<

for(i=1;i<=n;i++)

cin>>w[i];

cout<

knapsack (n,limitw,v,w,x);

cout<<"the selection is:";

for(i=1;i<=n;i++)

{

cout<

if(x[i]==1)

{totalw=totalw+w[i];

totalv=totalv+v[i];}

}

cout<

cout<<"背包的总重量为："<背包所装载总重量

cout<<"背包的总价值为："<背包的总价值

}

3.翻转烙饼排序问题：采用每次只能翻转最上面的若干个数字的方法将n个数排序。要求总的翻转次数最少。

程序：

#include

#include

void cakeSort(int cake[],int size);//排序函数，并输出排序方法

void reverse(int array[],int size);//数组逆序

int biggestFind(int array[],int size);//查找数组最大元素并输出位置

int step = 0;

int main(void)

{

system("title 32010072203--翻饼问题 ");

int cake[100],n,i;

printf("请输入要排序的数字个数n:");

scanf("%d",&n);

printf("请输入需要排序的序列：");

for(i=0;i

{scanf("%d",&cake[i]);}

int size = n;

cakeSort(cake, size);

printf("共需要%d步翻转\n",step);

printf("排序结果：");

for(i = 0; i < size; i++) {

printf("%d", cake[i]);

}

printf("\n");

return 0;

}

void cakeSort(int cake[],int size)

{

int maxLocation;

if(size > 1) {

maxLocation = biggestFind(cake, size);//获取最大值位置

if(maxLocation == 0) { //最大值在开头，则reverse整个数组

reverse(cake, size);

step++;

printf("第%d步：翻转上面的%d个饼\n", step, size);

cakeSort(cake, size - 1);

} else if(maxLocation == size-1) {//最大值在末尾，则对前面的数字进行排序

cakeSort(cake, size - 1);

} else { //最大值在中间某位置，则将开始到最大值位置处的子数组进行reverse，使最大值放在开头处

reverse(cake, maxLocation + 1);

step++;

printf("第%d步：翻转上面的%d个饼\n", step, maxLocation+1);

reverse(cake, size);

step++;

printf("第%d步：翻转上面的%d个饼\n", step, size);

cakeSort(cake, size - 1);

}

}

}

//功能：返回数组中最大值所在的位置

#include

int biggestFind(int array[],int size)

{

int location, max;//存储最大值所在位置和最大值

int i;

if(size <= 0)

{

printf("Null array!\n");

return -1;

}

max = array[0];

for(i = 0, location = 0; i < size; i++)

{

if(array[i] > max)

{

max = array[i];

location = i;

}

}

return location;

}

//将数组逆置

void reverse(int array[],int size)

{

int i, temp;

for(i = 0; i < size/2; i++) {

temp = array[size - 1 - i];

array[size - 1 - i] = array[i];

array[i] = temp;

}

}

4.24点问题：4张1~10的扑克牌，通过四则运算得到24。（穷举）

程序：

#include

#include

#include

int Myoperator(float a,float b,float c,floatd);

float flagSymbol(int flag,float m,float n);

void print24result(int type,int i,int j,intk,float a,float b,float c,float d);

int time,temp=0;

void main()

{

system("title 32010072203—24点问题 ");

inti,j,k,t,again,res,flag;

floatnum[4];

again=1;

while(again==1)

{

printf("\nPlease Enter 4 nums(1~10):\n");

i=0;

flag=0;

while(flag==0)

{

i++;

for(i=0;i<4;i++)

{

printf ("Inputnum-%d\n",++i);

i--;

scanf("%f",&num[i]);

if(num[i]<1 || num[i]>10 || num[i]!=int(num[i]))

flag++;

}

if(flag!=0)

{

printf("Error input again\n",i);

flag=0;

}

else

flag=1;

}

for(i=0;i<4;i++)

for(j=0;j<4;j++)

if(j!=i)

for(k=0;k<4;k++)

if(k!=j && k!=i)

for(t=0;t<4;t++)

if(t!=i && t!=j && t!=k)

{

res=Myoperator(num[i],num[j],num[k],num[t]);

}

if(res==0)

printf("\nNo answer\n");

else;

printf("time=%d\n\n",time);

printf("\n1: Go on\n2: Quit\n");

scanf("%d",&again);

}

}

int Myoperator(float a,float b,floatc,float d)

{

inti,j,k;

floatsum1,sum2,sum3;

for(i=0;i<4;i++)

for(j=0;j<6;j++)

for(k=0;k<6;k++)

{

if((!(i==3 && b==0)) && (!(j==3 && c==0)) &&(!(k==3 && d==0)))

{

sum1=flagSymbol(i,a,b);

sum2=flagSymbol(j,sum1,c);

sum3=flagSymbol(k,sum2,d);

if(fabs(sum3-24)<0.1)

{

temp++;

print24result(1,i,j,k,a,b,c,d);

}

}

if(k==2)

{

sum1=flagSymbol(i,a,b);

sum2=flagSymbol(j,c,d);

sum3=sum1*sum2;

if(fabs(sum3-24)<0.1)

{

temp++;

print24result(2,i,j,k,a,b,c,d);

}

}

if(k==3)

{

sum1=flagSymbol(i,a,b);

sum2=flagSymbol(j,c,d);

if(sum2!=0)

{

sum3=sum1/sum2;

if(fabs(sum3-24)<0.1)

{

temp++;

print24result(3,i,j,k,a,b,c,d);

}

}

}

}

if(temp==0)

return0;

else

return1;

}

float flagSymbol(int flag,float m,float n)

{

time++;

if(flag==0)

return(m+n);

if(flag==1)

return(m-n);

if(flag==2)

return(m*n);

if(flag==3)

if(n==0)

return30000;

else

return(m/n);

if(flag==4)

return(n-m);

if(flag==5)

if(m==0)

return30000;

else

return(n/m);

return0;

}

void print24result(int type,int i,int j,intk,float a,float b,float c,float d)

{

charsymbol[6];

symbol[0]='+';

symbol[1]='-';

symbol[2]='*';

symbol[3]='/';

symbol[4]='-';

symbol[5]='/';

if(type==1){

if(j==4|| j==5)

{

if(k==4 || k==5)

printf("%2.0f%c(%2.0f%c(%2.0f%c%2.0f))=24\n",d,symbol[k],c,symbol[j],a,symbol[i],b);

else

printf("(%2.0f%c(%2.0f%c%2.0f))%c%2.0f=24\n",c,symbol[j],a,symbol[i],b,symbol[k],d);

}

elseif (k==4 || k==5)

{

printf("%2.0f%c((%2.0f%c%2.0f)%c%2.0f)=24\n",d,symbol[k],a,symbol[i],b,symbol[j],c);

}

else

printf("((%2.0f%c%2.0f)%c%2.0f)%c%2.0f=24\n",a,symbol[i],b,symbol[j],c,symbol[k],d);

}

if(type==2 || type==3)

{

if(k==4 || k==5)

printf("(%2.0f%c%2.0f)%c(%2.0f%c%2.0f)=24\n",c,symbol[j],d,symbol[k],a,symbol[i],b);

else

printf("(%2.0f%c%2.0f)%c(%2.0f%c%2.0f)=24\n",a,symbol[i],b,symbol[k],c,symbol[j],d);

}

}