八、求循環節

文章目錄

• 八、求循環節
• • 題目描述
  • 解題思路
  • 上機代碼

題目描述

對于任意的真分數 N/M （ 0 < N < M ），均可以求出對應的小數。如果采用鏈表存儲各位小數，對于循環節采用循環鏈表表示，則所有分數均可以表示為如下鏈表形式。

輸入： N M

輸出： 整個循環節

要求： 編寫一個盡可能高效的查找循環節起始點的函數： NODE * find( NODE * head, int * n ) 。函數的返回值為循環節的起點（即圖中的指針p），n為循環節的長度。

說明：提交程序時請同時提交將分數轉換為小數的函數 change( int n, int m, NODE * head ) （前面題目中已經編寫）。

將分數轉換為小數的函數 change()我們在 六、求循環小數 中已經編寫過了，可以直接拷貝過來

預設代碼：

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */#include <stdio.h> #include <stdlib.h> typedef struct node { int data;struct node * next; } NODE;NODE * find( NODE * , int * ); void outputring( NODE * ); void change( int , int , NODE * ); void outputring( NODE * pring ) { NODE * p;p = pring;if ( p == NULL )printf("NULL");elsedo { printf("%d", p->data);p = p->next;} while ( p != pring );printf("\n");return; }int main() { int n, m;NODE * head, * pring;scanf("%d%d", &n, &m);head = (NODE *)malloc( sizeof(NODE) );head->next = NULL;head->data = -1;change( n, m, head );pring = find( head, &n );printf("ring=%d\n", n);outputring( pring );return 0; }/* Here is waiting for you. void change( int n, int m, NODE * head ) { }NODE * find( NODE * head, int * n ) {} *//* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 測試輸入期待的輸出時間限制內存限制額外進程

測試用例 1	1 3	ring=1 3	1秒	64M	0
測試用例 2	1 8	ring=0 NULL	1秒	64M	0
測試用例 3	29 33	ring=2 87	1秒	64M	0
測試用例 4	2 7	ring=6 285714	1秒	64M	0

解題思路

change()函數我們已經編寫過了，直接拷貝過來即可，這里就只考慮find()函數的編寫

我們借助于編寫change()時的思想，將 p1、p2 設置為全局變量。這樣，判斷如果 p2 > p1 ，即可證明存在循環

存在循環，循環的長度即為 p2 - p1 的距離，否則長度為0。

仔細觀察outputring()函數發現，函數從循環節開始的位置出發，將循環節打印一圈后終止。所以我們在find()函數中越過 p1 長度的前綴，直接將循環節開始的位置返回即可。

上機代碼

#include <string.h> int p1 = 0, p2 = 0; void change(int n, int m, NODE *head ) {//初始化int shang[10010], yushu[10010];memset(shang, 0, sizeof(shang));memset(yushu, 0, sizeof(yushu));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;} }NODE * find( NODE *head, int *n ) {if(p2 > p1)//存在循環{NODE *p = head->next;//初始化//計算長度*n = p2 - p1;//越過前綴for (int i = 0; i < p1; i++){p = p->next;}return p;}else//不存在循環{*n = 0;return NULL;} }

總結

以上是生活随笔為你收集整理的八、求循环节的全部內容，希望文章能夠幫你解決所遇到的問題。

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