UVA 202

在这里插入图片描述在这里插入图片描述

题目大意:

多组输入,每组数输入a b两个数,要求模拟循环节的位数,每个案例有两行输出,第一行输出a/b的值,循环节用()表示,如果循环节>50位,则用…代替,第二行则输出循环节的长度。

解题思路:

这道题一开始真的没思路…想到用数组模拟但是不知道循环节怎么求,直到看到了一句话:如果被除数在前面出现过了,那么一定循环。可以先输出整数部分,再去模拟数部分,整数部分很简单:直接a/b就可以了,然后a%=b,代表第一次已经除过了。之后是小数部分:先输出不循环的部分,然后再输出循环节。

  • 对于循环节:开一个标记数组,下标是被除数,里面存放的值是该数第一次出现的位置,再开一个答案数组ans,里面存放每次除完的结果,然后我们模拟除法的过程,即:更新一下被除数的位置vis[a]=cnt(为什么cnt后面会提到),a先*10,之后去/b,ans[cnt++]=a/b,然后a%=b,表示这次除完了,如果vis[a]!=0,就表示这个被除数出现过了,退出循环。
  • 对于循环节的长度:假设小数后面是 .12356785678,cnt是存放小数的位置,如果遇到了被除数相同的情况:即到了第二个5的位置,cnt==8,但是会退出循环,而此时vis[5]的值是4 ,用cnt-vis[a] 8-4 == 4 ,就可以得出循环节的长度了。
  • PS:要输出循环节前面的小数,只要输出vis[a]之前的数就可以了,因为vis[a]记录的是第一个循环的数出现的位置,那么他之前的肯定就是不循环的了。AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int vis[50000],ans[50000];
int main()
{
	int a,b;
	while(cin>>a>>b)
	{
		memset(vis,0,sizeof vis);
		printf("%d/%d = %d.",a,b,a/b);
		a%=b;
		int cnt=1;
		while(!vis[a])//被除数出现过则退出
		{
			vis[a]=cnt;//记录该数第一次出现的位置
			a*=10;
			ans[cnt++]=a/b;//记录每次的答案
			a%=b;
		}
		for(int i=1;i<vis[a];i++)//vis【a】之前即为不循环的位数
		  cout<<ans[i];
		cout<<"(";
		int ans1=cnt-vis[a];
		if(ans1>50)//只要输出前50位就可以
		  cnt=51;
		for(int i=vis[a];i<cnt;i++)
		  cout<<ans[i];
		if(ans1>50)
		  cout<<"...";
		cout<<")"<<endl;
		printf("   %d = number of digits in repeating cycle
",ans1);
		cout<<endl;
	}
	return 0;
}
原文地址:https://www.cnblogs.com/Hayasaka/p/14294230.html