問題:1ペンス、2ペンス、5ペンス、10ペンス、20ペンス、50ペンス、1ポンド、2ポンド硬貨を用いて2ポンドにする方法は何通りあるか。
二日間これにかかりきりでこっちお留守
小沢さんも気をもませる割には割りと呑気なのかなとか 油断しまくり。
できたプログラムがこれだ。
100 LET SUM=0
110 LET ANS=8+99+39+19+9+3+1+19+19+9+3+1+19+9+3+1+9+3+1+1+1+1
115 PRINT ANS
120 LET SUM=0
125 READ A,B
130 IF A=12 THEN
135 PRINT ANS
137 GOTO 300
139 END IF
150 LET J=1
155 LET SUM=SUM+B*J
160 LET SUM=SUM+A
170 IF SUM>=200 THEN GOTO 220
180 LET ANS=ANS+1
200 GOTO 160
210 REM
220 LET J=J+1
230 IF J>INT((200-A)/B) THEN GOTO 120
240 LET I=1
250 LET SUM=0
260 GOTO 155
300 RESTORE 4000
310 LET SUM=0
315 READ A,B,C
320 IF A=70 THEN
330 PRINT ANS
340 GOTO 600
350 END IF
360 LET K=1
370 LET J=1
380 LET SUM=SUM+C*K
390 LET SUM=SUM+B*J
400 LET SUM=SUM+A
410 IF SUM>=200 THEN GOTO 450
420 LET ANS=ANS+1
430 GOTO 400
440 REM
450 LET J=J+1
460 IF J>INT((200-A-C)/B) THEN GOTO 500
470 LET SUM=0
480 GOTO 380
500 LET K=K+1
510 IF K>INT((200-A-B)/C) THEN GOTO 310
520 LET SUM=0
530 GOTO 370
600 RESTORE 5000
604 LET SUM=0
610 READ A,B,C,D
620 IF A=19 THEN
630 PRINT ANS
640 GOTO 900
650 END IF
660 LET L=1
670 LET K=1
680 LET J=1
690 LET SUM=SUM+D*L
700 LET SUM=SUM+C*K
710 LET SUM=SUM+B*J
720 LET SUM=SUM+A
730 IF SUM>=200 THEN GOTO 770
740 LET ANS=ANS+1
750 GOTO 720
760 REM
770 LET J=J+1
780 IF J>INT((200-A-C-D)/B) THEN GOTO 810
790 LET SUM=0
800 GOTO 690
810 LET K=K+1
820 IF K>INT((200-A-B-D)/C) THEN GOTO 860
830 LET SUM=0
840 GOTO 680
860 LET L=L+1
870 IF L>INT((200-A-B-C)/D) THEN GOTO 604
880 LET SUM=0
890 GOTO 670
900 RESTORE 6000
910 LET SUM=0
920 READ A,B,C,D,E
930 IF A=4 THEN
940 PRINT ANS
950 GOTO 1300
960 END IF
970 LET M=1
980 LET L=1
990 LET K=1
1000 LET J=1
1010 LET SUM=SUM+E*M
1020 LET SUM=SUM+D*L
1030 LET SUM=SUM+C*K
1040 LET SUM=SUM+B*J
1050 LET SUM=SUM+A
1070 IF SUM>=200 THEN GOTO 1100
1080 LET ANS=ANS+1
1090 GOTO 1050
1100 LET J=J+1
1110 IF J>INT((200-A-C-D-E)/B) THEN GOTO 1150
1120 LET SUM=0
1130 GOTO 1010
1140 REM
1150 LET K=K+1
1160 IF K>INT((200-A-B-D-E)/C) THEN GOTO 1200
1170 LET SUM=0
1180 GOTO 1000
1190 REM
1200 LET L=L+1
1210 IF L>INT((200-A-B-C-E)/D) THEN GOTO 1250
1221 LET SUM=0
1230 GOTO 990
1240 REM
1250 LET M=M+1
1260 IF M>INT((200-A-B-C-D)/E) THEN GOTO 910
1270 LET SUM=0
1280 GOTO 980
1300 RESTORE 7000
1310 LET SUM=0
1320 READ A,B,C,D,E,F
1330 IF A=6 THEN
1340 PRINT ANS
1350 STOP
1360 END IF
1370 LET N=1
1380 LET M=1
1390 LET L=1
1400 LET K=1
1410 LET J=1
1420 LET SUM=SUM+F*N
1430 LET SUM=SUM+E*M
1440 LET SUM=SUM+D*L
1450 LET SUM=SUM+C*K
1460 LET SUM=SUM+B*J
1470 LET SUM=SUM+A
1480 IF SUM>=200 THEN GOTO 1520
1490 LET ANS=ANS+1
1500 GOTO 1470
1510 REM
1520 LET J=J+1
1530 IF J>INT((200-A-C-D-E-F)/B) THEN GOTO 1570
1540 LET SUM=0
1550 GOTO 1420
1560 REM
1570 LET K=K+1
1580 IF K>INT((200-A-B-D-E-F)/C) THEN GOTO 1610
1590 LET SUM=0
1600 GOTO 1410
1610 LET L=L+1
1620 IF L>INT((200-A-B-C-E-F)/D) THEN GOTO 1660
1630 LET SUM=0
1640 GOTO 1400
1650 REM
1660 LET M=M+1
1670 IF M>INT((200-A-B-C-D-F)/E) THEN GOTO 1700
1680 LET SUM=0
1690 GOTO 1390
1700 LET N=N+1
1710 IF N>INT((200-A-B-C-D-E)/F) THEN GOTO 1310
1720 LET SUM=0
1730 GOTO 1380
3000 DATA 2,5,2,10,2,20,2,50,2,100,5,10,5,20,5,50,5,100
3100 DATA 10,20,10,50,10,100,20,50,20,100,50,100,12,21
4000 DATA 2,5,10,2,5,20,2,5,50,2,5,100,5,10,20,5,10,50
4100 DATA 5,10,100,5,20,50,5,20,100,5,50,100
4200 DATA 10,20,50,10,20,100,10,50,100,20,50,100,70,12,21
5000 DATA 2,5,10,20,2,5,10,50,2,5,10,100,2,10,20,50,2,10,20,100
5100 DATA 2,10,50,100,2,20,50,100,5,10,20,50,5,10,20,100
5200 DATA 5,20,50,100,10,20,50,100,19,70,12,21
6000 DATA 2,5,10,20,50,2,5,10,20,100,2,10,20,50,100
6100 DATA 5,10,20,50,100,4,19,70,12,21
7000 DATA 2,5,10,20,50,100,6,4,19,70,12,21
END
ちなみにJavascriptだと
javascript:(function f(n,k,r,i){if(k==7)return 1;for(r=i=0;n>=0;n-=[200,100,50,20,10,5,2][k])r+=f(n,k+1);return r})(200,0)
で済むらしいお。
BASICでももっと短くできるが 速さの限界に挑戦するとこうなる。
ちなみに値が10000くらいずれて出るのでこのあとバグとりす
3000 DATA 2,5,2,10,2,20,2,50,2,100,5,10,5,20,5,50,5,100
3100 DATA 10,20,10,50,10,100,20,50,20,100,50,100,12,21
4000 DATA 2,5,10,2,5,20,2,5,50,2,5,100,2,10,20,2,10,50,2,10,100
4050 DATA 2,20,50,2,20,100,2,50,100,5,10,20,5,10,50
4100 DATA 5,10,100,5,20,50,5,20,100,5,50,100
4200 DATA 10,20,50,10,20,100,10,50,100,20,50,100,70,12,21
5000 DATA 2,5,10,20,2,5,10,50,2,5,10,100,2,5,20,50,2,5,20,100
5050 DATA 2,5,50,100,2,10,20,50,2,10,20,100
5100 DATA 2,10,50,100,2,20,50,100,5,10,20,50,5,10,20,100
5200 DATA 5,10,50,100,5,20,50,100,10,20,50,100,19,70,12,21
6000 DATA 2,5,10,20,50,2,5,10,20,100,2,10,20,50,100
6100 DATA 5,10,20,50,100,4,19,70,12,21
7000 DATA 2,5,10,20,50,100,6,4,19,70,12,21
修正後
あと59。