c - 为什么使用不相关的 printf 语句导致我的程序输出发生变化？

Question

我遇到了一个程序，其中只有 printf 语句导致输出发生变化。

我有一个 n 元素数组。对于每d个连续元素的median，如果第(d+1)个元素大于等于它的两倍(中位数)，我正在增加 notifications 的值。完整的问题陈述可以引用here .

这是我的程序:

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

#define RANGE 200

float find_median(int *freq, int *ar, int i, int d) {
    int *count = (int *)calloc(sizeof(int), RANGE + 1);
    for (int j = 0; j <= RANGE; j++) {
        count[j] = freq[j];
    }
    for (int j = 1; j <= RANGE; j++) {
        count[j] += count[j - 1];
    }
    int *arr = (int *)malloc(sizeof(int) * d);
    float median;
    for (int j = i; j < i + d; j++) {
        int index = count[ar[j]] - 1;
        arr[index] = ar[j];
        count[ar[j]]--;
        if (index == d / 2) {
            if (d % 2 == 0) {
                median = (float)(arr[index] + arr[index - 1]) / 2;
            } else {
                median = arr[index];
            }
            break;
        }
    }
    free(count);
    free(arr);
    return median;
}

int main() {
    int n, d;
    scanf("%d %d", &n, &d);
    int *arr = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%i", &arr[i]);
    }
    int *freq = (int *)calloc(sizeof(int), RANGE + 1);
    int notifications = 0;
    if (d < n) {
        for (int i = 0; i < d; i++)
            freq[arr[i]]++;
        for (int i = 0; i < n - d; i++) {
            float median = find_median(freq, arr, i, d);   /* Count sorts the arr elements in the range i to i+d-1 and returns the median */
            if (arr[i + d] >= 2 * median) {      /* If the (i+d)th element is  greater or equals to twice the median, increments notifications*/
                printf("X");
                notifications++;
            }
            freq[arr[i]]--;
            freq[arr[i + d]]++;
        }
    }
    printf("%d", notifications);
    return 0;
}

现在，对于像 this 这样的大输入，程序输出 936 作为 notifications 的值，而当我只排除语句 printf("X") 时，程序输出 1027 作为 notifications 的值。我真的无法理解是什么导致我的程序出现这种行为，以及我遗漏/监督了什么。

Answer 1

你的程序在这里有未定义的行为:

for (int j = 0; j <= RANGE; j++) {
    count[j] += count[j - 1];
}

您应该在 j = 1 处开始循环。按照编码，您在数组 count 开始之前访问内存，这可能会导致崩溃或产生不可预测的值。更改运行环境中的任何内容都可能导致不同的行为。事实上，即使什么都不改变。

其余代码乍一看比较难理解，但考虑到索引值的计算，那里可能也会有更多问题。

对于初学者，您应该添加一些一致性检查:

• 验证 scanf() 的返回值以确保正确转换。
• 验证读入 arr 的值，它们必须在 0..RANGE 范围内
• 验证 int index = count[ar[j]] - 1; 永远不会产生负数。
• 对于 count[ar[j]]--; 也是如此
• 验证 median = (float)(arr[index] + arr[index - 1])/2; 永远不会用 index == 0 求值。