[C&++] 分數化循環小數－Edison.X. Blog

這問題要解得好，不容易。先考慮一般比較簡單的情況，只考慮真分數，並以 32 / 99 為例假設 Q=32

32 * 10 = 320 , 320 / 99 = (3) 餘 23
23 * 10 = 230 , 230 / 99 = (2) 餘 32

餘數回到 32 (Q)，確定循環即為 0.(32)，這部份程式碼約如下

/*
 * filename : decimal_simple.c
 * author   : edisonx / edison.shih
 * compiler : Visual C++
 *
 */

#include <stdio.h>
int main()
{
    const int Q=32, P=99;
    int q=Q, p=P, len=0;

    printf("0.(");
    do{
        q*=10;
        printf("%d", q/p);
        q%=p;
        ++len;
    }while(q!=Q);
    printf("), len=%d\n", len);
    return 0;
}

這是最最最基本簡單的思維、寫法，但實際上完全沒考慮到下面二件事：

(1) 循環節與非循環節關係：試著去算 4/96，這程式會出包。
(2) 非循環小數：它也沒辦法判斷該分數是否為非循環小數。

-------------------

有人提了「暴力法」這概念，但這方法確實是非常非常糟！可試想一下，非循環節為 4 位，循環節為 35 位，怎麼做暴力法？就算披出來效率如何？這類型的東西，數學不好的話還是先去找相關資料為佳，關於這題目，先定義一些簡單的符號，同時以 1 / 28 做為舉例。

1/28 = 0.03(571428)
q : 被除數 (分子) -> 1
p : 除數 (分母) -> 28
m1: 非循環節部份，長度定 m1_len -> m1 = 03, m1_len=2
m2: 循環節部份，長度定 m2_len -> m2=571428, m2_len=6

接下來有幾個性質會用到，都以舉例說明。

(1) 循環節長度 - 次方性質
1/7 = 6
1/(7*7) = 6*7 = 42
1/(7*7*7) = 6*7*7 = 294

(2) 循環節長度 - 分母為質因數乘積
1/3=1 , 1/7=6, 1/(3*7) = 1/3 * 1/7 = lcm(1,6)=6
1/13=6, 1/17=16, 1/(13*17) = lcm(6,16) = 48

(3) 不循環節長度 - 2/5 性質 分母有一個2或一個5，不循環節長度就 +1，如 1/75 = 1/(3*5*5) = 0.01(3)，不循環2位數；分母同時含5之 m 方或2之 n 方時，不循環節長度為 max(m, n)，如 1/1500 = 1/(2*2*3*5*5*5) = 0.000(6)，不循環 3 位數。

----------------------

其它至少還有 2 個性質可用，是專門拿來求循環節數值的求法，但程式只用上面的 (3) 性質，應即可達到不錯的效果，甚至可以再直接一點的方式，直接去做2、5的因式分解，分解出來之後便知道非循環節長度，接下來的循環節就不是問題了(這在上面已寫過了)。

另有種情況必須注意，上述所有的計算，必須先進行過二個步驟：

(1) 先將假分數化為真分數 - 若是 11 / 7 ，必須先化成 1 + 4/7
(2) 必須進行約分 - 若為 18 / 24，必須先化成 3 / 4

順序不要顛倒！先化成真分數後，做約分速度會較快，且一定要進行約分，否則在循環節/不循環節長度計算上會發生錯誤。

最後的結論是：如果可完全拆解成 2 與 5 之乘積，這個數就不是循環小數了。這次，我們一起討論假分數的情況，程式碼約略如下。

/*
 * filename : decimal.c
 * author   : edisonx / edison.shih
 * compiler : Visual C++
 *
 */

#include <stdio.h>
int main()
{
    int Q, P, q, p;
    int integer;
    int len_noloop, len_loop, cnt2, cnt5;
    int i;
    
    printf("輸入 分子 與 分母:");
    while(scanf("%d%d", &Q, &P)==2){
        
        /* 調整為真分數 */
        integer = Q/P; 
        Q = q = Q%P, p=P;
        len_noloop=len_loop=cnt2=cnt5=0;
        printf("%d.", integer);

        /* 整除沒小數 跳過不處理 */
        if(Q==0) {
            printf(" 整除\n");
            printf("\n輸入 分子 與 分母:");
            continue;
        }

        /* 分母進行 2 5 分解 */
        while(P%2==0 && Q!=0) P/=2, ++cnt2;
        while(P%5==0 && Q!=0) P/=5, ++cnt5;

        /* 計算 非循環節 長度*/
        len_noloop = ((cnt2 > cnt5) ? (cnt2) : (cnt5));

        /* 輸出 非循環節 */
        for(i=0; i!=len_noloop; ++i) {
            q*=10;
            printf("%d", q/p);
            q%=p;
        }

        /* 輸出並計算循環節 */
        if(Q!=0) { /* 確定有循環節 */
            putchar('(');
            Q = q;
            do{
                q*=10;
                printf("%d",q/p);
                q%=p;
                ++len_loop; /* 計數循環節位數 */
            }while(q!=Q);
            putchar(')');
        }

        printf("\n非循環節長度 : %d\n", len_noloop);
        printf("  循環節長度 : %d\n", len_loop);
        printf("\n輸入 分子 與 分母:");
    }
    return 0;
}