《編程之美》有一個題是給定一個小數，將其轉化成最簡分數，思路比較簡單，首先將小數轉化成分數，然后對分數化簡。如果將問題倒過來，給定一個分數（N/D），將其轉化成對應的小數，這該如何做？

我們先分析一下分數轉化成小數的可能情況：1）小數是一個有限小數（0.abc…d）；2）小數是純循環小數（0.）；3）小數是非純循環小數（0.ab…c）。分數不可能產生無限不循環小數。第一種情況無需特殊考慮，只需要常規方法即可求得，但是可能小數位數非常長，這時我們只考慮前100位小數。如果小數是循環小數，但是循環節長度大于50，則我們認為其是一個有限小數。當小數是循環小數時，最關鍵的問題是找到循環節，這個問題不是一個非常簡單的問題。

方法一

一種可行的方案是：先不考慮循環節的問題，直接求出分數的前100位小數，然后尋找循環節。但是這時又存在尋找循環節的問題，該問題同樣不是一個非常容易的問題。問題的難度在于：1）針對小數位數很長的有限小數，怎樣避免將其識別成循環小數；2）尋找循環節的初始位置。第一個問題可以通過判斷小數是否是有限小數來解決，具體是：首先將分子分母約分成最簡形式，然后判斷分母的因子是否只包含2和5；如果是，則小數是有限小數，否則是無限小數。

第二個問題的前提是小數一定是循環小數，此時我們要找到循環節的長度和起始位置（因為不確定小數是純循環小數還是非純循環小數）。求循環節比較困難，有點類似于尋找字符串的最長重復子串，但是不完全一樣。不過我們可以知道，求循環節的問題至少和尋找字符串的最長重復子串難度相當。

方法二

通過對方法一的分析，我們可以知道算法最后落腳到求字符串的最長重復子串，難度比較大，而且復雜度也比較高。現在我們換種思路，不必求出小數的前100位，而在計算到第三個循環節的時候就可以返回（后面會詳述為什么是第三個循環節）。

要獲得小數的每一位，我們可以模擬除法操作完成。在除法操作中，當被除數大于除數時，可以直接相除，余數可以通過模運算獲得。在求第一位小數時，由于余數小于除數，按照運算規則，我們可以將余數乘以10，然后和被除數相除，獲得第一位小數和新的余數。重復上述過程，直到余數為零或者已經求得100位小數。

為了求循環節，我們要尋找一下循環節有什么規律。當出現一次循環節之后，第二遍遍歷時，循環節都會重復，我們可以利用這個規律去求循環節。保存循環節可以和每次除法之后的余數聯系起來。每一次得到一位小數，都會有一個對應的余數，而余數的范圍在0~D-1之間，所以我們可以利用一個長度為D的數組remainder保存每一次計算的小數結果。例如，某次運行的結果是5，余數是3，則remainder[3]=5。

一個直觀的結果是，如果對某個位置進行賦值時，發現要賦的值和已經保存的值相同，則說明我們已經得到循環節，開始一個新的循環節計算；否則將該位置賦值為新值。如果一個小數是純循環小數，則我們只需要統計我們對多少個位置進行賦值即可確定循環節的長度（如3/7）。如果小數是一個非純循環小數，但是在得到其結果時余數和循環節內的結果余數相同，也可以直接統計賦值的位置獲得循環節的長度（如5/6）。但是，這時我們會發現一個問題，非循環節部分的賦值位置和循環節的賦值位置沒有關系，如果我們單純地統計所有賦值的位置就會把非循環節的位置也統計進來導致錯誤（如7/12）。

這里的關鍵是我們沒有對非循環節部分和循環節部分進行區分，只需要將循環節部分從非循環節部分中區別出來就不會出錯。它們之間的根本區別就是非循環節部分只出現一次，而循環節部分出現無窮多次，我們可以利用這個結論去做區分。方法就是記錄每一個位置賦值的次數，統計兩遍循環節，這樣就可以將非循環節部分和循環節部分區分開來。為了統計每個位置賦值的次數，我們需要分配一個和保存結果數組等長的數組time。如果當前的余數對應的remainder位置的值與將要賦的值不一樣，則將time數組對應位置賦值為1，表示某個小數第一次出現。如果當前的余數對應的remainder位置的值與將要賦的值一樣，則將time數組對應位置加1。如果time數組中出現賦值為3的位置，則停止計算，此時已經計算了兩次循環節，已經獲得了所有的信息。通過統計次數為2的位置我們就可以獲得循環節的長度，然后就可以正常打印該分數的小數。

下面是完整的代碼：

#include <stdio.h>
#include <stdlib.h>

char small[101];//保存計算結果的字符串

int main()
{
	int N,D;
	int result;
	while(scanf("%d %d",&N, &D) != EOF)
	{
		result=N/D;
		N=N%D;
		if(N==0)
		{
			printf("%d.0
",result);
		}
		else
		{
			int i=0,r,len=0;
			//由于針對不同的分母，余數不同，不能提前分配空間，最好能先將分數化成最簡分數
			int* remainder=(int*)malloc(sizeof(int)*D);
			int* atime=(int*)malloc(sizeof(int)*D);
			//必須要將每一個余數可能的結果初始化為-1，因為每位結果可能是0~9
            memset(remainder,-1,sizeof(int)*D);
            memset(atime,0,sizeof(int)*D);
			while(N!=0&&i<100)
			{				
				N=N*10;
				r=N/D;//獲得商
				N=N%D;//獲得余數
				if(remainder[N]==r)//非第一次遇到
				{
                    if(atime[N]!=2)//非第三次遇到
                        atime[N]++;
                    else//第三次遇到
                    {
                        for(int j=0;j<D;j++)
                        {
                            if(remainder[j]!=-1&&atime[j]>1)len+=1;
                        }
                        break;
                    }
				}
				else
				{
					remainder[N]=r;
                    atime[N]=1;
				}
				small[i++]='0'+r;
			} 
			small[i-len]='';

			//獲得第一個循環節的第一個字符
			char tmp=small[i-len*2];
			small[i-len*2]='';
			//先打印非循環節部分
			printf("%d.%s",result,small);
			char *p=small+(i-len*2);
			*p=tmp;
			if(N!=0&&len>0)
				printf("(");
			printf("%s",p);
			if(N!=0&&len>0)
				printf(")
");
			else
				printf("
");

			free(remainder);
			free(atime);
		}
	}
	return 0;
}

總結

以上是生活随笔為你收集整理的分数化小数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。