[logo] Web連載「数学ガールの秘密ノート」
Share

第324回 シーズン33 エピソード4
アルゴリズム、なかなか大変(後編)

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\ABS}[1]{\left|\mathstrut #1\right|} \newcommand{\TT}[1]{\textrm{#1}} \newcommand{\ANGLE}[1]{\angle\textrm{#1}} \newcommand{\TRI}[1]{\triangle\textrm{#1}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{ $#1$ }} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\PS}[1]{\left(#1\right)} \newcommand{\LL}{\left\langle\,} \newcommand{\RR}{\,\right\rangle} \newcommand{\LLRR}[1]{\LL#1\RR} \newcommand{\Enil}{\textbf{nil}} \newcommand{\Fnext}{\textrm{next}} \newcommand{\Fprev}{\textrm{prev}} \newcommand{\Fvalue}{\textrm{value}} $

アルゴリズム、なかなか大変

双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことをに向けて《講義》している。

最大の値を求めるMAX-VALUEを題材にしたり(第321回参照)、 線形リストのノードを先頭に移動するMOVE-TO-FIRSTを題材にしたり(第322回参照)、 リストヘッド付き線形リストを議論したり(第323回参照)と、 いろんな議論を重ねてきた。

いまは、双方向リストというデータ構造を議論しているところだったんだけど……

テトラ「……難しいですけれど、具体例を使って《ステップ・バイ・ステップ》の図を描いて考えれば、まちがいを減らせます。 《例示は理解の試金石》ですから」

「あっ!」

テトラ「えっ!」

さっきからテトラちゃんは《図を描け》《図を描け》《ステップ・バイ・ステップの図を描け》と繰り返して言ってるのに、はいまだに図を描こうとしていない!

は、もしかしたら馬鹿じゃないのか?

その通りだ。

ほんの少しの時間を惜しむ馬鹿者だ。

ほんのちょっと手を動かして図を描く手間を惜しむ、大馬鹿者だ!

「……」

テトラ「……先輩?」

「……いや、大丈夫。テトラちゃんは何も悪くないよ。 《例示は理解の試金石》は本当に正しい。 そして《図を描け》も正しいよ」

テトラ「はい……?」

「僕は……ユーリに教えるときに『具体例を作ろうよ』『めんどうくさがらないで図を描こう』ってよく言うんだ」

テトラ「……」

「ユーリは『めんどくさーい』と言いながらも、図を描く。そしてたいていはよく理解できる」

テトラ「はい、わかります。実際に描いてみるといろんなことがはっきりしますよね」

「だよね。僕も、数学の問題で手がかりがつかめないときに、具体例を作ったり、図を描いたりする……でも、 今回はどうもそういう方向に頭が動いていかないみたいだ」

テトラ「慣れないと、おっくうになっちゃいますし……」

「だから、きっと、テトラちゃんにこうやって僕が苦手なことを《教えてもらう》というのはすごく大切なんだと思う」

テトラ「き、恐縮です」

「テトラ先生、引き続きよろしくお願いします(ふかぶか)」

テトラ「こ、こちらこそです(ふかぶか)」

問題5(MOVE-TO-LAST)

「それで、テトラちゃんの《双方向リスト版のMOVE-TO-FIRST》はこれなんだね(第323回参照)」

List 14 解答4(双方向リスト版のMOVE-TO-FIRST

テトラ「はい、そうです。双方向リストDとして実装された数列があったとして、MOVE-TO-FIRSTは『指定した値vが最初に見つかったノードを先頭に移動する』という手続きになります」

「うん。そしてこれが実行例だね」

MOVE-TO-FIRST(D, 59)の実行例(59という値を持つノードを先頭に移動する例)

テトラ「そうですね」

「さっきはおたおたしちゃったけど、 このMOVE-TO-FIRSTについては理解したと思うよ。 次の問題をお願いします、テトラ先生!」

テトラ「はいっ! それでは、せっかく双方向リストを使って実装してきたので、今度はこういう問題5はいかがでしょうか。MOVE-TO-LASTです」

問題5(双方向リスト版のMOVE-TO-LAST

与えられた双方向リストDに含まれているノードのうち「valueフィールドの値が与えられたvに等しいノード」を末尾に移動する手続きMOVE-TO-LAST(D, v)を書いてください。

もしも、vに等しいvalueフィールドを持つノードが見つからない場合には何もしません。

もしも、vに等しいvalueフィールドを持つノードが複数あった場合にはもっとも末尾に近いものだけを移動します。

手続き

  • $\textbf{MOVE-TO-LAST}(D, v)$

入力

  • 検索&移動の対象となる双方向リスト $D$
  • 検索する値 $v$

出力

  • なし
returnによる戻り値はありません。実行した結果はDからたどるリンクを変更することに反映されます。

「なるほどねえ……MOVE-TO-FIRSTは先頭に移動したけれど、このMOVE-TO-LASTは逆に末尾に移動するということだね。ちょうど同じ難易度の問題の出題になってる」

テトラ「え、ええと……同じ難易度なんですけど、同じ難易度じゃありません」

「??? どういうこと?」

テトラ「……あたし、気付いたことがあります」

「?」

テトラ「答えを知っていると、《ヒント》や《答えへの道筋》をつい、すぐに話したくなってしまいますね! テトラ、沈黙します……」

テトラちゃんはそう言うと、両手でぎゅっと口を塞いだ。

は考える。

MOVE-TO-LASTは、MOVE-TO-FIRSTと同じ難易度じゃないんだろうか。

指定された値のノードを探すのも、リンクのつなぎ方を変えるのも、似たような動作になるはずだ。そういう意味では、難易度は少し低くなるか。テトラちゃんのList 14を参考にすればいいから……

ああ、もしかすると……?

テトラ「……えんあい、いああえうあ?」

「テトラちゃん、もう口から手を離してもいいよ」

テトラ「……先輩、いかがですか?」

「うん、MOVE-TO-LASTのプログラムはもうできたよ。 いまは図を描いて確かめているところ。こういう実行例になるはずだよね」

MOVE-TO-LAST(D, 59)の実行例(59という値を持つノードを末尾に移動する例)

テトラ「そうですねっ!」

「……ああ、ちゃんとうまくいく。 List 15が僕の解答なんだけど、これ、すごいよね」

List 15 解答5(双方向リスト版のMOVE-TO-LAST

テトラ「すごいですよね……」

「うん。このList 15MOVE-TO-LASTは、 List 14MOVE-TO-FIRSTに対して《すべてのprevとnextを交換しただけで完成してしまう》んだ!」

MOVE-TO-FIRSTとMOVE-TO-LASTの比較

テトラ「はいはい、その通りです。先輩、さすがですね。 あたしが双倉図書館でこの問題を考えたときは、 気がつきませんでした……」

MOVE-TO-FIRSTから機械的にMOVE-TO-LASTが作れる。考えてみれば当たり前なんだけど、実際に図を描いて確かめてみるとやっぱり驚いちゃうなあ」

テトラ「はい。双方向リストが持っている《対称性》が効いていますよね」

「確かに」

テトラ「これであたしが思ったのは、別世界の言葉についてでした」

「別世界の言葉?」

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 434本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2021年5月21日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home