プログラミングでジュニア算数オリンピック『1997年度トライアル問題1問目』その２
筆者：昨日の続きです。始めて２回目ですが、上手く行って欲しいですね。
問題文：
『ぼくのお兄さんは、西暦ABDC年の生れです。
1997年の今年、ぼくのお兄さんの年令は、A＋B＋C＋Dになりました。
ぼくのお兄さんは何才になったのでしょうか。』
昨日はどう値が答えに近づいていくかを見ました。今日はその近づき方のルールを探りたいと思います。ちなみに今回は最初のゼロは取り除きます。
changedList = [] for i in range(len(gapList)): if i == 0: changedList.append(0) continue changedList.append(gapList[i] - gapList[i-1]) for year, gap, changed in zip(reversed(range(1998)), gapList, changedList): print(year, gap, changed)
1997 -26 0 1996 -24 2 1995 -22 2 1994 -20 2 1993 -18 2 1992 -16 2 1991 -14 2 1990 -12 2 1989 -19 -7 1988 -17 2 1987 -15 2 1986 -13 2 1985 -11 2 1984 -9 2 1983 -7 2 1982 -5 2 1981 -3 2 1980 -1 2 1979 -8 -7 1978 -6 2 1977 -4 2 1976 -2 2 1975 0 2 1974 2 2 1973 4 2 1972 6 2 （略） 1902 83 2 1901 85 2 1900 87 2 1899 71 -16 1898 73 2 1897 75 2 1896 77 2
作業にかかる前に、長さが違うリストを一覧で眺めれるような関数を定義します。
def printLists(listList): maxLength = 0 for list in listList: if maxLength < len(list): maxLength = len(list) for i in range(maxLength): for list in listList: if len(list) <= i: print("", end=" |") elif list[i] <= -10: print(list[i], end="|") elif list[i] < 0: print(list[i], end=" |") elif list[i] >= 10: print(list[i], end=" |") else: print(list[i], end=" |") print() list1 = [1,1,1,1,1,1,1,1] list2 = [22,22,22,22,22] list3 = [-3,-3,-3,-3,-3,-3,-3,-3,-3,-3,-3] list4 = [-44,-44,-44,-44,-44,-44] list5 = [] printLists([list1, list2, list3, list4, list5])
1 |22 |-3 |-44| | 1 |22 |-3 |-44| | 1 |22 |-3 |-44| | 1 |22 |-3 |-44| | 1 |22 |-3 |-44| | 1 | |-3 |-44| | 1 | |-3 | | | 1 | |-3 | | | | |-3 | | | | |-3 | | | | |-3 | | |
値の近づき方のルールということで、理想の小学生であれば10進数だという認識を利用して、1の位が変化する時の近づき方、10の位が変化する時の近づき方、100の位が変化する時の近づき方、1000の位が変化する時の近づき方をそれぞれ調べて、一回一回の計算を省いて、1975年に違いがゼロになってその後も逆転しないと予想するのでしょう。
同じ結果になる計算を省くのもアルゴリズムの計算量を減らすテクニックではあると思うのですが、10進数というのはあくまで表記の方法なのだと思いますし、あとまあ何となく思いつかないので、今回は違う方法を試して、この問題は2進数だとかにしてまた別の時に考えてみたいと思います。
まあとにかく、毎回の変化、10回に1回の変化、100回に1回の変化、1000回に1回の変化、それぞれ見つけることができれば良いかなと思って書いたのが下のコードです。
部分的な共通パターンで無く、全体的に周期性を持っているという想定なので、位の変化を基準にすると中途半端な所から始まっていても、まあいつか同じ周期の所で一致するだろうというのが最初のfor文までです。
def discoverySameChanged(changedList, ruleList): baseList = changedList[:len(changedList)//2] otherList = changedList[len(changedList)//2:] for i in range(len(otherList)): if otherList == baseList[:len(otherList)]: return baseList else: target = otherList.pop(0) baseList.append(target) copyList = baseList.copy() ruleList.append(copyList) baseList.pop() return baseList
で、最後の最後まで一致しない場合が（偶然見つけたのですが）100回に1回だとかの大きな変化がotherListの先頭に来ている場合みたいなので、全部の処理が終わってbaseListに全部移っている状態のものをruleListに入れて、baseListの先頭を取ってreturnしています。
最後までループできるようにしました。listListはどういう風に変化していくか自分で見る用です。
ruleList = [] listList = [] def discoverySameChangedLoop(changedList, ruleList, listList): baseList = discoverySameChanged(changedList, ruleList) if baseList == []: print("baseList is []") else: listList.append(baseList) discoverySameChangedLoop(baseList, ruleList, listList) discoverySameChangedLoop(changedList, ruleList, listList) printLists(ruleList)
baseList is [] 2 |2 |2 |2 | 2 |2 |2 | | 2 |2 |2 | | 2 |2 |2 | | 2 |2 |2 | | 2 |2 |2 | | 2 |2 |2 | | -7 |-7 |-7 | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -7 |-7 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | 2 |2 | | | -16|-16| | | 2 | | | | 2 | | | | 2 | | | | （略） 2 | | | | 2 | | | | 2 | | | | -25| | | |
とにかく一ヶ月の継続が第一の目標なので、この問題も焦らずゆっくり取り組んでいきたいです。最悪その日した考察だけでも書きたいです。
追記：一応listListの変化を晒しておきます。
2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | -7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 |-7 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | -16|-16|-16|-16|-16|-16|-16|-16| | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | | | 2 |2 |2 |2 |2 |2 |2 | | | | | | | | | | | | 2 |2 |2 |2 |2 |2 | | | | | | | | | | | | | 2 |2 |2 |2 |2 |2 | | | | | | | | | | | | | 2 |2 |2 |2 |2 |2 | | | | | | | | | | | | | （以下略）
追記2：最後のはwhile文で良さそうですね。
