Kombination von Addieren und Subtrahieren von Ziffern für bestimmte Werte in C

Question

Nehmen wir an, eine Zahl heißt glücklich, wenn es eine Kombination von Addition und Subtraktion der Ziffern gibt, so dass das Ergebnis 42 ist.
Beispiel:
9999993, 999399 und 399999 ist glücklich, weil 9 + 9 + 9 + 9 + 9 - 3 = 42
3783985861 ist auch glücklich, weil: 3 + 7 + 8 - 3 + 9 + 8 - 5 + 8 + 6 + 1 = 42

Meine Idee:

• Zahl, wie lange die gegebene Zahl ist
• zählen Sie die Kombinationen: 2^n Kombinationen | n = Anzahl Länge
• für Schleife und überprüfen Sie alle Kombinationen, so dass das Ergebnis 42 aber wie ?????
• tun es rekursiv. Ich kann es tun, indem ich alle Ziffern addiere. Aber wie überprüft man alle Kombinationen?

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

Beiträge, die sicherlich Hausaufgaben sind mit einige Führungs Code profitieren, aber nicht zu viel - schwierig, dieses Gleichgewicht zu schlagen.

---

Für jede Ziffer gibt es zwei Möglichkeiten, die Ziffer zu addieren oder die Ziffer zu subtrahieren. @Eugene Sh.. Dies ist eine klassische Überlegung für eine rekursive Lösung. Für eine n-stellige Zahl erwarten Sie O (2 ** n) Iterationen.

Other approaches kann effizienter sein.

hart Vermeiden Codierung 42

#define HAPPY 42 

eine Hilfsfunktion Stellen, die in der Anzahl übergibt und die aktuelle Summe und gibt Erfolgsstatus.

Was sollte die Abbruchbedingung sein?
Wie zu tun einige der Arbeit?
Wie verschiedene Pfade für den Rest der Aufgabe versuchen?

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); 
} 

Rufen Sie die Hilfsfunktion mit einer Summe von TBD

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

einige Testcode

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; 
} 

Erwartete Ausgabe

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