2.2.repeating_decimal 求循环小数

输入： N M

输出： 转换后的小数（不超过 50 ）

要求： 仅编写将分数转换为小数的函数 change( int n, int m, NODE * head ) 。

预设代码：前置代码

/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  
#include   
#include   typedef struct node  
{   int         data;  struct node * next;  
} NODE;  void output( NODE * );  
void change( int, int, NODE * );  void output( NODE * head )  
{   int k=0;  printf("0.");  while ( head->next != NULL && k<50 )  {   printf("%d", head->next->data );  head = head->next;  k ++;  }  printf("\n");  
}  int main()  
{   int n, m;  NODE * head;  scanf("%d%d", &n, &m);  head = (NODE *)malloc( sizeof(NODE) );  head->next = NULL;  head->data = -1;  change( n, m, head );  output( head );  return 0;  
}   
/* PRESET CODE END - NEVER TOUCH CODE ABOVE */ 

解题思路

本题只需编写change函数，也就是说给定N，M后直接算出小数各位用链表储存

难点两个：1）如何得出小数的各个数字？

2）循环小数的判定？

到这里了应该都会有一个初步想法。当然我觉得很明显直接算出整个小数是不太可能（

下面是一些思考：   

我们可以使用整数除法，然后依次移位来求各位数字——应该是这种问题基本解法——现在的问题是该怎么理解这种算法：我们以3/7为例。

可以非常直观地通过竖式除法来理解这个过程，因为人在计算竖式本身的时候是一位一位地得出数字的。可以看出这里的每一个数字都分别是该位前面留下的一位（需要*10）除以M的商；而余数则与下一个数字有关了。

所以，明显可以用循环来实现这个问题：首先用N/M，然后依次用余数*10/M，用链表存。

——然后我们还是来想一下怎么检测循环节吧，，

其实容易发现而且已经有一个非常聪明偷懒的做法，那就是直接存到50位，不用管是不是循环，也不去将循环节弄成图示的循环链表结构。包括之前的一些学长学姐的代码也是这样（respect），其实非常有效解决了问题，附上链接：

（数据结构）求循环小数_-Heisenberg-的博客-CSDN博客

这里附上前人的方法（respect）。这个是通过计算过程中考察商和余数都相等的情况来判断循环的开始，这基本是最标准的做法

六、求循环小数_风云诀4的博客-CSDN博客

然后就模仿这个判断方法来给出代码啦。

贴源代码

void change(int n, int m, NODE* cur)
{int fract[51], res[51];//fract存商（小数），res存余数int thisbit = n / m, i;fract[0] = thisbit;//为0，整数部分；小数从1开始NODE *start = cur, *pre = cur;cur->next = (NODE*)malloc(sizeof(NODE));if (cur->next)//检测malloc成功分配内存cur = cur->next;for (i = 1; i < 51; i++){n *= 10;thisbit = n / m;//商       n = n % m;//余数if (cur)//检测malloc成功分配内存{fract[i] = cur->data = thisbit;res[i] = n;int flag = 0, j;for(j = 1; j < i; j++){if(fract[i] == fract[j] && res[i] == res[j]){flag = 1;break;}}//检验有无循环if(flag){while(j--) start = start->next;pre->next = start;//这里注意新出现的相同数字属于下一循环节，用pre连接free(cur);break;}//循环节完成pre = cur;if (n == 0)//还有整除{cur->next = NULL;break;}else{cur->next = (NODE*)malloc(sizeof(NODE));cur = cur->next;}}}}

——2022.9.25