输入a,b两个整数求其商的循环节。
分析：高精度，以数组代替小数位。根据抽屉原则，a/b的余数只能是0~b-1所以计算b+1次必定有余数重复，再进行10*n/m重复的余数之后的余数必定与之前的对应相等。开数组将余数和商保存输出即可。另开数组记录余数是否出现过。
#include&iostream&//抽屉原则
#include&cstring&
int main()
int sh[3003],yu[3003],mark[3003];//sh用来记录商，yu记录余数，mark记录余数出现的位置。
int n,m,t;
while(cin&&n&&m)
int count=0;
memset(sh,0,sizeof(sh));
memset(mark,0,sizeof(mark));
sh[count++]=n/m;
while(n&&!mark[n])
//cout&&'.';
yu[count]=n;
sh[count++]=(10*n)/m;
cout&&sh[0]&&'.';
for(int i=1;i&count&&i&=50;i++)
if(n&&yu[i]==n)
cout&&'(';
cout&&sh[i];
cout&&"(0";
if(count&50)
cout&&"...";
cout&&')'&&
int ans=count-mark[n];
cout&&"循环节长度为:"&&ans&&
阅读(...) 评论()他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)UVa Online Judge（16）
Description
The decimal expansion of the fraction 1/33 is&&, where the&&is
used to indicate that the cycle 03 repeats indefinitely with no intervening digits. In fact, the decimal expansion of every rational number (fraction) has a repeating cycle as opposed to decimal expansions of irrational numbers, which have no such repeating
Examples of decimal expansions of rational numbers and their repeating cycles are shown below. Here, we use parentheses to enclose the repeating cycle rather than place a bar over the cycle.
Write a program that reads numerators and denominators of fractions and determines their repeating cycles.
For the purposes of this problem, define a repeating cycle of a fraction to be the first minimal length string of digits to the right of the decimal that repeats indefinitely with no intervening digits. Thus
for example, the repeating cycle of the fraction 1/250 is 0, which begins at position 4 (as opposed to 0 which begins at positions 1 or 2 and as opposed to 00 which begins at positions 1 or 4).
Each line of the input file consists of an integer numerator, which is nonnegative, followed by an integer denominator, which is positive. None of the input integers exceeds 3000. End-of-file indicates the end
For each line of input, print the fraction, its decimal expansion through the first occurrence of the cycle to the right of the decimal or 50 decimal places (whichever comes first), and the length of the entire
repeating cycle.
In writing the decimal expansion, enclose the repeating cycle in parentheses when possible. If the entire repeating cycle does not occur within the first 50 places, place a left parenthesis where the cycle begins
- it will begin within the first 50 places - and place ``...)& after the 50th digit.
Print a blank line after every test case.
76/25 = 3.04(0)
1 = number of digits in repeating cycle
5/43 = 0.()
21 = number of digits in repeating cycle
1/397 = 0.(92...)
99 = number of digits in repeating cycle
刚看到这个题的时候觉得好难好麻烦啊又是模拟，然后就把这个专题剩下的题都做完了再做这一个。。
研究了一下除法的特点，发现在计算小数部分的时候，如果某次得到的余数在之前出现过，那么这个小数就开始循环了，觉得挺简单，但是做起来发现没那么容易，因为没考虑周全，这个题也耽误了不少时间。
一开始直接用一个变量存储整数部分，然后用一个数组来存小数部分，把取整后剩下的部分作为后面求解的原始数，进行模拟运算，但WA后发现这对于整除的数不适用，再加上自己括号控制的不好，位置都会加错= =，最后整理了一下思路，重新敲了一遍，用了一个标记数组（因为看到了两数小于3000，所以余数的范围也不会超过它的，开数组变成了可能~），用于快速查询此余数是否在之前得出并且得到他的位置，然后循环模拟，当出现被标记且不为0的时候，就可以跳出了，得到循环小数的起始位置和终止位置，然后在合适的位置安排括号就可以了，另外注意超过50为要打...控制一下就好，代码如下：
#include &iostream&
#include &algorithm&
#include &cstring&
const int MAX=3003;
int decimal[MAX]; //存储商数
int remainder[MAX]; //存储余数
int mark[MAX*10]; //标记数组
int main()
ios::sync_with_stdio(false);
int quotient,start,ends,a,b,i;
while(cin&&a&&b)
memset(mark,-1,sizeof(mark)); //初始化为无标记
decimal[0]=quotient=a/b; //将整数部分单独拿出用于输入，并存到数组里用于模拟计算
mark[remainder[0]=a]=0;
//第0个余数为被除数，标记（位置）0
for(i=1;i++)
remainder[i]=(remainder[i-1]-b*decimal[i-1])*10; //模拟除法，列一个除法竖式验算一下就明了了
decimal[i]=remainder[i]/b;
if((start=mark[remainder[i]])&0) //当所得余数已经被标记并且不是第0个，说明开始循环了，将这个位置赋给start并跳出
mark[remainder[i]]=i; //将余数做上标记
cout&&a&&&/&&&b&&& = &&&quotient&&&.&;
for(ends=i,i=1;i&i++)
//到start之前输出不循环的那部分小数
cout&&decimal[i];
for(cout&&&(&,i=i&cout&&decimal[i],i++) //对循环小数的输出控制
cout&&&...&;
cout&&&)&&&endl&&&
&&&ends-start&&& = &&&&number of digits in repeating cycle&&&endl&&
访问：50511次
积分：1506
排名：千里之外
原创：104篇
(14)(7)(1)(1)(4)(1)(1)(12)(2)(1)(49)(13)下次自动登录
现在的位置:
& 综合 & 正文
UVa 202 Repeating Decimals（循环小数）
UVa 202 Repeating Decimals（循环小数）
题目名称：循环小数
题目描述：
输入整数a和b a大于等于0小于等于3000,b大于等于1小于等于3000,输出a/b的循环小数表示以及循环节长度。如果循环周期大于50,只显示50位，之后的全部用……表示
题目分析：
①所谓的循环小数，也就是我们理解的当每步作除法时候，会出现了重复的商，那个循环小数的周期肯定就在两个重复的商之间。
②现在就转化为类似于找周期的问题了，找重复出现的商，我们最常见想到的办法就是记录所有的商，每算出一个新的商，之后就顺序查找看该商是否出现过，这就比较复杂了，复杂度为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[]中，所以每次余数对应三个数组的值分别问商、计算次数、是否存在的。
===============================================================================参考代码：
#include &stdio.h&
#include &string.h&
#define maxn 100
#define display_limit 50
#define max_INT 10000
int digits[maxn];
int reminder_exist[max_INT];
int reminder_pos[max_INT];
int main()
int numerator,denominator,quotient,
while(scanf("%d%d", &numerator, &denominator) != EOF && denominator)
//初始化数组和商的整数部分
int original_numerator =
memset(reminder_exist, 0, sizeof(reminder_exist));
memset(reminder_pos, 0, sizeof(reminder_pos));
quotient = numerator/
reminder = numerator%
int integer =
//找出循环
int found_cycle = 0;
int cycle_pos =
int cycle_len = 0;
int i = 0;
for(i = 0; i &= i++)
if(reminder_exist[reminder])
cycle_pos = reminder_pos[reminder];
cycle_len = i - cycle_
reminder_exist[reminder] = 1;
reminder_pos[reminder] =
numerator = reminder * 10;
quotient = numerator/
reminder = numerator%
digits[i] =
printf("%d/%d = %d.(",original_numerator, denominator, integer);
if(i &= display_limit)
for(int j = cycle_ j & j++)
printf("%d", digits[j]);
for(int j = cycle_ j & display_j++)
printf("%d", digits[j]);
printf("...");
printf(")\n");
printf("%d = number of digits in repeating cycle\n", cycle_len);
To_捭阖_youth
【上篇】【下篇】他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)