斐波那契数列大数加法
发布时间:2020-12-14 02:06:26 所属栏目:大数据 来源:网络整理
导读:昨天做完n!的大数实现,再看变形的大数加法(fibonacci)实现,感觉好多了. 空间估算经验公式 size_t fnCalcFibonacciArySize(size_t n) { /// 从资料上看到的经验公式 return (size_t)(n / 4 + 4);} 实现 /// @file exam_fibonaccimain.cpp/// @brief 斐波
昨天做完n!的大数实现,再看变形的大数加法(fibonacci)实现,感觉好多了. 空间估算经验公式size_t fnCalcFibonacciArySize(size_t n) { /// 从资料上看到的经验公式 return (size_t)(n / 4 + 4); } 实现/// @file exam_fibonaccimain.cpp /// @brief 斐波那契数列大数加法 /// ary[0] = 1,ary[1] = 1; ary[2] = ary[0] + ary[1],ary[n] = ary[n-1] + ary[n-2] /// 大数数组的估算 ary[n/4 + 4] #include <stdlib.h> #include <stdio.h> #include <string.h> #include <conio.h> #ifndef WORD #define WORD unsigned short #endif void fnCalcFibonacci(); ///< 计算斐波那契数列n的大数 size_t fnCalcFibonacciArySize(size_t n); ///< 估算斐波那契数列n时的大数数组size void fnCalcFibonacci(WORD* pAryAdd1,WORD* pAryAdd2,WORD* pArySum,size_t nArySize); void fnPrintFibonacci(WORD* pArySum,size_t nArySize); int main(int argc,char* argv[]) { do { fnCalcFibonacci(); printf("press 'c' to continue,other key to quitn"); if ('c' != _getch()) break; } while (1); /// 和其它人实现的fibonacci大数加法结果比对过,正确^_^ /** run result please input fibonacci's n:0 press 'c' to continue,other key to quit please input fibonacci's n:1 press 'c' to continue,other key to quit please input fibonacci's n:2 2 press 'c' to continue,other key to quit please input fibonacci's n:100 573147844013817084101 press 'c' to continue,other key to quit please input fibonacci's n:200 453973694165307953197296969697410619233826 press 'c' to continue,other key to quit please input fibonacci's n:1000 70330367711422815821835254877183549770181269836358732742604905087154537118196933 57974224949456261173348775044924176599108818636326545022364710601205337412127386 7339111198139373125598767690091902245245323403501 press 'c' to continue,other key to quit */ return 0; } void fnCalcFibonacci() { size_t n = 0; size_t nArySize = 0; size_t nIndex = 0; WORD* pAry1 = NULL; WORD* pAry2 = NULL; WORD* pAry3 = NULL; WORD* pAryAdd1 = NULL; WORD* pAryAdd2 = NULL; WORD* pArySum = NULL; WORD* pAryTmp = NULL; printf("please input fibonacci's n:"); fflush(stdin); ///< 清空输入缓冲区 scanf("%u",&n); nArySize = fnCalcFibonacciArySize(n); /// 算出需要开配的WORD数组大小 nArySize = (nArySize - (nArySize % sizeof(WORD))) / sizeof(WORD) + 1; /// 开辟资源 pAry1 = (WORD*)malloc(nArySize * sizeof(WORD)); if (NULL != pAry1) { memset(pAry1,nArySize * sizeof(WORD)); pAry1[nArySize - 1] = 1; } pAry2 = (WORD*)malloc(nArySize * sizeof(WORD)); if (NULL != pAry2) { memset(pAry2,nArySize * sizeof(WORD)); pAry2[nArySize - 1] = 1; } pAry3 = (WORD*)malloc(nArySize * sizeof(WORD)); if (NULL != pAry3) { memset(pAry3,nArySize * sizeof(WORD)); } /// 计算Fibonacci大数数列 if ((NULL != pAry1) && (NULL != pAry2) && (NULL != pAry3)) { pAryAdd1 = pAry1; pAryAdd2 = pAry2; pArySum = pAry3; for (nIndex = 2; nIndex <= n; nIndex++) { fnCalcFibonacci(pAryAdd1,pAryAdd2,pArySum,nArySize); /// 如果不是最后一次加法,重新设置数组(被加数,加数,和) if (nIndex != n) { pAryTmp = pAryAdd1; pAryAdd1 = pAryAdd2; pAryAdd2 = pArySum; pArySum = pAryTmp; } } /// 打印结果 fnPrintFibonacci(pArySum,nArySize); } /// 释放资源 if (NULL != pAry1) { free(pAry1); pAry1 = NULL; } if (NULL != pAry2) { free(pAry2); pAry2 = NULL; } if (NULL != pAry3) { free(pAry3); pAry3 = NULL; } } void fnCalcFibonacci(WORD* pAryAdd1,size_t nArySize) { size_t nIndex = 0; size_t nPos = nArySize - 1; int iSum = 0; int iCarry = 0; memset(pArySum,sizeof(WORD) * nArySize); ///< ! sizeof(WORD) /// 为了防止数组nPos越界操作,循环的次数必须比数组size小2 for (nIndex = 0; nIndex < (nArySize - 1); nIndex++,nPos--) { iSum = pAryAdd1[nPos] + pAryAdd2[nPos] + iCarry; pArySum[nPos] = iSum % 10000; iCarry = (iSum - iSum % 10000) / 10000; } } void fnPrintFibonacci(WORD* pArySum,size_t nArySize) { bool bFirstShow = true; size_t nIndex = 0; for (nIndex = 0; nIndex < nArySize; nIndex++) { if (bFirstShow) { /// 找到第一个不为零的数据 if (0 == pArySum[nIndex]) continue; bFirstShow = false; printf("%d",pArySum[nIndex]); } else { printf("%4.4d",pArySum[nIndex]); } } printf("n"); } size_t fnCalcFibonacciArySize(size_t n) { /// 从资料上看到的经验公式 return (size_t)(n / 4 + 4); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |