嵌套循环的简化

chyanog

比如，在求水仙花数时可以用如下的方法，按照这种方法求3-9位的水仙花数时，就需要很多循环(貌似是42个for)，简化类似的循环我知道可以用递归，据说还可以用矩阵或者别的方法，但不知道该如何实现（说明：这里不是想探讨水仙花数的算法，同样是穷举我知道有相对比较简洁些的如分拆各位数字等）：

2. #include <stdio.h>
3. #include <time.h>
5. int power(int a,int b)
6. {
7. int t=1,i;
8. for (i=0;i<b;i++)
9. t*=a;
10. return t;
11. }
13. int main(int argc, char *argv[])
14. {
15. double t0=clock();
16. int a,b,c,d,e,f,g;
17. for (a=1;a<=9;a++)
18. for (b=0;b<=9;b++)
19. for (c=0;c<=9;c++)
20. for (d=0;d<=9;d++)
21. for (e=0;e<=9;e++)
22. for (f=0;f<=9;f++)
23. for (g=0;g<=9;g++)
24. {
25. int num=1000000*a+100000*b+10000*c+1000*d+100*e+10*f+g;
26. if (num==power(a,7)+power(b,7)+power(c,7)+power(d,7)+power(e,7)+power(f,7)+power(g,7))
27. printf(" %d ",num);
28. }
29. printf("\nElapsed time ：%f s",(clock()-t0)/CLOCKS_PER_SEC);
30. return 0;
31. }

复制代码

gxqcn

这个问题我自己也常碰到，比如我用在构造高维幻方时。 下面介绍一下我自己创造的一个方法（也许早已是通法）， 也就是借用我们常用的计数法则：

2. // 定义一个n元数组A[n]，
3. // 下标从小到大(0 to n-1)对应于嵌套for循环的由外到内的变量，
4. // 它们的值则对应于for循环中的循环变量值。
6. int i;
7. for ( i=0; i<n; ++i )
8. {
9. A[i] <-- A[i]_first; // 初始值
10. }
12. for ( ; ; )
13. {
14. // Call your function ...
16. i = n;
17. while ( --i >= 0 && A[i] == A[i]_last /* 终止值 */ )
18. {
19. A[i] <-- A[i]_first; // 复位
20. }
22. if ( i < 0 )
23. break;
25. A[i] <--next(A[i]); // 也许不是简单的递增，反正是 next 到下一个有效值。
26. }

复制代码

liangbch

这也是我自己创造的方法，不知道别人是否也做过类似的事情。 这是一个混合进制问题，其核心是进位处理。 比如：有个4位混合进制数， 最低位数字的范围是 0 to 5 次低位数字的范围是 0 to 8 第三低位数字的范围是 0 to 5 最高位数字的范围是 0 to 3 如果我们想要列举所有的数，最容易想到的方法是1个四重循环，代码如下 int i,j,k,m; for (i=0;i<=3;i++) { for (j=0;j<=5;j++) { for (k=0;k<=8;k++) { for (m=0;m<=5;m++) { printf("%d%d%d%d\n",i,j,k,m); } } } } 上面的问题有很大的局限，如果我们想要列举一个20位混合进制数，我们不得不重新编写一个具有20重循环的程序，当然，一个20重循环的程序既不优雅也不便于扩充和维护。我们能否找一个通用的方法来解决这个问题的，答案是肯定的。 以上面的例子为例。 对于每一位数字，我们定义一个结构体，如下。它包含3个字段min，max,curr. 在这个"位"上,其数字的值的范围为min到max,curr表示当前的数字，等价于上面程序的i,j,k.m。 typedef struct _dig_st { int min; int max; int curr; }DIG_ST; 一个4位数需要这样的四个结构体变量，故我们可以定义具有4个元素的结构体数组，为了便于扩充计，这里可定义更大的数组，比如32个元素。然会对每个元素的min,max字段作初始化。 代码如下： 定义一个数组 DIG_ST permutation[32]; 根据你的需要，定义这个混合进制数的每一位数的最小值和最大值 void init() { //最低位数字的范围是 0 to 5 permutation[0].min=0; permutation[0].max=5; //次低位数字的范围是 0 to 8 permutation[1].min=0; permutation[1].max=8; //第三低位数字的范围是 0 to 5 permutation[2].min=0; permutation[2].max=5; //最高位数字的范围是 0 to 3 permutation[3].min=0; permutation[3].max=3; } 取得第一个排列前面的那个排列，执行nextPerm函数后，便得到第一个排列 void preFirstPerm(DIG_ST arr[], int len) { int i; arr[0].curr=arr[0].min-1; for (i=1;i=len) return FALSE; arr[ i ].curr++; for (i--;i>=0;i--) arr[ i ].curr=arr[ i ].min; return TRUE; } 使用新的代码实现第一个例子，等价于原来的四重循环。很容易扩展为一个20重循环的替代品。 楼下给出完整的可编译通过的代码。

liangbch

2. // By liangbch@263.net, 2012-9-20
4. #include "stdio.h"
5. #include "stdlib.h"
6. #define TRUE 1
7. #define FALSE 0
9. typedef struct _dig_st
10. {
11. int min;
12. int max;
13. int curr;
14. }DIG_ST;
16. /*
17. 一个4位数需要这样的四个结构体变量，故我们可以定义具有4个元素的结构体数组，为了便于扩充计，这里可定义更大的数组，比如32个元素。然会对每个元素的min,max字段作初始化。
18. 代码如下：
19. */
21. //定义一个数组
22. DIG_ST permutation[32];
25. //根据你的需要，定义这个混合进制数的每一位数的最小值和最大值
26. void init()
27. {
29. //最低位数字的范围是 0 to 5
30. permutation[0].min=0; permutation[0].max=5;
32. //次低位数字的范围是 0 to 8
33. permutation[1].min=0; permutation[1].max=8;
35. //第三低位数字的范围是 0 to 5
36. permutation[2].min=0; permutation[2].max=5;
38. //最高位数字的范围是 0 to 3
39. permutation[3].min=0; permutation[3].max=3;
40. }
43. //取得第一个排列前面的那个排列，执行nextPerm函数后，便得到第一个排列
44. void preFirstPerm(DIG_ST arr[], int len)
45. {
46. int i;
47. arr[0].curr=arr[0].min-1;
48. for (i=1;i<len;i++)
49. {
50. arr[i].curr=arr[i].min;
51. }
52. }
54. //返回 TURE: 表示得到下一个排列
55. //返回 FALSE: 表示所有的排列都枚举过了
56. int nextPerm(DIG_ST arr[],int len)
57. {
58. int i=0;
59. while (i<len)
60. {
61. if ( arr[i].curr < arr[i].max)
62. break;
63. else
64. i++;
65. }
67. if (i>=len)
68. return FALSE;
70. arr[i].curr++;
71. for (i--;i>=0;i--)
72. arr[i].curr=arr[i].min;
74. return TRUE;
75. }
77. void old_flow()
78. {
79. int i,j,k,m;
80. for (i=0;i<=3;i++)
81. {
82. for (j=0;j<=5;j++)
83. {
84. for (k=0;k<=8;k++)
85. {
86. for (m=0;m<=5;m++)
87. {
88. printf("%d%d%d%d\n",i,j,k,m);
89. }
90. }
91. }
92. }
93. }
95. void new_flow()
96. {
97. init();
98. preFirstPerm(permutation,4);
100. while ( 1 )
101. {
102. int bRet;
103. bRet=nextPerm(permutation,4);
104. if ( !bRet)
105. break;
106. printf("%d%d%d%d\n",
107. permutation[3].curr,
108. permutation[2].curr,
109. permutation[1].curr,
110. permutation[0].curr);
111. }
113. }
115. int main()
116. {
117. old_flow();
118. //new_flow();
119. return 0;
120. }

复制代码

mathtime

如果就事论事,上面的过程对应的只是一个数学计数。原程序本想得到一个7个数的所有全排列，但这本质就是枚举0至999999的数的简单问题而已（我曾碰到类似问题，冥思苦想后发现只是映射为一类简单的数学算式）。即源程序可改为： int main(int argc, char *argv[]) { double t0=clock(); int a,b,c,d,e,f,g,i; for (i=0;i<=9999999;i++) { int num=i; //a=i\10^7; 取出每位数 printf(" %d ",num); } printf("\nElapsed time ：%f s",(clock()-t0)/CLOCKS_PER_SEC); return 0; }

liangbch

的确，就1楼的代码而言，其实质是遍历所有9位数，这个问题很简单，改成一个一重循环很容易，将1个9位数拆成9个数字就可以了。 2#实现的是针对一个更加通用的问题，实现混合进制数的遍历，这个4位混合进制的每一位数字的范围都是不一样的，用你的方法恐怕就没那么容易了。 在实际应用上，这类题目一般用于搜索，其搜索空间往往非常大，如果对每一个可能的值(比如几个数字的组合)都进行验证,时间代价是不可接受的。 而如果使用2楼的方法，改写nextPerm函数，在执行nextPerm时，一些不符合要求的值可直接跳过，这样就可以在合理的时间内完成搜索。

gxqcn

把内存里一个整数按十进制取出每个数字，代价很大， 因为需要用到除法指令， 或几次乘法及减法指令。

liangbch

而如果使用2楼的方法，改写nextPerm函数，在执行nextPerm时，一些不符合要求的值可直接跳过，这样就可以在合理的时间内完成搜索。

例如如下题目： 现有1角，2角，5角，1元，2元，5元的纸币，数量足够多。 问，现需要给顾客10元钱，有多少种给法。

wayne

本质上就是对 循环所需的全排列总个数 做一个线性的编号。 将多维循环变成一维的循环

chyanog

8# liangbch 递归写法

1. count = 0
2. coin=[50,20,10,5,2,1]
3. total=[100,0,0,0,0,0]
4. def func(i):
5. global count
6. for x in range(total[i-1]/coin[i-1]+1):
7. total[i]=total[i-1]-x*coin[i-1]
8. if i == 5:
9. count += 1
10. else:
11. func(i+1)
12. func(1)
13. print count

复制代码