循环 八式

八、求循环节

文章目录 八、求循环节题目描述解题思路上机代码

题目描述

对于任意的真分数 N/M （香港vps 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 */ 测试输入期待的输出时间限制内存限制额外进程测试用例 11 3ring=1
31秒64M0测试用例 21 8ring=0
NULL1秒64M0测试用例 329 33ring=2
871秒64M0测试用例 42 7ring=6
2857141秒64M0解题思路

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;}} 44991908