這問題要解得好,不容易。先考慮一般比較簡單的情況,只考慮真分數,並以 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;
}

注意到一點,當分子 = 1,分母 = 231547 時,輸出已經非常驚人,非循環節 0 位;循環節具 115773 位。若只是要求循環節長度,而不做細項輸出時,此時應用的是性質1與性質2做合用,於此便不再示範。

edisonx 發表在 痞客邦 PIXNET 留言(4) 人氣()


留言列表 (4)

發表留言
  • 緋村
  • 寫的太好了!!
    這個問題一直困擾著我~
    雖然我只有學過VB
    但是也差不多懂啦XD
    不循環節長度算法我還是第一次聽到QAQ!!!
    真的知道了就方便許多~
    感恩大大常有系統的整理~><!!
  • 哪裡,能靜下心看完這篇長文的人,我也該感謝你。
    最後這篇文章補上了之前沒說明到的二點,
    (1) 先將假分數化為真分數 - 若是 11 / 7 ,必須先化成 3 + 4/7
    (2) 必須進行約分 - 若為 18 / 24,必須先化成 3 / 4
    祝您實作愉快 *^_^*

    edisonx 於 2011/11/20 21:58 回覆

  • 風
  • 實在是感謝版主寫了這篇文章!!
    另外我想請問一下,找循環節除了用那暴力法以外,還有其他較好的方法可以更快地得知嗎?
  • 細仔看程式碼。程式碼裡用的並非暴力法。

    edisonx 於 2012/05/01 02:42 回覆

  • 風
  • 恩恩!
    實在是謝謝版主您的分享,讓我解惑許多
    感恩!!
  • 昊杨 于
  • 十分感謝!
    但是在2/5分解前應該先將小數約分,不然不循環節的長度會比實際的要長!
    比如當Q=34,P=18時,答案應爲1.(8),但程式的結果爲1.8(8)!
  • 你說的約分,我在上面的文章有提出來過了。片段如下

    >> 另有種情況必須注意,上述所有的計算,必須先進行過二個步驟:
    >> (1) 先將假分數化為真分數 - 若是 11 / 7 ,必須先化成 1 + 4/7
    >> (2) 必須進行約分 - 若為 18 / 24,必須先化成 3 / 4

    edisonx 於 2014/08/01 22:07 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼