首页 > 代码库 > HDU-1250

HDU-1250

/********************************************************************@file     Main_practise.cpp@date     2014-8-29@author   Tiger@brief    Hat‘s Fibonacci@details  大数********************************************************************/#include <cstdio>#include <string>#include <algorithm>const int SIZE = 2006;const int MAX = 100000;std::string g_Records[MAX];std::string Add(const std::string& strA, const std::string& strB);void CalFab(void);int main(int argc, const char* argv[]){    CalFab();    int nNum = 0;    while (scanf("%d", &nNum) != EOF)    {        printf("%s\n", g_Records[nNum].c_str());    }    return 0;}std::string Add(const std::string& strA, const std::string& strB){    char strTemp[SIZE] = {0};    for (int i=strA.size()-1, m=0; i>=0; --i, ++m)    {        strTemp[m] =  strA.at(i) - 0;    }    for (int i=strB.size()-1, n=0; i>=0; --i, ++n)    {        strTemp[n] += strB.at(i) - 0;    }    int nMax = std::max(strA.size(), strB.size());    std::string strSum(strTemp, strTemp+nMax);    strSum.resize(strSum.size()+1);    for (unsigned int i=0; i<strSum.size()-1; ++i)    {        strSum[i+1] += strSum[i]/10;        strSum[i] = strSum[i]%10 + 0;    }    strSum[strSum.size()-1] = strSum[strSum.size()-1]%10 + 0;    for (unsigned int i=0; i<strSum.size()/2; ++i)    {        std::swap(strSum[i], strSum[strSum.size()-1-i]);    }    if (strSum.at(0) == 0)    {        strSum.erase(strSum.begin());    }    return strSum;}void CalFab(void){    g_Records[1] = "1";    g_Records[2] = "1";    g_Records[3] = "1";    g_Records[4] = "1";    std::string str1 = g_Records[1], str2 = g_Records[2];    std::string str3 = g_Records[3], str4 = g_Records[4];    for (int i=5; i<MAX; ++i)    {        g_Records[i] = Add(str1, str2);        g_Records[i] = Add(g_Records[i], str3);        g_Records[i] = Add(g_Records[i], str4);        if (g_Records[i].size() > SIZE)        {            break;        }        str1 = str2;        str2 = str3;        str3 = str4;        str4 = g_Records[i];    }}

 

HDU-1250