USACO Training Section 2.4 Fractions to Decimals

英文原题  中文题译 

 

大意：将有理数表示为小数循环数，如：

1/3     =  0.(3)
22/5    =  4.4
1/7     =  0.(142857)
2/2     =  1.0
3/8     =  0.375
45/56   =  0.803(571428)

本身很简单，注意小数循环不是靠字符串的比较，而是除到某位时的商和余数比较，如果商和余数相同，则开始重复。不过在做的时候犯了不少错，立此存照：

1.一开始无法在OJ上通过编译，报错itoa找不到，include了stdlib.h之后依然报错，改成_itoa还是报错，无奈上网查了查，原来GNU GCC不支持此函数，必须用sprintf。

2.同样是编译器之间的差别，以前常遇到的是VS2008会自动include如memory.h，而在GCC中不会。这里，strlen函数同样在VS中不用特别引用头文件，而在GCC中需要string.h。

3.2/2=2.0，一开始没注意到这个，输出2，WA。

4.输出每行76个字符，必须把换行也算进去，WA一次。

5.此题和POJ3720类似，3720是要计算1/1,....1/n的循环小数表示中某个数字的出现次数。之前写过code，于是这里就基本重写了一回。结果超时。原因：原来的实现中逐个比较商和余数，为n^2复杂度。改成位置标识数组，就过了。

6.声明标识数组时，在GNU中可以放在函数内部作为局部变量，而在VS2008下不行，一运行就crash。

最后，之前用vector，没去估计最长表示，其实是商*余数，也就是10*quot。所以，用普通数组完全可行。

 

/*
ID: blackco3
TASK: fracdec
LANG: C++
*/
#include <iostream>
#include <string.h>
#include <memory.h>
#include <vector>
using namespace std;

#define _max_ 100000
struct t_dpos {
	int quot, remain ;
	t_dpos(int a,int b):quot(a),remain(b){};
};
vector<t_dpos> record ;
void out_char( char a, int &cp ) {
	cout << a ;
	if( (cp++)==75 )
		cout << endl , cp=0;
}
int pos[10][_max_]; /* if I use it in local function , VS2008 just not run into error  */
int main() {
	freopen("fracdec.in", "r", stdin);
	freopen("fracdec.out", "w", stdout);
	int nume, deno ;
	cin >> nume >> deno ;
	if( !(nume % deno ) ){
		cout << nume/deno << ".0" << endl ;
		return 0 ;
	}
	int repeat_pos, is_repeat=false ;
	memset( pos, 0xff, sizeof(pos) );
	for(register int remain=(nume%deno)*10, quot=0 ; remain ; remain*=10){
		quot = remain / deno , remain =remain % deno;
		if( pos[quot][remain]>=0 ){
			is_repeat=true, repeat_pos=pos[quot][remain] ;
			break ;
		} else
			pos[quot][remain]=record.size(), record.push_back( t_dpos(quot,remain) );
	}
	char int_str[77];
	sprintf( int_str, "%d.", nume/deno );
	cout << int_str ;
	int cp=strlen(int_str);
	for(int j=0; j<record.size(); j++){
		if(is_repeat && j==repeat_pos)
			out_char( '(', cp );
		out_char( '0'+record[j].quot, cp ) ;
	}
	if( is_repeat )
		cout << ')' << endl ;
	else if( cp!=75 )
		cout << endl ;
	return 0;
}