问答题 【说明】 计算n的合数。一个整数n可以有多种划分,使其划分的一列整数之和为n。例如,整数5的划分为: 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 共有7种划分。这种划分的程序如下所示。 【程序】 #include <stdio.h> int n[1000],m,k; void output sum() { int j; for(j=0;n[j]!=0;j++) printf("%d/t",n[j]); printf("/n"); } void sum(int i) if(m-n[i]<n[i]) { m=m-n[i]; {{U}}(1) {{/U}} i++; n[i+1]=0; } else { {{U}} (2) {{/U}} m-=n[i]; i++; } if(m!=n[i]) sum(i); else output_sum(); if(n[i]>1) { n[i]--; {{U}}(3) {{/U}} } else { while((n[i]==1)&&(i>O)) { i--; {{U}} (4) {{/U}} } if(i!=0) { {{U}} (5) {{/U}} sum(i); } } } void main() { int i; scanf("%d",&n[0]); m=k=n[0]; for(i=1;i<=k;i++) n[i]=0; while(n[0]!=1) { n[0]--; i=0; sum(0); m=k; } }
【正确答案】
【答案解析】(1)n[i+1]=m; (2)n[i+1]=n[i]; (3)sum(i); (4) m+=n[i]; (5)n[i]--; [分析] 本题考查C语言中计算n合数方法的实现。 题目要求计算n的合数,我们首先来了解一下什么是n的合数。在正整数n的所有不同的划分中,将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递推关系。 (1)q(n,1)=1,n≥1 当最大数n1不大于1时,任何正整数只有一种划分形式,就是全1。 (2)q(n,m)=q(n,n),m≥n 最大加数n1实际上不能大于n。因此,q(1,m)=1。 (3)q(n,n)=1+q(n,n-1) 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 (4)q(n,m)=q(n,m-1)+q(n-m,m),n>m>1 正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。要想求出所有解,只有递归到最底层即全为1为止。 知道了上述特性,下面我们来看代码。在代码中首先声明一个数组和两个全局变量 k,m。结合程序可以看出,其中数组n[i]中存放的是当前划分的最大加数,而m中存放的是当前被划分的数。程序代码中有三个函数,一个是主函数、一个output_sum()函数和一个sum()函数,函数output_sum()的功能很简单,就是输出一次划分结果,在sum()函数中被调用。 经过分析不难发现,函数sum()的作用是实现整数的划分。在函数体中,首先是一个条件判断语句,其作用是判断当前被划分的数m是否小于当前最大加数的两倍,如果条件成立,说明数被划分为两个数后,其最大加数大于另一个数,而另一个数应该存放在数组中。此时执行语句m=m-n[i]来求出另一个数,接下来应该是保存这个数到数组中的下个位置,第(1)空就用来完成这个任务,因此,答案为n[i+1]=m。 第(2)空所在的位置是条件不成立的情况下运行的语句,条件不成立,说明数被划分为两个数后,其最大加数小于另一个数,数可以有更大的最大加数,因此,将当前的最大加数保存到数组中的下个位置,此空答案为n[i+1]=n[i]。 第(3)空也在一个条件选择语句下面,此条件语句用于判断当前最大加数是否大于1,如果大于1,则需要接着划分,因此要调用函数sum(),其参数是i,所以此空答案为sum(i)。 第(4)空是条件不成立即当前最大加数为1的情况下执行的语句,当最大加数为1时,说明递归到了最底层,此时,递归应该往回走了,这需要还原当前最大划分数m(为这个数的其他划分做准备),因此,这个空的答案为m+=n[i]。 第(5)空是在条件i!=0为真的情况下执行的语句,如果条件为真,说明递归还没有回到最上层,应该求当前被划分数在当前最大加数变小后的其他划分情况,因此,此空答案为n[i]--。