c++ - 数组调试不正确的输出，复杂的算法

Question

我制作了这个算法，我正在调试它以查看为什么它不起作用，但后来我在每个周期结束时打印数组以查看问题首先出现在哪里时开始得到奇怪的东西。 乍一看，我的 while 循环似乎没有考虑最后一个数组值，但我不知道...... 有关算法和所有内容的所有信息都在源代码中。 我想了解的主要是这个问题的答案: 为什么输出有时会改变？如果我运行该程序，60-70% 的时间我会得到答案 14(这应该是错误的)，但其他时候我会得到奇怪的结果......为什么？ 如果我不断得到不同的结果，我该如何调试代码......另外，如果我编译发布而不是调试(在 debian sid 中​​可用的最新 gcc 下运行代码块)，我得到的结果大部分是 9。

代码:

#include <iostream>
#include <vector>
/*void print_array
{
    std::cout<<" ( ";
    for (int i = 0; i < n; i++) { std::cout<<array[i]<<" "; }
    std::cout<<")"<<std::endl;
}*/



///this algorithm must take an array of elements and return the maximum achievable sum
///within any of the sub-arrays (or sub-segments) of the array (the sum must be composed of adjacent numbers within the array)

///it will squeeze the array ...(...positive numbers...)(...negative numbers...)(...positive numbers...)...
///into ...(positive number)(negative number)(positive number)...

///then it will 'remove' any negative numbers in case it would be convienent so that the sum between 2 positive numbers
///separated by 1 negative number would result in the highest achievable number, like this:
// -- (3,-4,4) if u do 'remove' the negative number in order to unite the positive ones, i will get 3-4+4=3. So it would
// be better not to remove the negative number, and let 4 be the highest number achievable, without any sums
// -- (3,-1,4) in this case removing -1 will result in 3-1+4=6, 6 is bigger than both 3 and 4, so it would be convienent to remove the
// negative number and sum all of the three up into one number
///so what this step does is shrink the array furthermore if it is possible to 'remove' any negatives in a smart way
///i also make it reiterate for as long as there is no more shrinking available, because if you think about it not always
///can the pc know if, after a shrinking has occured, there are more shrinkings to be done

///then, lastly, it will calculate which of the positive numbers left is highest, and it will choose that as remaining maximum sum :)

///expected result for the array of input, s[], would be (i think), 7

int main() {
const int n=4;
int s[n+1]={3,-2,4,-4,6};
int k[n+1]={0};
///PRINT ARRAY, FOR DEBUG
std::cout<<" ( ";
    for (int i = 0; i <= n; i++) { std::cout<<k[i]<<" "; }
    std::cout<<")"<<std::endl;
int i=0, j=0;
// step 1: compress negative and postive subsegments of array s[] into single numbers within array k[]
/*while (i<=n)
{
    while (s[i]>=0)
    {
        k[j]+=s[i]; ++i;
    }
    ++j;
    while (s[i]<0)
    {
        k[j]+=s[i]; ++i;
    }
    ++j;
}*/

while (i<=n)
{

    while (s[i]>=0)
    {
        if (i>n) break;
        k[j]+=s[i]; ++i;
    }
    ++j;
    while (s[i]<0)
    {
        if (i>n) break;
        k[j]+=s[i]; ++i;
    }
    ++j;
}















std::cout<<"STEP 1 : ";
///PRINT ARRAY, FOR DEBUG
std::cout<<" ( ";
    for (int i = 0; i <= n; i++) { std::cout<<k[i]<<" "; }
    std::cout<<")"<<std::endl;



j=0;
// step 2: remove negative numbers when handy
std::cout<<"checked WRONG! "<<unsigned(k[3])<<std::endl;
int p=1;
while (p!=0)
{
    p=0;
    while (j<=n)
    {
        std::cout<<"checked right! "<<unsigned(k[j+1])<<std::endl;
        if (k[j]<=0) { ++j; continue;}
        if ( k[j]>unsigned(k[j+1]) && k[j+2]>unsigned(k[j+1]) )
        {
            std::cout<<"checked right!"<<std::endl;
            k[j+2]=k[j]+k[j+1]+k[j+2];
            k[j]=0; k[j+1]=0;
            ++p;
        }
        j+=2;
    }
}
std::cout<<"STEP 2 : ";
///PRINT ARRAY, FOR DEBUG
std::cout<<" ( ";
    for (int i = 0; i <= n; i++) { std::cout<<k[i]<<" "; }
    std::cout<<")"<<std::endl;


j=0; i=0; //i will now use "i" and "p" variables for completely different purposes, as not to waste memory
// i will be final value that algorithm needed to find
// p will be a value to put within i if it is the biggest number found yet, it will keep changing as i go through the array....

// step 3: check which positive number is bigger: IT IS THE MAX ACHIEVABLE SUM!!
while (j<=n)
{
    if(k[j]<=0) { ++j; continue; }
    p=k[j]; if (p>i) { std::swap(p,i); }
    j+=2;
}

std::cout<<std::endl<<"MAX ACHIEVABLE SUM WITHIN SUBSEGMENTS OF ARRAY : "<<i<<std::endl;

return 0;
}

可能会出现问题，因为我没有使用 vector ？ 感谢您的帮助!

编辑:我发现了我的算法错误! 一个是用户 m24p 提到的，在算法的第 1 步中找到，我用一种有点丑陋的解决方法修复了它，稍后将进行清理...... 另一个是在步骤2中找到的。似乎在 while 表达式检查中，我根据数组的无符号值检查某些内容，真正检查的是一些奇怪数字的无符号值。 我用简单的 cout 输出测试了它: 如果我执行 unsigned(k[anyindexofk]) 并且该点中包含的值是正数，我当然会得到无符号的正数 如果该数字是负数，则该值不会简单地无符号，而是看起来非常不同，就像我跨过数组或其他东西一样...当我期望 -2 返回为 2 或其他值时，我得到这个数字“4294967292” -4 变为 4。 (该数字代表 -4，-2 代表 4294967294)

我用我的新东西编辑了源代码，感谢您的帮助!

编辑2: nvm 我使用 c++ 的 cmath 库通过 std::abs() 进行了解析 不使用abs还有其他方法吗？

Answer 1

在您的代码中，您有:

while (s[i]>=0)
{
    k[j]+=s[i]; ++i;
}

s 的初始化如下

int s[n+1]={3,-2,4,-4,6};

这是一个明显的错误。您的 while 循环将超越数组并命中可能会或可能不会被清零的垃圾数据。没有什么可以阻止 i 大于 n+1。清理代码，以免超出数组，然后尝试调试它。另外，你的问题需要更加具体，这样我才能放心地回答你的问题，但是修复像我指出的那样的错误应该可以更容易地停止遇到不一致、未定义的行为并开始专注于你的算法。我很想回答这个问题，但我无法解析您具体要问的内容或出了什么问题。