仅使用奇数和最多 N 个数来查找数字的所有分解

Question

我想找到一个数字的所有分解，只使用奇数，最多 N 个数字。

例如对于数字 7 和 N = 3，我只能得到 1+1+5、1+3+3、7。我不能得到 1+1+1+1+3，因为它是大于 N.

他们暗示我们使用回溯。

我打算编写代码，但卡住了。如果有人能向我解释如何解决这个问题那就太好了。

int T(int n, int k)
{
    if (k == 0) 
    {
        return;
    }

    int arr[N];
    int f;
    for (f = 0; f < N; f++)
    {
        arr[f] = 0;
    }
    int sum = 0;
    int j = 1;
    int i = 1;
    int c = 0;

    while (j < k) {
        sum = sum + i;
        arr[c] = i;
        
        if (sum == n)
        {
            for (f = 0; f < N; f++)
            {
                if (arr[f] != 0)
                {
                    printf("%d ", arr[f]);
                }
            }
            printf("\n");
        }
        else if (sum > n)
        {
            arr[c] = 0;
            sum = sum - i;
            i = i - 2;
        }
        else 
        {
            i = i + 2;
            j++;
            c++;
        }
    }
    T(n, k - 1);
}

Answer 1

请带警告编译 (-Wall) 并修复所有警告（-Werror 有助于确保您这样做）。我没有构建你的代码，但 int T(int n, int k) 说它 returns 和 int，但函数代码是无效的。

使用回溯法，您无法在每个节点处打印，因为图中的当前节点实际上可能不会导致解决方案。在您实际到达之前向结果集提交任何内容为时过早。

无论如何最好not to print in functions that perform logical tasks，但它可以在开发逻辑时使编码更容易，所以我会坚持使用它。

回溯建议很好。逻辑如下：

“找到的结果”基本情况是 n == 0 && k >= 0，如果您递减 n 和 k 并使用它们来表示达到目标的剩余值，并且剩下的选择数。如果您递增变量以计数到 n 和 k，那也很好，在这种情况下，基本情况是 current_total == n && taken_so_far <= k.

接下来，“失败”的基本情况是 k < 0 || n < 0，因为我们已经超出了 n 或运行的数量。

在那之后，递归的情况在英语中是“尝试取每个奇数 i 直到 n，递归 i 可能是解决方案”。根据您的规范，我们不接受任何使递归树稍微 p运行es 的递减数序列。

这是代码；同样，返回结果也是一种练习。我正在使用 k 大小的数组来存储潜在结果，然后仅在找到结果时将其转储到标准输出。

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

void odd_decomposition_search(
    int n, const int k, int taken_length, int *taken
) {
    if (n == 0 && taken_length <= k && taken_length > 0) {
        for (int i = 0; i < taken_length - 1; i++) {
            printf("%d+", taken[i]);
        }

        printf("%d\n", taken[taken_length-1]);
    }
    else if (n > 0 && taken_length < k) {
        int i = taken_length ? taken[taken_length-1] : 1;

        for (; i <= n; i += 2) {
            taken[taken_length] = i;
            odd_decomposition_search(n - i, k, taken_length + 1, taken);
        }
    }
}

void odd_decomposition(const int n, const int k) {
    if (n <= 0 || k <= 0) {
        return;
    }

    int taken[k];
    odd_decomposition_search(n, k, 0, taken);
}

int main() {
    int n = 7;
    int k = 3;
    odd_decomposition(n, k);
    return 0;
}

如果您在理解调用堆栈时遇到困难，可以在浏览器中运行使用以下可视化工具：

const oddDecomp = (n, k, taken=[]) => {
  console.log("  ".repeat(taken.length), `[${taken}]`);

  if (n === 0 && taken.length <= k && taken.length) {
    console.log("  ".repeat(taken.length), "-> found result:", taken.join("+"));
  }
  else if (n > 0 && taken.length < k) {
    for (let i = taken.length ? taken[taken.length-1] : 1; i <= n; i += 2) {
      taken.push(i);
      oddDecomp(n - i, k, taken);
      taken.pop(i);
    }
  }
};

oddDecomp(7, 3);

仅使用奇数和最多 N 个数来查找数字的所有分解

Find all the decomposition of a number using only odd numbers and up to N numbers max

c

algorithm

recursion

backtracking