divisor.cpp

常用算法与数据结构原代码

#include <iostream.h>
#include <fstream.h>

#define MAXN 10

ofstream out("a.txt");

void 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==-1)
				break;
			t-=d[b[p]];
		}
		if (p>=0)
			t+=d[++b[p]];
	}
	if (t==n)
	{
		out<<n<<"="<<d[b[0]];
		for (s=1;s<=p;s++)
			out<<"+"<<d[b[s]];
		out<<endl;
	}
	else
		out<<"No solution!"<<endl;
}

void main()
{
	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));
}