时间戳

首页 > 解决方案 > 如何在 C++ 中精确地记忆递归函数

c++ - 如何在 C++ 中精确地记忆递归函数

问题描述

我正在编写一个程序来使用递归关系查找卢卡斯数。我使用地图来存储这些值，但是当我运行程序时，它会为输入输出正确的值，输入值大约为 45。例如 60 当 60 的解为 3461452808002 时返回 18446744073418719042 之后输出不正确。我不确定我的精度从哪里开始失败。

 #include <map>
#include <iterator>

using namespace std;

unsigned long long int lucasNumber( unsigned long long int n ){

    static std::map<unsigned long long int,unsigned long long int> values;

    if(n == 0) {
        return 2;
    } else if(n == 1) {
        return 1;
    }

    std::map<unsigned long long int,unsigned long long int>::iterator iter = values.find(n);

    if(iter == values.end()) {
        return values[n] = lucasNumber(n-1) + lucasNumber(n-2);
    } else {
        return iter->second;
    }

这是Main函数类。希望这将有助于澄清任何事情

#include <stdio.h>
#include "csce310homeWork04part01.hpp"
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;

int main( int argc , char* argv[] ){
    unsigned long long int n;
    cin >> n;
    try{
        fprintf( stdout , "Lucas number %llu has a value of %llu\n" , n , lucasNumber( n ) );
    }
    catch( exception e ){
        cerr << "ERROR" << endl;
    }
}

标签： c++

解决方案

以下清单对我来说很好。我只做了非常小的编辑，以便我可以调试它。检查我如何将整个计算的序列输出到文件中，这样我们就可以看到哪里出了问题，如果他们出错了。

#include <iostream>
#include <fstream>
#include <map>

using namespace std;

typedef std::map<unsigned long long, unsigned long long> StorageType;
StorageType g_previouslyCalculatedValues{ {0, 2}, {1, 1} };

// Calculate Lucas Numbers up to the index specified
unsigned long long LucasNumber(unsigned long long n)
{
    StorageType::iterator iter = g_previouslyCalculatedValues.find(n);

    if (iter == g_previouslyCalculatedValues.end()) {
        return g_previouslyCalculatedValues[n] = LucasNumber(n - 1) + LucasNumber(n - 2);
    }

    return iter->second;
}

int main(int argc, char* argv[])
{
    unsigned long long int n;
    cout << "Enter the index of Lucas numbers to calculate" << endl;

    if ((cin >> n).fail())
    {
        cout << "Use an unsigned integer next time. Exiting..." << endl;
        return -1;
    }

    try
    {
        StorageType::value_type result = LucasNumber(n);

        // Debug
        ofstream myfile("results.txt");
        for (auto element : g_previouslyCalculatedValues)
        {
            myfile << element.first << "\t: " << element.second << endl;
        }
        myfile.close();
    }
    catch (exception e)
    {
        cerr << "ERROR" << endl;
    }
}

我将存储设置为全局而不是静态的，但两种方式都试过了，效果很好。在现实世界中，它将是计算器类中的类成员。您确定您正在测试您提供给我们的列表吗？使用 VS2017 64 位对我来说似乎很好！

Expected result: 3461452808002
Actual result: 3461452808002

From command line:
Enter the index of Lucas numbers to calculate
60
The lucas number for 60 is 3461452808002

推荐阅读