prog26.cpp

经典算法实现题--半数单集问题

#include<stdio.h>   
#include<stdlib.h>    
#include<iostream.h>
#include<fstream.h>
#include<math.h>
             //林宗明   060320081
int *a;

int prog(int k)
{
	int i,s;
	if(k==1)
		return 1;
	else
	{
		if(a[k]==0)
		{
			s=1;
			for(i=1;i<=k/2;i++)
			{
				s+=prog(i);
				if(i>10&&(i/10<=(i%10)/2))
					s-=prog(i/10);
			}
			a[k]=s;
		}
		return a[k];
	}
}


void  main()   
{   
	ifstream params("input.txt"); 
	ofstream outtxt("output.txt"); 
	if(!params) 
	{
		cerr<<"input.txt file not open!"<<endl;
		params.close();
	}   
	int n,j;
    params>>n; 		  		 
	a=new int[n+1];
	for(j=0;j<=n;j++)
		a[j]=0;
	a[0]=0;
	outtxt<<prog(n)<<endl; 
	params.close();
	outtxt.close();
	delete a;
}