Die Reihenfolge der Operationen während einer sequentiellen Berechnung beibehalten

Question

Ich verbringe meinen Abend damit, einige Programmierprobleme von Kattis zu machen. Es gibt einen Teil des Problems 4 thought, auf dem ich feststecke.

Bei einer gegebenen Zahl soll das Programm die erforderlichen Operationen (+, -, * oder /) zwischen 4 Vieren zurückgeben, um diese Zahl zu erreichen.

Zum Beispiel der Eingabe

9 

in der Ausgabe führen würde

4 + 4 + 4/4 = 9 

Meine Lösung (nicht effizient, aber einfach) ist, alle Möglichkeiten zu bewerten, über die Operatoren zu kombinieren und sehen wenn eine der Kombinationen das gewünschte Ergebnis erzielt.

Um dies zu tun, habe ich die Funktion geschrieben, die unten zu sehen ist. Es nimmt ein Array von Zeichen auf, die die auszuwertenden Operatoren sind (uo[3], könnte wie {+, /, *} aussehen), und das gewünschte Ergebnis als eine Ganzzahl (expRes).

bool check(char uo[3], int expRes) { 
    int res = 4; 
    for(int oPos = 2; oPos >= 0; oPos--) { 
     switch (uo[oPos]) { 
      case '+' : res += 4; break; 
      case '-' : res -= 4; break; 
      case '*' : res *= 4; break; 
      case '/' : res /= 4; break; 
     } 
    } 
    return res == expRes;  
} 

Ich erkannte, dass dieser "sequenzielle" Ansatz mit einem Problem verbunden ist: Es folgt nicht der Reihenfolge der Operationen. Wenn ich die Funktion mit uo = {+, -, /} und expRes = 7 zu nennen war, würde es return false seit 4 + 4 = 8, 8-4 = 4, 4/4 = 1. Die wirkliche Antwort offensichtlich wahr ist, da 4 + 4 - 4/4 = 7.

Kann jemand von Ihnen an eine Möglichkeit denken, die Funktion neu zu schreiben, so dass die Auswertung der Reihenfolge der Operationen folgt?

Vielen Dank im Voraus!

Answer 1

Es ist ein einfaches Problem, wenn Sie es betrachten.

Sie sind mit vier 4er und drei Operatoren dazwischen eingeschränkt, dh Sie kennen Ihren Suchraum bereits. Eine Lösung besteht also darin, den vollständigen Suchraum zu erzeugen, der O (n^3) = 4^3 = 64 Gesamtgleichungen ist, wobei n die Anzahl der Operatoren ist. Halten Sie die Antwort auf diese Lösungen als <key, value> Paar, so dass bis zum Eingang des Testfalls O (1) nachschlagen.

Schrittweise würden Sie tun.

1. komplette Sequenz generieren und speichern sie als Schlüssel, Wert-Paare
2. Nehmen Eingabe von Testfällen
3. Überprüfen Sie, ob Schlüssel vorhanden ist, wenn ja die Reihenfolge drucken, sonst drucken, dass die Sequenz nicht
existiert
4. Lösung würde 64 * 1000 Operationen nehmen, die leicht mit in einem zweiten berechnet werden kann und würde Zeitlimit überschritten Fehler vermeiden, die in der Regel diese Wettbewerbe

in kodierter Form haben (das meiste davon ist nicht vollständig):

// C++ Syntax 
map<int, string> mp; 

void generateAll() { 
    // generate all equations 
} 

void main() { 
    generateAll(); 

    int n, t; scanf("%d", &t); 
    while (t--) { 
     scanf("%d", &n); 

     if (mp.find(n) != mp.end()) 
      // equation exists to the input 
     else 
      // equation doesn't exist for the input 
    } 
}