数学 - 公式 V[i] = ([ V[i-1] * V[i-1] / (i + 2)] + V[ i-1] * i + i + 1) % 666013

Question

我需要一些帮助来解决这个公式：

V[i] = ([ V[i-1] * V[i-1] / (i + 2)] + V[ i-1] * i + i + 1) % 666013 where v[0] = 3 and example: v[10000000] = 22230

我的解决方案是：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>

using namespace std;

ifstream fin ("smen.in");
ofstream fout ("smen.out");

unsigned long long int n, k;
int mod = 666013;

int numereus(int n)
{
    if (n > 0)
    {
        k = numereus(n-1) % mod;
        return ((((((((k*k)% mod)/((n%mod+2) % mod))%mod)+(k*(n%mod))% mod)% mod) + (n % mod)) % mod + 1) % mod;
    }
    else
    {
        return 3;
    }
}

int main()
{
    cin >> n;
    cout << numereus(n);
    return 0 ;
}

我的 C++ 解决方案不适用于大于 25000 的数字

Answer 1

递归解决方案最适合快速基本情况。

例如，对于每次递归，二分搜索都会去掉一半的解决方案 space，这样您就可以在大约 32 层递归中搜索 40 亿项。

处理 25,000 个项目的算法需要 25,000 个堆栈帧，因此可能更适合迭代解决方案。堆栈不是无限的资源。

在实现迭代解决方案方面，请参阅以下伪代码，它应该会给您一个想法：

def fn(n):
    rv = 3
    i = 0
    while n > 0:
        i = i + 1
        rv = (rv * rv / (i + 2) + rv * i + i + 1) % 666013
        n = n - 1
    return rv

这是 Python 中的概念验证，它看起来与上面的代码非常相似，因为老实说，如果你抛弃所有 lambda/closure/list-comprehension 的东西，Python制作完美的伪代码语言:-)

def fn(n):
    rv = 3
    i = 0
    while n > 0:
        i = i + 1
        rv = (rv * rv / (i + 2) + rv * i + i + 1) % 666013
        n = n - 1
    return rv

print fn(0)
print fn(1)
print fn(2)
print fn(10000000)

这输出：

根据您的问题，最后一个似乎是 10,000,000 的正确值。

等效的 C++ 代码如下：

#include <iostream>

int numereus (int n) {
    unsigned long long int rv = 3;
    int i = 0;
    while (n-- > 0) {
        i = i + 1;
        rv = (rv * rv / (i + 2) + rv * i + i + 1) % 666013;
    }
    return rv;
}

int main (void) {
    std::cout
        << numereus(0) << '\n'
        << numereus(1) << '\n'
        << numereus(2) << '\n'
        << numereus(10000000) << '\n';
    return 0 ;
}

Answer 2

保留现有代码的一种廉价方法是使用 memoization。您的代码很容易在循环中编写，在这种情况下，这可能应该是您的首选方法，但了解记忆是件好事。

这个想法是将昂贵的计算结果存储在缓存中，然后检索它们以节省时间（或资源）。

对于您的代码，每次调用 numereus 时，它都会将答案存储在一个数组中。如果稍后使用相同的参数调用 numereus，它会检查数组中是否有答案，如果有，returns 不进行进一步的递归或计算就得到答案。

为了回答你的问题，我们可以用更大的值重复调用 numereus 来建立缓存。这防止了堆栈溢出的可能性并且仍然在 O(N) 时间内工作，因为对 numereus(i) 的每次调用都能够获取 numereus(i-1).

的缓存值

当然，构建这么大的缓存会消耗大量内存。处理这个问题的一种方法是只缓存每个 xth 值。例如，您可以只缓存偶数的输入。这将您需要的存储量减半 space，同时将递归深度加倍。

对于您的问题，以下未经测试的代码可能有效：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>

#include <vector>

using namespace std;

ifstream fin ("smen.in");
ofstream fout ("smen.out");

unsigned long long int n, k;
int mod = 666013;

int numereus(std::vector<int> &memoized, int n){
    if(memoized[n]!=-1)
        return memoized[n];

    if (n > 0){
        k = numereus(memoized,n-1) % mod;
        return memoized[n]=((((((((k*k)% mod)/((n%mod+2) % mod))%mod)+(k*(n%mod))% mod)% mod) + (n % mod)) % mod + 1) % mod;
    } else {
        return 3;
    }
}

int main()
{
    std::vector<int> memoized(10000000);
    //I use -1 as a place holder here. Just make sure this is a value your function can never produce
    std::fill(memoized.begin(),memoized.end(),-1);
    cin >> n;

    for(int i=0;i<n;i++) //Build table of answers
      numereus(memoized,i);

    cout << numereus(memoized,n);
    return 0 ;
}

数学 - 公式 V[i] = ([ V[i-1] * V[i-1] / (i + 2)] + V[ i-1] * i + i + 1) % 666013

Math - Formula V[i] = ([ V[i-1] * V[i-1] / (i + 2)] + V[ i-1] * i + i + 1) % 666013

c++

math

formula