php - 算法：求两个整数相除的循环节

问题描述

问 题

循环节定义：依照一定顺序，不断重复出现的所有数字，叫做这个循环小数的循环节．
例如：
1/3=0.3333……－>0.[3]
1/7=0.142857142857142857……－>0.[142857]
9/7=1.285714285714285714……->1.[285714]
13/6=2.1666……->2.1[6]

求[]中的数字

解决方案

循环节有很长的，例如：

1/9997=0.0001000300090027008102430729218765629688906672001600480144043 212963889166750025007502250675202560768230469140742222666800040012003 60108032409722916875062518755626688006401920576172851855556667，长度是 192

贴代码：

#include<stdio.h>
#define mn 1000
void main()
{
    int i,m,n,r,t;
    int p[mn],q[mn];

    for(i=0;i<mn;i++) //给数组p初始化值全为-1
    {
        p[i]=-1;
        q[i]=0;
    }

    printf("input :m,n(0<=m<n<=1000)= ");
    scanf("%d%d",&m,&n);

    t=0; //初始化值
    r=m; //把被除数赋给r

    while(r!=0&&(p[r]==-1)) //循环条件当r不为0且p[r]=-1时执行循环体
    {
        p[r]=t;             //余数r第一次出现的位置
        r=10*r;             //把被除数扩大10倍，以至于取第一个小数

        t++;
        q[t]=r/n;           //计算小数点后t位的值：取整，即为m/n的小数从小数点开始逐个取出放到数组q中
        r=r%n;              //算完一位就去掉一位，即取余对n
    }

    printf("m/n = 0.");     //因为m<n,所以m/n整数部分0,所以先输出'0.'
    if (r!=0)               //被除数不为0就执行以下语句
    {
        for(i=1;i<=p[r];i++)   //输出循环小数中前面非循环的部分
            printf("%d",q[i]);

        printf("(");            //输出循环的小数放在括号中

        for(i=p[r]+1;i<=t;i++)
            printf("%d",q[i]);

        printf(")");
    }
    else                    //被除数为0的情况
        for(i=1;i<=t;i++)    //输出不循环的小数
            printf("%d",q[i]);
    printf("/n");
}  

参考：

探讨循环小数的循环节
笔试题——输出循环小数的循环节

这篇关于php - 算法：求两个整数相除的循环节的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！