嵌套循环的简化
比如，在求水仙花数时可以用如下的方法，按照这种方法求3-9位的水仙花数时，就需要很多循环(貌似是42个for)，简化类似的循环我知道可以用递归，据说还可以用矩阵或者别的方法，但不知道该如何实现（说明：这里不是想探讨水仙花数的算法，同样是穷举我知道有相对比较简洁些的如分拆各位数字等）：#include <stdio.h>
#include <time.h>
int power(int a,int b)
{
int t=1,i;
for (i=0;i<b;i++)
t*=a;
return t;
}
int main(int argc, char *argv[])
{
double t0=clock();
int a,b,c,d,e,f,g;
for (a=1;a<=9;a++)
for (b=0;b<=9;b++)
for (c=0;c<=9;c++)
for (d=0;d<=9;d++)
for (e=0;e<=9;e++)
for (f=0;f<=9;f++)
for (g=0;g<=9;g++)
{
int num=1000000*a+100000*b+10000*c+1000*d+100*e+10*f+g;
if (num==power(a,7)+power(b,7)+power(c,7)+power(d,7)+power(e,7)+power(f,7)+power(g,7))
printf(" %d ",num);
}
printf("\nElapsed time ：%f s",(clock()-t0)/CLOCKS_PER_SEC);
return 0;
} 这个问题我自己也常碰到，比如我用在构造高维幻方时。
下面介绍一下我自己创造的一个方法（也许早已是通法），
也就是借用我们常用的计数法则：
// 定义一个n元数组A，
// 下标从小到大(0 to n-1)对应于嵌套for循环的由外到内的变量，
// 它们的值则对应于for循环中的循环变量值。
int i;
for ( i=0; i<n; ++i )
{
A <-- A_first;// 初始值
}
for ( ; ; )
{
// Call your function ...
i = n;
while ( --i >= 0 && A == A_last /* 终止值 */ )
{
A <-- A_first; // 复位
}
if ( i < 0 )
break;
A <--next(A); // 也许不是简单的递增，反正是 next 到下一个有效值。
} 这也是我自己创造的方法，不知道别人是否也做过类似的事情。
这是一个混合进制问题，其核心是进位处理。
比如：有个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_STpermutation;
根据你的需要，定义这个混合进制数的每一位数的最小值和最大值
void init()
{
//最低位数字的范围是 0 to 5
permutation.min=0; permutation.max=5;
//次低位数字的范围是 0 to 8
permutation.min=0; permutation.max=8;
//第三低位数字的范围是 0 to 5
permutation.min=0; permutation.max=5;
//最高位数字的范围是 0 to 3
permutation.min=0; permutation.max=3;
}
取得第一个排列前面的那个排列，执行nextPerm函数后，便得到第一个排列
void preFirstPerm(DIG_ST arr[], int len)
{
int i;
arr.curr=arr.min-1;
for (i=1;i<len;i++)
{
arr[ i ].curr=arr[ i ].min;
}
}
返回下一个排列，这是列举所有循环的核心部分，其实质是进位处理。
返回 TURE: 表示得到下一个排列，返回 FALSE: 表示所有的排列都枚举过了
int nextPerm(DIG_ST arr[],int len)
{
int i=0;
while (i<len)
{
if ( arr[ i ].curr < arr[ i ].max)
break;
else
i++;
}
if (i>=len)
return FALSE;
arr[ i ].curr++;
for (i--;i>=0;i--)
arr[ i ].curr=arr[ i ].min;
return TRUE;
}
使用新的代码实现第一个例子，等价于原来的四重循环。很容易扩展为一个20重循环的替代品。
楼下给出完整的可编译通过的代码。
// By liangbch@263.net, 2012-9-20
#include "stdio.h"
#include "stdlib.h"
#define TRUE 1
#define FALSE 0
typedef struct _dig_st
{
int min;
int max;
int curr;
}DIG_ST;
/*
一个4位数需要这样的四个结构体变量，故我们可以定义具有4个元素的结构体数组，为了便于扩充计，这里可定义更大的数组，比如32个元素。然会对每个元素的min,max字段作初始化。
代码如下：
*/
//定义一个数组
DIG_STpermutation;
//根据你的需要，定义这个混合进制数的每一位数的最小值和最大值
void init()
{
//最低位数字的范围是 0 to 5
permutation.min=0; permutation.max=5;
//次低位数字的范围是 0 to 8
permutation.min=0; permutation.max=8;
//第三低位数字的范围是 0 to 5
permutation.min=0; permutation.max=5;
//最高位数字的范围是 0 to 3
permutation.min=0; permutation.max=3;
}
//取得第一个排列前面的那个排列，执行nextPerm函数后，便得到第一个排列
void preFirstPerm(DIG_ST arr[], int len)
{
int i;
arr.curr=arr.min-1;
for (i=1;i<len;i++)
{
arr.curr=arr.min;
}
}
//返回 TURE: 表示得到下一个排列
//返回 FALSE: 表示所有的排列都枚举过了
int nextPerm(DIG_ST arr[],int len)
{
int i=0;
while (i<len)
{
if ( arr.curr < arr.max)
break;
else
i++;
}
if (i>=len)
return FALSE;
arr.curr++;
for (i--;i>=0;i--)
arr.curr=arr.min;
return TRUE;
}
void old_flow()
{
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);
}
}
}
}
}
void new_flow()
{
init();
preFirstPerm(permutation,4);
while ( 1 )
{
int bRet;
bRet=nextPerm(permutation,4);
if ( !bRet)
break;
printf("%d%d%d%d\n",
permutation.curr,
permutation.curr,
permutation.curr,
permutation.curr);
}
}
int main()
{
old_flow();
//new_flow();
return 0;
}
如果就事论事,上面的过程对应的只是一个数学计数。原程序本想得到一个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;
} 的确，就1楼的代码而言，其实质是遍历所有9位数，这个问题很简单，改成一个一重循环很容易，将1个9位数拆成9个数字就可以了。
2#实现的是针对一个更加通用的问题，实现混合进制数的遍历，这个4位混合进制的每一位数字的范围都是不一样的，用你的方法恐怕就没那么容易了。
在实际应用上，这类题目一般用于搜索，其搜索空间往往非常大，如果对每一个可能的值(比如几个数字的组合)都进行验证,时间代价是不可接受的。
而如果使用2楼的方法，改写nextPerm函数，在执行nextPerm时，一些不符合要求的值可直接跳过，这样就可以在合理的时间内完成搜索。 把内存里一个整数按十进制取出每个数字，代价很大，
因为需要用到除法指令，
或几次乘法及减法指令。 而如果使用2楼的方法，改写nextPerm函数，在执行nextPerm时，一些不符合要求的值可直接跳过，这样就可以在合理的时间内完成搜索。
例如如下题目：
现有1角，2角，5角，1元，2元，5元的纸币，数量足够多。
问，现需要给顾客10元钱，有多少种给法。 本质上就是对 循环所需的全排列总个数 做一个线性的编号。
将多维循环变成一维的循环 8# liangbch
递归写法count = 0
coin=
total=
def func(i):
global count
for x in range(total/coin+1):
total=total-x*coin
if i == 5:
count += 1
else:
func(i+1)
func(1)
print count
页:
[1]
2