六、求循环小数
六、求循環小數
文章目錄
- 六、求循環小數
- 題目描述
- 解題思路
- 上機代碼
題目描述
對于任意的真分數 N/M （ 0 < N < M ），均可以求出對應的小數。如果采用鏈表表示各個小數，對于循環節采用循環鏈表表示，則所有分數均可以表示為如下鏈表形式。
輸入： N M k
輸出： 轉換后的小數（不超過 k ）
要求： 僅編寫將分數轉換為小數的函數 change( int n, int m, NODE * head ) 。
預設代碼：
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */#include <stdio.h> #include <stdlib.h>typedef struct node { int data;struct node * next; }NODE;void output( NODE *, int ); void change( int, int, NODE * );void output( NODE * head, int kk ) { int k=0;printf("0.");while ( head->next != NULL && k<kk ){ printf("%d", head->next->data );head = head->next;k ++;}printf("\n"); }int main() { int n, m,k;NODE * head;scanf("%d%d%d", &n, &m, &k);head = (NODE *)malloc( sizeof(NODE) );head->next = NULL;head->data = -1;change( n, m, head );output( head,k );return 0; }/************************************** void change(int n, int m, NODE *head) {This function is wating for you. } ***************************************//* PRESET CODE END - NEVER TOUCH CODE ABOVE */| 測試用例 1 | 1 8 50 | 0.125 | 1秒 | 64M | 0 |
| 測試用例 2 | 29 33 10 | 0.8787878787 | 1秒 | 64M | 0 |
| 測試用例 3 | 7 18 52 | 0.3888888888888888888888888888888888888888888888888888 | 1秒 | 64M | 0 |
| 測試用例 4 | 2 7 50 | 0.28571428571428571428571428571428571428571428571428 | 1秒 | 64M | 0 |
解題思路
建立兩個數組：商和余數，用來保存結果的商和余數。
讓num每次變為余數的十倍，這樣除以m后的商和余數都是正整數，而不是小數，方便操作。
每次計算完成后都與前面的結果進行比較，如果存在商和余數都相同的情況，那一定存在循環，用 p1、p2 記錄位置，flag進行標記。如果num被除盡，則證明沒有循環，用 p1 標記最后的位置即可。
根據 p1 的位置構建鏈表：
- 如果沒有循環，則構建的是完整鏈表；
- 如果flag標記有循環，則構建的是前綴，最后根據 p2 的位置補上循環部分即可
因為用到了memset函數，所以需要補充頭文件string.h
上機代碼
#include <string.h> void change(int n, int m, NODE *head ) {//初始化int shang[10010], yushu[10010];memset(shang, 0, sizeof(shang));memset(yushu, 0, sizeof(yushu));int p1 = 0, p2 = 0;int flag = 0;int num = n * 10;for (int i = 0; ; i++){shang[i] = num / m;yushu[i] = num % m;for (int j = 0; j < i; j++){/* 當商和余數與之前相同時，即標志著出現循環用p1、p2記錄位置，flag=1表示存在循環 */ if(shang[j] == shang[i] && yushu[j] == yushu[i]){p1 = j;p2 = i;flag = 1;break;}}num = yushu[i] * 10;if(!num)//如果num被除盡，變為0，則沒有循環{p1 = i + 1;break;}if(flag == 1){break;}}/*根據 p1 的位置，如果沒有循環，則建立完整鏈表；如果有循環，則建立前綴。 */NODE *r = head;for (int i = 0; i < p1; i++){//尾插法建立鏈表NODE *q = (NODE*)malloc(sizeof(NODE));q->data = shang[i];q->next = NULL;r->next = q;r = q;}//補上循環if (flag == 1){NODE *r_save = r;for (int i = p1; i < p2; i++){NODE *q = (NODE*)malloc(sizeof(NODE));q->data = shang[i];q->next = NULL;r->next = q;r = q;}r->next = r_save->next;} } 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀總結
