穷举及其应用
穷举概述
穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些应予排除。
1、穷举法又称列举法，其基本思想是逐--列举问题所涉及的所有情况。
2、穷举法常用于解决“是否存在”或“有多少种可能”等问题。
3、应用穷举法时应注意对问题所涉及的有限种情形须一--列举，既不能重复，又不能遗漏。
4、穷举通常应用循环结构来实现。在循环体中，应用选择结构实施判断筛选，求得所要求的解。
穷举法的框架就如下所示
接下来我们直接上例题
真分数升序排序算法设计
题目与解法思路
[例1 ]统计分母在区间[a, b]的最简真分数(分子小于分母，且分子分母无公因数)共有多少个，并求最简真分数升序序列中的第k项(正整数a, b, k从键盘输入)。
算法设计:
➢为排序方便，设置数组arr2存储分子，数组arr1存储分母。真分数升序排序后的
第k项为arr2[n]/arr1[n]。
➢在[a, b]内穷举分数j/i的分母i: a,a+1,.,b;
➢对每一个分母i穷举分子j: 1,2, ..j-1。
➢若分子j与分母i存在大于1的公因数,说明i/ j非最简,忽略不计;否则赋
值得一个最简真分数arr2[n]/arr1[n]。数组下标n统计最简真分数的个数。应用冒
泡法排序后即可打印出指定的第n项arr2[n-1]/arr1[n-1]。
代码实现
分母遍历模块
1. for (i = a; i < b; i++) 2. { 3. int j = 0; 4. for (j = 1; j < i; j++) 5. { 6. int c = gongyinshu(i, j); 7. if (c) 8. { 9. arr1[n] = i; 10. arr2[n++] = j; 11. } 12. } 13. }
gongyinshu()函数实现
若无公因数，则返回1，if语句判断成功，将分母i放入arr1中，分子放入arr2中
1. int gongyinshu(int m, int n) 2. { 3. int i = 0; 4. for (i = 2; i < n; i++) 5. { 6. if (m % i == 0 && n % i == 0) 7. { 8. return 0; 9. } 10. } 11. return 1;
冒泡排序实现升序
利用分数的比较方式进行比较后，分子与分母分别进行交换
1. for (i = 0; i < n; i++) 2. { 3. int j = 0; 4. for (j = 0; j < n - 1 - i; j++) 5. { 6. if (arr1[j] * arr2[j + 1] < arr1[j + 1] * arr2[j]) 7. { 8. int x = 0; 9. int y = 0; 10. x = arr1[j];//分母交换 11. arr1[j] = arr1[j + 1]; 12. arr1[j + 1] = x; 13. y = arr2[j];//分子交换 14. arr2[j] = arr2[j + 1]; 15. arr2[j + 1] = y; 16. } 17. } 18. }
进行输出
printf("第%d项为%d/%d", k, arr2[k - 1], arr1[k - 1]);
完整代码
1. #include <stdio.h> 2. 3. int gongyinshu(int m, int n) 4. { 5. int i = 0; 6. for (i = 2; i < n; i++) 7. { 8. if (m % i == 0 && n % i == 0) 9. { 10. return 0; 11. } 12. } 13. return 1; 14. } 15. 16. 17. int main() 18. { 19. int a = 0; 20. int b = 0; 21. int i = 0; 22. int n = 0; 23. int k = 0; 24. int arr1[100] = { 0 }; 25. int arr2[100] = { 0 }; 26. printf("请输入区间->"); 27. scanf("%d%d", &a, &b); 28. printf("请输入你要查询的序列->"); 29. scanf("%d", &k); 30. for (i = a; i < b; i++) 31. { 32. int j = 0; 33. for (j = 1; j < i; j++) 34. { 35. int c = gongyinshu(i, j); 36. if (c) 37. { 38. arr1[n] = i; 39. arr2[n++] = j; 40. } 41. } 42. } 43. for (i = 0; i < n; i++) 44. { 45. int j = 0; 46. for (j = 0; j < n - 1 - i; j++) 47. { 48. if (arr1[j] * arr2[j + 1] < arr1[j + 1] * arr2[j]) 49. { 50. int x = 0; 51. int y = 0; 52. x = arr1[j]; 53. arr1[j] = arr1[j + 1]; 54. arr1[j + 1] = x; 55. y = arr2[j]; 56. arr2[j] = arr2[j + 1]; 57. arr2[j + 1] = y; 58. } 59. } 60. } 61. printf("第%d项为%d/%d", k, arr2[k - 1], arr1[k - 1]); 62. return 0; 63. }
求解集合A元素的序列
题目与解法思路
[例2]
己知集合A定义如下:1∈A，2∈A; x, y∈A => 2x+3y∈A试求集合A元素从小到大排列的序列的前n项。
➢x, y可以是己产生的所有已有项中的任意两项，己产生项越多，递推生成
的新项也就越多。
➢穷 举循环变量k从3开始递增1取值，到第n项时k的终值尚无法确定，可约
定一个较大的终值(例如10000)。
➢若k可由己有的项j，i推得， 即若k满足条件
k=2*j +3*i或k=2*i+3*j， 说明k是a数列中的一-项，输出就好
➢当项 数t达到规定项数n时,则退出穷举。
代码实现
此题简单，就不分模块进行介绍了，代码与注释如下
1. #include<stdio.h> 2. 3. int main() 4. { 5. int n = 0; 6. int k = 0; 7. int t = 0; 8. printf("请输入->"); 9. scanf("%d", &n); 10. for (k = 3; k < 10000; k++) 11. { 12. int i = 0; 13. for (i = 2; i < k; i++) 14. { 15. int j = 0; 16. for (j = 1; j < i - 1; j++) 17. { 18. int coun = 0;//每找到一个后coun都会变为1，所以这里需要重新赋值 19. if (2 * i + 3 * j == k || 2 * i + 3 * j == k) 20. { 21. if (2 * i + 3 * j == k) 22. printf("第%d项为：2*%d+3*%d=%d\n", t+1, i, j, k); 23. else printf("第%d项为：2*%d+3*%d=%d\n", t+1, j, i, k); 24. coun++;//跳出条件 25. t++;//项数加一 26. } 27. if (coun == 1)//这层循环由于i已经确定，所以找到一个j时，便可以跳出 28. break; 29. } 30. if (t == n)//判断是否达到n项，跳出循环 31. break; 32. } 33. if (t == n)//判断是否达到n项，跳出循环 34. break; 35. } 36. return 0; 37. }
运行结果展示
六位数穷举法的实现
■[例3]把一个6位整数分为前后两个3位数,若该数等于所分两个3位数和的平方,则称该数为6位分段和平方数。试求出所有6位分段和平方数。
方法一 对六位数穷举
实现方法：
对六位数进行遍历，首先这个六位数可以开平方，并且开平方后所得数为这个六位数前三位与后三位相加即可
代码实现
1. #include<stdio.h> 2. #include<math.h> 3. 4. int main() 5. { 6. int i = 0; 7. for (i = 100000; i < 1000000; i++) 8. { 9. int b = sqrt(i);//开平方· 10. if (b * b == i)//判断是否可以开平方 11. { 12. int q = i / 1000;//前三位 13. int h = i % 1000;//后三位 14. if (q + h == b) 15. { 16. printf("%d ", i); 17. } 18. } 19. } 20. return 0; 21. }
结果展示
方法二 对三位数进行穷举
实现方法：
用双层循环对所有三位数进行遍历
i代表前三位，j代表后三位
满足条件：(i+j)^2=i*1000+j，且i * 1000 + j<1000000
即可输出此六位数i*1000+j
代码实现
1. 2. int main() 3. { 4. int i = 0; 5. int j = 0; 6. for (i = 100; i < 10000; i++) 7. { 8. for (j = 0; j < 10000; j++) 9. { 10. if ((i + j) * (i + j) ==(i * 1000 + j)&& i * 1000 + j<1000000) 11. printf("%d ", (i * 1000 + j)); 12. } 13. } 14. return 0; 15. }
结果展示
与上述结果一样
拓展 水仙花数
