Ok, ich denke, es kommt nix mehr rein. Herzlichen Glückwunsch onemorenerd, hier ist deine Medaille , und du bist dran, mit der nächsten Aufgabe
Programmieraufgabe zur Nacht
Einklappen
X
-
-
Meine Aufgabe ist eher was für Knobler.
Gegeben sei eine Liste (Array) mit beliebig vielen natürlichen Zahlen (ohne 0). Das letzte Element der Liste ist das Ergebnis einer Berechnung der anderen Listenelemente mit den Grundoperationen +, -, * und /.
Gesucht ist eine Formel, die jedes Listenelement 1...n-1 mindestens einmal enthält und mit den Grundoperationen so anordnet, dass das Ergebnis der Formel das Listenelement n ist oder zumindest so gut wie möglich annähert.
Ein Beispiel:
Eingabe 2,56,10,4711,90
Ausgabe (4711 / 56) + 10 - 2 = 92.125
Es gewinnt die Lösung mit der besten Annäherung an das Ergebnis und der kürzesten Formel.Zuletzt geändert von onemorenerd; 03.07.2008, 02:30.
Kommentar
-
Liste: 1,2,3
Formel: 1+2=3
Ich glaube aber auch, die Aufgabenstellung nicht ganz verstanden zu haben
Kommentar
-
Nein ...
Liste: 1,1
Formel: 1=1
Kommentar
-
Hm, ist die Aufgabe wirklich so unverständlich? Dann versuche ich es nochmal.
Es gilt ein Script zu schreiben, dem man z.B. als GET-Parameter ?in=2,56,10,4711,90 übergibt. Die letzte Zahl in dieser Reihe ist das Ergebnis einer Berechnung aus den anderen Zahlen und den Grundrechenoperationen.
Das Script soll versuchen, aus der Eingabe die ursprüngliche Berechnung zu rekonstruieren. Von dieser Berechnung ist bekannt, dass sie beliebig oft die Zeichen +, -, *, /, (, ), außerdem jede der Zahlen aus der Eingabe mindestens einmal, jedoch die letzte Zahl der Eingabe genau einmal und genau ein = enthielt.
Einige Beispiele, zuerst ein ganz einfaches:
1,2,3 => Ausgabe "1+2=3"
Das nächste Beispiel zeigt, dass jede Zahl (außer die letzte, die ist ja das Ergbnis) beliebig oft verwendet werden kann:
2,3 => Ausgabe "2+2/2=3"
Im dritten Beispiel kommen Klammern vor:
5,9,3,4,2 => Ausgabe "5+9-(3*4)=2"
Ich werde gleich noch den Code posten, mit dem ich die Lösungsvorschläge teste und bewerte. Sobald ich ihn fertig habe.
Spätestens dann sollte jeder die Aufgabe verstehen können.
Kommentar
-
Autsch. Und dafür Zeit bis Morgen früh?
Kommentar
-
Das ist doch ***** !!!
1. Das setzen der Klammern
2. Die Mehrfachverwendung der Zahlen
Treiben Rechenzeit ins Unermessliche!
Die Anzahl möglicher Kombinationen ist unbegrenzt.
Permanent muß man auf eine div durch null aufpassen.Zuletzt geändert von combie; 03.07.2008, 12:54.
Kommentar
-
Quick & Dirty. Aber ohne Nährung, immer mit dem exakten Ergebnis nach den Vorgaben
PHP-Code:<?php
$zahlen = explode(',', $_GET['in']);
$ergebnis = $zahlen[count($zahlen)-1];
$reihe = implode(' + ', array_splice($zahlen, 0, count($zahlen)-1));
$berechnung = array();
for($i = 1; $i <= $ergebnis; $i++){
$berechnung[] = "($reihe) / ($reihe)";
}
echo implode(' + ', $berechnung).' = '.$ergebnis;
?>Simploo CMS - das einfache Webseiten-Bearbeitungsprogramm
Kommentar
-
Hier die Testroutine. Ich werde mir natürlich verschiedene Testformeln ausdenken.
Beim Aufruf eurer Lösung komme ich euch entgegen. Ihr müsst die Eingabe nicht über GET holen. Ich schau mir euren Code an und fummel mir das zurecht.
PHP-Code:<?php
header('Content-Type: text/plain');
// Testcase, von mir ausgedacht.
$formel = '5+9-(3*4)';
$ergebnis = eval('return '.$formel.';');
echo "Testcase : $formel=$ergebnis\n\n";
// Eingabe für eure Scripte vorbereiten.
$zahlen = preg_split("/\+|\-|\*|\/|\(|\)|=/", $formel, -1, PREG_SPLIT_NO_EMPTY);
$zahlen = array_unique($zahlen);
shuffle($zahlen);
$eingabe = implode(',', $zahlen).','.$ergebnis;
echo "Eingabe : $eingabe\n\n";
// Aufruf eures Scripts. Whitespace wird aus der Ausgabe entfernt.
$ausgabe = file_get_contents('http://localhost/deinScript.php?in='.$eingabe);
$ausgabe = str_replace(array(' ', "\t", "\r", "\n"), '', $ausgabe);
echo "Ausgabe : $ausgabe\n\n";
// Ausgabe in Formel und Ergebnis zerlegen.
$teile = explode('=', $ausgabe);
// Prüfe Bedingung "genau ein =".
if (count($teile) !== 2)
die('FEHLER: Nicht genau ein "=".');
// Prüfe Bedingung "jede Zahl mindestens einmal".
$zahlen_ausgabe = preg_split("/\+|\-|\*|\/|\(|\)|=/", $teile[0], -1, PREG_SPLIT_NO_EMPTY);
if (count(array_diff($zahlen_ausgabe, $zahlen)) !== 0)
die('FEHLER: Nicht jede Zahl der Eingabe mindestens einmal verwendet oder unerlaubte Zeichen.');
// Prüfe Korrektheit der Lösung. Rundung auf 2 Nachkommastellen.
$ergebnis_ausgabe = round(eval('return '.$teile[0].';'), 2);
if ($ergebnis_ausgabe !== round($teile[1], 2))
die('FEHLER: Ausgabe ist nicht korrekt.');
echo "Genauigkeit: ".($ergebnis - $ergebnis_ausgabe);
?>
Kommentar
-
Die Nacht ist übrigens schon vorbei. Also verlängern wir mal bis ... keine weiteren Lösungsvorschläge mehr zu erwarten sind.
Wegen Division durch Null muss niemand aufpassen. Die Eingabe besteht aus natürlichen Zahlen ohne 0.
Und ja, es stimmt, dass die Anzahl möglicher Lösungen i.A. unbegrenzt ist. Aber es sollen ja auch nicht alle sondern nur eine Lösung bestimmt werden.
Original geschrieben von combie
1. Das setzen der Klammern
2. Die Mehrfachverwendung der Zahlen
Treiben Rechenzeit ins Unermessliche!
PHP-Code:for ($i = 1; $i < end($in); $i++)
$out .= '+'.$in[0].'/'.$in[0];
}
for ($i = 1; $i < count($in)-1; $i++) {
$out .= '+('.$in[$i].'-'.$in[$i].')';
}
echo trim($out, '+').'='.end($in);
1,2,3 => Ausgabe "1/1+1/1+1/1+(2-2)=3"
2,3 => Ausgabe "2/2+2/2+2/2=3"
5,9,3,4,2 => Ausgabe "5/5+5/5+(9-9)+(3-3)+(4-4)=2"
Diese Lösung ist zwar wunderschön linear in ihrer Laufzeit, aber leider auch in der Länge der Ausgabe, so dass man damit sicher keinen Blumentopf gewinnt. Aber es ist bewiesen, dass es geht. Und es ist auch nicht besonders schwierig.Zuletzt geändert von onemorenerd; 03.07.2008, 14:14.
Kommentar
-
Ist ja doof, wenn du deine Aufgabe postest, wenn Leute die Arbeiten müssen schon im Bettchen sind, und die Lösung dann erwartest, wenn Leute die Arbeiten müssen ... arbeiten.
Poste mal ne Reihe von Testcases. Ich hab da ne Idee, die werde ich mir zuhause mal zusammenfrickeln
Wobei das echt ne harte Nuss ist. Wenn man nicht grade einen extrem großen Algorithmus zusammenschreiben will, muss man sich auf eine der beiden Kriterien konzentrieren: Exaktes Ergebnis oder kurze Formel.Zuletzt geändert von unset; 03.07.2008, 14:29.
Kommentar
Kommentar