使用回溯法生成前缀为0721且后6位含3个不同偶数的10位电话号码

核心修改说明 #

• 补全valid校验逻辑，增加实时剪枝规则，大幅减少无效回溯
• 修正回溯逻辑的枚举范围：每一位可填充0-9的全量数字，而非原代码中循环N次的错误逻辑
• 修正文件写入逻辑，避免每次写入覆盖之前生成的号码
• 对齐你梳理的数学规则：后6位为3个互不相同的偶数+3个可重复的奇数

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

#define N 6 // 固定填充后6位
int v[N], even[5] = {0, 2, 4, 6, 8}, odd[5] = {1, 3, 5, 7, 9};

void display() {
    FILE *fout = fopen("telephone_numbers.txt", "a");
    if(!fout) {
        fprintf(stderr, "Error opening the file.\n");
        exit(EXIT_FAILURE);
    }
    fprintf(fout, "0721");
    for(int i = 0; i < N; i++) {
        fprintf(fout, "%d", v[i]);
    }
    fprintf(fout, ";\n"); // 单行列显方便后续处理
    fclose(fout);
}

bool valid(int step) {
    int distinct_even = 0;
    int odd_cnt = 0;
    int even_used[10] = {0}; // 标记对应偶数是否已经出现过

    for(int i = 0; i < step; i++) {
        if(v[i] % 2 == 0) {
            if(!even_used[v[i]]) {
                distinct_even++;
                even_used[v[i]] = 1;
            }
        } else {
            odd_cnt++;
        }
        // 提前剪枝：超出规则上限直接终止该分支
        if(distinct_even > 3 || odd_cnt > 3) {
            return false;
        }
    }

    // 填充完6位时做最终规则校验
    if(step == N) {
        return distinct_even == 3 && odd_cnt == 3;
    }
    return true;
}

void back(int step) {
    if(!valid(step)) {
        return;
    }
    if(step == N) {
        display();
        return;
    }
    // 枚举当前位所有可选数字
    for(int num = 0; num <= 9; num++) {
        v[step] = num;
        back(step + 1);
    }
}

int main(int argc, char **argv) {
    // 启动前清空旧文件内容
    FILE *f = fopen("telephone_numbers.txt", "w");
    if(f) fclose(f);
    back(0);
    return 0;
}

规则调整提示 #

如果你的实际需求是后6位至少包含3个互不相同的偶数（允许偶数数量、偶数种类超过3），仅需要修改两处即可：

1. 删除提前剪枝逻辑里的distinct_even > 3 || odd_cnt > 3判断
2. 将填充完成的最终校验改为return distinct_even >= 3;

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