计算体积对应长宽高组合数时如何避免重复计数？

问题核心 #

原代码的三层循环未限制三个边长的大小关系，导致同一种尺寸的不同排列被重复计数。要解决该问题只需保证遍历的边长满足 a ≤ b ≤ c 的规则，每个唯一组合只会被统计一次。

方案1：保留三层循环的低改动版本 #

仅调整内层循环起始值，逻辑和原代码差异最小，可快速实现去重：

#include <stdio.h>
#include <math.h>

int main(){
    int v, m = 0, k = 0;
    scanf("%d", &v); // a为长，b为宽，c为高，v为体积
    for(int a=1;a<=v;a++){
        // b从a开始，保证b≥a
        for(int b=a;b<=v;b++){
            // c从b开始，保证c≥b
            for(int c=b;c<=v;c++){
                m = a*b*c;
                if(m == v){
                    k = k + 1; //k为组合总数
                }
                // 乘积超过体积时直接跳出，减少无效计算
                if(m > v) break;
            }
        }
    }
    printf("组合总数为：%d", k);
    return 0;
}

方案2：优化性能的高效版本 #

通过数学计算移除第三层循环，体积较大时性能优势非常明显：

#include <stdio.h>
#include <math.h>

int main(){
    int v, k = 0;
    scanf("%d", &v);
    // a作为最小边，上限为三次根号v，减少无效遍历
    for(int a=1; a <= pow(v, 1.0/3); a++){
        if(v % a != 0) continue; // a不是体积因数时直接跳过
        int rem1 = v / a;
        // b作为中间边，至少等于a，上限为剩余值的平方根
        for(int b=a; b <= sqrt(rem1); b++){
            if(rem1 % b != 0) continue; // b不是剩余值因数时直接跳过
            int c = rem1 / b;
            // 满足c≥b则符合a≤b≤c的规则，计数+1
            if(c >= b){
                k++;
            }
        }
    }
    printf("组合总数为：%d", k);
    return 0;
}

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