![[中学数学]あの手法が役立つ問題！中央大附属高で出題された「バブルソート」に関する問題を解説！](https://i0.wp.com/you-can-blog.com/wp-content/uploads/2022/12/code-gb94aae044_1920.jpg?fit=1920%2C1282&ssl=1)
みなさんこんにちは、ゆーきゃんです。
今回は、中央大附属高で出題された「バブルソート」に関する問題を解説します。
この問題も過去に解説してきたあの手法を用いれば、簡単に解くことができます。
また、この問題の背景には「バブルソート」という情報科学で登場する概念があります。
これについても合わせて説明していきます。
また、本記事と合わせて以下の記事もぜひご覧ください。
問題演習をいくらこなしても未知の問題が解けるようにならないとお困りではありませんか。
未知の問題に立ち向かうには、思考の「型」を身に付ける必要があります。
思考の「型」を解説した書籍をAmazonで販売中。
Kindle Unlimitedなら、追加料金なしで閲覧可能。
「MARCH付属校をはじめとした人気難関私立校を志望しているが、対策が立てづらい・・・」
「解説を読んで『理解』できても、自力で『解けない』・・・」
などでお悩みではありませんか。
公立からMARCH付属校対策までをすべてを網羅する「裏ワザ」を解説中！
問題の概要
中央大附属高で出題された問題は以下の通りです。
1から\(k\)までの整数が書かれたカードを小さい順に並べ、隣り合う2枚を次々と交換し、できるだけ少ない回数で大きい順に並び替えるのに必要な交換の回数を\(n(k)\)とする。
ただし、1回に交換できるのは、隣り合う2枚1組のカードとする。
例えば、\(k=3\)のとき、
1,2,3→1,3,2→3,1,2→3,2,1と並び替えればよいため、\(n(3)=3\)である。
以下の問に答えよ。
(1)\(n(4),n(5)\)をそれぞれ求めよ。
(2)\(n(k+1)\)を\(n(k)\)と\(k\)を用いて表せ。
(3)\(k=10\)のとき、カードを何回か交換したところ1,2,3,4,5,10,6,7,8,9となった。
この状態からあと何回カードを交換したら大きい順に並び替えることができるか。
(1)の解説
まずは、(1)です。
とりあえずは、ここで「実験」を行い、(2)につなげていきましょう。
\(n(4)\)について考えましょう。
問題文に書かれている例を見てみると、
最も大きい数字を左に寄せるようにして、並び替えてゆく
ようにすればよいですね。
すべてのカードのうち最も大きい数字を左に寄せたら、
次はこれらのカードのうち、その次に大きい数字を左に寄せるようにして並び替えればよいです。
そうすると、
1,2,3,4→1,2,4,3→1,4,2,3→4,1,2,3
→4,1,3,2→4,3,1,2
→4,3,2,1
と並び替えることができるため、\(n(4)=6\)となります。
続いて、\(n(5)\)についてです。
1,2,3,4,5→1,2,3,5,4→1,2,5,3,4→1,5,2,3,4→5,1,2,3,4
→5,1,2,4,3→5,1,4,2,3→5,4,1,2,3
→5,4,1,3,2→5,4,3,1,2
→5,4,3,2,1
となるので、\(n(5)=10\)となります。
(2)の解説
続いて、(2)の解説です。
(1)での考察より、次のことが分かります。
- 最大値である\(k\)の書かれたカードを左に寄せるのに、\((k-1)\)回の交換が必要
- その後、その右側にある1から\((k-1)\)が書かれたカードを大きい順に並び替えてゆけばよい
よって、\(n(k+1)=k+n(k)\)と表されることが分かります。
この「漸化式」を用いて、(3)を考えていきましょう。
(3)の解説
最後に、(3)です。
1,2,3,4,5,10,6,7,8,9の状態から、10を左に寄せるのに5回の交換が必要となりますね。
10を左に寄せたとき、あとはその右側にある1~9のカードを大きい順に並び替えればよいので、
先ほどの漸化式を用いれば答えは次のように求まります。
\begin{eqnarray}
5+n(9)&=&5+8+n(8)\\
&=&5+8+7+n(7)\\
&=&5+8+7+6+n(6)\\
&=&5+8+7+6+5+n(5)\\
&=&5+8+7+6+5+10\\
&=&41
\end{eqnarray}
「バブルソート」の考察
今回の問題で扱ったアルゴリズムを「バブルソート」といいます。
このアルゴリズムについてもう少し深く考えていきましょう。
\(n(k)\)はどのように表される？
まずは、(2)で求めた漸化式を用いて\(n(k)\)を求めていきましょう。
この漸化式を繰り返し用いれば、\(n(k)\)は以下のように求まります。
\begin{eqnarray}
n(k)&=&(k-1)+n(k-1)\\
&=&(k-1)+(k-2)+n(k-2)\\
&=&(k-1)+(k-2)+(k-3)+n(k-3)\\
…\\
&=&(k-1)+(k-2)+…+4+n(4)\\
&=&(k-1)+(k-2)+…+4+3+n(3)\\
&=&(k-1)+(k-2)+…+4+3+2+n(2)\\
&=&(k-1)+(k-2)+…+4+3+2+1\\
\end{eqnarray}
つまり、\(n(k)\)は1から\((k-1)\)までの連続する正の整数の和をとることで求められます。
一般に、
1から\(N\)までの連続する正の整数の和は、\(\displaystyle \frac{N(N+1)}{2}\)
となるため(これは是非覚えておきましょう)、\(n(k)=\displaystyle \frac{(k-1)k}{2}\)と表されます。
「交換回数」の考察
さて、\(n(k)=\displaystyle \frac{(k-1)k}{2}\)となることを用いて、
\(k\)を変化させたときに「交換回数」がどうなるかを考えてみます。
\(k\)を1から100まで変化させたとき、\(k\)と\(n(k)\)の関係をグラフに表すと以下のようになります。
![[中学数学]あの手法が役立つ問題！中央大附属高で出題された「バブルソート」に関する問題を解説！](https://i0.wp.com/you-can-blog.com/wp-content/uploads/2022/12/バブルソート.png?resize=1024%2C615&ssl=1)
\(n(5)=10\)であったにもかかわらず、\(n(100)=4950\)となっています。
\(k\)の増加に伴って\(n(k)\)の値は爆発的に増加していくため、膨大なデータを扱う場合はこのアルゴリズムを用いるのは適しません。
ですので、実用上で「バブルソート」が用いられることはほとんどありません。
[中学数学]あの手法が役立つ問題！中央大附属高で出題された「バブルソート」に関する問題を解説！
いかがでしたか。
今回は、中央大附属高で出題された「バブルソート」に関する問題を解説しました。
「実験」をし、「漸化式」を適用できればすぐに解ける問題であったかと思います。
この問題の背景となっている「バブルソート」はデータ数が増えると効率の悪い並び替え方法となってしまいます。
どうしたらデータ数が増えても効率よく並び替えることができるのかを考えてみても面白いかもしれません。
今後も過去問等の解説を行ってゆくのでお楽しみに。
最後までご覧いただきありがとうございました。
また、本記事と合わせて以下の記事もぜひご覧ください。
コメント