pythonを用いてアルゴリズムの初心者向けの問題集を解いていたのですが、ある問題の途中で躓いてしまいました。再帰の使い方が間違っているのはわかっているのですが、どのように書けば適切に動くのかがわかりません。正しい書き方を教えていただけると嬉しいです。また、再帰以外の部分で改善点があったり、もっと良い解法があれば、後学のため教えていただけないでしょうか。
問題は以下のような内容です。
”いちごが円周上に並んだホールケーキの切り分け方について考えてみましょう。ホールケーキをN個に切り分けるとき、全てのケーキに乗っているいちごの数が1〜N個とすべて異なっているようにしたいです。なおかつ、隣り合った2つのケーキに乗っているいちごの数の合計が、いずれも平方数となるようにします。このような条件を満たすことができる最小のN(>1)を求めてください。
N個に切り分けるとき、いちごの数は合計でN(N+1)/2個となります。
例えばN=4のとき、いちごの数が1個となるもの、3個となるもの、2個となるもの、4個となるもの、という順番で切ったとします。この切り方は「ケーキに乗っているいちごの数がすべて数が異なる」という条件は満たしているものの、1個と3個のペア以外、3+2のペア、2+4のペア、4+1のペアいずれも「隣り合っているケーキのイチゴの合計が平方数」という条件を満たしていないので、この切り方は条件を満たさないことになります。
問題の答えはN=32,条件を満たす並べ方は
[1, 8, 28, 21, 4, 32, 17, 19, 30, 6, 3, 13, 12, 24, 25, 11, 5, 31, 18, 7, 29, 20, 16, 9, 27, 22, 14, 2, 23, 26, 10, 15]
のようです。
自分が書いたスクリプトは下記の通りです。
python
1def adding_next_number(boolean, n, circle_list, num_list, square): 2 if num_list == []: 3 num_sum = circle_list[-1] + 1 4 if num_sum in square: 5 print(n) 6 boolean == False 7 else: 8 for num in num_list: 9 last_num = circle_list[-1] 10 num_sum = last_num + num 11 if num_sum in square: 12 circle_list.append(num) 13 num_list.remove(num) 14 boolean, n, circle_list, num_list, square = adding_next_number(boolean, n, circle_list, num_list, square) 15 16 return boolean, n, circle_list, num_list, square 17 18 19def main(): 20 n = 2 21 boolean = True 22 while boolean == True: 23 num_list = [i for i in range(2, n+1)] 24 square = [i**2 for i in num_list if i**2 < n*2] 25 26 circle_list = [1,] 27 boolean, n, circle_list, num_list, square = adding_next_number(boolean, n, circle_list, num_list, square) 28 29 n += 1 30 31 32if __name__ == "__main__": 33 main()
検証する数nについて、2からnまでの数が収められたリスト(num_list)と隣り合ったケーキのイチゴの数が取りうる平方数が収められたリスト(square)を用意します。次に切り方の順番通りに数字を格納していくリスト、circle_listを用意します。Nの値にかかわらずイチゴが1個のケーキは存在するので、circle_listには予め1を格納しておいて、ここを皮切りに数字を格納していけるか検証していきます。
格納する数字を選ぶ関数がadding_next_number()です。もしcircle_listの末尾の数字とnum_listに残っている数字の合計が平方数になったらcircle_listに数字を格納します。そしてここで再帰を利用して次に格納される番号を調べにいく、といった内容で書いています。
書いている途中からわかってはいたのですが、この書き方だといつまでたっても答えを見つけることができません。仮に検証する数がN=31だとすると、circle_listの末尾との合計が平方数となる数字がnum_listに残っていない状態、つまりcircle_listが
[1, 3, 6, 10, 15, 21, 4, 5, 11, 14, 2, 7, 9, 16, 20, 29]
となった途端に、N=31の場合についての検証は終わってしまいます。
同様に本来であれば正解であるはずのN=32の場合でも、circle_listが同じ
[1, 3, 6, 10, 15, 21, 4, 5, 11, 14, 2, 7, 9, 16, 20, 29]
となった段階で検証が終了し、正解として出力されません。
circle_listへの格納がうまくいかなくなったタイミングで、一つ前の状態にもどって別の選択肢がないか考えるようなコードを書きたいのですが、どのように書いたら良いのかわかりません。そもそも、もっとスマートな書き方があるような気もするのですが、それも気がするという以上のものではない状態です。
アイデアをお持ちの方がいらっしゃいましたら、ご助言をいただけたるととても助かります。
ご協力いただけると幸いです。よろしくお願いいたします。
##回答を修正することができました。ご協力いただき有難うございました。
人のスクリプトを読んで理解するという経験がまだまだ少ないので教えていただいたリンク先のスクリプトを読み解くのに時間がかかってしまい、返事とお礼が遅れてしまいました。解き方自体が勉強になっただけではなく、人のスクリプトを読んで理解する体験が自分にとってはとても貴重なものでした。
リンク先の解き方をそのまま真似することはできなかったですが、じっくりスクリプトを読んでいく中でなんとかオリジナルの解き方というか修正の仕方を思いつくことができました。まだまだ初心者なのでとても体力がいる作業でしたが貴重な経験になりました。有難うございました。
python
1def adding_numbers(N, S, C): 2 new_list = [] 3 4 for l in C: 5 N_copy = list(N) 6 7 l_copy = list(l) 8 l_copy.remove(1) 9 10 for num in l_copy: 11 N_copy.remove(num) 12 13 for num in N_copy: 14 n_sum = num + l_copy[-1] 15 16 if n_sum in S: 17 l_copy_2 = list(l) 18 l_copy_2.append(num) 19 20 new_list.append(l_copy_2) 21 22 if new_list == []: 23 return N, S, new_list 24 25 elif len(new_list[0]) == len(N) + 1: 26 the_final_list = [] 27 28 for l in new_list: 29 n_sum = l[-1] + 1 30 if n_sum in S: 31 the_final_list.append(l) 32 33 return N, S, the_final_list 34 35 else: 36 return adding_numbers(N, S, new_list) 37 38 39def main(): 40 41 n = 2 42 while True: 43 # N -> numbers, S -> squares, C -> circle_list 44 45 N = [i for i in range(2, n+1)] 46 S = [i**2 for i in range(2, int((2*n - 1)**0.5 + 1))] 47 48 C = [] 49 for i in N: 50 n_sum = i + 1 51 if n_sum in S: 52 new_list = [1, i] 53 C.append(new_list) 54 55 if C != []: 56 N, S, C = adding_numbers(N, S, C) 57 58 if C != []: 59 print(n) 60 for l in C: 61 print(*l) 62 break 63 64 n += 1 65 66 67if __name__ == '__main__': 68 main()
回答1件
あなたの回答
tips
プレビュー