| 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
|
|
|
