我已经为算法类编写了一个程序，该程序将整数数组作为参数并找到其和最接近零的子数组。程序编译并运行。运行的大部分时间结果都是正确的，但看似随机，它会为子数组的总和和索引值打印零。当错误确实发生时，为其结果打印零的数据集总是相同的集。我无法弄清楚为什么会发生这种情况，可能是某种内存问题。如果结果总是不正确或正确，这是有道理的，但是，由于没有变量在变化，我很困惑。任何帮助将不胜感激。
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <string.h>
struct Numbers
{
int num;
int index;
};
struct Sums
{
int sum;
int indice_i;
int indice_j;
} ClosestToZero_default={INT_MAX,INT_MAX,INT_MAX};
typedef struct Sums ClosestToZero;
int struct_cmp(const void *a, const void *b)
{
struct Numbers *ia=(struct Numbers*)a; // magic
struct Numbers *ib=(struct Numbers*)b;
return (int)(ia->num-ib->num);
}
void print_result(int result,int indice_i,int indice_j)
{
printf("Sum of Subarray Closest to Zero: %d\nStart Index: %d End Index: %d\n\n",result,indice_i,indice_j);
}
struct Sums findMiddle(struct Numbers* array,int start_index,int end_index)
{
ClosestToZero result=ClosestToZero_default;
int i,j;
int n=end_index-start_index+1;
int size_left=(n+1)/2;
int size_right=n-size_left;
struct Numbers left_array[size_left];
struct Numbers right_array[size_right];
int sum=0;
j=size_left-1;
for(i=start_index+size_left-1;i>=start_index;i--,j--)
{
left_array[j]=array[i];
left_array[j].num+=sum;
sum+=array[i].num;
}
sum=0;
j=start_index+size_left;
for(i=0;i<size_right;i++,j++)
{
right_array[i]=array[j];
right_array[i].num+=sum;
sum+=array[j].num;
}
qsort(left_array,size_left,sizeof(struct Numbers),struct_cmp);
qsort(right_array,size_right,sizeof(struct Numbers),struct_cmp);
i=0;
j=size_right-1;
while(1)
{
if(left_array[i].num>0||right_array[j].num<0) break;
if(abs(left_array[i].num+right_array[j].num)<result.sum)
{
result.sum=abs(left_array[i].num+right_array[j].num);
result.indice_i=left_array[i].index;
result.indice_j=right_array[j].index;
}
if(abs(left_array[i].num)>abs(right_array[j].num)) i++;
else j--;
}
while(i<size_left&&j>=0)
{
if(left_array[i].num<0)
{
i++;
continue;
}
if(right_array[j].num>0)
{
j--;
continue;
}
if(abs(left_array[i].num+right_array[j].num)<result.sum)
{
result.sum=abs(left_array[i].num+right_array[j].num);
result.indice_i=left_array[i].index;
result.indice_j=right_array[j].index;
}
if(abs(left_array[i].num)>abs(right_array[j].num)) j--;
else i++;
}
return result;
}
struct Sums algorithm2(struct Numbers* array,int start_index,int end_index)
{
int i,j;
ClosestToZero result_left;
ClosestToZero result_right;
ClosestToZero result_mid;
if(end_index==start_index)
{
result_mid.sum=abs(array[start_index].num);
result_mid.indice_i=result_mid.indice_j=array[start_index].index;
return result_mid;
}
if(end_index-start_index==1)
{
int a=abs(array[start_index].num);
int b=abs(array[end_index].num);
int c=abs(array[start_index].num+array[end_index].num);
if(a<b&&a<c)
{
result_mid.sum=a;
result_mid.indice_i=result_mid.indice_j=array[start_index].index;
}
else if(b<a&&b<c)
{
result_mid.sum=b;
result_mid.indice_i=result_mid.indice_j=array[end_index].index;
}
else
{
result_mid.sum=c;
result_mid.indice_i=array[start_index].index;
result_mid.indice_j=array[end_index].index;
}
return result_mid;
}
int mid_index=(start_index+end_index)/2;
result_left=algorithm2(array,start_index,mid_index);
result_right=algorithm2(array,mid_index+1,end_index);
result_mid=findMiddle(array,start_index,end_index);
if(result_left.sum<result_right.sum&&result_left.sum<result_mid.sum)
return result_left;
if(result_right.sum<result_left.sum&&result_right.sum<result_mid.sum)
return result_right;
return result_mid;
}
int closestZeroSum(int* arr,int n)
{
int i;
struct Numbers array[n];
for(i=0;i<n;i++)
{
array[i].num=arr[i];
array[i].index=i;
}
struct Sums result=algorithm2(array,0,n-1);
print_result(result.sum,result.indice_i,result.indice_j);
return 0;
}
int main(int argc,int argv[])
{
int arr1[]={499228, 21572, -323857, 288186, -451707, -228193, -443913, -313419, 236065, -52692, 42198, -169000, 418130, 246890, 16091, 201633, 124538, 418432, -385986, 154610, 85740, 211439, -169332, 104064, 162438, 251, -179159, 136801, -187420, 189088, 67512, -74248, -150024, -467850, -235169, 214345, 455041, 453804, -467983, -56033, 479772, 494760, -168594, 10655, 437440, 157697, 407151, 466806, -168368, 74531, 214696, -35099, -344876, -377398, -392111, 236400, 93324, 155484, -110424, 440427, -220568, -147152, -330916, 419883, 332187, 314146, 379534, -351921, -374375, 301787, -18693, -88397, 68640, -90075, -165441, 7676, -49795, -358864, 110334, 3909, 51923, -350801, 211367, 178221, -48033, 173907, 137308, 454152, 334786, 247404, 261047, 122729, -439424, -318938, -367503, 379156, -170671, -154459, -395737, -193401};
int arr1_size=sizeof(arr1)/sizeof(int);
int arr2[]={386521, -426105, -51327, -479314, 266939, -483585, 5174, -26325, -174507, 420884, 16180, 349704, 60431, -345921, 402022, 139333, -132008, 72744, -102568, -46460, 450996, -371577, -488895, 58007, -235653, 297566, -325213, -257872, 93030, 3737, -166953, -32082, -149683, -359092, -414417, 78794, 61943, 223186, 79294, -170009, -32876, 412168, -199555, 488317, 432080, 448046, 98065, 304298, -183989, -72475, -148109, 397536, 482222, 374665, -389837, -220047, -474078, -345931, -180385, -136260, 427174, 417819, 318218, 83008, 239618, 496199, 195442, -346491, -182687, -12742, -315836, 129197, -165305, 13224, -63483, 461599, 118305, -136678, 252502, 304408, 192900, -384603, -49832, -225063, -388805, 30286, -58632, 224370, -212093, -214778, 227535, -263757, 430684, 318599, 21355, 52281, -73725, -486957, -118220, 62683};
int arr2_size=sizeof(arr2)/sizeof(int);
int arr3[]={258821, 306066, -231500, -436295, 306425, 241361, 68153, 216106, -353968, 425757, 438111, -65653, -90992, -408188, -319437, 151786, -356247, -424078, -230531, 51863, 371945, 439278, -98784, 445010, -8235, 177337, 123174, 375508, -308068, 420045, 410467, 344006, 272623, 226552, -198151, -38586, 233206, -479137, -64701, -185958, 17319, 9237, -451752, 28414, 45946, -99873, -451984, 325519, -372670, 330385, 26093, 331932, 66849, -346808, 105535, 313619, -437154, 489421, -294743, -82994, -328806, 425808, -4951, 380292, -284245, -263289, 99328, -136943, 334475, -488275, 45777, 462572, -105101, -268580, 445742, 228270, -386481, -311534, -493956, -465020, 414547, -407161, 62069, -258371, 442358, 170609, -337386, 316532, -247616, 281311, -327522, -472093, -418488, 45369, -122124, 356880, 392005, -228005, -404684, -315306};
int arr3_size=sizeof(arr3)/sizeof(int);
int arr4[]={-214717, 361303, 416397, -60197, 324864, -330864, 269005, 24278, -212135, 328504, 444353, -286586, 168424, -101904, -316543, -423435, -255180, 287940, 445395, 115632, -253558, 147979, -152719, 365455, -495117, -276957, -198353, 407462, 72712, -363120, -290174, -21743, -273045, 447738, -391003, 322787, 130778, 266059, -215648, 335540, 379559, -409427, -434836, -326577, -56499, 299815, 154620, 407297, -481496, 59677, 229793, 495171, 498055, -339219, 271951, 487629, -396570, -424726, 309446, 320962, 362817, -89534, 82070, 146429, -145523, 356977, 286852, -436864, 237388, -211029, 395540, 330818, 299266, 453390, -184790, 187741, -242354, -151414, -416877, 384540, 341533, 415449, 294444, 257065, 230018, 240416, -317276, -306150, -162259, -135509, -32091, 77089, -231556, -134644, 11163, 320983, 443832, -393703, -384938, -20882};
int arr4_size=sizeof(arr4)/sizeof(int);
int arr5[]={-210333, -203574, -29420, -375363, -393800, 421046, -244507, 354795, -489162, 163316, 108146, -130364, 189343, -265580, -104608, -354593, -196407, -83326, -259045, 91954, 102741, -374334, -195592, -328131, -128635, -145780, -268674, -206437, 168629, -496691, 83207, 464554, -184084, -409403, -445299, 41312, 234004, -459966, -127733, -427338, -311021, -449664, 85188, -482381, -21829, -381143, -158807, -317729, -181146, 102318, -112927, 493008, 333608, 187402, -201813, 288212, -262296, -306723, -220246, 479108, 415186, -372438, -246269, -353105, 333361, 394104, 482347, -23831, 168611, -207283, 38343, 314168, -281553, 281228, -474763, 332710, -198532, 321268, -344461, 483687, 31910, 90240, 435233, 466993, -389003, 67743, 454699, 76577, 204593, 13466, 362508, -68273, -187942, -363061, -485642, 409273, 285247, 411904, 80985, 324690};
int arr5_size=sizeof(arr5)/sizeof(int);
int arr6[]={368944, 321652, -362363, -234897, 105687, 65523, -404365, 176408, 182830, 338002, -290518, 166771, -365419, -271724, -127480, -322735, -378171, -39266, -435294, 476897, 499179, 157601, 198607, 491320, -389158, -303347, -472691, 100100, -14174, -29001, 421124, 270487, -376761, 481298, 36273, 459798, 358359, -63152, -206361, 117190, 185374, 41951, -124229, -73667, -214465, -182715,-215614, -476948, 315622, 64995, 497534, -12914, 415459, -52916, 460256, 400891, 183325, 429259, -153934, -180787, -21403, -193158, 272599, -136778, -368140, -279420, -250377, -220183, -439302, 464769, 214400, -120020, 374103, 128886, 381712, -3005, 487535, 39729, 148154, 446269, -312541, -78711, 97321, 152678, -438171, 60025, -390485, -363629, 17071, 356450, -189293, -157489, -146602, -219611, 427199, -446551, -490620, 325541, 210627, 384613};
int arr6_size=sizeof(arr6)/sizeof(int);
printf("\n\nExpected Output is: 251, 25, 25\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr1,arr1_size);
printf("Expected Output is: 89, 94, 96\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr2,arr2_size);
printf("Expected Output is: 3, 3, 96\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr3,arr3_size);
printf("Expected Output is: 576, 3, 47\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr4,arr4_size);
printf("Expected Output is: 325, 72, 73\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr5,arr5_size);
printf("Expected Output is: 271, 68, 96\n");
printf("algorithm2--------------------------\n");
closestZeroSum(arr6,arr6_size);
return 0;
}
我进行了一些测试并发现了一些有趣的结果；我无法理解它们。当我在返回 result_mid.num 值之前将打印语句放在基本情况下时，我收到了段错误。当只剩下 3 个元素可供比较时，我还添加了一个额外的基本情况。对于我发布的一组测试数据，这会起作用，但是对于必须更大的一组实际数据，我仍然会遇到相同类型的错误。这次错误发生在以前总是正确的数据集中。
Why might the results of some sets of data randomly, and incorrectly, produce zeros?
最佳答案
随机数据很好地提示数组访问越界。
算法错误导致访问right_array[-1]
while (1) {
if (!(j >= 0 && j < size_right)) {
printf("!1 %d %d\n", j, size_right);
exit(0);
}
if (!(i >= 0 && j < size_left)) {
printf("!2 %d %d\n", j, size_left);
exit(0);
}
if (left_array[i].num > 0 || right_array[j].num < 0) break;
输出
Expected Output is: 251, 25, 25
algorithm2--------------------------
!1 -1 1
怀疑 while (1) 应该是
while (j >= 0)
其他小问题。
struct_cmp()
// return (int) (ia->num - ib->num);
return (ia->num - ib->num) - (ia->num < ib->num);
size_t 用于数组索引。 INT_MAX --> SIZE_MAX 用于索引类型。
abs(int + int) 有两种方式的问题:求和溢出和 INT_MIN
总的来说，代码会因一些注释而受益。
关于c - 分而治之算法的结果随机变为零，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35587228/