练习： 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; }
评论