fraction.cpp

用排序方法解决埃及分数问题的Visual C++ 实现

// Fraction.cpp: implementation of the CProperFractionReduce class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "Fraction.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CProperFractionReduce::CProperFractionReduce()
{

}

CProperFractionReduce::~CProperFractionReduce()
{

}
//最大公约数 greatest common divisor
int CProperFractionReduce::max_div(int x,int y)
{
	int i,start;

	start=x<y?x:y;
	i=start;
	while((x%i!=0)||(y%i!=0))i--;
	return i;
}
//最小公倍数 lease common multiple
int CProperFractionReduce::min_mul(int x,int y)
{
	int i,start;

	start=x>y?x:y;
	i=start;
	while((i%x!=0)||(i%y!=0))
	{
		i+=start;
	}
	return i;
}
//缓冲区中两数比较,用于srch_div中qsort的比较回调函数
int CProperFractionReduce::compare(const void *first,const void *second)
{
	int x,y;
	x=*(int *)first;
	y=*(int *)second;

	if(x<y)return -1;
	else if(x==y)return 0;
	else return 1;
}
int CProperFractionReduce::srch_div(int x)
{
	int i,j;
	//因为x最大为MAXSIZE,所以i不会超过32,因而j不会超过64
	
	for(j=0,i=2;i<=(int)(sqrt(x));i++)
	{
		if(x%i==0)
		{
			databuf[j]=i;j++;
			if(i*i!=x){databuf[j]=x/i;j++;}
		}
	}
	databuf[j]=x;j++;
	qsort(databuf,j,sizeof(int),compare);//从小到大排序

	//printf("****************************************************\n");
	//for(i=0;i<j;i++)printf("%d ",databuf[i]);
	//printf("\n");

	return j;//返回约数个数
}

int CProperFractionReduce::calculate(int fractcnt)
{
	int i,sum=0;

	for(i=0;i<fractcnt;i++)
	{
		sum+=calden/databuf[idxbuf[i]];
	}
	return(sum==calnum);
}
int CProperFractionReduce::combnum(int neednum,int begnum,int leftnum)
{
	int i,j;
	static int sum=0;

	if(leftnum==0)//完成了一组排列数的选择
	{
		if(neednum>0)//Cni
		{
			if(calculate(neednum))//查看找到的数是否满足要求
			{
				//找到了:条件满足
				if(neednum<bestcnt)
				{
					//for(j=0;j<neednum;j++)printf("%d ",databuf[idxbuf[j]]);
					//printf("\n");
					for(j=0;j<neednum;j++)bestbuf[j]=databuf[idxbuf[j]];
					bestcnt=neednum;
				}
				else if(neednum==bestcnt)
				{
					if(bestbuf[neednum-1]>databuf[idxbuf[neednum-1]])
					{
						//for(j=0;j<neednum;j++)printf("%d ",databuf[idxbuf[j]]);
						//printf("\n");
						for(j=0;j<neednum;j++)bestbuf[j]=databuf[idxbuf[j]];
					}
				}
			}
		}
		else{printf("*");printf("\n");}//Cn0
		sum++;//统计个数
	}
	else
	{
		for(i=begnum;i<=datacnt-leftnum;i++)
		{
			*(idxbuf+neednum-leftnum)=i;//将约数的索引号存入索引缓冲区
			combnum(neednum,i+1,leftnum-1);
		}
	}
	return sum;
}
int CProperFractionReduce::workitout(int x,int y)
{
	int numerator,denominator;//分子,分母,测试数据组个数
	int prpnum,prpden,z,loopcnt;//真分数的分子,分母,最大公约数,最大循环计数
	int i;

	z=max_div(x,y);//找最大公约数
	numerator=x<y?x:y;
	denominator=y>x?y:x;
	prpnum=numerator/z;//化为最简
	prpden=denominator/z;
	calden=prpden;//计算用分子,分母
	calnum=prpnum;
	//初始化结果缓冲区和结果计数
	for(i=0;i<MAXSIZE;i++)bestbuf[i]=MAXSIZE;
	bestcnt=MAXSIZE;
	while(calden<MAXSIZE)
	{
		datacnt=srch_div(calden);
		//用穷取法从datacnt个约数中选取2...datacnt个约数
		loopcnt=datacnt<bestcnt?datacnt:bestcnt;
		for(idxcnt=2;idxcnt<=loopcnt;idxcnt++)
		{
			combnum(idxcnt,0,idxcnt);
		}
		calnum+=prpnum;
		calden+=prpden;
	}
	for(i=0;i<bestcnt;i++)printf("%d ",bestbuf[i]);
	printf("\n");

	return 1;
}