在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中添加和减去特定值的数字的组合

回答

相关问题