循环小数.cpp

给定一个分式A/D

//////////////////////////////////////////////////////////////////////////
/*
* 
* 
*
* 文件名称：循环小数.cpp
* 作 者：郭运凯
* 完成日期：2008.09.23
* 此版本采用纯理论计算，当循环节长度大于 9后，会出现计算错误
 
*/////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <vector>
using namespace  std;

int zhengshu;//整数部分
int yushu;

 typedef struct node 
 {
	 int data;
	 int count;
	 struct node *lchild;
	 struct node *rchild;
 }*STree,TreeNode;

 typedef struct cnode 
 {
	 int data;
	 int count;
 }Cnode;
 
 vector<Cnode> R; //存储分解质因式的结果

 STree tr = NULL;

 void insertTree(STree & root,int n)
 {
	 if (root == NULL)
	 {
		 TreeNode * temp = new TreeNode;
		 temp->data = n;
		 temp->count = 1;
		 temp->lchild = NULL;
		 temp->rchild = NULL;
		 root = temp;
	 }
	 else 
	 {
		 if (root->data == n)
		 {
			 root->count ++;
		 }
		 else if (root->data > n)
		 {
			 insertTree(root->rchild,n);
		 }
		 else
		 {
			 insertTree(root->lchild,n);
		 }
	 }
 }

 void inorder(STree const root)
 {
	 if (root != NULL)
	 {
		 inorder(root->lchild);
		 Cnode t;
		 t.data = root->data;
		 t.count = root->count;
		 R.push_back(t);
		 inorder(root->rchild);

	 }	 
	 else		 
	 {		
	   return;
	 }
 }

int findgcd(int m, int n)
{ //求最大公约数 
	if (m < n)
	{
		int t = m;
		m = n;
		n = t;
	}

	int temm = 0;
	while ( m % n != 0)
	{
		temm = m;
		m = n;
		n = temm % n;
	}
	return n;
}

void huajian(int & n,int & m)
{
	int gcd = findgcd(m,n);

	if (gcd == 0)
	{
		printf("gcd = 0 \n");
	}
	else
	{
		m /= gcd;
		n /= gcd;
	}	
}
 void fenjie(int m)
 {
	 int i = 2;
	 bool fc = false;
	 bool found = false;

	 while(true)    //永远循环
	 {
		 for ( ;i<=sqrt(m);i++)
			 if(m % i==0) //i肯定是质数,N肯定不是质数
			 {
				 fc = true;
				 found =  true;
				// cout<<i<<"×";
				 insertTree(tr,i); //把分解结果存入到查找树中
				 m = m/i;
				 break ;
			 }
			 
			 if(fc) 
			 {
				 fc = false;
				 continue;
			 }
			 
			 if(found)
			 {
				 //cout<<m<<endl;
				 insertTree(tr,m);
			 }
			 else
			 {
				// cout<<m<<"是个质数，不能分解"<<endl;
				 insertTree(tr,m);				 
			 }
			  break;			
	 }
 }
 void check(int n,int m)
 {
	 vector< int> result;
	 
	 bool other = false;
	 int othervalue = 1 ;

	 int shang,yushu;

	 int max25 = 0;

	 printf("%d.",zhengshu);

	 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
		 {
			 other = true;	
			 for (int k = 0;k < R[i].count;k++)
			 {
				  othervalue *= R[i].data;	
			 }
			
		 }
	 }

	 if (max25 != 0 )
	 {
		 if (!other)
		 {
			 /*结论1，一个最简分数，如果分母中除了2 和5 以外，不含其它质因
				 数，则这个分数必化为有限小数且在这个有限小数中，小数部分的位数
					等于分母中含2，5 因数个数的最大数．*/
		//////////////////////////////////////////////////////////////////////////
	//	printf(" 1. 一个最简分数 \n");
			 
		yushu = n;
		while (yushu != 0)
		{
			shang = (10*yushu)/m;
			result.push_back(shang);
			yushu = (10*yushu) % m;
		}
	
		for (int i = 0;i < result.size();i++)
		{
			printf("%d",result[i]);
		}	

		 }
		 else
		 { 
			 //混合小数 
			 /*结论3，一个最简分数的分母中，如果既有2，5 这样的因数，又含
			 有2，5 以外的质因数则这个分数定能化成混循环小数，它的不循环部分
			 的数字个数等于分母因数中2，5 个数较多一个的个数，循环节的最小位
			 数等于分母中除2，5 以外因数积能整除的9 构成数字中最小数中含9 的
			个数．*/
			 //////////////////////////////////////////////////////////////////////////
			 
			yushu = n;

			for (int i = 0;i < max25;i++)
			{
				shang = (10*yushu)/m;
				result.push_back(shang);
			    yushu = (10*yushu) % m;
			}

			//计算后面循环节的长度
			int len = 1;
			int k = 9;
			while (k % othervalue != 0)
			{
				len++;
				k = k*10 +9;
				if (len >= 1024)
				{
					printf("is too long,break\n");
					break;
				} 
			}
            //求循环节
			for (i = 0; i< len; i++)
			{
				shang = (10*yushu)/m;
				result.push_back(shang);
			    yushu = (10*yushu) % m;
			}
		
			for (i = 0;i < max25; i ++)
			{
				printf("%d",result[i]);
			}

			printf("(");
			for (; i < max25 + len;i++)
			{
			printf("%d",result[i]);
			}
			printf(")");
		 }
		
	 }//end max 25 != 0
	 else
	 { 
	 /*结论2，一个最简分数，如果分母中只能分解出2 和5 以外的质因数，
	 则这个分数必化成纯循环小数，这个纯循环小数的循环节的最少位数等
	于能被分母整除的、由9 构成的数中最小数的9 的个数．		 */
		 //计算后面循环节的长度
		// printf("3. 纯循环小数 \n");
		 //printf("%d \n",othervalue);
		 int len = 1;
		 int k = 9;
		
		 while (k % othervalue != 0)
		 {
			 len++;
			 k = k*10 +9;
			 if (len >= 1024)
			 {
				 printf("is too long,break\n");
				 break;
			 }
		 }

		 yushu = n;
		 
		 for (int i = 0;i < len;i++)
		 {
			 shang = (10*yushu)/m;
			 result.push_back(shang);
			 yushu = (10*yushu) % m;
		}

		 printf("(");
		 for (i = 0 ; i < max25 + len;i++)
		 {
			 printf("%d",result[i]);
		 }
			printf(")");
	 }
	 printf("\n");	 

 }
 void distroy(STree & root)
 {
	 if (root != NULL)
	 {
		 distroy(root->lchild);
		 distroy(root->rchild);
		 delete root;
		 root = NULL;
	 }
	 else 
		 return;
 }

 void caculate( int n,int m)
 {
   zhengshu = n/m;
   yushu = n % m;
   if (yushu == 0)
   {
	   printf("%d\n",zhengshu);
   }
   else
   {
	   n = yushu;
	   if (R.size() != 0)
	   {
		   R.erase(R.begin(),R.end());
	   }
	   if (tr != NULL)
	   {
		   distroy(tr);
	   }
	   huajian(n,m);
	   
	   fenjie(m);
	   inorder(tr);
      check(n,m);

   }
 
 }

 void main()
 {
	 int n,m;
	 printf("input n,m \n");
	 scanf("%d%d",&n,&m);
	 while (m != 0)
	 {
	caculate(n,m);
	 printf("input n,m \n");
   scanf("%d%d",&n,&m);
	 }	
 }