Pythonで「Look-and-Say（見て言って）」数列のn番目の項を求める方法

整数 n が与えられたとき、「Look-and-Say（見て言って）」数列の n 番目の項を生成するプログラムを作成します。この数列は、直前の項を読み上げるようにして次の項を作っていく特徴的な数列です。最初のいくつかの項は以下のようになります。

• 1
• 11
• 21
• 1211
• 111221

読み方のルール

各項は、前の項を「数字の連続する個数 + その数字」という形式で読み上げることで生成されます。

• 1（イチ）
• 11（1が1つ）→ 前の項「1」を読んで「1が1つ」
• 21（1が2つ）→ 前の項「11」を読んで「1が2つ」
• 1211（2が1つ、1が1つ）→ 前の項「21」を読んで「2が1つ、1が1つ」
• 111221（1が1つ、2が1つ、1が2つ）→ 前の項「1211」を読んで「1が1つ、2が1つ、1が2つ」

解法のアプローチ

n が 1 ≤ n ≤ 30 の範囲で与えられるとき、n 番目の項を求めます。以下の手順で解くことができます。

1. s を "1" に初期化します。
2. n = 1 の場合は s をそのまま返します。
3. i = 2 から n まで繰り返します。
   • j = 0、temp = 空文字列、curr = 空文字列、count = 0 と初期化します。
   • j が s の長さ未満である間、以下を繰り返します。
     • curr が空文字列なら、curr := s[j]、count := 1 とし、j を1増やします。
     • curr が s[j] と同じなら、count と j をそれぞれ1増やします。
     • それ以外の場合は、temp に count と curr を連結し、curr を空文字列、count を 0 にリセットします。
   • ループ終了後、残った count と curr を temp に追加し、s を temp で更新します。
4. s を返します。

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution(object):
    def solve(self, n):
        s = "1"
        if n == 1:
            return s
        for i in range(2, n+1):
            j = 0
            temp = ""
            curr = ""
            count = 0
            while j < len(s):
                if curr == "":
                    curr = s[j]
                    count = 1
                    j += 1
                elif curr == s[j]:
                    count += 1
                    j += 1
                else:
                    temp += str(count) + curr
                    curr = ""
                    count = 0
            temp += str(count) + curr
            s = temp
        return s

ob = Solution()
n = 5
print(ob.solve(n))

入力

5

出力

"111221"

まとめ

このアルゴリズムは、文字列を先頭から走査しながら同じ数字が連続している個数を数え、「個数 + 数字」の形式で新しい文字列を構築するものです。計算量は各項の長さに依存しますが、Look-and-Say 数列は項ごとに文字列が伸びていくため、n が大きくなると処理時間も増加します。ただし n ≤ 30 の制約下では十分に高速に動作します。