// 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;
}