递归计算细菌玻璃覆盖占比的代码异常问题求助

任务说明 #

在一块正方形玻璃上存在细菌，分布规则如下：

• 2：表示该正方形被分割为4个小正方形，后续4个输入值描述各小正方形的细菌分布（支持递归分割）
• 1：表示细菌占据整个正方形
• 0：表示该正方形无细菌
  需计算细菌覆盖玻璃的比例，输出最简分数。

示例 #

• 输入：0 → 输出：0/1
• 输入：2 1 0 1 1 → 输出：3/4
• 输入：2 0 2 0 1 1 0 2 0 1 0 1 1 → 输出：1/2

问题描述 #

原代码使用局部变量kl处理递归数组索引时，仅支持最多两层递归；改为全局变量kl后，程序打印第一条调试信息即崩溃，需定位原因并修复。

原代码 #

#include <stdio.h>
#include <stdlib.h>

int kl = 1;
int bakterie(int n,int arr[n], int poziom, int j)
{
    int suma = 0;
    if (arr[j] == 0)
    {
        suma = suma;
    }
    if (arr[j] == 1)
    {
        suma += poziom;
    }
    if (arr[j] == 2)
    {
        for (int m = 1;m<=4;m++)
        {
            suma+=bakterie(n,arr,poziom/4,kl);
            printf("%d",suma);
            printf(",");
            printf("%d",kl);
            printf("\n");
            kl++;
        }
    }
    return suma;
}
int main() {
    int i=0,last_2=0,poziom=1;
    int arr[99999];
    char temp;
    do {
        scanf("%d%c", &arr[i], &temp);
        if (arr[i] == 2)
        {
            if(last_2<=4)
            {
                poziom = poziom*4;
            }
            last_2 = 0;
        }
        last_2++;
        i++;
    } while(temp != '\n');

    int n0 = bakterie(i,arr,poziom,0);
    int n1 = n0;
    int n3 = poziom;
    int n2 = n3;
    while(n1!=n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    printf("%d",n0/n1);
    printf("/");
    printf("%d",n3/n1);

    return 0;
}

崩溃原因 #

全局变量kl被所有递归调用共享，无法正确跟踪每个递归分支的数组索引：

1. 当递归嵌套调用时，内层递归会修改kl的值，导致外层递归后续循环使用的索引完全偏离预期。
2. 递归返回后，kl不会回溯，最终会访问数组越界的位置，触发程序崩溃。

修复方案 #

移除全局变量kl，改用指针传递索引，让每个递归调用独立且正确地推进当前处理的数组位置：

修改后的代码 #

#include <stdio.h>
#include <stdlib.h>

// 指针参数idx跟踪当前处理的数组索引
int bakterie(int arr[], int *idx, int poziom)
{
    int suma = 0;
    int current_val = arr[(*idx)++]; // 取出当前元素，索引自增

    if (current_val == 1)
    {
        suma += poziom;
    }
    else if (current_val == 2)
    {
        int sub_poziom = poziom / 4;
        // 处理4个子正方形
        for (int m = 0; m < 4; m++)
        {
            suma += bakterie(arr, idx, sub_poziom);
        }
    }
    // current_val为0时，suma保持0，无需处理
    return suma;
}

int main() {
    int i = 0, last_2 = 0, poziom = 1;
    int arr[99999];
    char temp;

    // 读取输入数组
    do {
        scanf("%d%c", &arr[i], &temp);
        if (arr[i] == 2)
        {
            if (last_2 <= 4)
            {
                poziom *= 4;
            }
            last_2 = 0;
        }
        last_2++;
        i++;
    } while (temp != '\n');

    int idx = 0;
    int bacteria_area = bakterie(arr, &idx, poziom);
    int numerator = bacteria_area;
    int denominator = poziom;
    int a = numerator, b = denominator;

    // 辗转相除法求最大公约数
    while (a != b)
    {
        if (a > b)
            a -= b;
        else
            b -= a;
    }

    printf("%d/%d\n", numerator / a, denominator / a);

    return 0;
}

关键修改点 #

1. 用指针idx替代全局变量，每次递归调用时自动推进索引，确保每个分支处理正确的数组元素。
2. 简化了bakterie函数的逻辑，移除冗余代码，提高可读性。
3. 移除了原调试打印代码，避免干扰递归流程。

内容的提问来源于stack exchange，提问作者Wow1345