再次求助1元钱分解为5角2角1角的问题
求一共的分法,要求不能用穷举法做,实在没找到这个问题的解法,用递归做的,出现了很多重复情况,怎么可以去掉这些重复呢,哪位好心人帮忙改下吧,十分感谢啊!!!!!这个问题上次问过了,可是我没看懂就结贴了,再也不着急结贴了
int a[10],m[4]={10,5,2,1};
int sum(int a[],int n)
{
int i,s=0;
for(i=0;i<=n;i++)
s=s+a[i];
return s;
}
void prin(int a[],int n)
{
int i;
for(i=0;i<=n;i++)
printf("%d ",a[i]);
printf("\n");
}
void divide(int i,int top,int number)
{
int j;
for(j=0;j<4;j++)
{
a[top]=m[j];
if(number==sum(a,top))
{
prin(a,top); continue;
}
else if(number<sum(a,top)) continue;
if(top>=number) continue;
divide(m[j],top+1,number);
}
}
void main()
{
int number=10,top=0;
int i=0;
divide(i,top,number);
}
好像是递归的次数多了,不知道怎么改啊,这个还是参照一个别的问题的解法,求帮忙啊!!!!