UVA10334 Ray Through Glasses【大数】
Suppose we put two panes of glass back-to-back. How many ways an are there for light rays to pass through or be reflected after changing direction n times? Following figure shows the situations when the value of n is 0,1 and 2. Input It is a set of lines with an integer n where 0 ≤ n ≤ 1000 in each of them. Output For every one of these integers a line containing an as described above. Sample Input 0 1 2 Sample Output 1 2 3 题链接:UVA10334 Ray Through Glasses 问题简述:(略) 问题分析: ? 这个问题其实就是fibonacci数列,只是起始项的值不同。递推式如下: ? f0=0 ? f1=2 ? ...... ? fn=fn-2 + fn-1(n>=2) ? 大数计算是用模拟法来实现的,参见程序。 程序说明: ? 用Java程序来完成大数计算是最为方便的。 题记:(略) 参考链接:(略) AC的C++语言程序如下: AC的C++语言程序(模拟法)如下: /* UVA10334 Ray Through Glasses */ #include <bits/stdc++.h> using namespace std; typedef unsigned long long ULL; const int N = 1000; const int N2 = 1000 / 17; const ULL BASE = 1e17; ULL fib[N + 1][N2 + 1]; void setfib() { fib[0][0] = 1; fib[1][0] = 2; int len = 1; for(int i = 2; i <= N; i++) { int carry = 0; for(int j = 0; j < len; j++) { fib[i][j] = fib[i - 2][j] + fib[i - 1][j] + carry; carry = fib[i][j] / BASE; fib[i][j] %= BASE; } if(carry) fib[i][len++] = carry; } } int main() { memset(fib,sizeof(fib)); setfib(); int n; while(~scanf("%d",&n)) { int k = N2; while(fib[n][k] == 0) k--; printf("%lld",fib[n][k]); for(int i = k - 1; i >= 0; i--) printf("%017lld",fib[n][i]); printf("n"); } return 0; } AC的Java语言程序如下: /* UVA10334 Ray Through Glasses */ import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); BigInteger[] fib = new BigInteger[1001]; fib[0] = new BigInteger("1"); fib[1] = new BigInteger("2"); for(int i = 2; i <= 1000; i ++) fib[i] = fib[i - 1].add(fib[i - 2]); while(cin.hasNext()) { int N = cin.nextInt(); System.out.println(fib[N]); } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |