Beitrag
von Giga » 22. Aug 2012, 17:31
Erstmal vorraus - ich zumindest komme auch grad ständig durcheinander mit Ziffern und Höchstwert. Daher nochmal zur Erinnerung - Höchstwert 5 bedeutet 6 Ziffern.
Deswegen sollten wir hier kurz klären, wovon wir ausgehen. Andi sagt ja nach obiger Rechnung, dass er von 5 Ziffern und 5 Stellen ausgeht (heißt, Zahlen von 0-4 auf 5 Stellen). Das hieße dann aber, dass es weitaus weniger Versuche benötigen würde als in der Tabelle (während seine Rechnung durchaus stimmt), da bereits bei 0 0 0 0 3 feststeht, ob die letzte Stelle eine 4 oder eine 3 ist. Dafür braucht er dann in der Tat im Worst Case 21 Schritte und der Worst Case ist auch 4 4 4 4 4, aber seine Tabelle im vorletzten Post ergibt nicht soviel Sinn^^
00000-00004 = 5 Schritte (letzte Stelle entweder 4 oder 5, aber das weiß man jetzt)
00004-00044 = 5 Schritte (vorletzte Stelle entweder 4 oder 5, aber das weiß man jetzt)
...
04444-44444 = 5 Schritte (erste Stelle entweder 4 oder 5, aber das weiß man jetzt)
Und erst DANN steht die richtige Lösung fest, weil erst wenn auch die erste Stelle eindeutig bestimmt ist, ist man fertig. Bis dahin sind es 25 Schritte, es fehlt aber noch der finale Schritt, wo man die richtige Kombination (5 5 5 5 5 in diesem Fall) eingibt. Daher lautet die Rechnung:
(Anzahl Ziffern -1) * (Anzahl Stellen) + 1
... wie Andi richtig angegeben hat. Kurze Erklärung noch für die, die nicht so ganz durchblicken:
Die Anzahl der Ziffern bestimmt, wieviele Ziffern man testen muss, bis man sicher weiß, welche Ziffer an einer gewissen Stelle steht. Da man aber, sobald man die vorletzte Ziffer getestet hat und das Ergebnis immer noch negativ ist, genau weiß, dass es dann ja die letzte verbliebene Ziffer ist, muss man eine Ziffer weniger testen, daher das -1. Man muss dies für jede Stelle separat machen (daher * Stellenanzahl), sobald man aber die finale Lösung hat, muss man sie noch eingeben, daher +1.
Vince Ebert hat geschrieben:Vor hundertfünfzig Jahren war man sich in der Fachwelt einig, das größte Zukunftsproblem in Großstädten werde der Pferdemist sein. Halten Sie mich für verrückt, aber Pferdemist ist derzeit nicht unser größtes Problem.
