今回は、計算手順に従って反復計算をするようなプログラムをしてみましょう。
▼事前に読んで欲しい記事▼
再帰関数
国家試験「基本情報技術者」に必ずでる関数問題をやってみましょう。
「再帰関数」ってのは、自分自身を呼び出す関数です。
自然数nに対して、次のように再帰的に定義される関数f(n)を考える。
f(n): if n ≦1 then return 1
else return n+f(n-1)
このままプログラムを組めばOKです。
試験での手計算は下記です。
これは最も単純なケースで、もっと複雑な問題もでます。
def f(n):
print(f"# call f({n}) -> ",end="")
if n <= 1:
print(f"return 1")
return 1
else:
print(f"return {n}+f({n-1})")
return n+f(n-1)
print(f(5))# call f(5) -> return 5+f(4)
# call f(4) -> return 4+f(3)
# call f(3) -> return 3+f(2)
# call f(2) -> return 2+f(1)
# call f(1) -> return 1
15木の成長
別サイト様に問題があります。
文章が難しいと思うので、ヒント気味に書き下します。
競技プログラミングや現実問題でも理解をしっかりしないとですね。
- 0日目には、1mの木があります。
- 1日後には、0日目の1/2だけ伸びます。
- つまり1mの1/2だけ伸びて1.5ｍになる。
- 2日後には、1日目の1/3だけ伸びます。
- つまり1.5ｍの1/3だけ伸びる。
- 3日後には、2日目の1/4だけ伸びます。
- この木が100mになるには何日かかりますか？
tree = 1
for i in range(1,1000):
tree = tree*(1+1/(i+1))
print(f"{i} {tree}")
if tree >= 100:
break
print(f"{i} {tree}")1 1.5
2 2.0
3 2.5
4 3.0
5 3.5
6 4.0
7 4.5
8 5.0
9 5.5
10 6.0
11 6.5
12 7.0
13 7.5
14 8.0
15 8.5
16 9.0
17 9.5
18 10.0
19 10.5
20 11.0
21 11.5
22 12.0
23 12.5
24 13.0
25 13.500000000000002
26 14.000000000000002
27 14.500000000000004
28 15.000000000000005
29 15.500000000000007
30 16.000000000000007
31 16.500000000000007
32 17.000000000000007
33 17.500000000000007
34 18.000000000000007
35 18.500000000000007
36 19.000000000000007
37 19.500000000000007
38 20.000000000000007
39 20.500000000000007
40 21.000000000000007
41 21.500000000000007
42 22.000000000000007
43 22.500000000000007
44 23.000000000000007
45 23.50000000000001
46 24.00000000000001
47 24.50000000000001
48 25.00000000000001
49 25.50000000000001
50 26.00000000000001
51 26.50000000000001
52 27.00000000000001
53 27.500000000000014
54 28.00000000000001
55 28.50000000000001
56 29.00000000000001
57 29.500000000000007
58 30.000000000000007
59 30.500000000000007
60 31.000000000000007
61 31.500000000000007
62 32.00000000000001
63 32.50000000000001
64 33.00000000000001
65 33.50000000000001
66 34.00000000000001
67 34.50000000000001
68 35.00000000000001
69 35.50000000000001
70 36.00000000000001
71 36.50000000000001
72 37.00000000000001
73 37.50000000000001
74 38.00000000000001
75 38.50000000000001
76 39.0
77 39.5
78 40.0
79 40.5
80 41.0
81 41.5
82 42.0
83 42.5
84 43.0
85 43.5
86 44.00000000000001
87 44.500000000000014
88 45.000000000000014
89 45.500000000000014
90 46.000000000000014
91 46.500000000000014
92 47.000000000000014
93 47.500000000000014
94 48.000000000000014
95 48.50000000000002
96 49.00000000000002
97 49.500000000000014
98 50.000000000000014
99 50.500000000000014
100 51.000000000000014
101 51.500000000000014
102 52.000000000000014
103 52.500000000000014
104 53.000000000000014
105 53.50000000000002
106 54.000000000000014
107 54.500000000000014
108 55.000000000000014
109 55.500000000000014
110 56.00000000000001
111 56.50000000000001
112 57.00000000000001
113 57.50000000000001
114 58.00000000000001
115 58.50000000000001
116 59.00000000000001
117 59.50000000000001
118 60.00000000000001
119 60.50000000000001
120 61.00000000000001
121 61.5
122 61.99999999999999
123 62.49999999999999
124 62.99999999999999
125 63.49999999999999
126 63.99999999999999
127 64.49999999999999
128 64.99999999999999
129 65.49999999999999
130 65.99999999999999
131 66.49999999999999
132 66.99999999999999
133 67.49999999999999
134 67.99999999999999
135 68.49999999999999
136 68.99999999999999
137 69.49999999999999
138 69.99999999999999
139 70.49999999999999
140 70.99999999999997
141 71.49999999999997
142 71.99999999999997
143 72.49999999999997
144 72.99999999999997
145 73.49999999999997
146 73.99999999999997
147 74.49999999999997
148 74.99999999999999
149 75.49999999999999
150 75.99999999999999
151 76.49999999999999
152 76.99999999999999
153 77.49999999999999
154 77.99999999999997
155 78.49999999999997
156 78.99999999999997
157 79.49999999999997
158 79.99999999999997
159 80.49999999999997
160 80.99999999999996
161 81.49999999999996
162 81.99999999999996
163 82.49999999999996
164 82.99999999999996
165 83.49999999999996
166 83.99999999999996
167 84.49999999999996
168 84.99999999999996
169 85.49999999999996
170 85.99999999999996
171 86.49999999999996
172 86.99999999999996
173 87.49999999999996
174 87.99999999999996
175 88.49999999999996
176 88.99999999999996
177 89.49999999999994
178 89.99999999999994
179 90.49999999999994
180 90.99999999999996
181 91.49999999999996
182 91.99999999999996
183 92.49999999999994
184 92.99999999999994
185 93.49999999999994
186 93.99999999999994
187 94.49999999999993
188 94.99999999999993
189 95.49999999999993
190 95.99999999999993
191 96.49999999999991
192 96.99999999999991
193 97.49999999999991
194 97.99999999999991
195 98.49999999999991
196 98.9999999999999
197 99.49999999999989
198 99.99999999999987
199 100.49999999999986
199 100.49999999999986手計算では198日目に100mに到達しますが、
プログラムでは計算誤差で199日目になりました。
すっきりしなくてすみません。
ピラミッド
問題は別サイト様の記事を見てください。
左端と右端にくる数を、段の数で表現できれば勝ちです。
left = 1
right = 1
for stage in range(2,101):
left = left + 2*(stage-1)-1
right = right+ 2*(stage-1)+1
print(f"{stage} {left} {right}")
if left+right==222:
print(f"### {stage} {left} {right} {left+right}")
print(f"### {stage} {left} {right} {left+right}")
2 2 4
3 5 9
4 10 16
5 17 25
6 26 36
7 37 49
8 50 64
9 65 81
10 82 100
11 101 121
### 11 101 121 222
12 122 144
13 145 169
14 170 196
15 197 225
16 226 256
17 257 289
18 290 324
19 325 361
20 362 400
21 401 441
22 442 484
23 485 529
24 530 576
25 577 625
26 626 676
27 677 729
28 730 784
29 785 841
30 842 900
31 901 961
32 962 1024
33 1025 1089
34 1090 1156
35 1157 1225
36 1226 1296
37 1297 1369
38 1370 1444
39 1445 1521
40 1522 1600
41 1601 1681
42 1682 1764
43 1765 1849
44 1850 1936
45 1937 2025
46 2026 2116
47 2117 2209
48 2210 2304
49 2305 2401
50 2402 2500
51 2501 2601
52 2602 2704
53 2705 2809
54 2810 2916
55 2917 3025
56 3026 3136
57 3137 3249
58 3250 3364
59 3365 3481
60 3482 3600
61 3601 3721
62 3722 3844
63 3845 3969
64 3970 4096
65 4097 4225
66 4226 4356
67 4357 4489
68 4490 4624
69 4625 4761
70 4762 4900
71 4901 5041
72 5042 5184
73 5185 5329
74 5330 5476
75 5477 5625
76 5626 5776
77 5777 5929
78 5930 6084
79 6085 6241
80 6242 6400
81 6401 6561
82 6562 6724
83 6725 6889
84 6890 7056
85 7057 7225
86 7226 7396
87 7397 7569
88 7570 7744
89 7745 7921
90 7922 8100
91 8101 8281
92 8282 8464
93 8465 8649
94 8650 8836
95 8837 9025
96 9026 9216
97 9217 9409
98 9410 9604
99 9605 9801
100 9802 10000
### 100 9802 10000 19802カプレカ定数
四桁の数値について、各桁の数値を操作したりします。
手計算でやれる操作をプログラムでやるには、いろんなテクニックが必要です。それらを学びながらやってみましょう。
計算手順の説明
以下の計算手順のプログラムを作ります。
- 四桁の数を考えます。※四桁の数のうち少なくとも1つは違う数にします。0001や0256など0によって一桁や三桁になっていてもOKです。
- 4つの数を並び替えて、最大値と最小値を作ります。
- ４つの数を大きい順に並べれば最大値ができます。
- ４つの数を小さい順に並べれば最小値ができます。
- 最大値－最小値をします。
- ３でできた数で、手順２～３をずっと繰り返します。
そうすると、最終的に6174になって変化しなくなります。
この6174がカプレア定数です。
四つの数から最大値と最小値を作る
このプログラムに必要なヒントを出しましょう。
- 4つの数は、変数a,b,c,dに入れる。
- arr=[a,b,c,d]でリストに入れる。
- sorted(arr)で小さい順、sorted(arr, reverse=True)で大きい順にできる。
- sorted(arr)で作ったリストから、数を一つずつ抜き出して、4桁の数値を作る。
arr=[2,1,4,3]
print(sorted(arr))
print(sorted(arr, reverse=True))[1, 2, 3, 4]
[4, 3, 2, 1]リストから各要素を取り出す
リストから各要素を取り出せるかどうかが分かればできます。
インデックスを使ってみても良いですし、
a=5
b=6
c=7
d=8
arr=[a,b,c,d]
for i in range(0,4):
print(arr[i])for文で取り出しても良いです。
a=5
b=6
c=7
d=8
arr=[a,b,c,d]
for i in arr:
print(i)今回は2つの配列から取り出すので、zip()を使うと良いですね。
arr1=[1,2,3,4]
arr2=[5,6,7,8]
for i,j in zip(arr1, arr2):
print(f"{i} {j}")1 5
2 6
3 7
4 8プログラムコードを写させてもOK
ちょっと難しいと思いますので、写させて、説明をするでも良いですね。
アルゴリズムは下記です。板書してもOKです。
- 4つの変数a,b,c,dに数値を入れる。
- 計算を10回ぐらい繰り返す。
- 4つの変数をリストarrにいれる。
- リストarrを小さい順にならべてarr2に入れる。
- リストarrを大きい順にならべてarr3に入れる。
- arr2とarr3から1つずつ取り出し、変数i,jに入れる。
- iとjから4桁の数値を作る。変数はnum2とnum3とする。
- 最大値num3から最小値num2を引く
num2 = arr2[0]*1000 + arr2[1]*100 + arr2[2]*10 + arr2[3]a=0
b=0
c=0
d=1
for rep in range(0,10):
arr=[a,b,c,d]
arr2 = sorted(arr) # 小さい順に並べる
arr3 = sorted(arr,reverse=True) # 大きい順に並べる
num2 = 0
num3 = 0
for cnt,(i,j) in enumerate(zip(arr2,arr3)):
num2=num2+i*10**(3-cnt) # 最小値を作る
num3=num3+j*10**(3-cnt) # 最大値を作る
num4=num3-num2
print(f"{num3} {num2} -> {num4}")
a = int(num4/1000) # 1000の位の数を抜き出す。
b = int((num4-a*1000)/100) # 100の位の数を抜き出す。
c = int((num4-a*1000-b*100)/10) # 10の位の数を抜き出す。
d = int((num4-a*1000-b*100-c*10)/1) # 1の位の数を抜き出す。
print(f"-> {a} {b} {c} {d}")
print(num4)1000 1 -> 999
-> 0 9 9 9
9990 999 -> 8991
-> 8 9 9 1
9981 1899 -> 8082
-> 8 0 8 2
8820 288 -> 8532
-> 8 5 3 2
8532 2358 -> 6174
-> 6 1 7 4
7641 1467 -> 6174
-> 6 1 7 4
7641 1467 -> 6174
-> 6 1 7 4
7641 1467 -> 6174
-> 6 1 7 4
7641 1467 -> 6174
-> 6 1 7 4
7641 1467 -> 6174
-> 6 1 7 4
6174
