我想只使用奇數和最多 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);
}
uj5u.com熱心網友回復：
請使用警告 ( -Wall) 進行編譯并修復所有警告（-Werror有助于確保您執行此操作）。我沒有構建你的代碼，但int T(int n, int k)說它回傳一個int，但函式代碼是無效的。
使用回溯，您無法在每個節點上列印，因為圖中的當前節點實際上可能不會導致解決方案。在您真正到達結果集之前將任何內容提交到結果集還為時過早。
無論如何最好不要在執行邏輯任務的函式中列印，但它可以在開發邏輯時使編碼更容易，所以我會堅持下去。
回溯建議是一個很好的建議。這是邏輯：
“找到的結果”基本情況是 when n == 0 && k >= 0，如果您正在遞減n并k使用它們來表示達到目標的剩余值和剩余的選擇數。如果您將變數遞增到n和k，那也沒關系，在這種情況下，基本情況是current_total == n && taken_so_far <= k.
接下來，“失敗”的基本情況是k < 0 || n < 0因為我們要么超支，n要么用完了數字。
在那之后，遞回情況在英語中是“嘗試將每個數字取到n，遞回每個數字可能是解決方案的一部分”。根據您的規范，我們不接受任何會稍微修剪遞回樹的降序數字序列。
這是代碼；再次，回傳結果是一個練習。我正在使用一個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);轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350153.html
上一篇：一行JSP代碼導致文本在一處顯示為超鏈接，而在另一處顯示為淡文本
下一篇：遞回求和函式，如何限制求和？