本文共 2855 字，大约阅读时间需要 9 分钟。
题目名称：循环小数
题目描述：
输入整数a和b a大于等于0小于等于3000,b大于等于1小于等于3000,输出a/b的循环小数表示以及循环节长度。如果循环周期大于50,只显示50位，之后的全部用……表示
样例：
Alt text
题目分析： ①所谓的循环小数，也就是我们理解的当每步作除法时候，会出现了重复的商，那个循环小数的周期肯定就在两个重复的商之间。 ②现在就转化为类似于找周期的问题了，找重复出现的商，我们最常见想到的办法就是记录所有的商，每算出一个新的商，之后就顺序查找看该商是否出现过，这就比较复杂了，复杂度为O(n^2) ③改进方法就是我们可以考虑用一个数组记录某个商是否出现过，这样来做复杂度就为O(n) ③我们需要设置的变量 输入：分子numerator 分母denominator 商 quotient 商的整数部分 integer 商的小数部分 digits[] 余数是否存在 reminder_exist[] 余数存在的位置 reminder_pos 商是否存在循环 found_cycle 商的小数部分开始循环的位置 cycle_pos 循环的长度 cycle_len 循环长度的限制 display_limit算法思路
a）首先我们要表示商的小数点左边的部分，并且由于分子一直在变化，所以我们要设置一个新的变量保存下初始的分子，方便之后的输出
b）查找循环，由简单的数学知识可知，如果某两步计算的余数相等，那么他们之间的这些计算就是属于我们的循环小数了，所以我们需要就是找每步计算余数相等的，我们要知道他们分别的位置，这里我们采用两个数组来区分一个是reminder_exist[]这里保持，哪个余数存在，对应的值就为1，所以我们可以通过检测这个数组的值来找循环，之后因为我们还需要之前第一次出现这个循环的位置，所以我们还需要有一个数组保存第几次运算出现哪个余数。之后再用第二次出现计算次数减去第一次出现的次数，我们就可以得到循环节的长度了。而且每一步计算得到的商需要保存在一个数组中，这里命名为digits
c）最后再比较下计算最后一次与50进行比较，来按要求输出。
学习笔记：本题最核心的算法在于，我们怎么去找出循环小数的循环体个数了，循环体初始位置和最后位置。
通过数学知识可以知道找余数相同的时候，每次计算得到的余数放在一个数组中，且数组对于位置为1，代表存在这个余数，之后再通过一个循环找这个位置为1的时刻，这就是余数相同的时候，并且用一个数组保存计算的次数，取每次计算得到的商保存在digits[]中，所以每次余数对应三个数组的值分别问商、计算次数、是否存在的。
//.c#include#include #define maxn 100#define display_limit 50#define max_INT 10000int digits[maxn];int reminder_exist[max_INT];int reminder_pos[max_INT];int main(){ int numerator,denominator,quotient,reminder; while(scanf("%d%d", &numerator, &denominator) != EOF && denominator) { //初始化数组和商的整数部分 int original_numerator = numerator; memset(reminder_exist, 0, sizeof(reminder_exist)); memset(reminder_pos, 0, sizeof(reminder_pos)); quotient = numerator/denominator; reminder = numerator%denominator; int integer = quotient; //找出循环 int found_cycle = 0; int cycle_pos = maxn; int cycle_len = 0; int i = 0; for(i = 0; i <= maxn; i++) { if(reminder_exist[reminder]) { cycle_pos = reminder_pos[reminder]; cycle_len = i - cycle_pos; break; } else { reminder_exist[reminder] = 1; reminder_pos[reminder] = i; } numerator = reminder * 10; quotient = numerator/denominator; reminder = numerator%denominator; digits[i] = quotient; } //输出 printf("%d/%d = %d.(",original_numerator, denominator, integer); if(i <= display_limit) { for(int j = cycle_pos; j < i; j++) { printf("%d", digits[j]); } } else { for(int j = cycle_pos; j < display_limit;j++) printf("%d", digits[j]); printf("..."); } printf(")\n"); printf("%d = number of digits in repeating cycle\n", cycle_len); } return 0;}
转载地址：http://kugsi.baihongyu.com/