首页 > 代码库 > POJ 3047 Fibonacci
POJ 3047 Fibonacci
DEBUG很辛苦,且行, 且珍惜
原代码:
ans[0][0] = (ans[0][0] * a[flag][0][0] + ans[0][1] * a[flag][1][0]) % 10000; ans[0][1] = (ans[0][0] * a[flag][0][1] + ans[0][1] * a[flag][1][1]) % 10000; ans[1][0] = (ans[1][0] * a[flag][0][0] + ans[1][1] * a[flag][1][0]) % 10000; ans[1][1] = (ans[1][0] * a[flag][0][1] + ans[1][1] * a[flag][1][1]) % 10000;
问题在于:修改后ans[][]的值再次调用,就不是原来的值了,会导致程序出错
QAQ
改进后:
ans[0][0] = (temp_1 * a[flag][0][0] + temp_2 * a[flag][1][0]) % 10000; ans[0][1] = (temp_1 * a[flag][0][1] + temp_2 * a[flag][1][1]) % 10000; ans[1][0] = (temp_3 * a[flag][0][0] + temp_4 * a[flag][1][0]) % 10000; ans[1][1] = (temp_3 * a[flag][0][1] + temp_4 * a[flag][1][1]) % 10000;
算法思路:利用快速幂,实现大数范围的快速计算,不会超时
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 const int INF = 0x3f3f3f3f; 9 10 int a[40][2][2];11 void test_print(){12 for(int i = 0; i < 40; ++i){13 printf("i = %d\n",i);14 printf("%d\n\n",a[i][0][1]);15 }16 }17 int main(){18 int i, j, k;19 int n;20 a[0][0][0] = 1;21 a[0][0][1] = 1;22 a[0][1][0] = 1;23 a[0][1][1] = 0;// n = 124 25 for(i = 1; i < 40; ++i){26 a[i][0][0] = (a[i-1][0][0] * a[i-1][0][0] + a[i-1][0][1] * a[i-1][1][0]) % 10000;27 a[i][0][1] = (a[i-1][0][0] * a[i-1][0][1] + a[i-1][0][1] * a[i-1][1][1]) % 10000;28 a[i][1][0] = (a[i-1][1][0] * a[i-1][0][0] + a[i-1][1][1] * a[i-1][1][0]) % 10000;29 a[i][1][1] = (a[i-1][1][0] * a[i-1][0][1] + a[i-1][1][1] * a[i-1][1][1]) % 10000;30 }31 // test_print();32 while(EOF != scanf("%d",&n)){33 if(-1 == n) break;34 else if(0 == n){35 printf("0\n");36 continue;37 }38 int count = 0;39 int flag;40 int ans[2][2];41 int array[65];42 int flag_t = 0;43 bool init_ok = false;44 memset(array, 0, sizeof(array));45 while(n){46 if(n % 2 == 0){47 n /= 2;48 array[flag_t] = 0;49 } else{50 n = (n - 1) / 2;51 array[flag_t] = 1;52 }53 ++flag_t;54 }55 //for(i = 0; i < flag_t / 2; ++i) swap(array[i], array[flag_t - i -1 ]);56 for(i = 0; i < flag_t; ++i){57 if(!array[i]) continue;58 int flag = i;59 if(!init_ok){60 ans[0][0] = a[i][0][0];61 ans[0][1] = a[i][0][1];62 ans[1][0] = a[i][1][0];63 ans[1][1] = a[i][1][1];64 init_ok = true;65 continue;66 }67 int temp_1 = ans[0][0];68 int temp_2 = ans[0][1];69 int temp_3 = ans[1][0];70 int temp_4 = ans[1][1];71 ans[0][0] = (temp_1 * a[flag][0][0] + temp_2 * a[flag][1][0]) % 10000;72 ans[0][1] = (temp_1 * a[flag][0][1] + temp_2 * a[flag][1][1]) % 10000;73 ans[1][0] = (temp_3 * a[flag][0][0] + temp_4 * a[flag][1][0]) % 10000;74 ans[1][1] = (temp_3 * a[flag][0][1] + temp_4 * a[flag][1][1]) % 10000;75 }76 printf("%d\n",ans[0][1]);77 }78 return 0;79 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。