试题五

[程序5说明]
本程序采用递归算法将一个自然数 n 分解成不多于 m 个整数之和。设构成和数 n 的各个整数取于数组 d ,d 中的整数互不相等且由大到小存储。例如,数组 d 中存储以下整数: d[] = {100 ,81 ,64 ,49 ,36 ,25 ,16 ,9 ,4 ,1} ,则有:
　n 　m 　程序运行后的输出
　100 2 100 = 100
　13　2 13 = 9 + 4
　14　2 No answer　 (9+4+1超过2个)
　71　5 71 = 49 + 9 + 9 + 4　 (表示可重复取数)
函数 End()的形参 c 表示 d 中可取的整数个数;形参 pd 指向能成为和数的整数的存放位置。

[程序5]
#include〈stdio.h〉
#define N 20
int find( int n ,int m ,int *d ,int c ,int *pd )
{ int r ;
if ( n == 0 ) return 0 ; /* 已分解完成 */
if ( m == 0 || c == 0 ) return -1 ; /* 不可以分解 */
if ( __(1)__ ) return find( n ,m , d+1 ,c-1 ,pd ) ;
else { *pd = *d ;
r = find( __(2)__ ,d , c , __(3)__ ) ; /* 继续对剩余数作分解 */
if ( r >= 0 ) return __(4)__ ;
return find( n ,m , __(5)__ ,pd ) ;
}
}
void main()
{ int n ,m ,k ,i ,p[N] ,*pptr = p ;
int d[ ] = { 100, 81, 64, 49, 36, 25, 16, 9, 4, 1 } ;
printf( "Enter n , m : " ; scanf( %d %d ,&n ,&m );
k = find( n , m , d , 10 , pptr ) ;
if ( k <= O ) printf ( "No answer!\n" ) ;
else{ printf( "%d = %d" , n , p[0] ) ;
for ( i = l ; i < k ; i++ )
printf(" +%d" , p[i] ) ;
printf("\n");
}

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]