第324回 アルゴリズム、なかなか大変(後編)

うまくいかなくて意気消沈した「僕」。はげますテトラちゃん。新たなアルゴリズムに挑戦して……

新シリーズ「数学ガールの物理ノート」始動!

『数学ガールの物理ノート/ニュートン力学』

『数学ガールの物理ノート/ニュートン力学』をアマゾンで見る

登場人物紹介

:数学が好きな高校生。

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

$ \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{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \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が作れる。考えてみれば当たり前なんだけど、実際に図を描いて確かめてみるとやっぱり驚いちゃうなあ」

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

「確かに」

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

「別世界の言葉?」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

プログラミングと数学のやさしい関係を解きほぐす一冊。

プログラマの数学第2版

結城 浩
SBクリエイティブ; 第2版
2018-01-17

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

wed7931 次回以降につながる準備なのかな?と勝手に想像しながら読んだ。アルゴリズムもおもしろいけど、計算量の話もおもしろい。 |結城浩 @hyuki |数学ガールの秘密ノート https://t.co/eYXgNClqU1 約2ヶ月前 replyretweetfavorite

LGipnoz へええ双方向リストの端っこ同士、きれいに対になってるんだあ…。機械的に付け替えればいいと分かっても動かすまでハラハラしそう 2ヶ月前 replyretweetfavorite

fall_twtr あぁやっぱり。メタトークで言われている動かないケース、1要素のときか。感覚的になんでそうなるか理解できてないから後でもうちょい考えよう 2ヶ月前 replyretweetfavorite

Lsdu2DalePerry 今回も読む、読む、読むしかない(理解出来ているかは・・・)。 《僕》が描いた図を見ながら勉強しましょうかね・・・。 2ヶ月前 replyretweetfavorite