首页 > 代码库 > 山科SDUST OJ Problem J :连分数
山科SDUST OJ Problem J :连分数
Problem J: 连分数
Time Limit: 1 Sec Memory Limit: 64 MBSubmit: 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 4
2
2 4
9 4
3
2 3 1
Sample Output
YES
YES
HINT
Append Code
这道题目适合用递归写，思路一开始就是对的，但由于自己缺乏对细节的掌控能力，逻辑思维一直以来不是很严密（可能跟高数学的不好有关），一开始考虑问题不全面，导致题目错了很多次。
因此，得到的很重要的教训有：
1.仔细考虑好思路再动手写程序，如果写程序过程中有明显的卡顿，证明自己思路还不够清晰，停下来想清楚再写；
2.测试程序的时候注意边缘数据，边缘数据一般在题目给的范围中找，例如特别大，或者特别小的数。在这个题中最好n=1,2,3自己推一遍，此外自己多构造几组数据测试一下；
1 #include <stdio.h> 2 unsigned long long last=1; 3 unsigned long long num[200]; 4 unsigned long long gcd(unsigned long long a,unsigned long long b){ 5 return (a==0) ? b: gcd(b%a,a); 6 } 7 unsigned long long fun(int n){ 8 if(n == 0) return 1; 9 unsigned long long d=num[n];10 unsigned long long k=fun(n-1);11 unsigned long long t=k*d+last;12 last=k;13 return t;14 }15 int main(){16 int n;17 unsigned long long p,q,t;18 while(scanf("%llu%llu",&p,&q)!=EOF){19 last=1;20 scanf("%d",&n);21 for(int i=n; i>=1; i--) 22 scanf("%llu",&num[i]);23 if(n!=1){24 num[1]--;25 t = fun(n);26 }27 else {28 t = 1;29 last = num[n];30 }31 unsigned long long gcd1 = gcd(p,q);32 unsigned long long gcd2 = gcd(last,t);33 if(p / gcd1 == t / gcd2 && q / gcd1 == last / gcd2) 34 printf("YES\n"); 35 else36 printf("NO\n");37 }38 return 0;39 }
山科SDUST OJ Problem J :连分数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。