verzwickte Aufgabe..bitte mal angucken

[xMänneken]

Ein Kollege und ich sitzen gerade an einer verzwicktnen Aufgabe:

Das Quadrat einer 5stelligen Zahl ergibt eine 9stellige Zahl. In dem Ergebnis soll jede Ziffer (1,2,3,4,5,6,7,8,9) nur einmal vorkommen. Es gibt 30 Möglichkeiten, es soll eine Klasse geschrieben werden, die diese Zahlen findet und ausgibt. Hinweis: Keine langen Abfragen im Programm.

Ausgabe:
1. Zahl: zahl * zahl = ergebnis
...
...
30. Zahl: zahl * zahl = ergebnis

Also bisher sind wir soweit, das wir alle Quadrate der 5stelligen Zahlen (von 10000 bis 99999) ausrechnen und diese dann mit der Funktion ultoa in einen String kopieren. Mit Hilfe des String können wir nun die einzelnen Stellen vergleichen...das artet aber in die besagten langen Abfragen aus

Wir hängen hier nun schon seit Stunden und uns fällt nix mehr ein..bestimmt war unser Ansatz schon falsch
Hat wer eine Idee ? Wir wollen keine fertig programmierte Lösung, nur einen Weg bzw. Ansatz.

Danke!!

[witte_]

Also ich würde die Zeichen im String sortieren und dann mit std::mismatch gegen "0123456789" testen.

[Nexus]

Was man tun könnte, ohne in Strings umzuwandeln, wäre bei der Zahl (als Integer) ganz vorne anzufangen und Stelle für Stelle durchzuarbeiten.

Hat man z.B. die Zahl 245367849, so dividiert man zuerst durch 100000000 (10^8), erhält also 2 (die erste Ziffer). Dann 2*10^8 von der Anfangszahl subtrahieren, also hat man noch 45367849. Anschliessend kann man durch 10000000 (10^7) dividieren und erhält die nächste Ziffer (4). So machst du immer weiter (die einzelnen Ziffern speicherst du am besten in einem Array) bis zur letzten Ziffer. Währenddessen kannst du ja überprüfen, ob eine Ziffer bereits einmal im Array vorkommt.

Jedoch ist das nur gerade eine spontane Lösung, die mir eingefallen ist, keine Ahnung, ob sie deinen Anforderungen ("keine langen Abfragen") genügt
Ich kenne jedoch std::mismatch nicht; gut möglich, dass es damit viel einfacher geht. Von der Performance her kann ich deshalb auch nichts sagen.

[Don Quijote]

mich würde interessieren, was du unter langen Abfragen verstehst, denn mit 2 zeilen Code ist das Problem bestimmt nicht zu lösen.

Tipp: nur die Quadrate der Zahlen 10000-31622 berechnen, der rest hat mehr wie 9 stellen.

Ich bin mir nicht zu 100% sicher, ob die gewünschten zahlen dabei herauskommen, aber ich würde folgendermaßen vorgehen.

Die Quadrate berechnen und dann die einzelnen Stellen der Ergebnisse miteinander multiplizieren. Der einzige Vergleich, der gemacht werden muss, ist der, dass man vor dem Multiplizieren prüfen muss, ob die jeweilige stelle 0 ist. (-> dann natürlich nicht multiplizieren)

Die Ergebnisse in einem Feld speichern. Jetzt vergleichen, welche Ergebnisse mit 362880 übereinstimmen und die entsprechenden Anfangszaheln ausgeben.

[xMänneken]

witte_ schrieb:

Also ich würde die Zeichen im String sortieren und dann mit std::mismatch gegen "0123456789" testen.

Prüft mismatch dann nicht nur gegen "123456789" ?
Lösungen wie "879546312" sind ja auch richtig, solange jede Zifferr von 1-9 nur einmal vorkommt.

[witte_]

xMänneken schrieb:

witte_ schrieb:

Also ich würde die Zeichen im String sortieren und dann mit std::mismatch gegen "0123456789" testen.

Prüft mismatch dann nicht nur gegen "123456789" ?
Lösungen wie "879546312" sind ja auch richtig, solange jede Zifferr von 1-9 nur einmal vorkommt.

Nein, die Zeichen müssten erst in einem assoziativen Container sortiert werden, z.B. std::set. Da jedes Zeichen ja genau einmal da sein muss, muesste die Länge dieses#s set genau 10 Elemente enthalten. Vergiss std::mismatch.

[Don06]

Ihr sucht eine 9-stellige Zahl, die alle 10 Ziffern enthält?
Wenn ich davon ausgehe, dass ihr eine 10-stellige Zahl sucht, finde ich 58 Lösungen.

Gruß
Don06

[camper]

wie alle 10 Ziffern in einer nur 9stelligen Zahl vorkommen sollen, erschließt sich mir nicht, falls doch 10stellige Zahlen gesucht sind, kann man dadurch schon einmal die zu durchsuchenden Zahlen eingrenzen:
kleinste interessante 10stellige Zahl: 1023456789 -> untere Grenze 31992
größte interessante 10stellige Zahl: 9876543210 -> obere Grenze 99380
zudem haben alle diese 10stelligen Zahlen die Quersumme 45, sind also durch 9 teilbar, die gesuchten 5stelligen Zahlen müssen also durch 3 teilbar sein. Damit muss man nur von 31992 bis 99378 (einschließlich) jede dritte Zahl untersuchen.

Edit: aha, die Aufgabe wurde also korrigiert, entsprechend ergibt sich:
sqrt(123456789) -> 11112
sqrt(987654321) -> 31426
und wieder nur jede dritte Zahl untersuchen.
Die Überprüfung der Zahl selbst kann man auf verschiedene Weise durchführen, strings sind mit Sicherheit eine schlechte Wahl aus Performancesicht. Zur Demonstration kann man es nat. so machen. Sinnvoller ist zum Beispiel ein bitset, dass man füllt, während die Zahl in ihre Ziffern zerlegt wird, etwa:

bool check_digits(long long n)
{
    bool digits[10] = { true };
    for ( int i = 0; i < 9; ++i )
    {
        int j = n % 10;
        if ( digits[j] )
            return false;
        digits[j] = true;
        n /= 10;
    }
    return n == 0;
}

[xMänneken]

Sorry, alle Ziffern ausser 0, also 1- 9 sollen in der neun-stelligen Zahl vorkommen.

@Don: gibts da eine Formel wie man die Möglichkeiten rausbekommt oder wie bist Du so schnell auf die 58 gekommen ?

[camper]

siehe Edit oben

[queer_boy]

erstens mal müsst ihr nicht bis 99999 zählen, sondern nur bis ceil(sqrt(987654321)) - das ist 31426, womit ihr euch immerhin schon ein drittel aller abfragen spart.

und schließlich könnt ihr den ergebnisstring, den ihr bekommt, sortieren und einfach mit "123456789" auf gleichheit vergleichen.

/edit: zu spät. und camper hat natürlich gleich eine viel komplettere lösung ^^'

[Nexus]

Hehe, mein Beitrag ist natürlich untergegangen unter den Mathematikern hier^^
Aber eure Methode würde nicht funktionieren, wenn man z.B. eine 7-stellige Zahl überprüfen sollte und alle Ziffern verschieden sein sollten, oder? Sie basiert ja auf der "Schönheit" der Zahl 123456789 und ihren Zifferpermutationen. Ich frage nur, im Falle, dass man eine möglichst "portable" Anwendung gewährleisten will.