输入1:

64

输出:(大小为3)
1 x 1 x 64  =64
1 x 2 x 32  =64
1 x 4 x 16  =64
1 x 8 x 8   =64
2 x 2 x 16  =64
2 x 4 x 8   =64
4 x 4 x 4   =64

输入2:
6

输出:(大小为2)
1 x 6  =6
2 x 3  =6

我试过使用完整的二叉树,但没有得到所有可能的组合
是的。
这里是:
                             64

                    32                  2

              16          2         2       1

           8     2     1    2     1   2   1    1

如果逐级跟踪元素,则只有一些组合可用
64 x 1 X 1
32 X 2 X 1
16 x 2 x 2
8  x 2 x 2 x 2( limit > 3 )

问题是我需要所有可能的组合

最佳答案

可以使用递归方法考虑以下php代码(我想您可以将想法转换为所需的每种语言):

    function comb($num, $cnt, $prefix, $minDiv) {
        if ($cnt == 0)
        {
                if ($num == 1)
                        return rtrim($prefix,",");
                else return false;
        }
        $arrs = array();
        for ($i=$minDiv; $i <= $num; $i++) {
                if ($num % $i == 0) { // if num modulo i equal 0
                        $ans = comb($num/$i, $cnt-1, $prefix . $i . ",", $i );
                        if ($ans) // if valid combination add it
                                $arrs[] = $ans;
                }
        }
        return $arrs;
}


$ans = comb(64,3, "",1);
echo "ANSWER:\n";
echo print_r($ans);

此代码将为comb(6,2,“”,1)生成以下答案:
1,6
2,3

关于algorithm - 找出正整数k的所有可能倍数(n的大小),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/51462045/

10-09 23:52