在C中添加和減去特定值的數字的組合

假設有一個數字被稱爲開心，如果有任何數字加減的組合，那麼結果是42.
例如：
9999993，999399和399999很高興，因爲9 + 9 + 9 + 9 + 9 - 3 = 42
3783985861也很高興，因爲：3 + 7 + 8 - 3 + 9 + 8 - 5 + 8 + 6 + 1 = 42在C中添加和減去特定值的數字的組合

我的想法：

計數給定的數字有多長
數組合：2^n種組合| N =號碼長度
for循環，並檢查所有的組合，以使結果是42 但如何?????
做遞歸。我可以通過添加所有數字來完成。但如何檢查所有組合？

int isHappy(unsigned int aNum){ 

int count = 0; 

while(aNum != 0){ 
    aNum /= 10; 
    count++; 
} 

int nTimes = 1; 

for(int i=0;i<count;i++){ 
    nTimes = nTimes * 2; 
} 

for(int i=0;i<nTimes;i++){ 
    ???? 
} 

return nTimes; 
} 

int main(){ 

printf("%d", isHappy(999993)); 

return 0; 
}

來源

2017-06-29 Apex

每位數有兩種可能的跡象的和輔助功能。給你一個漂亮的二叉樹，你可以遍歷和回溯遞歸。 –

使用動態編程可以實現O（n^2）解決方案。想想是否有可能獲得特定的前幾位數字的加/減法。創建一個二維數組索引的數字位數和結果。（實際上編輯：O（n^2）） –

只是爲了好玩，請注意整數* x *的base- * b *表示中的位數是O（log * x *），對於任何* b * 。因此，如何描述問題的漸近複雜性很大程度上取決於您如何定義問題的大小。 –

帖子是肯定的功課可以一些引導代碼中獲益，但不會太大 - 難以求取這種平衡。

對於每個數字，有兩種方法可以去，增加數字或減去數字。 @Eugene Sh.。這是遞歸解決方案的經典考慮因素。對於一個n位數字，期望O（2 ** n）次迭代。

Other approaches可能更有效。

避免硬編碼42

#define HAPPY 42

作出這樣的傳遞的數量和當前的總和，並返回成功狀態的輔助功能。

我應該終止條件是什麼？
怎麼辦工作的一些？
如何嘗試其餘任務的各種路徑？

int isHappy_helper(unsigned int aNum, int sum) { 
    if (aNum == TBD) { 
    return sum == HAPPY; 
    } 
    // Extract one digit from aNum (how about the least significant digit?) 
    int digit = TBD; 
    // What is left in aNum once the above digit is removed? 
    aNum = TBD; 
    // Try adding and subtracting the digit with the sum 
    return isHappy_helper(aNum, TBD) || isHappy_helper(aNum, TBD); 
}

呼叫與TBD

int isHappy(unsigned int aNum) { 
    return isHappy_helper(aNum, TBD); 
}

一些測試代碼

void isHappy_test(unsigned int aNum) { 
    printf("%u %d\n", aNum, isHappy(aNum)); 
} 

int main() { 
    isHappy_test(0); 
    isHappy_test(1); 
    isHappy_test(9999993); 
    isHappy_test(999993); 
    isHappy_test(999399); 
    isHappy_test(399999); 
    isHappy_test(3783985861); 
    return 0; 
}

預計輸出

0 0 
1 0 
9999993 0 
999993 1 
999399 1 
399999 1 
3783985861 1

來源

2017-06-29 19:20:57 chux

謝謝你的幫助。我現在有另一個解決方案的想法。我想要將數字拆分爲數字數組並進行一些排列。 – Apex

在作業幫助答案中提供一些測試代碼的簡單但不錯的主意。順便說一句，「O（2 ** n）」：編碼FORTRAN的遺失青春編碼的青春？ –

@DavidBowling ...我也想念[3-way if]（https://docs.oracle.com/cd/E19957-01/805-4939/6j4m0vn9p/index.html）。 – chux

在C中添加和減去特定值的數字的組合

回答

相關問題