【程序2】
# include
# define SIDE_N 3
# define LENGTH 3
# define VARIABLES 6
int A,B,C,D,E,F;
int *pt[]={&A,&B,&C,&D,&E,&F};
int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
int side_total[SIDE_N];
main{}
{ int i,j,t,equal;
for (j=0;j *pt[j]=j+1;
while(1)
{ for (i=0;i { for (t=j=0;j t+=*side[i][j];
side_total[i]=t;
}
for (equal=1,i=0;equal&&i if (side_total[i]!=side_total[i+1] equal=0;
if (equal)
{ for (i=1;i printf(“M”,*pt[i]);
printf(“\n”);
scanf(“%*c”);
}
for (j=VARIABLES-1;j>0;j--)
if (*pt[j]>*pt[j-1]) break;
if (j==0) break;
for (i=VARIABLES-1;i>=j;i--)
if (*pt[i]>*pt[i-1]) break;
t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;
for (i=VARIABLES-1;i>j;i--,j++)
{ t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t; }
}
}
从上述问题解决的方法中，最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。
【问题】 背包问题
问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中，限制重量为tw。考虑一个n元组（x0，x1，…，xn-1），其中xi=0 表示第i个物品没有选取，而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题，需要枚举所有的选取方案，而根据上述方法，我们只要枚举所有的n元组，就可以得到问题的解。
显然，每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数，且这些二进制数的取值范围为0～2n-1。因此，如果把0～2n-1分别转化为相应的二进制数，则可以得到我们所需要的2n个n元组。
【算法】
maxv=0;
for (i=0;i<2n;i++)
{ B[0..n-1]=0;
把i转化为二进制数，存储于数组B中;
temp_w=0;
temp_v=0;
for (j=0;j { if (B[j]==1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if ((temp_w<=tw)&&(temp_v>maxv))
{ maxv=temp_v;
保存该B数组；
}
}
}
三、递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。
【问题】 阶乘计算
问题描述：编写程序，对给定的n（n≦100），计算并输出k的阶乘k！（k=1，2，…，n）的全部有效数字。 |
