C中特定值的数字加减组合

Question

比方说，如果对数字进行加法和减法的任何组合，那么结果就是 42，那么这个数字就叫做 happy。
示例:
9999993、999399 和 399999 很高兴，因为 9 + 9 + 9 + 9 + 9 - 3 = 42
3783985861 也很高兴，因为: 3 + 7 + 8 − 3 + 9 + 8 − 5 + 8 + 6 + 1 = 42

我的想法:

• 计算给定的数字有多长
• 计算组合数: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;
}

Answer 1

当然是家庭作业的帖子可以从一些指导代码中受益，但不要太多 - 很难达到平衡。

---

对于每个数字，有两种方法，加数字或减数字。 @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