蓝桥杯 历届试题 小数第n位

问题描述

我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。

输入格式

一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）

输出格式

一行3位数字，表示：a除以b，小数后第n位开始的3位数字。

样例输入1

1 8 1

样例输出1

125

样例输入2

1 8 3

样例输出2

500

样例输入3

282866 999000 6

样例输出3

914

解题思路

为了输出除法的每一位，需要做一下递推，假设被除数和除数分别是a和b，则a/b是他们的整数部分，之后令a = (a%b)*10，可得到下一个小数位的被除数，a/b为该位的小数位，依次类推。

开一个map，记录每次的被除数及其位置，如果要记录的被除数已经存在，则可判断这是一个无限循环小数。记录无限循环小数时可使用start记录循环开始位置，len记录一个循环的长度，当位置index大于等于start时，index位置的小数位等于start+(index-start)%len位置的小数位。

#include<iostream>
#include<vector>
#include<map>
using namespace std;
//开始循环的位置，循环长度，当前位置
int start = -1,len = -1,Count = 1;
long long a,b,n;
map<long long,int> achieved;
vector<int> numbers;
int main(){
	scanf("%lld %lld %lld",&a,&b,&n);
	int temp = a/b;
	a = (a%b)*10;
	numbers.push_back(temp);
	while(a!=0){
		if(achieved.count(a)!=0){
			start = achieved[a];
			len = Count-start;
			break;
		}
		achieved[a] = Count++;
		temp = a/b;
		numbers.push_back(temp);
		a = (a%b)*10;
	}
	//有限小数 
	if(start == -1){
		for(int i = n;i<=n+2;i++){
			if(i<numbers.size()) printf("%d",numbers[i]);
			else printf("0");
		}
	}else{//无限循环小数 
		for(int i = n;i<=n+2;i++){
			if(i<start) printf("%d",numbers[i]);
			else printf("%d",numbers[start+(i-start)%len]);
		}
	}
	return 0;
}