循环小数
时间限制：3000 ms | 内存限制：65535 KB
难度：1
- 描述
-
我们可爱的 c小加 近段儿正在潜心研究数学，当他学习到循环小数这一部分时不是太明白循环体是什么意思（比如说3.23232323的循环体是23、2323、23232323），假设我们现在的循环小数都是严格循环的并且有限的，也就是说不出现2.16666666（循环体为6，长度为1）的情况，只有123123这样的循环出现。给他一个小数，他需要找出最小循环体的长度、循环体和循环的次数，请你帮他解决这个问题。
- 输入
- 输入的第一行是t，表示有t组测试数据（t<=100）。
随后的t行，每行都是一个小于10并且大于0的小数（总长度<=200）。 - 输出
- 对每组输入，输出结果单独成行，输出最小循环体的长度、循环体和出现循环的次数。
- 样例输入
-
3 8.6987698769876987 0.666 5.1
- 样例输出
-
4 6987 4 1 6 3 1 1 1
看算法看的头疼，水一道#include<stdio.h> #include<string.h> int f[210]; int len,len1; char str[210],s[210]; char put[210]; void getmap() { int i,j,k; memset(s,' ',sizeof(s)); scanf("%s",str); len=strlen(str); for(i=0;i<len;i++) { if(str[i]=='.') { k=i; break; } } j=0; for(i=k+1;i<len;i++) s[j++]=str[i]; len1=strlen(s); } void getfail() { int i,j; f[0]=f[1]=0; for(i=1;i<len1;i++) { j=f[i]; while(j&&s[i]!=s[j]) j=f[j]; f[i+1]=s[i]==s[j]?j+1:0; } } void kmp() { int i,j,length,times; int k; length=len1-f[len1]; times=len1/(len1-f[len1]); j=0; for(i=0;i<len1;i++) { while(j&&s[i]!=s[j]) j=f[j]; if(s[i]==s[j]) j++; if(j==length) { k=i-length+1;//循环体出现位置 break; } } memset(put,' ',sizeof(put)); j=0; for(i=k;i<length;i++) put[j++]=s[i]; printf("%d %s %d ",length,put,times); } int main() { int t; scanf("%d",&t); while(t--) { getmap(); getfail(); kmp(); } return 0; }