8-2-6.c

2005软件工程师考试下午编程题源代码

/*中国系统分析员顾问团，http://www.csai.cn*/
/*程序员下午考试指南书籍源码*/

#include <stdio.h>
#define MAXN 10

divisor( int n ,int m ,int d[] ,int dn ){ 
int s,p,t,b[MAXN];
for ( s=0;s<dn && d[s]>n;s++ );
p=0; b[0]=s; t=d[b[p]];
while ( t != n && p >= 0 ){
if  (p<m-1) {
for ( s=b[p]; s<dn-1 && t+d[s]>n ;s++ );
if ( s <= dn-1 && t+d[s] <= n ){
b[ ++p ]=s;
t += d[s];
continue;
}
}
t -= d[b[p]]; 
while ( p>=0 && b[p]==dn-1 ) //循环内的语句作了调整,原题程序当找不到结果时会报错.
{
	if (p>0)
	t -= d[ b[--p] ]; 
	else
	p--;
}
if ( p >= 0 ) 
t += d[++b[p]]; 
}

printf("print....");
if ( t==n ) {
printf( "%4d=%3d",n,d[b[0]] ); 
for ( s = 1;s<= p;s++ ) 
printf( "+%3d",d[b[s]] ); 
printf( "\n" ); 
} 
else printf( "No solution.\n" ); 
}

main(){
static int list[] = { 100,81,64,49,36,25,16,9,4,1 }; 
int i; 
  for ( i=50; i<300; i++ )
divisor( i,4,list,sizeof(list)/sizeof(int) ); 

}