xunhuan.rar_循环节

////////////////////////////////////////////////////////////////////////// /* * * * * 文件名称：循环小数.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); } }