现在的位置: 首页 > 综合 > 正文

UVa 202 大数除法

2017年11月16日 ⁄ 综合 ⁄ 共 874字 ⁄ 字号 评论关闭

背景:1_WA:忘了每个答案之间有一个空白行!2_WA:没看见等号左右两边都有空格!!!!!!!!

思路:整数和小数分开来求,整数部分直接用整型除法,小数部分:分子=(分子%分母)*10.并且把每个分子储存在str[0]中,当出现已经出现过的分子时,小数部分开始循环!

学习:

1.巢鸽原理(抽屉原理,狄利克雷原则):

 简单的描述:如果有n个笼子,n+1只鸽子居住,则至少有一个笼子有两只鸽子。

一般化的描述(用高斯函数来叙述):将n个元素分到m个集合中,至少有一个集合中元素个数大于等于[(n-1)/m]+1 。

对于本题,a%b最多有b-1个情况,根据巢鸽原理,循环节数小于等于b-1.

#include<stdio.h>
int str[2][10000];  
int main(void){
	  int a,b,intger;
	  while(scanf("%d %d",&a,&b)!=EOF){
	  	int count=0,start,aa=a;
	  	intger=a/b;
	  	a=a%b;
	  	while(1){
	  		a*=10;
	  		for(int i=0;i < count;i++){
	  			if(a==str[0][i]){
	  				start=i;
            goto l1;
	  			}
	  		}
	  		str[0][count]=a;
	  		str[1][count++]=a/b;
	  		a=a%b;
	  	}
l1:   printf("%d/%d = %d.",aa,b,intger);
      for(int i=0;i < start;i++){
      	printf("%d",str[1][i]);
      }       
      if(count<=50){
      	printf("(");
      	for(int i=start;i < count;i++){
      		printf("%d",str[1][i]);
      	}
      	printf(")\n");
      }else{
      	printf("(");
      	for(int i=start;i < start+50;i++){
      		printf("%d",str[1][i]);
      	}
      	printf("...)\n");
      }
      printf("   %d = number of digits in repeating cycle\n\n",count-start);
	  }
	  return 0;
} 

抱歉!评论已关闭.