c++ - 寻找整数可以表示为唯一自然数的 n 次幂之和的方法。给出错误输出的代码

Question

我有 t 个测试用例。给定两个数字 x 和 n，找出 x 可以表示为唯一自然数的 n 次方之和的方式。

方法是选择一个数字或移动到下一个。返回的ans存储在一个数组中，因为我使用的是dp方法。

这是我的代码

#include<bits/stdc++.h>
using namespace std;

int arr[101];

int func(int x,int n,int ind)
{
    if(arr[x]!=-1)
    {
        return arr[x];
    }
    if(x==0)
    {
        return 1;
    }
    if(ind>=(sqrt(x)+1))
    {
        return 0;
    }
    if(x<0)
    {
        return 0;
    }

    //you can either take ind or just move to the next one

    arr[x]=func(x-pow(ind,n),n,ind+1)+func(x,n,ind+1);
    return arr[x];
}

int main()
{

    int t;
    cin>>t;
    while(t)
    {

        int ans=0;
        memset(arr,-1,sizeof(arr));

        int x,n;
        cin>>x>>n;

        int ind=1;
        ans=func(x,n,ind);

        cout<<"printing the ans\n"<<ans;
        t--;
    }

    return 0;
}

用于输入1个10 2
我正进入(状态打印答案-297160607虽然 ans 是 1

Answer 1

我在 func 中插入了一个简单的调试输出.对于给定的输入“1 10 2”x有时会变得消极。这在访问数组时会导致UB，但不一定会崩溃。

您已经检查了 x 是否小于 0，但是在使用 x 之后。移动 if(x < 0)起来，你就完成了。

一般来说，为了避免此类错误，您应该使用类似 std::array 的 STL 容器或 std::vector .虽然它不受 c++ 标准的保证，但许多实现将对 operator[] 执行边界检查。在 Debug模式下编译时。或者你可以使用 at()标准保证边界检查的地方。