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

Question

我坚持使用一个程序,只是有一个printf语句导致输出的变化.

我有一系列n元素.对于median每个d连续元素,如果(d+1)th element大于或等于它的两倍(中位数),我正在递增值notifications.完整的问题陈述可能会在这里提及.

这是我的计划:

#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;
}

现在,对于像这样的大输入,程序输出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.