Autor |
Beitrag |
Xion
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: Di 01.04.14 14:06
Das stimmt nur, wenn man sich genau auf die Aufgabenstellung bezieht. Dort ist die Anzahl der Frames vorgegeben, und damit ist die Laufzeit konstant (übrigens auch im naiven Fall, alle Möglichkeiten durchzuprobieren).
Wenn man aber, wie Mathematiker sagte, bestimmen will, wielange die Berechnung in etwa bei 1000 Frames dauern würde, dann ist die Komplexität auf jeden Fall relevant. Natürlich könnte man wieder sagen, sie ist konstant, aber das hilft einem nicht weiter
Sind n die Anzahl der Frames, dann ergibt sich die Laufzeit als:
O(66 + n*(30*n*66)) = O(n^2)
Da sowohl die Anzahl der Iterationen, als auch die Anzahl der Punkte von der Anzahl der Frames abhängig ist, ist dies ein Algorithmus mit quadratischer Laufzeit. Ganz klassisch für dynamische Programmierung, bei der oft eine zweidimensionale Tabelle (Frames x Punkte) gefüllt wird.
Bei 1000 Frames käme man also in eine Region von 2000 Millionen Möglichkeiten. Das sollte kein Problem darstellen.
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 01.04.14 14:45
Hallo,
Xion hat folgendes geschrieben : | Bei 1000 Frames käme man also in eine Region von 2000 Millionen Möglichkeiten. Das sollte kein Problem darstellen. |
Ich habe aus Spaß einmal 100 bis 1000 Frames durchgerechnet.
int64 musste ich gegen extended tauschen und den Stack auf das 4fache erhöhen. Andernfalls wollte er die Felder nicht mehr nehmen.
Meine erste Vermutung (1s! ) war zu optimistisch, aber es ist dennoch in vertretbarer Zeit machbar. Auf die Ausgabe der Einzelwerte habe ich aber verzichtet.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39:
| 100 Frames Summe 3,90135663009767E182 Zeit 0,4 s
200 Frames Summe 3,51244235889393E364 Zeit 1,6 s
300 Frames Summe 3,16229775800925E546 Zeit 3,5 s
400 Frames Summe 2,84705799797363E728 Zeit 6,2 s
500 Frames Summe 2,56324352230777E910 Zeit 9,7 s
600 Frames Summe 2,30772164084085E1092 Zeit 14,0 s
700 Frames Summe 2,07767195167253E1274 Zeit 19,1 s
800 Frames Summe 1,8705552101136E1456 Zeit 24,9 s
900 Frames Summe 1,68408530098625E1638 Zeit 31,6 s
1000 Frames Summe 1,51620400491987E1820 Zeit 39,0 s |
Trägt man auf der Abszisse die Frames in 100 ab und auf der Ordinate die Laufzeit, so ergibt sich eine "schöne" quadratische Kurve.
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
|
|
jackle32
Beiträge: 183
Erhaltene Danke: 7
Win7
Delphi XE5 Starter, RAD Studio XE7 Pro
|
Verfasst: Di 01.04.14 20:29
Hallo nochmal,
ich komme mir ja schon langsam wie so ein Dauernörgler vor, aber eine kleine Anmerkung hab ich doch wieder.
Und zwar hierzu:
Mathematiker hat folgendes geschrieben : | Hallo,
Im 10.Frame gibt es 55 Möglichkeiten Pins stehen zu lassen, ohne einen weiteren Wurf. 10 Möglichkeiten für einen Spare mit einem weiteren Wurf mit 11 möglichen Ausgängen. Der 1 Strike hat 2 Würfe zur Folge mit je 11 Ausgängen.
Damit gibt es im 10.Frame 55 + 10*11 + 1*11*11 = 286 Möglichkeiten und insgesamt für ein Bowling-Game
|
Ich kann deinen Argumenten nicht ganz folgen. Wo kommen die 55 her? Gleich noch vorne weg, meine Ursprüngliche Behauptung mit 241 war auch falsch, da hatte ich mich einfach verzählt.
Jetzt zu der neuen Berechnung:
Für die ersten beiden Würfe gibt es die üblichen 66 Möglichkeiten + 10 wegen der Sonderregelung, dass auch bei einem Strike im erste Wurf noch ein zweiter folgen darf, also 76 Möglichkeiten.
Hinzu kommen im Falle eines Strikes im ersten oder Spare im Zweiten ein dritter Wurf und hier wird es jetzt auch schwieriger. Da die Annahme bei Strike im ersten Wurf des 10. Frames mit zwei vollen 11 Möglichkeiten nicht richtig ist.
Hier nur beispielhaft ein Fall wie ich meine:
1.Wurf: Strike
2. Wurf: 5
Somit bleiben für den dritten Wurf nur die Möglichkeiten: 0,1,2,3,4 oder Spare. Also 6 Möglichkeiten.
Es gibt nach den ersten beiden Würfen 12 Varianten wo im dritten Wurf 11 Möglichkeiten vorhanden sind. Das sind 132 Möglichkeiten.
So und dann gibt es wie oben beschrieben noch die Fälle in denen im ersten Wurf aber nicht im zweiten ein Strike geworfen wurde. Das sind dann nochmal 54 Möglichkeiten. (Markierung in Tabelle)
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
| 1. Wurf | 2. Wurf | 3. Wurf | Möglichekeiten X 0 0-X 11
X 1 0-8, Y 10 X 2 0-7, Y 9 X 3 0-6, Y 8 X 4 0-5, Y 7 X 5 0-4, Y 6 X 6 0-3, Y 5 X 7 0-2, Y 4 X 8 0-1, Y 3 X 9 0, Y 2
X X 0-X 11 |
Somit komme ich auf
76 + 132 + 54 = 262 Möglichkeiten
Was auch noch nicht ganz passen kann, ist das es mehr als eine Möglichkeit gibt 298 Punkte zu erreichen. Für die Punkte von 291 bis 300 gibt es nur jeweils eine Möglichkeit diese zu erreichen.
Und zwar sind diese Punkte nur möglich bei 11 Strikes und 1 bis 10 Punkte im letzten Wurf. Sobald vorher eine Strike fehlt, fehlen in der Summe sofort mindestens 10 Punkte und ich kann nur noch höchstens 290 Punkte erreichen. (Klar ist natürlich wenn der Strike in einem der ersten Frames fehlt, fehlen sofort weit mehr als 10 Punkte).
So jetzt genug geredet, ich bin mir sicher, dass wird auch wieder kein Problem für euch darstellen.
Gruß,
Jack
_________________ Es gibt keine dummen Fragen, nur dumme Antworten.
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Di 01.04.14 21:27
Hallo,
also irgendwie habe ich Probleme diesen 10.Frame zu verstehen. Vielleicht stimmt es jetzt.
Also: Für den 1.Wurf im 10.Frame gibt es 11 Möglichkeiten. Einer davon ist der Strike. Für die Restlichen ergibt sich kein Spare, wenn
Quelltext 1: 2: 3: 4: 5: 6:
| 1.Wurf ... 2.Wurf 0 ... 0 bis 9 1 ... 0 bis 8 2 ... 0 bis 7 ... 9 ... 0 |
Das sind insgesamt 55 Möglichkeiten, die nicht zum Spare führen. Die verbleibenden 10 führen zum Spare.
Nach dem Spare folgt noch 1 Wurf mit 11 Möglichkeiten, d.h. insgesamt für den Spare = 10*11 Möglichkeiten.
Nach dem Strike folgt ein 1.Wurf mit 11 Möglichkeiten. 10 davon räumen nicht ab und ergeben für den 2. weiteren Wurf
Quelltext 1: 2: 3: 4: 5: 6:
| 1.Wurf ... 2.Wurf 0 ... 0 bis 10 1 ... 0 bis 9 2 ... 0 bis 8 ... 9 ... 0 bis 1 |
mit insgesamt 65 Möglichkeiten. Sollte der 1.Zusatzwurf ein Strike sein, wird neu aufgesetzt, mit 11 Wurfmöglichkeiten im 2.Zusatzwurf. Für den Strike werden das insgesamt 65 + 1 * 11 Möglichkeiten.
Fügen wir alles zusammen, gibt es im 10.Frame
55 + 10·11 + 65 + 11 = 241 Möglichkeiten. Und damit war Deine erste Bemerkung richtig. Ich hatte mich vertan.
Für das ganze Bowling-Game also
Quelltext 1:
| 11^9·6^9·(55 + 10·11 + 65 + 11) = 5726805883325784576 |
Jetzt müsste es stimmen.
Und damit wird für den Quelltext:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136:
| procedure TForm1.Button15Click(Sender: TObject); var feld,feld2:array[0..300,0..3] of int64; pu,nr,strikespare:integer; abbruch:integer; frames:integer; i,j,m:integer; faktor,summe:int64; summand:int64; t1x,t2x,frequenz : TLargeInteger; laeufe:integer; moeglich:integer; procedure wurf(nr:integer;moeglich:integer;pu:integer;strikespare:integer); var i,zusatz,doppelt:integer; begin if nr>abbruch then begin feld[pu+summand,strikespare]:=faktor+feld[pu+summand,strikespare]; exit end;
for i:=0 to moeglich do begin if strikespare>0 then begin zusatz:=i; doppelt:=0; if strikespare>2 then begin zusatz:=2*i; doppelt:=1 end; if odd(nr) then begin if i=moeglich then wurf(nr+2,10,pu+i+zusatz,strikespare+1-doppelt) else wurf(nr+1,10-i,pu+i+zusatz,strikespare-1-doppelt) end else begin if i=moeglich then wurf(nr+1,10,pu+i+zusatz,strikespare-doppelt) else wurf(nr+1,10,pu+i+zusatz,strikespare-1-doppelt) end; end else begin if odd(nr) then begin if i=moeglich then wurf(nr+2,10,pu+i,strikespare+2) else wurf(nr+1,10-i,pu+i,strikespare) end else begin if i=moeglich then wurf(nr+1,10,pu+i,strikespare+1) else wurf(nr+1,10,pu+i,strikespare) end; end; end end; begin listbox1.clear;
frames:=10; nr:=1; pu:=0; strikespare:=0; fillchar(feld,sizeof(feld),0); fillchar(feld2,sizeof(feld2),0); abbruch:=2; QueryPerformanceFrequency (frequenz); QueryPerformanceCounter (t1x); faktor:=1; summand:=0; wurf(nr,10,pu,strikespare);
for laeufe:=1 to frames-1 do begin feld2:=feld; fillchar(feld,sizeof(feld),0); for j:=0 to 30*frames do for m:=0 to 3 do begin if feld2[j,m]>0 then begin faktor:=feld2[j,m]; summand:=j; nr:=1; pu:=0; strikespare:=m; wurf(nr,10,pu,strikespare); end; end; end;
feld2:=feld; for j:=0 to 270 do begin if (feld2[j,3]>0) then begin dec(feld[j,0],feld2[j,3]); for i:=0 to 10 do begin if i=10 then moeglich:=10 else moeglich:=10-i; for m:=0 to moeglich do begin inc(feld[j+m+2*i,0],feld2[j,3]) end; end; end; if (feld2[j,2]>0) then begin dec(feld[j,0],feld2[j,2]); for i:=0 to 10 do begin if i=10 then moeglich:=10 else moeglich:=10-i; for m:=0 to moeglich do begin inc(feld[j+m+i,0],feld2[j,2]) end; end; end; if feld2[j,1]>0 then begin dec(feld[j,0],feld2[j,1]); for i:=0 to 10 do inc(feld[j+i,0],feld2[j,1]); end; end; QueryPerformanceCounter (t2x); summe:=0; for j:=0 to 30*frames do begin listbox1.items.add(inttostr(j)+#9+inttostr(feld[j,0]+feld[j,1]+feld[j,2]+feld[j,3])); summe:=summe+feld[j,0]+feld[j,1]+feld[j,2]+feld[j,3]; end; listbox1.items.insert(0,inttostr(frames)+' Frames'); listbox1.items.insert(0,'Summe '+inttostr(summe)); listbox1.items.insert(0,'Zeit '+FormatFloat('0.0 ms',1000*(t2x-t1x)/frequenz)); application.processmessages; listbox1.items.savetofile('Lrekursiv.txt'); end; |
als Endergebnis folgt damit
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187: 188: 189: 190: 191: 192: 193: 194: 195: 196: 197: 198: 199: 200: 201: 202: 203: 204: 205: 206: 207: 208: 209: 210: 211: 212: 213: 214: 215: 216: 217: 218: 219: 220: 221: 222: 223: 224: 225: 226: 227: 228: 229: 230: 231: 232: 233: 234: 235: 236: 237: 238: 239: 240: 241: 242: 243: 244: 245: 246: 247: 248: 249: 250: 251: 252: 253: 254: 255: 256: 257: 258: 259: 260: 261: 262: 263: 264: 265: 266: 267: 268: 269: 270: 271: 272: 273: 274: 275: 276: 277: 278: 279: 280: 281: 282: 283: 284: 285: 286: 287: 288: 289: 290: 291: 292: 293: 294: 295: 296: 297: 298: 299: 300: 301: 302: 303: 304:
| Zeit 3,1 ms Summe 5726805883325784576 10 Frames 0 1 1 20 2 210 3 1540 4 8855 5 42504 6 177100 7 657800 8 2220075 9 6906900 10 20030010 11 54627084 12 141116637 13 347336412 14 818558424 15 1854631380 16 4053948342 17 8574134256 18 17590903116 19 35084425512 20 68153183370 21 129156542039 22 239128282128 23 433093980298 24 768175029950 25 1335679056261 26 2278764308864 27 3817721269708 28 6285424931278 29 10176048813473 30 16210652213304 31 25423690787719 32 39274771758064 33 59789973730461 34 89736657900900 35 132834787033075 36 194006223597572 37 279661205716974 38 398018151390200 39 559449136091831 40 776838931567572 41 1065940588576732 42 1445705502357343 43 1938561121705315 44 2570605432880903 45 3371684590465908 46 4375319099346208 47 5618445228564793 48 7140942201229333 49 8984922304030443 50 11193770355829009 51 13810930667765157 52 16878453276117746 53 20435326129713654 54 24515635362932954 55 29146610869639549 56 34346628376654913 57 40123251227815383 58 46471404549689351 59 53371780703441318 60 60789577452586487 61 68673668434334934 62 76956298564663402 63 85553384395717227 64 94365480254213528 65 103279445170253902 66 112170812747354087 67 120906827121834566 68 129350064451661348 69 137362512979745598 70 144809940796620325 71 151566341291631624 72 157518221668013078 73 162568486673578693 74 166639683923175378 75 169676402232105648 76 171646676234883305 77 172542309343731946 78 172378125687965848 79 171190226627438257 80 169033430825208027 81 165978103316094584 82 162106654714921075 83 157509948809043576 84 152283892386077931 85 146526364181517039 86 140334651650668803 87 133803399444707801 88 127023103852577896 89 120079021507938035 90 113050455155943519 91 106010240661754449 92 99024411737621323 93 92151904402003308 94 85444345654857875 95 78945863453573001 96 72693023944120045 97 66714881583314335 98 61033240145235763 99 55663091133973346 100 50613244155051856 101 45887089510794122 102 41483436078768079 103 37397371704961189 104 33621048067136846 105 30144388614623696 106 26955619314626157 107 24041709119775647 108 21388640692533960 109 18981680119465910 110 16805547548715206 111 14844654231857239 112 13083276623221517 113 11505812292077067 114 10096971927616045 115 8842020009154293 116 7726929590817265 117 6738528470417086 118 5864552560171552 119 5093653838062639 120 4415377510495980 121 3820097597373727 122 3298981687014508 123 2843905747206868 124 2447444695948898 125 2102793053565659 126 1803790254604935 127 1544848145184291 128 1320992367181792 129 1127775864826813 130 961294388171457 131 818085023387881 132 695128788327698 133 589753122859383 134 499630252931260 135 422696870992462 136 357151976811922 137 301400973036441 138 254052574077937 139 213889601295347 140 179862464456172 141 151065169242834 142 126722015973414 143 106169469752641 144 88840622360686 145 74252067274687 146 61990415093876 147 51701385089887 148 43082666091665 149 35870481552300 150 29843343433392 151 24808172866872 152 20607116162379 153 17101443169235 154 14181008701762 155 11747089496422 156 9723545122578 157 8040378083433 158 6644452641044 159 5486702080236 160 4529003381568 161 3736165201688 162 3081105018158 163 2539255963377 164 2091793858275 165 1721930513702 166 1416734360140 167 1164733232308 168 957190045595 169 785911852914 170 645295369580 171 529489941608 172 434606120455 173 356481490646 174 292487050484 175 239755303889 176 196550315542 177 160954253448 178 131791387388 179 107847709116 180 88241591630 181 72162948863 182 59038079745 183 48284335855 184 39509743432 185 32308399043 186 26423428886 187 21582203262 188 17624621529 189 14368737009 190 11720626558 191 9552812749 192 7790240907 193 6351933169 194 5185250585 195 4232118751 196 3457204258 197 2821392492 198 2302090127 199 1874802017 200 1526313637 201 1239515641 202 1007719386 203 818568928 204 666193896 205 542061609 206 442072320 207 360234562 208 293886739 209 239045260 210 194337731 211 157306293 212 127325163 213 102799565 214 83194097 215 67300605 216 54691522 217 44477808 218 36317458 219 29606794 220 24117404 221 19554213 222 15820964 223 12736481 224 10258846 225 8244157 226 6659561 227 5381526 228 4385243 229 3576841 230 2930385 231 2376760 232 1924226 233 1541327 234 1231527 235 975760 236 777090 237 617547 238 498228 239 404981 240 335065 241 275998 242 226966 243 183727 244 148442 245 117291 246 93525 247 73010 248 57960 249 45826 250 37965 251 31193 252 26131 253 21406 254 17422 255 13613 256 10696 257 7975 258 6005 259 4374 260 3534 261 3016 262 2635 263 2264 264 1933 265 1603 266 1323 267 1045 268 810 269 585 270 406 271 277 272 258 273 227 274 206 275 173 276 150 277 115 278 90 279 53 280 26 281 15 282 15 283 14 284 14 285 13 286 13 287 12 288 12 289 11 290 11 291 1 292 1 293 1 294 1 295 1 296 1 297 1 298 1 299 1 300 1 |
Ich kann nur hoffen, dass es jetzt stimmt.
Auf jeden Fall werde ich keine Bowling-Bahn mehr betreten. Das ist mir alles viel zu kompliziert.
Beste Grüße
Mathematiker
Für diesen Beitrag haben gedankt: jackle32
|
|
jackle32
Beiträge: 183
Erhaltene Danke: 7
Win7
Delphi XE5 Starter, RAD Studio XE7 Pro
|
Verfasst: Di 01.04.14 21:53
Hallo,
also ich hab jetzt auch nochmal nachgezählt und hab gemerkt, wenn ich keine Möglichkeiten doppelt zähle stimmen meine Ursprünglichen 241.
Also bleibt es bei den angesprochenen 5726805883325784576 Möglichkeiten.
Jetzt sehen alle Werte auf jeden Fall plausibel aus.
Bin doch immer beeindruckt wie schnell und ergiebig diese Forum ist.
Danke an alle die Mitdiskutiert haben.
@Mathematiker:
Sorry wenn ich dir jetzt das bowlen vermiest habe, aber immerhin weißt du jetzt wann du statistisch betrachtet gut spielst
Gruß,
Jack
_________________ Es gibt keine dummen Fragen, nur dumme Antworten.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
|