C语言分解数组

时间：2011-05-24 来源：孤独的猫

阅读下列程序说明和 C 程序，把应填入其中__n__ 处的字句，写在答卷的对应栏内。

[程序说明]

对于正整数 n ，输出其和等于 n 且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如n=4，程序输出为

4 = 4

4 = 3 +1

4 = 2 +2

4 = 2 +1 +1

4 = 1 + 1 + 1 + 1

程序中给出了分别采用递归和非递归解法的两个函数 rd() 和 nd()。

函数 rd( )采用递归解法，它有两个参数n和k。其意义分别是被分解和式的数n，及当前第k深度分解。算法思想是对n的所有合理的和式分解，将分解出的数(称为和数)存于数组a[ ]中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组 a[] 中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调整用分解和式函数。

函数 nd( )以要分解的数为参数，另开设一个数组 r[]，用于存贮当前还未分解的余数。

在求一个解的第k步时，a[k] 为第 k 个和数，r[k] 为相应的余数。当找到一个分解后( 此步 r[k] 等于 0 )，输出解，并作回溯处理，从当前k退回到第－个不为1的和数，将其减1，并将其余数加1，准备去找另一个解；否则，生成下一步的分解和数与余数。

代码为：

 1 #define MAXN 100
 2  int a[MAXN],r[MAXN];
 3 rd(int n,int k)
 4 {    int j,i;
 5     for (j=n<a[k-1]?n:a[k-1];j>=1;j--)
 6     {     
 7         a[k]=j;
 8         if (j==n)
 9         { 
10             printf("％d = ％d",a[0],a[1]);
11             for (i=2;i<=k;i++)
12                 printf("+％d",a[i]);
13             printf("\n");
14         }
15         else rd(n-j,k+1); 
16     }
17 }
18 
19 nd (int n)
20 { 
21     int i,k;
22     k=0;
23     r[0]=n;
24     do
25     {
26         if (r[k]==0)
27         { 
28             printf("％d=％d",a[0],a[1]);
29             for (i=2;i<=k;i++)
30                 printf("+％d",a[i]);
31             printf("\n");
32             while (k>0 && a[k]==1) k--;
33             if (k>0) { a[k]--;r[k]++;}
34         }
35         else
36         {
37             a[k+1]=a[k]<r[k]?a[k]:r[k];
38             r[k+1]=r[k]-a[k+1];k++;
39         }
40     } while (k>0);
41 };
42 
43 int test_data[]={3,4,5};
44 main()
45 {
46     int i;
47     for (i=0;i<sizeof(test_data)/sizeof(int);i++)
48     { 
49         a[0]=test_data[i];
50         rd(test_data[i],1);
51         printf("\n__________\n\n");
52         nd(test_data[i]);
53         printf( "\n_________\n\n");
54     }
55 }