HDU (1250 Hat's Fibonacci 高精度递加)

题目的意思:就是说s[1]=1,s[2]=1,s[3]=1,s[4]=1; 其他的都用统一方程求 s [ n ]=  s[n-1 ] +s [n -2 ] + s[ n-3 ] +s [ n-4];

题目分析:

其实没什么算法,就是用二维数组里的每一行 模拟每个一个大数,这一行里的第一个数就是 实际意义上的一个 “ 位 ”! 可以是以8位为一个“位”

也可以以其他位数为一“ 位 ”,这样做是为了压缩内存,也是位了能够高效模拟! 其他的跟我们 普通的加法是一样的!从左往右,把前面四行的对应的列上的值都加到 我这行的对应的列上来! 最后一个循环考虑一下,进位之类的  所以您别 一看就慌了 毕竟每个人都是由 不会到会的  如果有不懂的 您可以密我 我更详细的跟您解说{^ _ ^}

代码如下:

#include<iostream>
#include<cstring>
#include<cstdio>
int s[10000][356]={0};
using namespace std;
int solve(){
	int i,j;
	s[1][1]=1;
	s[2][1]=1;
	s[3][1]=1;
	s[4][1]=1;
	for(i=5;i<10000;i++){
		for(j=1;j<=350;j++)
			s[i][j]+=s[i-1][j]+s[i-2][j]+s[i-3][j]+s[i-4][j];//记得这里别把j跟I弄混淆了,我第一次为这个小错误
            //找了点时间,嘿嘿
		for(j=1;j<=350;j++){
			if(s[i][j]>100000000){
				s[i][j+1]+=s[i][j]/100000000;
				s[i][j]=s[i][j]%100000000;
			}	
		}		
	}
	return 0;
}
int main(){
	int cas,i,j,n;
	solve();
	while(scanf("%d",&n)!=EOF){
		for(i=350;i>=1;i--){
			if(s[n][i]!=0)
				break;
		}
		printf("%d",s[n][i]);
		for(j=i-1;j>=1;j--)
			printf("%08d",s[n][j]);
		printf("\n");
	}
	return 0;
}

 

HDU 1018(Big Number 求N!的位数,各种求法!)

题目:

Problem Description
In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number, you have to determine the number of digits in the factorial of the number.
 
Input
Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 ≤ n ≤ 107 on each line.
 
Output

            The output contains the number of digits in the factorial of the integers appearing in the input.
 
Sample Input
2
10
20
 
Sample Output
7
19
 

题目分析:

第一种做法:

N!=1*2*3....*n

求位数我们一般用对一个数取对数就可以了 ,

log10(n!)=log10(1)+ log10(2) +log10(3)...+log10(n);

所以循环求和就可以了!

但是这里注意一点 结果要加1!因为这里计算出来的 log10(1)=0  !

所以结果要加上这个误差 ‘1’

第二种做法:

这就是我最近研究的斯特林数,第一类斯特林数就可以做这个!

补充一点,斯特林数能够做一切关于阶乘有关的大数运算 要深入学习!

这里给出递归公式:

log10(n!)=1.0/2*log10(2*pi*n)+n*log10(n/e)

然后我就附上代码了;

两种做法都有!

#include<iostream>
#include<cmath>
#include<cstdio>
#define e 2.7182818284590452354
#define pi acos(-1)
using namespace std;
int main(){
	int cas,ans,n;
	cin>>cas;
	while(cas--){
		scanf("%d",&n);
		ans=(int)(1.0/2.0*log(2.0*pi*n)/log(10.0)+1.0*n*log(n/e)/log(10.0)+1);
		printf("%d\n",ans);
	}
	return 0;
}
#include<iostream>
#include<cmath>
#include<cstdio>
#define e 2.7182818284590452354
#define pi acos(-1)
using namespace std;
int main(){
	int cas,ans,i,n;
	double sum;
	cin>>cas;
	while(cas--){
		scanf("%d",&n);
		sum=1;
		for(i=1;i<=n;i++)
		 	sum+=log10(i);
		printf("%d\n",((int)sum));
	}
	return 0;
}

 

HDU 3625( Examining the Rooms 斯特林数的应用 )

题目:

就是给你N个房间,然后每个房间1把钥匙,你最初手里没有任何钥匙,要靠破门而入!这里只有第一个房间不能破门进去,其他都可以,

给你房间数N,和最多能破门的个数,让你求能全部把房间打开的概率!

题目分析:

又是是我的第一次啊!受教育了?有木有?这种题目是斯特林第一类数的应用,虽然很裸,但是很经典啊 !

首先这题其实让我们求的是给 N个元素,让我们求K个环排列的 方法数。

斯特林第一类数的第推公式:

S(N,0)=0;

S(N,N)=1;

S(0,0)=0;

S(N,K)=S(N-1,K-1)+S(N-1,K)*(N-1);

这个公式的意思是:

当前N-1个数构成K-1 个环的时候,加入第N个 ,N只能构成单环!---S(N-1,K-1)

如果N-1个数构成K个环的时候,加入第N个,N可以任意加入,N-1内的一个环里,所以是--(N-1)*S(N-1,K)

这个题目里,因为不能破坏第1个门:

所以

S(N,K)-S(N-1,K-1)才是能算构成K个环的方法数!就是去掉1自己成环的情况!

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=20;
long long f[25],stir[25][25];
int solve(){
	int i,j;
	f[0]=1;
	for(i=1;i<=maxn;i++)
		f[i]=i*f[i-1];
            //因为N有N!种排列顺序,这作为总数
        //计算概率
	for(i=1;i<=maxn;i++)
		stir[i][0]=0;
	stir[1][1]=1;
	for(i=1;i<=maxn;i++)
		for(j=1;j<=i;j++){
			if(i==j)
				stir[i][j]=1;
			else
				stir[i][j]=stir[i-1][j-1]+(i-1)*stir[i-1][j];
		}
	for(i=1;i<=maxn;i++)
		for(j=1;j<=maxn;j++)
			if(stir[i][j]<0)
				stir[i][j]=-stir[i][j];
	return 0;
}
int main(){
	int cas,n,i,k;
	long long sum;
	solve();
	scanf("%d",&cas);
	while(cas--){
		scanf("%d %d",&n,&k);
		sum=0;
		for(i=1;i<=k;i++)
			sum+=stir[n][i]-stir[n-1][i-1];
		printf("%.4lf\n",1.0*sum/f[n]);//因为写成printf("%.4lf\n",(double)sum/f[n]);
		//run time error! 下次一定记好了!
	}
	return 0;
}

 

HDU 1055(Number Sequence) 典型的找循环节的题目!

题目:

Problem Description
A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).
 

Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
 

Output

For each test case, print the value of f(n) on a single line.

题目分析:

这种题目第一次做,学会了 什么时候找循环节!因为这种题目,数据量那么大 ,肯定有循环节的!

这里我就是以找到与第1个跟第2个等的两个数作为一个循环节!因为每个数都是由前面两个数决定的!所以循环节要找到第一对 与第1个与第2个匹配的!

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int f[1009];
int main(){
	int a,b,n,i,c;
	f[1]=f[2]=1;
	 while(scanf("%d%d%d",&a,&b,&n),a || b || n){ 
		for(i=3;i<50;i++){
			f[i]=(a*f[i-1]+b*f[i-2])%7;
			if(f[i]==1&&f[i-1]==1)
				break;
		}
		c=i-2;
		n=n%c;
		if(n==0)
			printf("%d\n",f[c]);
		else
			printf("%d\n",f[n]);
	}
	return 0;
}

 

HDU 1290 2050 (切蛋糕 折线分平面--二维,三维 的分割区间问题)

题目:

Problem Description
或许你曾经牢骚满腹
或许你依然心怀忧伤
或许你近在咫尺
或许你我天各一方

对于每一个学子
母校
永远航行在
生命的海洋

今年是我们杭电建校五十周年,这是一个值得祝福的日子。我们该送给母校一个怎样的礼物呢?对于目前的大家来说,最好的礼物当然是省赛中的好成绩,我不能参赛,就送给学校一个DOOM III球形大蛋糕吧,这可是名牌,估计要花掉我半年的银子呢。

想象着正式校庆那一天,校长亲自操刀,把这个大蛋糕分给各地赶来祝贺的校友们,大家一定很高兴,呵呵,流口水了吧...

等一等,吃蛋糕之前先考大家一个问题:如果校长大人在蛋糕上切了N刀(校长刀法极好,每一刀都是一个绝对的平面),最多可以把这个球形蛋糕切成几块呢?

做不出这个题目,没有蛋糕吃的!
为-了-母-校-,为-了-蛋-糕-(不是为了DGMM,枫之羽最会浮想联翩...),加-油-!
 
Input
输入数据包含多个测试实例,每个实例占一行,每行包含一个整数n(1<=n<=1000),表示切的刀数。
 
Output
对于每组输入数据,请输出对应的蛋糕块数,每个测试实例输出一行。
 
Sample Input
1
2
3
 
Sample Output
2
4
8

这种题目有公式可以套的s[n] = (n^3 + 5n)/6 +1

文章最后会给出这一类问题的 模板公式,只需具体问题,待定系数去解就可以了 ,很方便

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int n;
	while(~scanf("%d",&n)){
		int ans=(n*n*n+5*n)/6+1;
		printf("%d\n",ans);
	}
	return 0;
}

2050题目:

 
 

折线分割平面

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5605    Accepted Submission(s): 4007



Problem Description
我们看到过很多直线分割平面的题目,今天的这个题目稍微有些变化,我们要求的是n条折线分割平面的最大数目。比如,一条折线可以将平面分成两部分,两条折线最多可以将平面分成7部分,具体如下所示。
 

Input
输入数据的第一行是一个整数C,表示测试实例的个数,然后是C 行数据,每行包含一个整数n(0<n<=10000),表示折线的数量。
 
 

Output
对于每个测试实例,请输出平面的最大分割数,每个实例的输出占一行。
 
 

Sample Input
2
1
2
 
Sample Output
2
7

这个题目的公式:s[n] = 2*n^2 - n +1;

代码:

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int cas,n;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d",&n);
		int ans=2*n*n-n+1;
		printf("%d\n",ans);
	}
	return 0;
}

总结:

其实这类题目都有模板公式的,只许具体问题,您带入几个解去求出各个系数就可以了!

 一般二维的是 a*n^2 +b *n +c

三维的是: a*n^3 + b* n^2 + c*n +d

具体问题带定系数法求出各个系数就OK了,不用想破脑筋找规律。。。。。。

HDU 1222(Wolf and Rabbit)约瑟夫最小公倍数问题

Problem Description
There is a hill with n holes around. The holes are signed from 0 to n-1.



A rabbit must hide in one of the holes. A wolf searches the rabbit in anticlockwise order. The first hole he get into is the one signed with 0. Then he will get into the hole every m holes. For example, m=2 and n=6, the wolf will get into the holes which are signed 0,2,4,0. If the rabbit hides in the hole which signed 1,3 or 5, she will survive. So we call these holes the safe holes.
 
Input
The input starts with a positive integer P which indicates the number of test cases. Then on the following P lines,each line consists 2 positive integer m and n(0<m,n<2147483648).
 
Output

            For each input m n, if safe holes exist, you should output "YES", else output "NO" in a single line.
 
Sample Input
2
1 2
2 2
 
Sample Output
NO
YES
 

题目分析:

假设步长是m 总长度是N, 这里首先我们计算出他们的周期,也就是最小公倍数,当过了这个周期,狼搜索的点肯定重复了!

因为狼每走一次肯定是搜索了一个点,搜索完n个点的时候,走的长度正好是这个周期,说明他没有重复的搜索了N个点!你可以在纸上画一下

其实不难理解!

代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
int gcd(int x,int y){
	int c;
	if(x<y){
		c=x;	x=y;
		y=c;
	}
	if(y==0)
		return x;
	else
		return gcd(y,x%y);
}
int main(){
	int cas,n,m;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d %d",&m,&n);
		printf(gcd(n,m)==1?"NO\n":"YES\n");
	}
	return 0;
}

 

HDU 1997(汉诺塔VII 思想很NB)

题目大意;

Problem Description
n个盘子的汉诺塔问题的最少移动次数是2^n-1,即在移动过程中会产生2^n个系列。由于发生错移产生的系列就增加了,这种错误是放错了柱子,并不会把大盘放到小盘上,即各柱子从下往上的大小仍保持如下关系 :
n=m+p+q
a1>a2>...>am
b1>b2>...>bp
c1>c2>...>cq
ai是A柱上的盘的盘号系列,bi是B柱上的盘的盘号系列, ci是C柱上的盘的盘号系列,最初目标是将A柱上的n个盘子移到C盘. 给出1个系列,判断它是否是在正确的移动中产生的系列.
例1:n=3
3
2
1
是正确的
例2:n=3
3
1
2
是不正确的。
注:对于例2如果目标是将A柱上的n个盘子移到B盘. 则是正确的.
 
Input
包含多组数据,首先输入T,表示有T组数据.每组数据4行,第1行N是盘子的数目N<=64.
后3行如下
m a1 a2 ...am
p b1 b2 ...bp
q c1 c2 ...cq
N=m+p+q,0<=m<=N,0<=p<=N,0<=q<=N,
 
Output

            对于每组数据,判断它是否是在正确的移动中产生的系列.正确输出true,否则false
 
Sample Input
6
3
1 3
1 2
1 1
3
1 3
1 1
1 2
6
3 6 5 4
1 1
2 3 2
6
3 6 5 4
2 3 2
1 1
3
1 3
1 2
1 1
20
2 20 17
2 19 18
16 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
 
Sample Output
true
false
false
false
true
true
 
题目分析:
             这个题目幸好只是判断他是不是最优化的,不然真的TBT了,我也是刚刚才能理解,网上解题报告几乎都没说什么思路,琢磨了好久~
其实
1) 最初我们要判断一下是不是已经完全放好了,这样就不用考虑是不是最优化了, 因为都已经放好了,肯定是最合法的! 或者说全部在A上,这是还没开始动作的一个状态,所以也是合法的!
2) 否则我们  要对每次状态的最大的那个进行判断,因为我们知道,汉诺塔最大的那个不可能停在B上,(假设 最初的时候都在A上,要移到C上去!),只可能在A或者C上面!如果是放在B上面,停止判断,直接断定他非法~这样我们得出了第二个判段依据!
3)如果最大的在A上面,我可以想到的是,他还没有放在C上,此时这个状态的上面一系列状态都是想把其他的放在B上,然后就可以把A放到C上了,所以我们在这里做出更新,因为他上面一系列动作都是想让A上面的除最大的外都放到B上面去,所以,我们这个时候往上考虑,对N-1进行 判断!这个时候动作的方向是A->B所以为了统一操作,我们得把B跟C互换!
4)如果最大的在C上面,这时候倒数第二大的不是放在B上就是C上,我们要把要把倒数第二大的以及其他的放在C上,这时候的动作方向是B—>C;所以把A跟B交换一下!
代码:
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int one[4],n[4],h[4][1000];
	int a,b,c,i,N;
	int cas,t;
	bool flag;	
	scanf("%d",&cas);
	while(cas--){
		a=1;	b=2;	c=3;
		one[a]=1,one[b]=1,one[c]=1;
		scanf("%d",&N);
		scanf("%d",&n[a]);
		for(i=one[a];i<=n[a];i++)
			scanf("%d",&h[a][i]);
		scanf("%d",&n[b]);
		for(i=one[b];i<=n[b];i++)
			scanf("%d",&h[b][i]);
		scanf("%d",&n[c]);
		for(i=one[c];i<=n[c];i++)
			scanf("%d",&h[c][i]);
		while(1){
			if(n[c]==N||n[a]==N){
				flag=true;
				break;
			}
			if(n[b]>0&&h[b][one[b]]==N){
				flag=false;
				break;
			}
			if(n[a]>0&&h[a][one[a]]==N){
				N--;
				n[a]--;
				one[a]++;
				t=b;	b=c;
				c=t;
				continue;
			}
			if(h[c][one[c]]==N&&n[c]>0){
				N--;
				n[c]--;
				one[c]++;
				t=b;	b=a;
				a=t;
				continue;
			}
		}
		if(flag)
			printf("true\n");
		else
			printf("false\n");
	}
	return 0;
}

 

 

HDU 1443( Joseph 约瑟夫问题 )


Problem Description
The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.
 

Input
The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.
 
Output
The output file will consist of separate lines containing m corresponding to k in the input file.
 

Sample Input
3
4
0
 
Sample Output
5
30

题目分析:这个题目我目前没找到更好的办法,上网没查到,唉,我的代码跑了500MS 郁闷死了!我是用枚举+模拟的

思路:

for i : 1 -> 14

    for j : i ->

     然后分别用长度位2 * i, 周期为 j 的循环模拟,

solve( k ,m ) :

      每次都是用 kill = (m - 1)%i (这是求本次需要去除的元素的下标)

      更新: start=((start-m)%i+i)%i   ( 其实也可以写成 :start =( (start - kill -1) %i + i )%i   )

              end=((end - m ) % i + i )  % i; 同理也可以写成上面的那样!

 示例:

    1(0)  2(1)  3(2)  4(3)  5(4)  6(5)

假设  :周期为5

第一次: kill = ( 5-1)%6=4(因为数组里下标4 就是第5个元素)

然后关键地方 start=(( 0 - 5 )%6+6) %6=1  这里就是关键: 此时 1(1)  2(2)  3(3) 4(4)  6(0)

同理 end=((2-5)%6+6)%6 =3;

这个时候 我们把数组 的顺序做个变动 按下标 重新 排列!

6(0)  1(1)  2(2) 3(3)  4(4)

这样不是又重复了上述过程麽? 但是start 与end 的指向 永远都是

没变 还是指向那几个元素!

 就这样整个模拟过程的准备工作都完成了!

源程序+部分注释:

#include<iostream>
#include<cstdio>
using namespace std;
int f[15];
bool solve(int k,int m){
	bool flag=true;
	int start=0,end=k-1,kill;
	for(int i=2*k;i>k;i--){
		kill=(m-1)%i;
		//cout<<"i = "<<i<<" "<<"kill = "<<kill<<endl;
		if(kill>=start&&kill<=end){
			flag=false;
			break;
		}
		start=((start-m)%i+i)%i;
		end=((end-m)%i+i)%i;//这样是为了更新起始点,以当前点为0坐标!想象成一个圆形!
		//cout<<"start = "<<start<<" "<<" end = "<<end<<endl;
	}
	return flag;
}

int main(){
	int n;
	for(int i=1;i<=14;i++){
		for(int j=i;;j++){
			if(solve(i,j)){
				f[i]=j;
				break;
			}
		}
	}
	while(~scanf("%d",&n),n){
		printf("%d\n",f[n]);
	}
	return 0;
}

题目总结: 注意学习,模拟约瑟夫循环的过程!

三个方程:

       kill = ( m - 1 ) % n

      start = ( (start - m) % n +n )%n

     end = ((end - m )%n +n)% n;

上述的n是当前的长度,是动态的!

HDU 1568(非常经典微妙的 斐波纳契计算)

Problem Description
2007年到来了。经过2006年一年的修炼,数学神童zouyu终于把0到100000000的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2](i>=2))的值全部给背了下来。
接下来,CodeStar决定要考考他,于是每问他一个数字,他就要把答案说出来,不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了,可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。
 

Input
输入若干数字n(0 <= n <= 100000000),每个数字一行。读到文件尾。
 

Output
输出f[n]的前4个数字(若不足4个数字,就全部输出)。
 

Sample Input
0
1
2
3
4
5
35
36
37
38
39
40
 
Sample Output
0
1
1
2
3
5
9227
1493
2415
3908
6324
1023

题目分析:这个题目非常精美!首先题目要求求第N个斐波纳契数的前四位,前提是他不止四位哦!

然后引用到的知识点,斐波纳契的计算公式:(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

还有对数log()的作用,先让我们回忆一下log 的运算性质吧~

1)log(a*b)=log(a)+log(b); 2)log(a/b)=log(a)-log(b);

其实在数学里面,log可以求一个大数的科学计数法的数值部分,比如说123456

首先log10(1234567)=log(1.234567*10^6)=log(1.234567)+6; 然后log10(1.234567)就是log10(1234567)的小数位

然后10^log10(1.234567)=1.234567,所以通过这样的转换 我们可以很巧妙的得到了一个很大的数的科学计数法的表示值!

然后您要取4位就拿4位!要多少位就拿多少位!

既然这样可以我们就干下去吧!

斐波纳契的计算公式:(1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n](n=1,2,3.....)

log10((1/√5) * [((1+√5)/2)^n-((1-√5)/2)^n])

化简一下得到:

-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)+log10(1-((1-√5)/(1+√5))^n)其中f=(sqrt(5.0)+1.0)/2.0;

在这里  log10(1-((1-√5)/(1+√5))^n)无穷小可以忽略不计!

最后得到 log10(an)=-0.5*log10(5.0)+((double)n)*log(f)/log(10.0)   !

然后就是直接贴代码了

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int s[21]={0,1,1,2};
const double f=((double)sqrt(5)+1)/2.0;
void get_Fibonacci(int x){
	if(x<=20)
		printf("%d\n",s[x]);
	else{
		double ans=(-0.5)*log(5.0)/log(10.0)+(double(x))*log(f)/log(10.0);
		ans=ans-floor(ans);
		double k=pow(10.0,ans);
		//cout<<"k= "<<k<<endl;
		while(k<1000.0)
			k*=10.0;
		printf("%d\n",(int)k);
	}
	
}
int main(){
	int x,i;
	for(i=3;i<=20;i++)
		s[i]=s[i-1]+s[i-2];
      //在这里为了区别其他多于4位的答案我先把4位以内的
     //都计算好存起来!
	while(~scanf("%d",&x)){
		if(x==0){
			printf("0\n");
			continue;	
		}
		get_Fibonacci(x);
	}
	return 0;
}

 

HDU 1717(小数化分数2 --非常犀利)

题目大意:

Problem Description
Ray 在数学课上听老师说,任何小数都能表示成分数的形式,他开始了化了起来,很快他就完成了,但他又想到一个问题,如何把一个循环小数化成分数呢?
请你写一个程序不但可以将普通小数化成最简分数,也可以把循环小数化成最简分数。
 
Input
第一行是一个整数N,表示有多少组数据。
每组数据只有一个纯小数,也就是整数部分为0。小数的位数不超过9位,循环部分用()括起来。
 
Output
对每一个对应的小数化成最简分数后输出,占一行。
 
Sample Input
3
0.(4)
0.5
0.32(692307)
 
Sample Output
4/9
1/2
17/52

题目大意分析:这个思路非常精妙,刚开始的时候我推到一半,差点就出来了,但是还是没自信以为这样是错的,后来看完各位神牛的思路,果断肯定了 。这个题目的解题思路非常值得学习!

首先跟你一个小数 令X= 0 . s1 s2 ..sn ( y1 y2 y3..ym ) 这样的话我们把小数点分为三个部分,分别用三种颜色标记了!

我们可以把表达式转换成:X * 10 ^n=s1s2..sn+0.y1y2..ym;    我们用S1替换 s1s2..sn ,Y替换 0.(y1y2..yn), 然后可以把表达式写成: X * 10^n=S1 + Y;  然后 Y=0.(y1y2..ym) 变形一下:Y * 10 ^m=y1y2..ym + Y; 在这里我们另y1y2..ym等于S2;

宗上所述:我们得到两个表达式 X * 10^n=S1 +  Y;    Y * 10^m=S2 + Y; 然后将两个式子合并成一个用表达式,

$$\frac{s2 + (10^m-1)*s1}{10^n * ( 10^m -1 )}$$然后就可以根据这个公式,求出分子分母的 最大公约式 然后化简 就可以了{^_^}

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int gcd(int x,int y){
	int c;
	if(x<y){
		c=y;	y=x;
		x=c;
	}
	if(y==0)
		return x;
	return gcd(y,x%y);
}
int main(){
	char ch[25];
	int cas,i,p1,k1,p2,k2;
	int t1,t2,len;
	scanf("%d",&cas);
	while(cas--){
		scanf("%s",ch);
		len=strlen(ch);
		//cout<<"len = "<<len<<endl;
		i=0;	
		while(ch[i]!='.')
			i++;
		p1=0;	k1=1;
		while((ch[++i]!='(')&&(i<len)){
			p1=p1*10+ch[i]-'0';
			k1*=10;
		}
		//cout<<"p1 = "<<p1<<"k1 = "<<k1<<endl;
		p2=0;	k2=1;
		while(ch[++i]!=')'&&i<len){
			p2=p2*10+ch[i]-'0';
			k2*=10;
		}
		//cout<<"p2 = "<<p2<<"k2 = "<<k2<<endl;
		if(p2){
			t1=p1*(k2-1)+p2;
			t2=(k2-1)*k1;
		}
		else{
			t1=p1;
			t2=k1;
		}
		int w=gcd(t1,t2);
		printf("%d/%d\n",t1/w,t2/w);
	}
	return 0;
}