假设一个数字是快乐的,如果数字有加和减的组合,那么结果是42。
例子:
9999993、999399和399999是快乐的,因为9+9+9+9-3=42
3783985861也很高兴,因为:3+7+8-3+9+8-5+8+6+1=42
我的想法:
数一数给定的数字是多少
计算组合:2^n组合| n=数字长度
循环检查所有组合,结果为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;
}
最佳答案
当然是家庭作业的职位可以受益于一些指导性的准则,但不太难达到这种平衡。
对于每个数字,有两种方法去做,加上数字或减去数字@Eugene Sh.这是递归解决方案的经典考虑对于n位数字,需要o(2**n)迭代。
Other approaches可能更有效。
避免硬编码42
#define HAPPY 42
生成一个helper函数,传递数字和当前和并返回成功状态。
终止条件应该是什么?
怎么做一些工作?
如何尝试其他任务的不同路径?
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的和调用helper函数
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