![算法习题---3.08循环小数（UVa202）]( "算法习题---3.08循环小数（UVa202）")
一：题目
输入整数a和b（<=a<=,<=b<=),输出a/b的循环小数表示以及循环节长度。
例如，a=,b=，小数表示为0.（），循环字节长度为21
当循环节长度超过50时，后面使用...代替，不进行输出后面部分
（一）样例输入
（二）样例输出
/ = 3.04()
= number of digits in repeating cycle
/ = .()
= number of digits in repeating cycle
/ = .(...)
= number of digits in repeating cycle
二：题目分析
（一）余数用作判断循环节的依据：（循环节长度大小不会超过余数大小，原因如下：）
/-->/=...
/-->/=...4出现两次4，所以一定会出现循环节
/-->/=...4出现三次4，所以循环节就在二三次之间（即商6）
（二）同时也要记录商，用于记录循环节
若是除数为P,则余数为0->P-1；所以在P次之间一定会出现两个相同余数 //（一中原因）
所以我们再记录一次余数，当出现某个余数出现为3次，那么循环节在两个余数位置中间
由于商数组和余数数组对应，所以可以轻松找到循环节
（三）商数组和余数数组大小
余数数组大小应该为除数大小 //余数只需要除数大小，用于记录余数出现次数
商数组大小应该为除数大小的两倍 //商用于记录对应余数中的商值，由于每一个余数必须出现3次，所以我们记录的商必须足够长，足以支持余数次数到达3
例：
其中0<=a<=,<=b<=--->
所以余数数组不会超过3000 商数组大小不超过6000
注：上面的商和余数数组只记录小数点后的值，不记录整数值
三：代码分析（使用76/25 ，1/6 ，5/43分析）
（一）处理整数部分：只剩下会出现小数部分的被除数进行下一步处理
//开始处理数据
//1.获取整数
//先记录整数：可以在记录时直接输出，节省篇幅
printf("%d/%d = ", a, b);
if (!(a / b))
printf("");
else
while (a / b)
{
printf("%d", a / b);
a %= b;
}
printf(".");
（1）76/25
（2）1/6
（3）5/43
（二）获取商数组和余数数组
//2.开始记录商和余数
i = ;
while () //例如：1/6
{
//记录商和余数
res[i] = a * 10 / b; //10/6=1 //1.记录商
rem[a * 10 % b]++; //10%6=4 //2.记录对应余数位置出现次数
//注意两次和三次都是只记录一次即可
if (rem[a * 10 % b] == 2&&!two_flag) //3.若是出现两次，则开始进行记录 只记录第一个出现两次的余数
{
r_s = i;
two_flag = ;
}
if (rem[a * 10 % b] == 3) //4.若是出现3次，则确定了循环节位置，直接跳出
{
r_e = i;
break;
}
//处理被除数
a = a * % b; //a = 4
i++;
}
（1）76/25
/=... 0 1 第一个为商下标，第二个为余数次数
/=... 1 1
/=... 2 2 余数出现两次时的商0和出现一次时的商4不一致
/=... 3 3
（2）1/6
/=... 0 1 第一个为商下标，第二个为余数次数
/=... 1 2 余数出现两次时的商6和出现一次时的商1不一致
/=... 2 3
（3）5/43
/=... 0 1
/=...
...
.....=... 21 2 余数出现两次时的商和出现一次时的商一致
...
.....=... 42 3
（三）：进行数据输出
注意记录数据时要区分0.() 3.04() 和0.(....)
不同之处在于循环节是不是从小数第一位开始
处理原则在于看1，2两次余数相同时，商是否一致（上面案例）
int rep_count = r_s;
if (res[r_s] != res[2 * r_s - r_e]) //若是余数第一次和第二次对应的商值不一样，则加一
rep_count++;
for (j = ; j <rep_count ;j++) //注意，先看下面注释，可以知道，真正循环节结束在我们获取的第二个相同余数位置-->即r_s
{
if (j == * r_s - r_e && rep_count==r_s) //注意这里：不是j-r_s
printf("(");
else if (j == * r_s - r_e+&&rep_count==r_s+) //遇到循环节不是从小数点后开始，则向后一位
printf("(");
printf("%d", res[j]);
if (j +r_e- *r_s == ) //不是j-r_s -->因为我们虽然确定r_s到r_e时一个循环节，但是r_s是第二个相同余数开始，r_e是第三个余数开始
{ //4 4 4--->r_s是第二个开始，r_e是第三个开始，但是真的循环节是从第一个4到第二个4
printf("...");
break;
}
}
printf(")\n");
printf(" %d = number of digits in repeating cycle\n", r_e - r_s);
四：代码实现
void test33()
{
int a, b;
int zs[]; //存放整数，例如结果10.13161616，这里用于存放10
//由于程序变更，后面没有用到zs，但是为了便于理解，留在这
int res[MAX_REP]; //存放商
int rem[MAX_REP]; //存放余数
int two_flag; //注意两次和三次都是只记录一次即可,但是由于三次直接break，所以不做标志
int i, j;
int r_s, r_e; //循环节开始，循环节结束
FILE* fi = freopen("data2.in", "r", stdin);
freopen("data2.out", "w", stdout);
while (!feof(fi))
{
scanf("%d", &a);
scanf("%d", &b);
memset(zs, , sizeof(zs));
memset(res, , sizeof(res));
memset(rem, , sizeof(rem));
two_flag = ;
//开始处理数据
//1.获取整数
//先记录整数：可以在记录时直接输出，节省篇幅
printf("%d/%d = ", a, b);
if (!(a / b))
printf("");
else
while (a / b)
{
printf("%d", a / b);
a %= b;
}
printf(".");
//2.开始记录商和余数
i = ;
while () //例如：1/6
{
//记录商和余数
res[i] = a * / b; //10/6=1
rem[a * % b]++; //10%6=4
//注意两次和三次都是只记录一次即可
if (rem[a * % b] == &&!two_flag) //若是出现两次，则开始进行记录
{
r_s = i;
two_flag = ;
}
if (rem[a * % b] == )
{
r_e = i;
break;
}
//处理被除数
a = a * % b; //a = 4
i++;
}
//开始记录数据
//注意记录数据时要区分0.1(6) 3.04(0) 和0.(11....)
//不同之处在于循环节是不是从小数第一位开始
//处理原则在于看1，2两次余数相同时，商是否一致
int rep_count = r_s;
if (res[r_s] != res[ * r_s - r_e])
rep_count++;
for (j = ; j <rep_count ;j++) //注意，先看下面注释，可以知道，真正循环节结束在我们获取的第二个相同余数位置-->即r_s
{
if (j == * r_s - r_e && rep_count==r_s) //注意这里：不是j-r_s
printf("(");
else if (j == * r_s - r_e+&&rep_count==r_s+) //遇到循环节不是从小数点后开始，则向后一位
printf("(");
printf("%d", res[j]);
if (j +r_e- *r_s == ) //不是j-r_s -->因为我们虽然确定r_s到r_e时一个循环节，但是r_s是第二个相同余数开始，r_e是第三个余数开始
{ //4 4 4--->r_s是第二个开始，r_e是第三个开始，但是真的循环节是从第一个4到第二个4
printf("...");
break;
}
}
printf(")\n");
printf(" %d = number of digits in repeating cycle\n", r_e - r_s);
}
freopen("CON", "r", stdin);
freopen("CON", "w", stdout);
}
