枚举法——精选推荐
- 格式：pdf
- 大小：96.85 KB
- 文档页数：2
枚举法
⼀，枚举算法的思想：
1，枚举算法的定义：
在进⾏归纳推理时，如果逐个考察了某类事件的所有可能情况，因⽽得出⼀般结论，那么该结论是可靠 的，这种归纳⽅法叫做枚举法。
2，枚举算法的思想是：
将问题的所有可能的答案⼀⼀列举，然后根据条件判断此答案是否合适，保留合适的，舍弃不合适的。
3，使⽤枚举算法解题的基本思路如下：
（1）确定枚举对象、范围和判定条件。
（2）逐⼀枚举可能的解并验证每个解是否是问题的解。
4，枚举算法步骤：
（1）确定解题的可能范围，不能遗漏任何⼀个真正解，同时避免重复。
（2）判定是否是真正解的⽅法。
（3）为了提⾼解决问题的效率，使可能解的范围将⾄最⼩，
5，枚举算法的流程图如下所⽰：
⼆，枚举算法实例
例⼀：百钱买⽩鸡
1，问题描述：
公鸡每只5元，母鸡每只3元，三只⼩鸡1元，⽤100元买100只鸡，问公鸡、母鸡、⼩鸡各多少只？
2，算法分析：
利⽤枚举法解决该问题，以三种鸡的个数为枚举对象,分别设为mj,gj和xj，⽤三种鸡的总数 （mj+gj+xj=100）和买鸡钱的总数（1/3*xj+mj*3+gj*5=100）作为
判定条件，穷举各种鸡的个数。
例⼆：使⽤枚举法解决“填写运算符问题”
1，问题描述：在下⾯的算式中，添加“+”、“-”，“*”，“/”,4个运算符，使得这个式⼦成⽴。
5 5 5 5 5=5
2，算法分析：
上述式⼦左侧有5个数字，⼀共需要4个运算符。根据题⽬要求，两个数字之间的运算符只能有4中选择。在 具体编程时，可以通过循环来填⼊各种运算符，
然后再判断算式左侧的值是否等于右侧的值。并保证，当填⼊的 是除号时，则右侧的数不能为0，并且乘除的优先级⾼于加减的优先级。
三，算法实现：
例⼀：百钱买⽩鸡
1. #include
2. using namespace std;
3. int main()
4. {
5. int mj=0, gj=0, xj=0; //定义变量分别表⽰母鸡、公鸡、⼩鸡并初始化
6. for (gj = 0; gj <= 20; gj++) //公鸡最多可买20个
7. {
8. for (mj = 0; mj <= 33; mj++) //母鸡最多可买33个
9. {
10. xj = 100 - gj - mj; // 三种鸡的总数是100只
11. if (xj % 3 == 0 && 5 * gj + 3 * mj + xj / 3 == 100) // 总花费为100元。
12. printf("公鸡为 %d 只，母鸡为 %d 只，⼩鸡为 %d 只！\n", gj, mj, xj);
13. }
14. }
15. system("pause");
16. return 0;
17. }
例⼆：使⽤枚举法解决“填写运算符问题”
1. #include
2.
3. int main()
4. {
5. int j, i[5]; // 循环变量，数组i⽤来表⽰4个运算符
6. int sign; // 累加运算时的符号；
7. int result; // 保存运算式⼦的结果值
8. int count=0; // 计数器，统计符合条件的⽅案
9. int num[6]; // 保存操作数
10. float left, right; //保存中间结果
11. char oper[5] = { ' ','+','-','*','/' }; //运算符
12.
13. printf("输⼊5个数，之间⽤空格隔开：");
14. for (j = 1; j <= 5; j++)
15. scanf_s("%d",&num[j]);
16. printf("输⼊结果：");
17. scanf_s("%d",&result);
18. //注：这⾥i[1]代表的第⼀个运算符的意思，i[1]=1代表第⼀个运算符是“+”，i[1]=2代表第⼀个运算符是“减”，i[1]=3代表第⼀个运算符是“-”，i[1]=4代表第⼀个运算符是“/”
19. //注：这⾥i[2]代表的第⼆个运算符的意思，i[2]=1代表第⼆个运算符是“+”，i[2]=2代表第⼆个运算符是“减”，i[2]=3代表第⼆个运算符是“-”，i[2]=4代表第⼆个运算符是“/”
20. //i[3],i[4]依次类推。
21. for (i[1]=1; i[1]<=4; i[1]++) //循环4种运算符，1表⽰+，2表⽰-，3表⽰*，4表⽰/
22. {
23. if ((i[1]<4) || (num[2] != 0)) //运算符若是/,则第⼆个运算数不能为0，（注：“||”是或运算，两个条件⾄少要有⼀个成⽴，即第⼀个运算符为/时，第⼆个运算数不为0）
24. {25. for (i[2]=1; i[2]<=4; i[2]++)
26. {
27. if ((i[2]<4)||(num[3]!= 0)) //当第⼆个运算符为/时，第三个运算数不为0
28. {
29. for (i[3] = 1; i[3] <= 4; i[3]++)
30. {
31. if ((i[3] < 4) ||( num[4] != 0)) //当第三个运算符为/时，第四个运算数不为0
32. {
33. for (i[4] = 1; i[4] <= 4; i[4]++)
34. {
35. if ((i[4] < 4) || (num[5] != 0)) //当第四个运算符为/时，第五个运算数不为0
36. {
37. left = 0;
38. right = num[1];
39. sign = 1;
40. //使⽤case语句，将4种运算符填到对应的空格位置，并进⾏计算
41. for (j = 1; j <= 4; j++)
42. {
43. switch (oper[i[j]])
44. {
45. case '+':
46. left = left + sign*right;
47. sign = 1;
48. right = num[j + 1];
49. break;
50. case '-':
51. left = left + sign*right;
52. sign = -1;
53. right = num[j + 1];
54. break;
55. case '*':
56. right = right*num[j + 1];
57. break;
58. case '/':
59. right = right / num[j + 1];
60. break;
61. }
62. }
63. //开始判断，如果运算式⼦的结果和输⼊的结果相同，则表⽰找到⼀种算法，并输出这个解
64. if (left + sign*right == result)
65. {
66. count++;
67. printf("%3d:",count);
68. for (j = 1; j <= 4; j++)
69. printf("%d%c",num[j],oper[i[j]]);
70. printf("%d=%d\n",num[5],result);
71. }
72. }
73. }
74. }
75.
76. }
77. }
78. }
79. }
80. }
81. if (count == 0)
82. printf("没有符合要求的⽅法！\n");
83. system("pause");
84. return 0;
85. }
