计算Fibonacci数列任意项计算

#include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <memory.h> /* ARRAY_SIZE 的设定: (按照预计算位数/5) 的数值进行设定和编译 [参考数据] 32 位 可以计算到 154 位, 155 位出错, 倍数: 4.8125 (154/32) 64 位 可以计算到 307 位, 308 位出错, 倍数: 4.796875 (307/64) 128 位 可以计算到 614 位, 615 位出错, 倍数: 4.796875 (614/128) 256 位 可以计算到 1226 位, 1227位出错, 倍数: 4.7890625 (614/128) */ #define ARRAY_SIZE 64 #define FILL_SYMBOL '_' #define CHAR_0 '0' // 变量 char g_a[ARRAY_SIZE+1]={0}; char g_b[ARRAY_SIZE+1]={0}; char g_rel[ARRAY_SIZE+1]={0}; // 缓冲 char g_buf[ARRAY_SIZE+1]={0}; // febo使用说明 void usage() { printf("febo N 计算Fibonacci数列从3项开始到第N项的数列值\n"); // type:0 (default) }; /* 问程序员, 一个与数学有关的问题: 第一行, 命令行脚本: %echo 1 > data_tmp1; echo 2 > data_tmp2; 第二行,, 命令行脚本: %cat data_tmp1 >> data_tmp2; cat data_tmp2 >> data_tmp1; 请问, 第二行重复执行100次后, data_tmp1, 和 data_tmp2 的文件大小各是多少? 【警告】: 这是一个数字问题, 千万不要写脚本来尝试执行, 否则肯定得不偿失！ */ // 脚本计算逻辑 void febo_2N(int N, unsigned long long& llTmp1, unsigned long long& llTmp2) { int i; for(i=0; i<N; i++) { // 1,1,2,3,5,8,... llTmp2 = llTmp2+llTmp1; llTmp1 = llTmp1+llTmp2; }; }; // 有溢出2 unsigned long long febo(int N) { if(1==N || 2==N) return 1; unsigned long long llTmp1 = 0; unsigned long long llTmp2 = 1; unsigned long long llTmp; int i; for(i=0; i<N-1; i++) { // 1,1,2,3,5,8,... llTmp = llTmp2+llTmp1; llTmp1 = llTmp2; llTmp2 = llTmp; } return llTmp2; }; void initArray(char arr[ARRAY_SIZE+1]) { memset(arr, FILL_SYMBOL, ARRAY_SIZE); arr[ARRAY_SIZE] = '\0'; }; // arr_calc: 加法 void arrayAdd(const char a[ARRAY_SIZE+1], const char b[ARRAY_SIZE+1], char rel[ARRAY_SIZE+1]) { short vA,vB,vRel; short full_flag=0; int i=0; // step_0: 将rel内存清空 initArray(rel); // step_1: i 循环从a,b的[63]算到[0]计算 for(i=ARRAY_SIZE-1; i>=0; i--) { // 1. 初始化1 vA=vB=vRel=0; // 2. 无数据 break if(FILL_SYMBOL==a[i] && FILL_SYMBOL==b[i]) break; // 3. 按位计算,取数位[] vA = (FILL_SYMBOL==a[i]) ? 0 : (a[i]-CHAR_0); vB = (FILL_SYMBOL==b[i]) ? 0 : (b[i]-CHAR_0); // 4. 计算数据位 vRel = vA+vB+full_flag; // printf("[%d+%d+%d]=%d\n", vA, vB, full_flag, vRel); // _debug // 5. 写结果 rel[i] = CHAR_0 + (vRel%10); // 6. 设置进位标识 full_flag = (vRel>9) ? 1 : 0; } // step_2: 最后一个进位值 break; 时 i恰好位于 进位处 if(1==full_flag) rel[i] = CHAR_0 + full_flag; }; // 从 "12345" 取值, 右对齐放入 char arr[_____12345] void setArrayValue(char val[ARRAY_SIZE+1], const char buf[ARRAY_SIZE+1]) { // 先初始化 initArray(val); // 找下标 int pIdx = 0; while(buf[pIdx]!=FILL_SYMBOL) pIdx++; pIdx--; // printf("__pIdx=%d\n", pIdx); int i; for(i=0; i<pIdx; i++) { val[ARRAY_SIZE-1-i] = buf[pIdx-1-i]; // printf("val[%d]=[%s]\n", i, val); } val[ARRAY_SIZE]='\0'; // for printf }; // 固定数据测试 int arrayTest() { char a[ARRAY_SIZE+1]={0}; char b[ARRAY_SIZE+1]={0}; char rel[ARRAY_SIZE+1]={0}; char buf[ARRAY_SIZE+1]={0}; // 预处理(每次做之前)? initArray(a); initArray(b); initArray(rel); initArray(buf); puts("____________________________init:"); printf("a=[%s]\n", a); printf("b=[%s]\n", b); printf("rel=[%s]\n", rel); printf("buf=[%s]\n", buf); puts("____________________________calc_arr1:"); sprintf(buf, "%s", "12345"); // -- 如何取值1, 数据类型1: 12345 + _____ (00000) printf("set buf=[%s] to a.\n", buf); setArrayValue(a, buf); printf("a=[%s]\n", a); printf("b=[%s]\n", b); printf("rel=[%s], add a+b to rel\n", rel); arrayAdd(a, b, rel); printf("rel=[%s]\n", rel); puts("____________________________calc_arr2:"); initArray(buf); sprintf(buf, "%d", 100111); // -- 如何取值2, 数据类型2: 12345 + 100111 (5位+6位) printf("set buf=[%s] to b.\n", buf); setArrayValue(b, buf); printf("a=[%s]\n", a); printf("b=[%s]\n", b); printf("rel=[%s], add a+b to rel\n", rel); arrayAdd(a, b, rel); printf("rel=[%s]\n", rel); puts("____________________________calc_arr3:"); initArray(buf); sprintf(buf, "%d", 999); // -- 如何取值3, 数据类型3: 进位测试 printf("set buf=[%s] to a.\n", buf); setArrayValue(a, buf); initArray(buf); sprintf(buf, "%d", 1); printf("set buf=[%s] to b.\n", buf); setArrayValue(b, buf); printf("a=[%s]\n", a); printf("b=[%s]\n", b); initArray(rel); // 初始化rel printf("rel=[%s], add a+b to rel\n", rel); arrayAdd(a, b, rel); printf("rel=[%s]\n", rel); return 0; } // 包含输入输出的测试 int arrayTest2() { char a[ARRAY_SIZE+1]={0}; char b[ARRAY_SIZE+1]={0}; char rel[ARRAY_SIZE+1]={0}; char buf[ARRAY_SIZE+1]={0}; while(1) { // 预处理(每次做之前)? initArray(a); initArray(b); initArray(rel); printf("输入a('q'退出): "); initArray(buf); // scanf数据前, 必须清空初始化buf内存; scanf("%s", buf); setArrayValue(a, buf); if('q'==buf[0]) break; printf("输入b: "); initArray(buf); // scanf数据前, 必须清空初始化buf内存; scanf("%s", buf); setArrayValue(b, buf); printf("===calc array{a+b}===\n"); printf("a=[%s]\n", a); printf("b=[%s]\n", b); arrayAdd(a, b, rel); printf("R=[%s]\n", rel); sleep(1); printf("\n"); } }; // 计算数列值febo(N), 结果写g_rel并打印 int arrayFebo(int N) { if(1==N || 2==N) { // 使用array前, 必须初始化 initArray(g_buf); initArray(g_rel); sprintf(g_buf, "%d", 1); // -- 如何取值2 setArrayValue(g_rel, g_buf); // 打印输出: arrFebo[%d]=【%s】 printf("arrayFebo[%d]\t=【%s】\n", N, g_rel); return 0; } // 初始化 initArray(g_buf); sprintf(g_buf, "%d", 1); setArrayValue(g_a, g_buf); // febo(1) setArrayValue(g_b, g_buf); // febo(2) // 设定初始值: int i; // 迭代计算N次 for(i=3; i<=N; i++) { arrayAdd(g_a, g_b, g_rel); // printf("ab:%s,%s\n", g_a, g_b); // _debug printf("arrayFebo[%d]\t=【%s】\n", i, g_rel); strncpy(g_a, g_b, ARRAY_SIZE); strncpy(g_b, g_rel, ARRAY_SIZE); } return 0; }; int main(int argc, char* argv[]) { // return arrayTest(); // 固定数测试 // return arrayTest2(); // 循环输入 int N=1; if(argc>=2) { N = atoi(argv[1]); } arrayFebo(N); return 0; };