从水仙花数说起
程序设计是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。程序设计是一门实践性很强的课程，通过实践锻炼出的程序设计能力将直接关系到人们的软件开发能力。本篇文章通过对水仙花数问题的不断扩展，来讨论程序设计能力的培养方法。
1.1 水仙花数的连营
1.1.1 水仙花数
在学习程序设计课程时，大多数读者一定采用循环结构编写过求解水仙花数的程序。
【实例1-1】水仙花数
一个三位整数（100～999），若各位数的立方和等于该数自身，则称其为“水仙花数”（如：153=13+53+33），找出所有的这种数。
- 编程思路
对三位数n（n为100~999之间的整数）进行穷举。对每个枚举的n，分解出其百位a（a=n/100）、十位b（b=n%100/10）和个位c（ c=n%10），若满足a*a*a+b*b*b+c*c*c== n，则n是水仙花数。
- 源程序及运行结果
#include
using namespace std;
int main()
int n, a, b, c; //n、a、b和c分别为三位数自身及其百位、十位和个位
for(n=100 ;n<=999;n++)
{
a=n/100;
b=n%100/10;
c=n%10;
if(a*a*a+b*b*b+c*c*c== n)
cout< } cout< return 0; 编译并执行以上程序，得到如下所示的结果。 153 370 371 407 Press any key to continue 在“三国杀”游戏中，武将陆逊有一个技能是“连营”，其技能描述是：每当你失去最后一张手牌时，可立即摸一张牌。 借用这个概念，在程序设计实践中，我们设计了一个程序后，可以在这个程序的基础上，再进行扩展，提出相类似的另一个问题，再进行设计。即解决一个问题后，再解决一个问题，类比解释就是失去一张手牌后，再摸一张牌。 在前面水仙花数问题的基础上，我们通过连营，可以提出下面几个问题。 【实例1-2】4位花朵数 一个四位整数（1000～9999），若其各位数的4次方之和等于该数自身，则称其为4位花朵数（如：1634=14+64+34+44），找出所有的这种数。 编程的思路完全类同于水仙花数。即对四位数n（n为1000~9999之间的整数）进行穷举。对每个枚举的n，分解出其千位a（a=n/1000）、百位b（b=n%1000/100）、十位c（b=n%100/10）和个位d（d=n%10），若满足a*a*a*a+b*b*b*b+c*c*c*c+d*d*d*d== n，则n是4位花朵数。 #include using namespace std; int main() int n, a, b, c,d; //n、a、b、c和d分别为四位数自身及其千位、百位、十位和个位 for(n=1000 ;n<=9999;n++) { a=n/1000; b=n%1000/100; c=n%100/10; d=n%10; if(a*a*a*a+b*b*b*b+c*c*c*c+d*d*d*d==n) cout< } cout< return 0; 编译并执行以上程序，得到如下所示的结果。 1634 8208 9474 Press any key to continue 【实例1-3】5位花朵数 一个5位整数（10000～99999），若其各位数的5次方之和等于该数自身，则称其为5位花朵数（如：54748=55+45+75+45+85），找出所有的这种数。 仍然可以采用完全类同于水仙花数的求解方法来求出所有的5位花朵数。即对5位数n（n为10000~99999之间的整数）进行穷举。对每个枚举的n，分解出其万位a（a=n/10000）、千位b（b=n%10000/1000）、百位c（c=n%1000/100）、十位d（d=n%100/10）和个位e（e=n%10），若满足a*a*a*a*a+b*b*b*b*b+c*c*c*c*c+d*d*d*d*d+e*e*e*e*e== n，则n是5位花朵数。 #include using namespace std; int main() int n, a, b, c,d,e; //n、a、b、c和d分别为5位数自身及其万、千、百、十和个位 for(n=10000 ;n<=99999;n++) { a=n/10000; b=n%10000/1000; c=n%1000/100; d=n%100/10; e=n%10; if(a*a*a*a*a+b*b*b*b*b+c*c*c*c*c+d*d*d*d*d+e*e*e*e*e==n) cout< } cout< return 0; 编译并执行以上程序，得到如下所示的结果。 54748 92727 93084 Press any key to continue 仿照实例1-2和1-3的方法，我们可以求解出所有的6位花朵数、7位花朵数等等。但是按照上面的方法，都需要修改程序，在程序中相应地增加变量、添加语句。能不能输入一个自然数N（为简单起见，N<=9，因为C++中32位整数的最大值为2147483647，更多的位数会超过int型数据的表数范围），求解出所有的N位花朵数呢？ 【实例1-4】N位花朵数 一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为N位花朵数。 例如：当N=3时，153就满足条件。当N=4时，1634满足条件。当N=5时，54748满足条件。 实际上，对N的每个取值，可能有多个数字满足条件。编写程序，对输入的N（N<=9），求出所有的N位花朵数。 为求解N位的花朵数，需要对N位数x（x为10N-1~10N-1之间的整数）进行穷举。对每个枚举的x，求出其每个位上的数字的N次方的和digitsum，若满足digitsum==x，则x是N位花朵数。 为求解N位花朵数，可以抽象两个函数。一个是int power(int x,int n)，用于求x的n次方；另一个是int digitsum(int x,int n)，用于求x的各位数的n次方之和。 #include #include using namespace std; int power(int x,int n) int i,p=1; for (i=1;i<=n;i++) p*=x; return p; int digitsum(int x,int n) int s=0; while(x!=0) { s+=power(x%10,n); x=x/10; } return s; int main() int n, x,a, b; //a、b分别为相应穷举区间的上下界限 cin>>n; a=power(10,n-1); b=power(10,n)-1; int start=clock(); for(x=a; x<=b; x++) { if(digitsum(x,n)==x) cout< } cout< return 0; 编译并执行以上程序，若输入5，可得到如下所示的结果。 54748 92727 93084 Running Time :16 ms. Press any key to continue 若输入7，可得到如下所示的结果。 1741725 4210818 9800817 9926315 Running Time :3234 ms. Press any key to continue 若输入8，可得到如下所示的结果。 24678050 24678051 88593477 Running Time :39282 ms. Press any key to continue 若输入9，可得到如下所示的结果。 146511208 472335975 534494836 912985153 Running Time :457875 ms. Press any key to continue 上面的程序可以根据输入的N，求出所有的N位花朵数。但从执行结果可以看出，求7位花朵数用时3234ms，比求5位花朵数的16ms多得多。求9位花朵数更是用时457875ms。能否想一些办法更快速地求解呢？ 实际上，在我们解决问题时，当数据量比较小时，采用什么样的办法都无所谓，因为一般都能快速得到结果；但当数据量比较大时，就需要对解决问题的办法进行优化了，否则，时间上的开销是难以接受的。 在“三国杀”游戏中，武将黄月英有一个技能是“集智”，其技能描述是：每当你使用一张非延时类锦囊，（在它结算之前）你可以立即摸一张牌。也就是说，当黄月英在游戏中打出诸如无中生有、顺手牵羊、过河拆桥、借刀杀人、五谷丰登、南蛮入侵、万箭齐发、决斗、桃园结义、无懈可击、铁锁链环等牌时，可以另外摸一张牌。 借用这个概念，在程序设计实践中，我们设计了一个程序后，可以在这个程序的基础上，再进行优化和扩展，看能否采用另外的、更好的方法来解决这个问题。即采用一种方法解决一个问题后，再采用另外的方法来解决这个问题，也就是打出一张非延时类锦囊牌后，再摸一张牌（看能否找到一种更好的解法）。 下面对实例1-4中的程序进行初步的优化。 从给出的程序中可以看出，对于每个枚举的数x的每一位（x%10），程序中都会调用power函数求它的n次方。例如，若输入的是5，则穷举90000个5位数（10000~99999），每个数有5位，则power函数会被调用450000次。 实际上，每次调用power无非是求0~9这10个数字中某个数字的n次方。因此，若事先调用power函数将0~9的n次方求出来并存放在一个数组中，则在求x的各位数字的n次方之和时，只需要取用数组中相应的值即可，而无需反复调用power函数。这样一定可以缩短求解的时间。 采用这个思路优化后的源程序如下： #include #include using namespace std; int table[10]; int power(int x,int n) int i,p=1; for (i=1;i<=n;i++) p*=x; return p; int digitsum(int x,int n) int s=0; while(x!=0) { s+=table[x%10]; // 直接引用表中预先求得的值 x=x/10; } return s; int main() int n, x,a, b; //a、b分别为相应穷举区间的上下界限 cin>>n; a=power(10,n-1); b=power(10,n)-1; int start=clock(); for (x=0; x<=9; x++) // 初始化数据表 table[x]=power(x,n); for(x=a; x<=b; x++) { if(digitsum(x,n)==x) cout< } cout< return 0; 编译并执行以上程序，若输入7，得到如下所示的结果。 1741725 4210818 9800817 9926315 Running Time :984 ms. Press any key to continue 若输入8，得到如下所示的结果。 24678050 24678051 88593477 Running Time :11125 ms. Press any key to continue 从执行结果可以看出，采用打表的方法后，求解耗时明显减少了。 上面的程序虽然效率得到了提升，但仍然不理想。例如，执行上面的程序，若输入9，可得到如下所示的结果。 146511208 472335975 534494836 912985153 Running Time :125563 ms. Press any key to continue 从运行结果可以看出，求9位的花朵数，耗时近2分钟。下面我们来寻找更好的方法来解决求N位花朵数这个问题。 实例1-3中求5位花朵数是对所有的90000个5位数（10000~99999）进行穷举，看每个数的各位数字的5次方之和是否等于这个数字。实际上，可以穷举0~9这10个数字出现的次数（每个数字都可能出现0~5次），当所有数字出现次数之和等于5时，说明这时数字的组合有可能为5位花朵数，进而求出每个数字的5次方分别乘以其出现的次数的和值sum，再判断sum内各个数字出现的次数是否与穷举各个数字时每个数字出现的次数分别相同，若相同，则sum就是一个5位花朵数。 例如，当穷举到数字2出现了2次、7出现2次、9出现1次时，由于2+2+1=5，此时计算sum=2*25+2*75+1*95=64+33614+59049=92727，检查得到的和sum的各个位，若恰好出现2个2、2个7和1个9，说明这种数字组合使得其和为5位花朵数。 按这样的思路穷举，只需处理2002种情况。这是因为新思路是对数字出现的次数进行穷举。共有7种情形： （1）5位数中每个数字只出现1次（即1+1+1+1+1），有种情况。 （2）5位数中1个数字出现2次、另3个数字各出现1次（即1+1+1+2），有种情况。 （3）1+2+2（即1个数字出现1次，一个数字出现2次，还有一个数字出现2次）有种情况。 （4）1+1+3（即1个数字出现1次，另一个数字也出现1次，还有一个数字出现3次）有种情况。 （5）1+4（即1个数字出现1次，另一个数字出现4次）有种情况。 （6）2+3（即1个数字出现2次，另一个数字出现3次）有种情况。 （7）1个数字出现5次，有10种情况。 252+840+360+360+90+90+10=2002。 因此，按新思路解决问题的关键在于怎样穷举各数字的出现次数。 【实例1-5】取数组合 有0~9共10个数字，现需从这10个数字中取出n个数字构成一个取数组合，每个数字可以重复取，但不考虑取数顺序。 例如，当n=3时，123、132、213、231、312和321均视为同一种取数组合（数字1、2、3各取1个），而112（两个1和一个2）和122（一个1和两个2）是不同的取数组合。 编写程序，输入n，输出所有的取数组合种数。例如，输入3，输出220；输入5，输出2002；输入8，输出24310。 定义一个take数组来保存n位数中每个数字的出现次数。最直接的办法可以编写一个9重循环，最外层循环次数从0~n用于对take[0]赋值、第2层内循环次数从0~n-take[0]用于对take[2]赋值、…、依次类推，最内层循环次数从0~用于对take[8]赋值，剩下的次数赋给take[9]。 #include using namespace std; int main() int n,i,cnt=0,take[10]={0}; cin>>n; for (take[0]=0; take[0]<=n; take[0]++) { for (take[1]=0; take[1]<=n- take[0]; take[1]++) { for (take[2]=0; take[2]<=n- take[1]- take[0]; take[2]++) { for (take[3]=0; take[3]<=n- take[2]- take[1]- take[0]; take[3]++) { for (take[4]=0; take[4]<=n- take[3]- take[2]- take[1]- take[0]; take[4]++) { for (take[5]=0; take[5]<=n- take[4]- take[3]- take[2]- take[1]- take[0]; take[5]++) { for (take[6]=0; take[6]<=n- take[5]- take[4]- take[3]- take[2]- take[1]- take[0]; take[6]++) { for (take[7]=0; take[7]<=n- take[6]- take[5]- take[4]- take[3]- take[2]- take[1]- take[0]; take[7]++) { for (take[8]=0; take[8]<=n- take[7]- take[6]- take[5]- take[4]- take[3]- take[2]- take[1]- take[0]; take[8]++) { take[9]=n- take[8]- take[7]- take[6]- take[5]- take[4]- take[3]- take[2]- take[1]- take[0]; for (i=0;i<=9;i++) cout<<"i:"< cout< cnt++; } } } } } } } } } cout<<"Count="< return 0; 上面的思路虽然直接，但按9重循环的写法太累赘。实际上，如果将take数组从take[0]~take[9]赋值看出一个依次赋值的过程，那么这个过程可以抽象为一个递归过程。 设函数DFS(int take[],int index,int leave)表示对数组元素take[index]赋予0~leave之间每个值，则其后会对数组元素take[index+1]赋予0~leave- take[index]之间的每个值，即递归地调用函数DFS(take[], index+1, leave- take[index])。递归的终止条件为index==10，即take[0]~take[9]全部赋了值。递归的初始调用为index=0、leave=n。 #include using namespace std; int cnt=0; void DFS(int take[],int index,int leave) int i; if(index==9) // 0~8各数字使用个数列举完成 { take[index]=leave; // 剩余的给数字9 cnt++; // 有效取数组合，计数 return ; } for(i=0;i<=leave;i++) { take[index]=i; DFS(take,index+1,leave-i); } int main() int n, take[10]={0}; cin>>n; DFS(take,0,n); cout<<"Count="< return 0; 编译并执行以上程序，若输入5，可得到如下所示的结果。 Count=2002 Press any key to continue 有了上面的取数组合函数void DFS(int take[],int index,int leave)，将n位数中0~9每个数字出现的次数，存储在take数组中后，可以采用循环 sum=0; for (i=0;i<10;i++) sum=sum+take[i]*power(i,lenN); 计算出在当前组合情况下各位数字的lenN次方之和sum。再用函数Judge判断sum中出现的数字组合情况是否与take数组中的组合情况相同，若相同，则就是n位花朵数。 采用新思路优化后的源程序如下： #include #include using namespace std; int table[10]; int power(int num,int n) int p=1,i; for (i=1;i<=n;i++) p=p*num; return p; bool Judge(int take[], int sum) int i,a[10]={0}; while (sum) { a[sum%10]++; sum/=10; } for(i=0; i<10 && a[i]==take[i];i++); return i==10; void DFS(int take[],int index,int leave) int i,sum; if(index==9) // 0~8各数字使用个数列举完成 { take[index]=leave; // 剩余的给数字9 sum=0; for (i=0;i<10;i++) sum=sum+take[i]*table[i]; if(Judge(take,sum)) { cout< } return ; } for(i=0;i<=leave;i++) { take[index]=i; DFS(take,index+1,leave-i); } int main() int n,i,take[10]={0}; cin>>n; int start=clock(); for (i=0; i<=9; i++) // 初始化数据表 table[i]=power(i,n); DFS(take,0,n); cout< return 0; 编译并执行以上程序，若输入9，可得到如下所示的结果。 534494836 472335975 912985153 146511208 Running Time :15 ms. Press any key to continue 从这个执行结果看出，采用新思路优化后的程序的执行效率好很多。 实际上，我们还可以进一步优化。以5位花朵数为例，由于9的5次方等于59049，因此9最多只能在5位花朵数中出现1次，否则和值会超过5位数，因此可以对和值可能超过5位数的情况进行剪枝；另外，当小数字用得太多，还可能导致和值的位数达不到，例如4的5次方为1024，5个4的5次方的和值才5120，因此若5位数全部由5以下的数字组成，5次方之和不可能达到5位数，可以直接进行下次搜索，增加大数字的个数。实验验证，经过两次剪枝后，处理的情况为1329种，又会大大减少。并且，如果位数越大，采用两次剪枝后的效率越好。例如，求解8位花朵数时，0~9的8位取数组合情况有24310种，采用剪枝后，处理的情况为16131种。 为进行剪枝处理，在当前数字index确定了个数i后，将i*indexn累加到和sum中，为此，可以考虑在DFS函数中增加一个参数sum，用于保存当前和。这样，在剪枝处理时可以引用这个和值。 采用剪枝处理后的源程序如下： #include #include using namespace std; int table[12]; // 其中table[10]保存power(10,n)，table[11]保存power(10,n-1) int power(int num,int n) int p=1,i; for (i=1;i<=n;i++) p=p*num; return p; bool Judge(int take[], int sum) int i,a[10]={0}; while (sum) { a[sum%10]++; sum/=10; } for(i=0; i<10 && a[i]==take[i];i++); return i==10; void DFS(int take[],int index,int leave,int sum) int i,tmp,tmp1; if(index==10) // 0~9各数字使用个数列举完成 { if(leave>0) return; // 位数不足，直接返回 if(Judge(take,sum)) { cout< } return ; } for(i=0;i<=leave;i++) { take[index]=i; tmp=sum+i*table[index]; if (tmp>=table[10]) break; // 剪枝1，和值已超过power(10,n) tmp1=tmp+(leave-i)*table[9]; // 剩余的数字全用9的话 if(tmp1 DFS(take,index+1,leave-i,tmp); } int main() int n,i,take[10]={0}; cin>>n; int start=clock(); for (i=0; i<=9; i++) // 初始化数据表 table[i]=power(i,n); table[10]=power(10,n); table[11]=power(10,n-1); DFS(take,0,n,0); cout< return 0; 在前面优化程序的基础上，下面我们来解决“蓝桥杯”软件设计大赛的一道比赛题。这是一个大Boss哟！ 【实例1-6】21位花朵数 编写一个程序，输出所有的21位花朵数。（注意：这个整数有21位，它的各位数字的21次方之和正好等于这个数本身。） 按照上面的剪枝优化程序的思路，可以求21位花朵数。由于21位整数超出了long整型数的范围，因此采用大整数来处理。定义结构体BigNum如下： struct BigNum int dig[4]; int len; }; 其中，数组元素dig[0]~dig[3]分别保存大整数从低位到高位的数字，为节省空间，每个数组元素保存大整数中的8位数字。即存储大整数时，从低位到高位每8位1组，每组保存到一个数组元素中。Len表示每8位1组的组数，意即大整数的位数（不过以8位为1个单位）。 在大整数的基础上，编写如下6个函数，来进行大整数的处理。 void Init(BigNum &a)； // 大整数a初始化为0 void PrintBigNum(BigNum a)； // 输出大整数 a BigNum CarryUp(BigNum a)； // 大整数 a 的处理进位 BigNum Multi(BigNum a,int n)； // 大整数 a 和整数 n 相乘 int Cmp(BigNum a,BigNum b)； // 大整数a和b比较大小 BigNum Add(BigNum a,BigNum b)；// 大整数a 和 b 相加 另外，由于求1个数字的21次方也较耗时。为了减少程序运行时间，可以先把0~9的21次方及其不同的出现次数的值先算出来，存储到指定的数组中。 定义数组BigNum pow[10]; ，其中 pow[i]（0<=i<=9）存储数字i的21次方。 定义数组BigNum sp[10][22]; ，其中 sp[i][j] 存储数字i的21次方乘以 j（出现次数）得到的值，即 。 这样，程序中需要用到这些值时，可直接引用相应数组元素的值，从而最多只需计算10个大数连加（想想为什么？），无需计算求幂和乘法，大大节约时间。 #include #include using namespace std; const int BIT=100000000; // 每8位一组 struct BigNum int dig[4]; int len; }; BigNum pow[10],MAX,MIN; BigNum sp[10][22]; int take[10]={0}; int LEN=21; void Init(BigNum &a) a.len=1; for (int i=0;i<4;i++) a.dig[i]=0; void PrintBigNum(BigNum a) int i; cout< for(i=a.len-2; i>=0; i--) { cout.fill('0'); // 定义填充字符'0' cout.width(8); cout< } cout< BigNum CarryUp(BigNum a) // 处理进位 int i; for(i=0;i { a.dig[i+1]+=a.dig[i]/BIT; a.dig[i]%=BIT; } return a; BigNum Multi(BigNum a,int n) BigNum c; int i; Init(c); c.len=a.len+1; for(i=0;i { c.dig[i]=(a.dig[i])*n; } c=CarryUp(c); if(c.len>0 && c.dig[c.len-1]==0)c.len--; return c; int Cmp(BigNum a,BigNum b) if(a.len>b.len) return 1; if(a.len int i; for(i=a.len-1;i>=0 && a.dig[i]==b.dig[i];i--); if(i==-1) return 0; return a.dig[i]-b.dig[i]; BigNum Add(BigNum a,BigNum b) int i; if(b.len>a.len) a.len=b.len; for(i=0;i { a.dig[i]+=b.dig[i]; } a=CarryUp(a); if(a.dig[a.len]) a.len++; return a; bool Judge(BigNum sum) int aa[10]={0}; int i,j; for(i=1;i<=8;i++) // 求 sum 中0~9各个数字出现的次数，保存到数组aa中 for (j=0;j<3; j++) { aa[sum.dig[j]%10]++; sum.dig[j]/=10; } aa[0]=aa[0]-3; for(i=0; i<10 && aa[i]==take[i];i++); return i==10; void DFS(int deep,BigNum Sum,int leave) BigNum check; BigNum cc; int i; if(deep==10) { if(leave>0)return; if(Judge(Sum)) { PrintBigNum(Sum); } return ; } for(i=0;i<=leave;i++) { take[deep]=i; check=Add(Sum,sp[deep][i]); if(Cmp(check,MAX)>=0) break; // 剪枝1 cc=Add(check,sp[9][leave-i]); if(Cmp(cc,MIN)<0) continue; // 剪枝2 DFS(deep+1,check,leave-i); } int main() int start=clock(); int i, j; BigNum sum; Init(pow[0]); for(i=1;i<10;i++) { Init(pow[i]); pow[i].dig[0]=1; for (j=1;j<=21;j++) pow[i]=Multi(pow[i],i); } for(i=0;i<10;i++) Init(sp[i][0]); for(j=0;j<10;j++) for(i=1;i<22;i++) { sp[j][i]=Add(sp[j][i-1],pow[j]); } Init(sum); MAX.dig[2]=100000; MAX.len=3; MIN.dig[2]=10000; MIN.len=3; DFS(0,sum,LEN); cout< return 0; 编译并执行以上程序，得到如下所示的结果。 128468643043731391252 449177399146038697307 Running Time :32046 ms. Press any key to continue 在进行程序设计实践时，一定不能就题论题，而应该贯穿着“连营”和“集智”。在这个实践过程中，有提出问题、解决问题、扩展问题、再解决问题、对解决问题的方法评价、优化设计等几个环节，实际上是一个螺旋式滚动向前的过程，在这个螺旋式不断向前的过程中，能够非常自然地调动程序设计学习者的学习兴趣，而且通过问题的不断扩展“连营”，有效地开阔读者的思维。这种通过一个程序的层层推进，不断连营，进行程序设计训练的方法，本质上是一个循序渐进、螺旋式上升的过程，可使学习者在“走台阶”的过程中，进入到程序设计的殿堂。1.1.2 水仙花数的初步连营
1.1.3 水仙花数的进一步连营
1.2 花朵数的集智
1.2.1 花朵数的初步集智
1.2.2 花朵数的进一步集智
1.3 21位花朵数