文档介绍：1990年下午试题五阅读下列说明和流程图。回答问题1和2。有一个集合,集合中有n个元素,每个集合元素都是正整数,它们存放在一维数组A中,每个数组元素存放一个集合元素。对给定的整数total(假定集合中每个元素的值均小于total),流程图求出所有满足下列条件的子集:子集中各元素之和等于total。本题在使用试探法找出全部解答的过程中,依次选取当前的候选元素,尝试组成一个小于total的部分和,如果合适,则选取下一元素试探;若不合适,则回溯取另一个候选元素尝试,题中利用s栈存放候选元素的下标,用它实现回溯。如果候选元素加上部分和等于total,则表示找到一个解答,然后通过回溯,再试探寻找其它的解答。[问题1]流程图中的④应与A~D中的哪一点相连,并填充图中的①~③,使之成为完整的流程图。[问题2]设total=10,n=6,数组A中各元素的值为(8,4,1,2,5,3)。若图中的(1)框改为sp:0,则执行该流程图后输出什么结果。1990年下午试题五[问题1]①i→s[sp] ②T+A[s[sp]]→T ③s[sp]+1 ④D[问题2] J=1时输出的解为: 82 4123 415 253 J=2时输出的解为: 4123 415 253 J=3时输出的解为: 253 J=4时输出的解为: 253 J=5,6时无解1993年下午试题七[程序说明]对于正整数n,输出其和等于n且满足以下限制条件的所有正整数的和式,即组成和式的数字自左至右构成一个非递增的序列。如n=4,程序输出为 4=4 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1k深度分解将要分解出的和数a[k]应该为k-1度分解所分解出的和数a[k-1]和其余数的较小者(因为和式要降序排列)1993年下午试题七程序中给出了分别采用递归和非递归解法的两个函数rd()和nd()。函数rd()采用递归解法,它有两个参数n和k。其意义分别是被分解和式的数n,及当前第k深度分解。算法思想是对n的所有合理的和式分解,将分解出的数(称为和数)存于数组a[]中。当其中一个分解已不再需要进一步分解时,即找到一个解,将存于数组a[]中的一个完整和式的和数输出。当还需要进一步分解时,以要进一步分解的数及分解深度为参数,递归调用分解和式函数。1993年下午试题七函数nd()以要分解的数为参数,另开设一个数组r[],用于存贮当前还未分解的余数。在求一个解的第k步时,a[k]为第k个和数,r[k]为相应的余数。当找到一个分解后(此步r[k]等于0),输出解,并作回溯处理,从当前k退回到第一个不为1的和数,将其减1,并将其余数加1,准备去找另一个解;否则,生成下一步的分解和数与余数。#defineMAXN100 inta[MAXN],r[MAXN];rd(intn,intk)//递归求解 {intj,i; for(j=_①_;j>=1;j--)//依次求解 {a[k]=j; if(_②_)//判断k深度分解是否为解 {printf(“%d=%d”,a[0],a[1]);//找到解 for(i=2;i<=k;i++) printf(“+%d”,a[i]); printf(“\n”); } else_③_//不是解,递归求k+1深度的分解 } }执行过程 rd(4,1); rd(3,2); rd(2,2); rd(2,3); rd(1,4);n<a[k-1]?n:a[k-1]n==a[k]或n==jrd(n-j,k+1);重点:数组a的变化nd(intn)//回溯法求解 {inti,k;k=0;r[0]=n; do {if(_④_)//和②相同的判断 {printf(“%d=%d”,a[0],a[1]); for(i=2;i<=ksi++) printf(“+%d”,‘a[i]); print(“\n”); while(k>0&&_⑤_)k--;//找到解后回溯 if(k>0){a[k]--;r[k]++;} } else{a[k+1]=_⑥_;//生成下一步分解的和数和余数 r[k+1]=r[k]-a[k+1]; k++; } }while(k>0); }r[k]==0a[k]==1a[k]<r[k]?a[k]:r[k]1993年下午试题七inttest_data[]={3,4,5}; main() {inti; for(i=0;i<sizeof(test_data)/sizeof(int);i++) {a[0]=test_data[i]; rd(test_data[i],1); printf(“\n__________\n\n”); nd(test_data[i]); printf("\n_________\n\n")