练习：
1．元旦义卖：总共带50件商品，有两种构成，钥匙扣2块一个，漫画书4块一本，要卖出160块要如和搭配？
2．构造一个3*3的魔方：把数字1-9添入如图的表格中
|
2 |
7 |
6 |
|
9 |
5 |
1 |
|
4 |
3 |
8 |
要求每横，竖，斜列之和均相等（如图是一种情况）。输出所有可能的魔方。
3. 虫食算: 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子：
43#9865#045
+ 8468#6633
____________
44445509678
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制：
首先，我们只考虑10进制加法的虫食算。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。
给定等式 A B C D E
D F G
+ D F G
───────
X Y Z D E
其中每个字母代表一个数字，且不同数字对应不同字母。编程求出这些数字并且打出这个数字的算术计算竖式。
参考答案：
1．#include<stdio.h>
const int KEYPRICE = 2; //一个钥匙扣的价格
const int BOOKPRICE = 4; //一本漫画书的价格
void Print(int money, int res);//计算并输出两种物品的数量各是多少
int main()
{
int money = 160;//钱的总数
int res = 50;//物品的总数
Print(money, res);//计算并输出两种物品的数量各是多少
getchar();
return 0;
}
void Print(int money, int res)
{
int maxKey = money / KEYPRICE;
int key, book;
for (key=0; key<maxKey; ++key)//枚举钥匙扣的可能数量
{
book = res - key;//漫画书的数量根据约束条件求得
if (key*KEYPRICE + book*BOOKPRICE == money)//约束条件
{
printf("key = %d, book = %d\n", key, book);
}
}
}
2．参考程序一：九重循环，不做任何剪枝。
#include<stdio.h>
#include<stdlib.h>
int Different(int a[], int len);
int main()
{
int a[9] = {0};
int i;
for (a[0]=1; a[0]<=9; a[0]++)
for (a[1]=1; a[1]<=9; a[1]++)
for (a[2]=1; a[2]<=9; a[2]++)
for (a[3]=1; a[3]<=9; a[3]++)
for (a[4]=1; a[4]<=9; a[4]++)
for (a[5]=1; a[5]<=9; a[5]++)
for (a[6]=1; a[6]<=9; a[6]++)
for (a[7]=1; a[7]<=9; a[7]++)
{
if (Different(a, 8))
{
a[8] = 45-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7];
if ((a[0]+a[1]+a[2]) == (a[3]+a[4]+a[5]) && (a[0]+a[1]+a[2]) == (a[6]+a[7]+a[8])
&& (a[0]+a[3]+a[6]) == (a[1]+a[4]+a[7]) && (a[0]+a[3]+a[6]) == (a[2]+a[5]+a[8])
&& (a[0]+a[1]+a[2]) == (a[0]+a[4]+a[8]) && (a[0]+a[1]+a[2]) == (a[2]+a[4]+a[6]))
{
for (i=0; i<9; i++)
{
printf("%5d", a[i]);
if ((i+1)%3 == 0)
printf("\n");
}
printf("\n\n");
}
}
}
system("pause");
return 0;
}
int Different(int a[], int len)
{
int i, j;
for (i=0; i<len-1; i++)
{
for (j=i+1; j<len; j++)
{
if (a[i] == a[j])
return 0;
}
}
return 1;
}
参考程序二：八重循环，对每重循环均进行剪枝。
#include<stdio.h>
#include<stdlib.h>
int IsElement(int a[], int len, int x);
int main()
{
int a[9] = {0};
int i;
for (a[0]=1; a[0]<=9; a[0]++)
for (a[1]=1; a[1]<=9; a[1]++)
{
if (IsElement(a, 1, a[1]))
{
for (a[2]=1; a[2]<=9; a[2]++)
{
if (IsElement(a, 2, a[2]))
{
for (a[3]=1; a[3]<=9; a[3]++)
{
if (IsElement(a, 3, a[3]))
{
for (a[4]=1; a[4]<=9; a[4]++)
{
if (IsElement(a, 4, a[4]))
{
for (a[5]=1; a[5]<=9; a[5]++)
{
if (IsElement(a, 5, a[5]))
{
for (a[6]=1; a[6]<=9; a[6]++)
{
if (IsElement(a, 6, a[6]))
{
for (a[7]=1; a[7]<=9; a[7]++)
{
if (IsElement(a, 7, a[7]))
{
a[8] = 45-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7];
if ((a[0]+a[1]+a[2]) == (a[3]+a[4]+a[5]) && (a[0]+a[1]+a[2]) == (a[6]+a[7]+a[8])
&& (a[0]+a[3]+a[6]) == (a[1]+a[4]+a[7]) && (a[0]+a[3]+a[6]) == (a[2]+a[5]+a[8])
&& (a[0]+a[1]+a[2]) == (a[0]+a[4]+a[8]) && (a[0]+a[1]+a[2]) == (a[2]+a[4]+a[6]))
{
for (i=0; i<9; i++)
{
printf("%5d", a[i]);
if ((i+1)%3 == 0)
printf("\n");
}
printf("\n\n");
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
system("pause");
return 0;
}
int IsElement(int a[], int len, int x)
{
int i;
for (i=0; i<len; i++)
{
if (a[i] == x)
return 0;
}
return 1;
}
3．算法分析：先看最高位和次高位， A, B都是和进位相加，又C+D+D的进位（设为j）不可能大于2，B+j的进位不能大于1，所以B = 9; Y = 1; X = A + 1;
E+G+G的个位数字仍为E，说明G=0或G=5；同理 F=0或F=5；
做了这些简单的判断以后，可以大大提高穷举的效率。
#include<stdio.h>
int main()
{
int A, B, C, D, E, F, G, X, Y, Z;
int m, n, sum;
B = 9;
Y = 1;
for (G=0; G<6; G+=5)
for (F=0; F<6; F+=5)
if (F!=G)
for (A=2; A<9; A++)
if (A!=G && A!=F)
for (C=2; C<9; C++)
if (C!=A && C!=G && C!=F)
for (D=2; D<9; D++)
if (D!=A && D!=C && D!=G && D!=F)
for (E=2; E<9; E++)
if (E!=A && E!=C && E!=D && E!=G && E!=F)
{
X = A + 1;
if (B!=X && C!=X && D!=X && E!=X && F!=X && G!=X)
{
Z = 45 - A - B - C - D - E - F - G - X - Y;
m = A*10000 + B*1000 + C*100 + D*10 + E;
n = D*100 + F*10 + G;
sum = X*10000 + Y*1000 + Z*100 + D*10 + E;
if (m + n * 2 == sum)
{
printf(" %d%d%d%d%d\n", A, B, C, D, E);
printf(" %d%d%d\n", D, F, G);
printf("+ %d%d%d\n", D, F, G);
printf("_____________\n");
printf(" %d%d%d%d%d\n", X, Y, Z, D, E);
printf("\n");
}
}
}
getchar();
return 0;
}
评论