對於下圖所示的二叉樹 其先序、中序、後序遍歷的序列如下： 先序遍歷： A、B、D、F、G、C、E、H 中序遍歷： B、F、D、G、A、C、E、H 後序遍歷： F、G、D、B、H、E、C、A 層序遍歷： A、B、C、D、E、F、G、H /** * Definition for a binary tre ...
【例1】求1/n的值。
問題描述
給定個非0的整數n，計算1/n的值。
輸入
第一行整數T，表示測試組數。後面T行，每行一個整數 n (1≤|n|≤10^5)。
輸出
輸出1/n (是迴圈小數的，只輸出第一個迴圈節)。
輸入樣例
4
2
3
7
168
輸出樣例
0.5
0.3
0.142857
0.005952380
（1）編程思路。
定義數組int vis[100001];，其中vis[i]表示整數i作為餘數是否出現過。初始時，數組vis的各元素值（除vis[0]外）全部置為0，置vis[0]=1，因為若餘數為0，表示除法結束。
模擬豎式除法過程，從num=1開始，先置vis[num]=1（表示餘數num出現了），再輸出 num*10/n的整數部分（也是當前位的商），同時修改num為num*10%n。若vis[num]==1，則表示餘數num已出現，此時要麼除盡（num==0），要麼構成迴圈小數，結束除法過程；若vis[num]==0，則繼續上面的豎式除法過程。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); if (n<0) { printf("-"); n = -n;} if (n==1) { printf("1\n"); continue; } else printf("0."); int vis[100001]; memset(vis, 0, sizeof(vis)); vis[0] = 1; // 如果餘數為0，表示可以除盡 int num = 1; while (1) { if (vis[num]) break; vis[num] = 1; printf("%d", num * 10 / n); num = (num * 10) % n; } printf("\n"); } return 0; }
將上面的源程式提交給HDU題庫 HDU 2522 A simple problem （http://acm.hdu.edu.cn/showproblem.php?pid=2522），可以Accepted。
【例2】分數化小數
問題描述
編寫一個程式，輸入一個形如N/D的分數，輸出它的小數形式。如果小數有迴圈節的話，把迴圈節放在一對圓括弧中。
例如，1/3=0.33333333… 寫成 0.(3)，4/2=2 寫成 2.0。
輸入
輸入包含兩個整數N和D（1≤N，D≤105）。
輸出
輸出按照上面規則計算出的小數表達式。如果結果長度大於 76，每行輸出76個字元。
輸入樣例
45 56
輸出樣例
0.803(571428)
（1）編程思路。
同例1的方法，模擬豎式除法過程。但要註意保存已輸出的字元數信息（每輸出76個字元要換行），還需要尋找出迴圈節，將其用括弧括起來。
（2）源程式。
#include <stdio.h> #include <string.h> int main() { int n,d; scanf("%d%d", &n,&d); if (n%d==0) { printf("%d.0\n",n/d); } else { int len=0; int temp=n/d; do { len++; temp/=10; }while (temp!=0); len++; // n/d整數部分的長度加小數點 printf("%d.",n/d); int vis[100001],a[100001]; memset(vis, 0, sizeof(vis)); vis[0] = 1; // 如果餘數為0，表示可以除盡 int num = n%d; int cnt=0; while (1) { if (vis[num]) break; vis[num] = cnt+1; a[++cnt]=num * 10 / d; num = (num * 10) % d; } int i; if (num==0) { for (i=1;i<=cnt;i++) printf("%d",a[i]); } else { int k=vis[num]; for (i=1;i<k;i++) { printf("%d",a[i]); len++; if (len%76==0) printf("\n"); } printf("("); len++; if (len%76==0) printf("\n"); for (i=k;i<=cnt;i++) { printf("%d",a[i]); len++; if (len%76==0) printf("\n"); } printf(")"); } printf("\n"); } return 0; }
將上面的源程式提交給洛谷題庫 P1530 [USACO2.4]分數化小數 Fractions to Decimals （https://www.luogu.com.cn/problem/P1530），可以Accepted。
【例3】小數化分數
問題描述
編程式寫一個程式，不但可以將普通小數化成最簡分數，也可以把迴圈小數化成最簡分數。
輸入
第一行是一個整數N，表示有多少組數據。
每組數據只有一個純小數，也就是整數部分為0。小數的位數不超過9位，迴圈部分用()括起來。
輸出
對每一個對應的小數化成最簡分數後輸出，占一行。
輸入樣例
3
0.(4)
0.5
0.32(692307)
輸出樣例
4/9
1/2
17/52
（1）編程思路。
普通純小數化分數非常方便，將小數部分乘以10的m次方，使得小數部分全部變成整數，之後將這個整數作為分子，10的m次方作為分母，將分子和分母都除以它們的最大公約數，化簡為最簡分數即可。
因此，本題主要要考慮無限小數如何轉換為分數，無限小數分為無限迴圈小數和無限不迴圈小數。而無限不迴圈小數是不可以化為分數的。題目中給的無限小數都是無限迴圈小數。其轉化為分數的基本思想是將小數擴大倍數，使得擴大後的小數與擴大前的小數部分相同，再將兩個小數作差即可得出答案。
例如，將無限迴圈小數0.32(692307)轉化為分數的過程為
0.32(692307) * 100 = 32.(692307)
0.32(692307) * 100000000 = 32692307.(692307)
上面兩個式子相減得 0.32(692307)* 99999900 = 32692275 ，這樣迴圈小數 0.32(692307) 轉化為分數為32692275/99999900，分子與分母再同除以它們的最大公約數1923075，化簡為最簡分數得 17/52。
（2）源程式。
#include <stdio.h> int gcd(int a, int b) { if (a%b==0) return b; return gcd(b, a % b); } int main() { int t; scanf("%d", &t); while(t--) { char s[20]; scanf("%s", s); int t1 = 1, t2, i, k; int fz = 0,fm; // 分別表示分子和分母 for (i = 2; s[i]!='\0' && s[i] != '('; i++) { fz = fz * 10 + s[i] - '0'; t1 *= 10; } fm = fz; t2 = t1; if (s[i] != '(') { k = gcd(t1, fz); fz /= k; fm = t1 / k; } else { for (++i; s[i] != ')'; i++) { fm = fm * 10 + s[i] - '0'; t2 *= 10; } fz = fm - fz; fm = t2 - t1; k = gcd(fz, fm); fz /= k; fm /= k; } printf("%d/%d\n", fz, fm); } return 0; }
將上面的源程式提交給HDU題庫 HDU 1717 小數化分數2 （http://acm.hdu.edu.cn/showproblem.php?pid=1717），可以Accepted。
