斐波那契非递归 C语言源码 大数加法

#include "stdio.h" #include "string.h" #include "stdlib.h" #include "fibnacci.h" /*************整数实现的fibnacci计算****************/ int fibnacciINT(int n) { int iPreFirst=0,iPreSec=0,iCurrent=0; int i; if( (0==n) || (1==n) ) { return n; } iPreSec = fibnacciINT(0); iPreFirst = fibnacciINT(1); for(i=2;i<=n;i++) { iCurrent = iPreSec+iPreFirst; iPreSec = iPreFirst; iPreFirst = iCurrent; } return iCurrent; } /*========================================*/ /* 由于整形数字表示的数字范围有限， 因此下面实现由字符串方式实现的fibnacci计算， 包括了大数加法的实现 */ /*========================================*/ /******************单字符加法*********************/ TStrSingleSum SingleCharAdd(const char chAdderFst, const char chAdderSec) { TStrSingleSum tSum; char strLocAdderFst[2] = {0}; char strLocAdderSec[2] = {0}; int iSum = 0; strLocAdderFst[0] = chAdderFst; strLocAdderSec[0] = chAdderSec; memset(&tSum, 0, sizeof(tSum)); iSum = atoi(strLocAdderFst)+atoi(strLocAdderSec); itoa(iSum/FIB_DECIMAL, &tSum.chCarry,FIB_DECIMAL); itoa(iSum%FIB_DECIMAL, &tSum.chRemainder,FIB_DECIMAL); return tSum; } /******************字符串加法*********************/ void StringLargeNumberAdd(const char *strAdderFirst, const char *strAdderSec, char *strSum) { /* 为了不改变原入参， 此处定义两个临时变量保存两个加数*/ char strLocAdderFst[FIB_RET_MAX_LEN] = {0}; char strLocAdderSec[FIB_RET_MAX_LEN] = {0}; char *pchAdderFst = NULL; char *pchAdderSec = NULL; int iAdderFstLen = 0; int iAdderSecLen = 0; int iAdderMaxLen = 0; char chCarry = 0; /* 加法操作的进位 */ char chLowerCarry = 0; /* 加法操作的低位的进位 */ char chRemainder = 0; /* 加法操作的本位余数 */ int i; TStrSingleSum tSingleOrigSum; TStrSingleSum tSingleCarrySum; memset(&tSingleOrigSum, 0, sizeof(tSingleOrigSum)); memset(&tSingleCarrySum, 0, sizeof(tSingleCarrySum)); pchAdderFst = &strLocAdderFst[0]; pchAdderSec = &strLocAdderSec[0]; iAdderFstLen = strlen(strAdderFirst); iAdderSecLen = strlen(strAdderSec); iAdderMaxLen = iAdderFstLen>=iAdderSecLen ? iAdderFstLen : iAdderSecLen; strcpy(strLocAdderFst,strAdderFirst); strcpy(strLocAdderSec,strAdderSec); /*字符串翻转，使加法数低位在低位*/ strrev(strLocAdderFst); strrev(strLocAdderSec); /***pchAdderFst + pchAdderSec 两者长度相同,均为iAdderMaxLen******/ for(i=0; i<iAdderMaxLen; i++) { tSingleOrigSum = SingleCharAdd(pchAdderFst[i],pchAdderSec[i]); chCarry = tSingleOrigSum.chCarry; chRemainder = tSingleOrigSum.chRemainder; tSingleCarrySum = SingleCharAdd(tSingleOrigSum.chRemainder,chLowerCarry); strSum[i] = tSingleCarrySum.chRemainder; tSingleCarrySum = SingleCharAdd(tSingleCarrySum.chCarry,tSingleOrigSum.chCarry); chLowerCarry = tSingleCarrySum.chRemainder; } if(chLowerCarry > '0') { strSum[i++] = chLowerCarry; } strSum[i] = '\0'; strrev(strSum); return ; } void fibnacciStr(int n,char *strFib) { char strFibTemp[FIB_RET_MAX_LEN] = {0}; char strPreFirst[FIB_RET_MAX_LEN] = {0}; char strPreSec[FIB_RET_MAX_LEN] = {0}; char strCurrent[FIB_RET_MAX_LEN] = {0}; int i = 0; if( (0==n) || (1==n) ) { itoa(n,strFib,FIB_DECIMAL); return ; } fibnacciStr(0,strPreSec); fibnacciStr(1,strPreFirst); for(i=2;i<=n;i++) { memset(strCurrent,0,FIB_RET_MAX_LEN); StringLargeNumberAdd(strPreSec,strPreFirst,strCurrent); strcpy(strPreSec,strPreFirst); strcpy(strPreFirst,strCurrent); } strcpy(strFib,strCurrent); return ; } /********************测试函数********************/ int Test_StringLargeNumberAdd(void) { char *stradder1 = "998"; char *stradder2 = "1128"; int istradder1Len = strlen(stradder1); int istradder2Len = strlen(stradder2); int istrMaxLen = (istradder1Len>=istradder2Len ? istradder1Len:istradder2Len) ; char *strSum = (char *)malloc(istrMaxLen+1); char *strAddVar_1 = (char *)malloc(istradder1Len+1); char *strAddVar_2 = (char *)malloc(istradder2Len+1); memset(strSum,0,istrMaxLen+1); memset(strAddVar_1,0,istradder1Len+1); memset(strAddVar_2,0,istradder2Len+1); strcpy(strAddVar_1,stradder1); strcpy(strAddVar_2,stradder2); StringLargeNumberAdd(strAddVar_1, strAddVar_2, strSum); printf("%s\n",strSum); free(strSum); free(strAddVar_1); free(strAddVar_2); return 0; } /* int Test_fibnacciINT(void) { int iFib = 0; int i=0; iFib = fibnacciINT(2); printf("%u: %u;\n ",2, iFib); printf("\n"); return 0; } */ int Test_fibnacciINT(void) { int iFib = 0; int i=0; printf("************************************\n"); for(i=0; i<20;i++) { iFib = fibnacciINT(i); printf("%u: %u;\n",i, iFib); } printf("************************************\n"); printf("\n"); return 0; } int Test_fibnacciStr(void) { char strFib[FIB_RET_MAX_LEN] = {0}; fibnacciStr(10000,strFib); printf("%u: %s;\n ",10000, strFib); printf("\n"); return 0; } /* int Test_fibnacciStr(void) { char strFib[FIB_RET_MAX_LEN] = {0}; int i=0; printf("************************************\n"); for(i=0; i<20;i++) { fibnacciStr(i,strFib); printf("%u: %s;\n",i, strFib); } printf("\n"); printf("************************************\n"); return 0; } */