算数、いや数学を習いました。その2
おもしろい数学。前回のその1から、はや9か月。ふたつめの問題を解いてみました。 （ふたつめの問題はすぐに出題されていました。怠惰から解くのに9か月もかかってしまいました。）
この記事は JSL (日本システム技研) | Advent Calendar 2022 9日目 の記事です。
なにしたの
問題を出してもらい、それをやりました。
動作環境
- Python: 3.11.1
問題
全文を掲載します。ぜひやってみてください。
from unittest import TestCase, main
"""
★ python -m unittest sample2.py でテスト実行できます.
数字の並び 2, -4, 8, -16, 32, -64 .... を作りたい.
index 0番目は要素2
index 1番目は要素-4
index 2番目は要素8
...省略...
問1. index番号がidx(数値型)で与えられた時、
対応する要素を求める関数 chinoppy_festival を作成して、
TestsChinoppyFestivalテストを通してください.
問2. 合計を求める関数、chinoppy_carnivalを作成して、
TestsChinoppyCarnival テストを通してください.
"""
def chinoppy_festival(idx: int) -> int:
"""inxに対応する要素を求める関数"""
...
def chinoppy_carnival(idx: int) -> int:
"""idxまでの合計を求める関数."""
...
class TestsChinoppyFestival(TestCase):
def test1(self):
input_ = 0
expected = 2
self.assertEqual(chinoppy_festival(input_), expected)
def test2(self):
input_ = 5
expected = -64
self.assertEqual(chinoppy_festival(input_), expected)
class TestsChinoppyCarnival(TestCase):
def test1(self):
input_ = 0
expected = 2
self.assertEqual(chinoppy_carnival(input_), expected)
def test2(self):
input_ = 5
expected = -42
self.assertEqual(chinoppy_carnival(input_), expected)
if __name__ == "__main__":
main()ヒントとして、先生から以下のコメントをいただいております。
(今回は速度計測のテスト作ってないのでfor文でも通りますが、数列の考えを使って解いてみることをお勧めします)
ふんふん。for文でも通るようです。まずはそこから試してみましょう。
（´-`）.｡oO（数列の考え...知らない子ですね）
誤答
結論からいうと、forを使うことでしか解けませんでした（テストを通すことはできました）。 今回もプロセスをつらつら書いていきます。後半解説です。
問1
さて、まず1つ目の問題を見てみましょう。
2倍になっていることが分かります。そして交互にマイナスです。
そして渡される値に順に増えていくとのこと。
数字の並び 2, -4, 8, -16, 32, -64 .... を作りたい.index 0番目は要素2 index 1番目は要素-4 index 2番目は要素8
1つ目の答えは2の乗数ですね。一瞬です。そして引数が奇数の場合、マイナスになれば良い。簡単です。
def chinoppy_festival(idx: int) -> int:
"""inxに対応する要素を求める関数"""
i: int = 1 if idx % 2 == 0 else -1
return (2 ** (idx + 1)) * i 一緒にやった算数仲間の問1の答えは以下。
def chinoppy_festival(idx: int) -> int:
"""inxに対応する要素を求める関数"""
return -(2 ** (idx + 1)) if (idx % 2) else 2 ** (idx + 1)かっこいいですね。
問2
そして問2です。合計を求める関数を求めます。 まずはfor文をぶん回す方法で考えてみました。これでテストはひとまず通ります。
def chinoppy_carnival(idx: int) -> int:
"""idxまでの合計を求める関数."""
result: int = 2
for i in range(idx):
result += chinoppy_festival(i+1)
return resultさて、ここからが勝負です。この答えではかっこわるい。そして、なんでもないただの関数です。for文をやめたい。
ヒントにある数列の考え方を思い出しましょう。
(今回は速度計測のテスト作ってないのでfor文でも通りますが、数列の考えを使って解いてみることをお勧めします)
前回学んだ「考え方のポイント」は以下です。
- (小) より簡単な問題を抽出して、解いてみる.(Sumより一般項を求める方が楽)
- 数列には法則性がある -> うまく変形することで、項目を置き換えることができる.
- 数列を具体的に書いてみる -> 一般化する(引数nの関数をつくる.)
先生は前回何をしても良い、と言っていました。
先生は言いました。
「順序は分かっているので、その順序に対してはなにをしてもいいですよね？たとえば逆さまにしても同じ答えになりますよね？」 \( S2 = 4 + 3 + 2 + 1 \) \( S2 = 1 + 2 + 3 + 4 \)
まずは数字を並べたり、入れ替えたり、マイナスを無くしてみたりしましたが、何も見えてきません。
\( -42 = 2 + (-4) + 8 + (-16) + 32 + (-64)\)
\( -42 = (-64) + 32 + (-16) + 8 + (-4) + 2\)
\( S = 2 + 4 + 8 + 16 + 32 + 64\)
\( S = 64 + 32 + 16 + 8 + 4 + 2\)
算数仲間のメモも転載します。
[2, -4, 8, -16, 32, -64]
[-64, 32, -16, 8, -4, 2]
= [-62, 28, -8, -8, 28, -62]
= -84 / 2 = -42
[2, -4, 8, -16, 32]
[32, -16, 8, -4, 2]
= [34, -20, 16, -20, 34]
= 44 / 2 = 22
[2, -4, 8, -16]
[-16, 8, -4, 2]
= [-14, 4, 4, -14]
= -20 / 2 = -10
[2, -4, 8]
[8, -4, 2]
= [10, -8, 10]
= 12 / 2 = 6
[2, -4]
[-4, 2]
= [-2, -2]
= -4 / 2 = -2
[2]
[2]
= [4]
= 4 / 2 = 2
0: 2
1: -2
2: 6
3: -10
4: 22
5: -42何も分かりません。マイナスがキーなのかと思いました。
よーく見てると、マイナスだけ合計して2で割ると答えになることが分かりました（計算量は半分になりました）。
def chinoppy_carnival(idx: int) -> int:
"""idxまでの合計を求める関数."""
result: int = 2
for i in range(0, idx, 1):
result += chinoppy_festival(i+1)
return resultただ、なんの法則性も見えてきません。終了です。
解法
先生は言いました。「惜しいところまで来ている」と。あと1時間やればいけるのではと。
並べるところは良いようです。
\( -42 = 2 + (-4) + 8 + (-16) + 32 + (-64)\)
「どういう法則になっているかよくみてみましょう」「2倍になってることがわかりますね」
「では両辺を2倍してみましょう」
\(1 \times S = 2 + (-4) + 8 + (-16) + 32 + (-64)\)
\(-2 \times S = (-4) + 8 + (-16) + 32 + (-64) + 128\)
よくみてみると...上と下で気持ち悪いところが見えてきます。
同じです。
「では上と下を引いてみましょう」「ファッ？！」
「そうすると最初と最後の数が残りますね」
\(3 \times S = 2 - 128\)
\(S = -42\)
答えが求まりました。ただ並べるだけでなく、両辺に同じ値をかけたり、元の値を引いたりしても良いようです。
本当に何をしても良い。
規則性のヒントは ルールを見つけること 。この場合「2倍になっていること」です。
汚いですがコードです。
def chinoppy_carnival(idx: int) -> int:
"""idxまでの合計を求める関数."""
return (2 + (2 * (2 ** (idx + 1)) * -1)) / 3 if idx != 0 else 2先生の答えはもっとかっこいいです。
def chinoppy_festival(idx: int) -> int:
"""inxに対応する要素を求める関数"""
return 2 * ((-2) ** idx)
def chinoppy_carnival(idx: int) -> int:
"""idxまでの合計を求める関数."""
return 2 * (1 - (-2) ** (idx + 1)) / (1 - (-2))まとめ
このような問題を「初項2、公比-2の等比数列」というそうです。
とても楽しかった。ありがとうございました。次の問題も楽しみです。
おまけ
ChatGPTは解けるのでしょうか？聞いてみました。
ほう？一番かっこいいコードです。
☻ python -m unittest sample2.py
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s
OKすばらしいですね！