循环小数优化版0924.cpp

给定一个分式A/D

//////////////////////////////////////////////////////////////////////////
/*
* 
* 
*
* 文件名称：循环小数优化版0924.cpp
* 作 者：郭运凯
* 完成日期：2008.09.24
* 改进了循环节的计算，使之能计算长度在1，000，000，000内的循环小数
 
*/////////////////////////////////////////////////////////////////////////


#include <stdio.h>
#include <vector>
#include <math.h>
#include <iostream>

using namespace std;

int zhengshu;	//整数部分
int yushu;		//余数部分
int len = 0;	//循环节的长度
int maxlen;		//最长的循环节位数

int shang;

typedef struct treenode 
{
	int data;					//质因数数字			
	int count;					//出现次数
	struct treenode * lchild;
	struct treenode * rchild;
}* STree,TreeNode;

typedef struct RNode 
{
	int data;
	int count;
}RNode;

vector<RNode> R;		//存贮分解质因数的结果

vector< int > result;   //存贮结果

STree treeroot;		//搜索树的根节点

void insertTree(STree & root,int n)
{
	//将分解的质因数 n 在排序二叉树中搜索，没有发现时插入到树中，
	//如发现，则对应节点计数增一

	if (NULL == root)	//防止误写成root = NULL，造成将根节点直接重置
	{
		STree newnode = new TreeNode;
		newnode->data = n;
		newnode->count = 1;
		newnode->lchild = newnode->rchild = NULL;
		root = newnode;
	}
	else //root is not null
	{
		if (root->data == n)
		{
			root->count ++;
		}
		else if (root->data > n)
		{
			insertTree(root->lchild,n);
		}
		else
		{
			insertTree(root->rchild,n);
		}

	}
} //end of insertTree

void inorder(STree const root)
{
	//中序遍历排序二叉树，将质因数存入到向量R中

	if (root != NULL)
	{
		inorder(root->lchild);

		RNode temp;
		temp.data = root->data;
		temp.count = root->count;
		R.push_back(temp);

		inorder(root->rchild);
	}
	else
	{
		return;
	}
} // end inorder

int findgcd( int m,int n)
{
	//求 m和n 的最大公约数

	if (m < n)
	{
		int t = m;
		m = n;
		n = t;
	}

	if (0 == n)
	{
		return m;
	}
	
	if (m % 2 == 0)
	{
		if (n % 2 == 0)
		{
			return(findgcd(m >> 1, n >> 1) <<1 );
		}
		else
		{
			return findgcd(m >> 1,n);
		}
	}
	else
	{
		if (n % 2 == 0)
		{
			return findgcd(m,n >> 1);
		}
		else
		{
			//return findgcd(m,m - n);
			return findgcd(n,m - n);
		}
	}

} //end findgcd


void predigest(int & n,int  & m)
{
	//如分式不是最简形式，则将分式化简成最简形式

	int k = findgcd(m,n);

	m /= k;
	n /= k;
}

void fenjie(int m)
{
	//对m 分解质因数

	int i = 2;

	bool fcontinue = false;

    while (true)
    {
		for (; i <= sqrt(m);i++)
		{
			if (m % i == 0)
			{
				insertTree(treeroot,i);
				m /= i;
				fcontinue = true;	
				//一定要加上break 2008.09.23 18：36
				break;
			}
		}
		if (fcontinue)
		{
			fcontinue = false;
			continue;
		}

		insertTree(treeroot,m);
		break;
    }
}

void distroytree(STree & root)
{
	//释放排序二叉树的空间

	if (root != NULL)
	{
		distroytree(root->lchild);
		distroytree(root->rchild);
		delete root;
		root = NULL;
	}
}

void chunxiaoshu( int max25,int n,int m)
{
	//结果是纯小数形式

	FILE * fp;
	fp = fopen("result.txt","a");

	yushu = n;	
	

	for (int i = 0;i < max25;i++)
	{
		//只计算前 max25  个，此时小数个数只有max25 个

		shang = 10 *yushu / m;
		yushu  = 10* yushu % m;
		result.push_back(shang);
	}

	for (i = 0;i < max25;i++)
	{
		printf("%d",result[i]);	
		fprintf(fp,"%d",result[i]);
	}
	
	fclose(fp);

}

void chunxunhuan(int max25,int n,int m)
{
	//纯循环小数

	FILE * fp;
	fp = fopen("result.txt","a");

	int first_index = max25;  //循环节开始的位置，纯循环时，max25 = 0

	int second_index = first_index + 1;
	
	bool found = false;

	if (max25 == 0)  //纯循环小数，则余数取n,否则，保留前面计算下来的结果
	{
		yushu = n;
	}


	//初始化result
	for(int k = 0;k< 2;k++)
	{
		
		shang = 10 *yushu / m;
		yushu  = 10 * yushu % m;	
		result.push_back(shang);
	}


	while (! found)
	{
		while (result[second_index] != result[first_index])
		{
			//当没有发现循环节的第一个数字时，继续向后计算
			shang = 10 *yushu / m;
			yushu  = 10* yushu % m;
			result.push_back(shang);

			second_index++;
		}

		len = second_index - first_index;

		if (len > maxlen )
		{
			printf("循环节超过最大长度[%d],退出计算\n",maxlen);
			exit(-1);
		}
		
		int ntime;		//验证循环节的次数，当循环节较长时，
		                //出现很多连续的数字的可能性越来越小，因而适当减少验证的次数
		if (len  < 10)
		{
			ntime = 17;			
		}
		else if (len < 100)
		{
			ntime = 13;
		}
		else
		{
			ntime = 7;
		}
		if ((result.size() - first_index) < (ntime +1) * len )
		{
			int no = (ntime +1)*len - result.size() + first_index;
			for (int k = 0;k <no;k++)
			{
				shang = 10 *yushu / m;
				yushu  = 10* yushu % m;
				result.push_back(shang);
			}
		}

		found = true;

		for (int i = 0;i< ntime ;i++)
		{
			//对循环节校验nTime次
			for (int j = 0;j < len;j++)
			{
				if (result[second_index + i*len +j] != result[first_index + i* len +j])
				{
					found = false;
					break;
				}

			}
			//对循环节校验nTime次
		}

		if(found)
		{
			printf("(");
			fprintf(fp,"(");
			
			for (i = first_index; i < first_index +len;i++)
			{
				printf("%d",result[i]);
			    fprintf(fp,"%d",result[i]);
			
			}
			printf(")");
			fprintf(fp,")\n");
			fprintf(fp,"循环节长度为:%d\n",len);
			
			fclose(fp);
			break;
			
		}

		//如果前面没有找到循环节，则second_index 增1，
		//寻找下一个循环节的位置,否则程序陷入死循环
		second_index ++;
	}

}

void hunhe( int max25,int n,int m)
{
	//混合小数形式
	chunxiaoshu(max25,n,m);
	chunxunhuan(max25,n,m);
}

void calculate( int n,int m)
{
	int max25 = 0;			//max25是分母分解质因数后，因数中2 和 5 当中个数最大的

	int othervalue = 1;		//其他因数的乘积
	
	for (int i = 0; i < R.size(); i++)
	{
		if(R[i].data == 2 || R[i].data == 5)
		{
			if (R[i].count > max25)
			{
				max25 = R[i].count;
			}
		}
		else
		{
			for (int j = 0;j < R[i].count;j++)
			{
				othervalue *= R[i].data;
			}
		}
	}
  
	//开始分情况讨论 
	if(max25 != 0)
	{
		if (othervalue > 1)
		{		
			hunhe(max25,n,m);
			/*一个最简分数的分母中，如果既有2，5 这样的因数，又含有2，5 以外的
			质因数则这个分数定能化成混循环小数，它的不循环部分的数字个数
			等于分母因数中2，5 个数较多一个的个数，循环节的最小位数
			等于分母中除2，5 以外因数积能整除的9 构成数字中最小数中含9 的个数．*/
		}
		else
		{				
		/*一个最简分数，如果分母中除了2 和5 以外，不含其它质因数，则这个分数必化为
		有限小数且在这个有限小数中，小数部分的位数等于分母中
		含2，5 因数个数的最大数．*/
			chunxiaoshu(max25,n,m);
		}
	}
	else
	{		
		chunxunhuan(max25,n,m);
		/*一个最简分数，如果分母中只能分解出2 和5 以外的质因数，
		则这个分数必化成纯循环小数，这个纯循环小数的循环节的最少位数等
	于能被分母整除的、由9 构成的数中最小数的9 的个数．		 */
	}
	
}
void deal( int n,int m)
{

	FILE * fp;
	fp = fopen("result.txt","a");

	//n 是分子，m是分母
	zhengshu = n/m;
	yushu = n % m;
	if (yushu == 0)
	{
		printf("%d\n",zhengshu);	
		fprintf(fp,"%d",zhengshu);
		fclose(fp);
		
	}
	else
	{
		n = yushu;
		printf("%d.",zhengshu);
		fprintf(fp,"%d.",zhengshu);
		fclose(fp);
		if (R.size() != 0)
		{
			R.erase(R.begin(),R.end());
		}
		if (treeroot != NULL)
		{
			distroytree(treeroot);
		}
		if (result.size() != 0)
		{
			result.erase(result.begin(),result.end());
		}

		predigest(n,m);		//将分式化成最简形式
		fenjie(m);			//将分母分解质因数
		inorder(treeroot);	//将分解质因数的结果存入到R中	
		calculate(n,m);		//开始计算	

	}
}

void main()
{
	FILE * fp;
	fp = fopen("result.txt","a");
	
	int n,m;
	printf("input max len\n");
	scanf("%d",&maxlen);
	printf("input n,m\n");
	scanf("%d%d",&n,&m);
	while (m != 0)
	{
		fprintf(fp,"%d/%d = ",n,m);
		fclose(fp);
		deal(n,m);
		printf("\n循环节长度为%d\n",len);
		printf("input n,m\n");
		scanf("%d%d",&n,&m);
	}	
}