その３：C - 1 2 1 3 1 2 1
※この記事は下の記事の補足記事です。こちらを先に読むことを勧めます
問題
列$${S_n}$$ を次のように定義します。
$${S_1}$$は 1 つの 1 からなる長さ 1 の列である。
$${S_n}$$ (n は 2 以上の整数) は
をこの順につなげた列である。
たとえば,
$${S_2}$$ は $${S_1, 2, S_1}$$ をこの順につなげた列なので ,1,2,1 である。
$${S_3}$$ は $${S_2, 3, S_2}$$ をこの順につなげた列なので 1,2,1,3,1,2,1 である。
N が与えられるので、列 $${S_N}$$
をすべて出力するプログラムを書きなさい。
制約
・Ｎは整数
・1≦Ｎ≦16
数十秒考えてみてください。
解き方１：全部書く。
プログラムの中に$${S_1,S_2,S_3…}$$を全部書き込んで、「もしNが1なら～,2なら~,３なら～,を出す」みたいなプログラムを組みます。
まあ16だからコピペを駆使すればできないこともない。
ちなみに$${S_1}$$から並べていくとこんなん
1
1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 7 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 6 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
ちなみに16はこうなる
いやまあこれ1つ上のを作るときは
コピー→ペースト→「 (空白)(数字) 」をうつ→ペースト
で終わるから言うてそんな手間でもないんだけどね。
解き方2（正規ルート）：再帰関数
（結構難しいので、「ふーん」ぐらいに思えれば十分です。あとから見に来て成長を実感しましょう。）
時に皆さん。関数というものを知っていますか？
Scratchには「ブロックを作る」という名前であります。
(知ってる人は適当に飛ばしてください)
例えばこれ。Scratchで$${n^x}$$を計算する関数を作ったところです。
「変数」という箱に最初1を入れて、x回 n倍しています。
なんとなくやってることはわかるのではないでしょうか。
こんな感じで使います。こうすると、n=4,x=3になってさっきのやつが実行されます。
$${4^3}$$を計算して、「64」と言ってくれます。
1回だけやるだけだったらちょっと見やすくなるだけですが、何回も使うとこの効果はよくわかります。
このぐちゃぐちゃしたブロックが
これだけで済みます。
https://scratch.mit.edu/projects/678498967/
一応公開してあります。
というわけで関数というものがわかりましたね。その上でこれを見てください。
若干難しいのでじっくり見てください。
わからないですよねごめんなさい。
これは、「いうこと」っていう変数に答えを順番に書いていく仕組みになっています。
そしてこの関数では、
ｎが１かどうか調べる→
(1のとき)→「いうこと」に「 1」という文字列を足す。
(それ以外の時)→「n-1」をnにした再帰関数を実行する
→「 n」という文字列を「いうこと」に足す
→「n-1」をnにした再帰関数を実行する。
という処理をしています。
例えばこの関数をn=3で実行すると、こんな感じになります。
灰色の四角が関数です。
図でも解説します
n=3で実行されてる途中の「再帰関数」も
これに従って実行されるので、あんな感じの入れ子構造になります。
これを左上から順に(赤い線が出てるところはそっちを先に)「いうこと」に注目してみていくと、「いうこと」が
$${S_3}$$ = 1 2 1 3 1 2 1になるのがわかるんじゃないでしょうか？
かなり見づらいので切り抜いたバージョンも
これを実行すれば、変数「いうこと」に答えが入ってくれます。
n=3でないときでも、しっかりと答えが出ます。
というわけで、さっきの問題はスクラッチだったらこんな感じで解けます。
わからなくてもそれは僕のせいなのでセンスがないとか思わないでください
これも一応公開してあります。
https://scratch.mit.edu/projects/678494378/
解き方３：法則性を見つける
$${S_1}$$から順に、番号ともに並べてみましょう
じーっと見てください。番号と値に規則性が見えてきませんか？
そうです！！
どの番号でも、n番目の文字は、「nが何回２で割り切れるか＋１」になっています！
これに気付けばあとは長さを求めるだけ。
長さは、
$${S_1→1 S_2→3 S_3→7 S_4→15}$$です。
つまり$${S_n}$$の長さは$${2^n-1}$$になっていますね。
これさえわかれば、長さが$${2^n-1}$$になるまで、iを1から順に増やしつつ、「iが何回２で割り切れるか＋１」「(空白)」を交互に出力し続けていればいいですね！！
これもまた、正解です。解き方1,2,3どれでもちゃんとした正解が出ます。
ちゃんとした正解が出るならばそれは正解なのです。
解き方がいろいろあって人によって違うのも競プロの面白いところですね！
おわりに
わざわざこれも見に来ていただきありがとうございました！
わからなかったとしても、競プロセンスないとかでは全くないです。
僕の説明が下手/単純にまだ基礎知識が足りないだけです。
ここまで来たあなたは興味を持っているはずなので、ぜひとも競プロを初めて見ましょう！！