Problem J: 连分数
Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 2723 Solved: 801
[Submit][Status][Web Board]
Description
一个高为n的连分数定义为 。
给出2个数,一个用p/q的方式表达,另一个用高度为n的连分数来表示,请你判断他们是否相等。
Input
输入有多组,每组包含两部分用来表示两种形式的分数:第一部分是p和q(1 ≤ q ≤ p ≤ 10^18),表示分数p/q;然后是一个数字n(1 ≤ n ≤ 90)和由n个数 ai(1 ≤ ai ≤ 10^18)代表的连分数。
Output
如果相等请输出“YES”,否则输出“NO”。
Sample Input
9 422 49 432 3 1
Sample Output
YESYES
HINT
Append Code
这道题目适合用递归写,思路一开始就是对的,但由于自己缺乏对细节的掌控能力,逻辑思维一直以来不是很严密(可能跟高数学的不好有关),一开始考虑问题不全面,导致题目错了很多次。
因此,得到的很重要的教训有:
1.仔细考虑好思路再动手写程序,如果写程序过程中有明显的卡顿,证明自己思路还不够清晰,停下来想清楚再写;
2.测试程序的时候注意边缘数据,边缘数据一般在题目给的范围中找,例如特别大,或者特别小的数。在这个题中最好n=1,2,3自己推一遍,此外自己多构造几组数据测试一下;
#include <stdio.h>
unsigned long long last=;
unsigned long long num[];
unsigned long long gcd(unsigned long long a,unsigned long long b){
return (a==) ? b: gcd(b%a,a);
}
unsigned long long fun(int n){
if(n == ) return ;
unsigned long long d=num[n];
unsigned long long k=fun(n-);
unsigned long long t=k*d+last;
last=k;
return t;
}
int main(){
int n;
unsigned long long p,q,t;
while(scanf("%llu%llu",&p,&q)!=EOF){
last=;
scanf("%d",&n);
for(int i=n; i>=; i--)
scanf("%llu",&num[i]);
if(n!=){
num[]--;
t = fun(n);
}
else {
t = ;
last = num[n];
}
unsigned long long gcd1 = gcd(p,q);
unsigned long long gcd2 = gcd(last,t);
if(p / gcd1 == t / gcd2 && q / gcd1 == last / gcd2)
printf("YES\n");
else
printf("NO\n");
}
return ;
}