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

さあ、いっしょにアルゴリズムを学ぼう! いつもは教える立場が多い「僕」だけど、今回はテトラちゃんからアルゴリズムを教わる立場。その結果……

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

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

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

登場人物紹介

:数学が好きな高校生。

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

$ \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回参照)と、 いろんな議論を重ねてきた。

いまは、 リストヘッド付き線形リストというデータ構造を議論しているところ。

テトラ「リストヘッドがあると、List 9のようにシンプルに書けるんですよ!」

List 9:リストヘッド付き線形リスト版MOVE-TO-FIRST

実行例

はしばらくList 9を眺めた。

うん、確かにずいぶんシンプルになったけど……!

「ちょっと待って。これって$a_1 = v$のときでもうまくいく? 怪しくない? だって、H5H9ではどんなときでもリンクを切り換えてしまうよね?」

テトラ「驚くことに、うまく行くんですよ!」

テトラちゃんが図を描こうとしているあいだ、はもう一度List 9を読み返した。

「いやいや、駄目だよ。だって、$a_1 = v$のときは、pはリストヘッドを指していて、qは最初のノードを指している。その状態でH6にやってくる。H6はいいとして、H7がまずいよ。だって、 $$ q.\Fnext \leftarrow H.\Fnext $$ を実行してしまったら、最初のノードは自分自身を指してしまうことになる! 線形リストが途中で切れてしまうはずだよ」

テトラ「……ところがそうはならないんですよ、先輩。こちらのステップ・バイ・ステップで描いた図をごらんください。 先輩が気になさっていたH7を実行するときには、$H.\Fnext$の値は最初のノードではなくなっているので、 途中で切れることはないんですっ!」

HEAD-TO-FIRST(H, v)でvに31が渡された場合の、H6, H7, H8の動き

は、彼女が描いた図を見てショックを受けた。

「本当だね。うーん……」

テトラ「もちろんこの場合、代入を三回行って結局は何も変わっていないことになります。でも、先頭を特別扱いしなくて済むとプログラムはシンプルになりますので、 間違いが入り込む危険性も少なくなります。 リストヘッド付きの線形リストでは、そういうことがよくあるそうです」

「いや……それはわかったんだけど」

テトラ「先輩?」

「テトラちゃんはきちんと図を描いて説明してくれたけれど、僕は先を急いで読もうとしてしまい……まちがった。 たった三ステップしかないんだから、ほんの少しの時間を使うだけですぐに図を描けるし、 図を描きさえすれば自分のまちがいに気がつく。 その《ほんの少しの時間》を、自分が無意識のうちに惜しんだことがショックなんだ」

テトラ「双倉図書館の一般講座でも、講師の先生はそんなことをおっしゃっていました。《ステップ・バイ・ステップ》で確かめることが、結局のところ近道になることが多いというお話です。 あたし、それにすごく励まされました。 たとえ、すごいひらめきがやってこなくても、 根気よく確かめることはあたしにもできそうだからです!」

「なるほどねえ……」

そしてまたは『グラフを描かないのが君の弱点だ』といったミルカさんのことを思い出した。

グラフに限った話じゃないなあ……

代入で起きていること(左辺値と右辺値)

テトラ「先輩はすっと理解してしまいましたが、あたしはアルゴリズムの一般講座で悩んだのは、たとえば、$$ p \leftarrow H $$ という代入でした。この表記が……」

「これはHをpに代入するということだよね」

テトラ「はい。もちろんそうなんですが、あたしが引っかかったのは、$$ p \leftarrow H $$ と表現されたとき、pとHとでは意味が違うという点でした」

「意味が違う?」

テトラ「はい。こういうことです」

  • 左辺の$p$は、どこかにあるメモリの場所を表している。
  • 右辺の$H$は、どこかにあるメモリの場所に保持されているを表している。

「……ああ、確かにそうだね。$p \leftarrow H$と書かれているときに行われるのは、こうだから」

  • $H$と名前がついている場所に保持されているを、
  • $p$と名前がついている場所に格納する。

テトラ「はいはい! そういうことです。図を描いていて、それに気付いてからプログラムが読みやすくなりました。講師の先生にお尋ねしたところ、左辺値(さへんち)と右辺値(うへんち)という名前がついているそうです。 《左辺値》は《値を保持している場所を表す値》のことで《メモリのアドレス》と思えばわかりやすいです」

「《左辺値》は代入の左辺に来ることができる値ってことだね。代入できる場所を表す値だ」

テトラ「だいたいはそうなんですが、プログラミング言語によってはメモリのアドレスは表しているけれど、代入できない定数のような概念があるので《左辺値》のことを《代入できる場所を表す値》というのは不正確だそうです」

「そうなんだね……ところで《右辺値》の方は123のような値のことかな」

テトラ「はい。《右辺値》は、123のような値の場合もあるし、《左辺値》を《右辺値》として扱う場合もあるそうです。先ほどの$p \leftarrow H$の場合もそうですよね」

「変数Hの値は、ノードを表すアドレスだから《左辺値》といえるけど、$$ p \leftarrow H $$ では、その値を変数pに代入する《右辺値》として扱っている?」

テトラ「そうです、そうです。いずれにしても、図を描けばあまりまちがうことはありません」

「いわれてみると、$$ p.\Fnext \leftarrow q.\Fnext $$ は自然に読んじゃったけど、左辺と右辺で確かに違うものを表しているね」

$p.\Fnext \leftarrow q.\Fnext$

左辺の$p.\Fnext$は、《pが指している先にあるノードの、nextフィールドという場所》を表している。

右辺の$q.\Fnext$は、《qが指している先にあるノードの、nextフィールドに保持されている》を表している。

テトラ「そうです! この場合、代入によって、同じ場所を指すようになるわけですね。図に描くとわかりやすいです」

※nextフィールドに書かれた数値はアドレスの例を表しているものとします。

※nextフィールドに書かれた数値はアドレスの例を表しているものとします。

テトラちゃんのクイズ

テトラ「それではここで先輩にクイズをひとつ、お出しします!」

テトラちゃんはにこやかにそう言って、人差し指を立てた。

「おっ?」

テトラ「線形リストにリストヘッドをつけて、プログラムがシンプルになった理由は何でしょう?」

「理由……?」


テトラ「いかがですか?」

「リストヘッドをつけると、先頭を特別扱いしなくて良くなるから、かな。List 8のテトラちゃんのプログラムがまさに先頭を特別扱いしていたから(第322回参照)」

テトラ「はい、そうですね。先頭を特別扱いしなくてよくなります。もう少しいいますと、こうなります」

リストヘッドがない場合

  • 先頭のノードには《一つ前のノード》が存在しません。
  • 先頭のノード以外には《一つ前のノード》が存在します。

リストヘッドがある場合

  • すべてのノードには《一つ前のノード》が存在します。

「確かにそうなるね。リストヘッドという特別のノードを最初に置くことで、すべてのノードを統一的に扱えるようになる。だからプログラムがシンプルになる」

テトラ「はい。いうなれば《一様性》や《均一性》があるためにシンプルになるんです」

「なるほどね」

テトラちゃんのクイズ、もっと

テトラ「ところで先輩に、もうひとつ、クイズをお出しします」

「今度は何だろう」

テトラ「あたしたちは《リストヘッド付き線形リスト》を扱ってきましたけれど、ここにはまだ《一様性》に欠けている部分があります。 それはどこでしょうか?」

「うーん……」


テトラ「いかがでしょう?」

「たぶん、リストの最後だね。リストの最後にあるノードには《一つ次のノード》が存在しない。最後のノードのnextフィールドには、nilが保持されている。 でも、nextフィールドにnilが保持されているのは最後のノードだけ。ここじゃない?」

テトラ「はいっ! 正解です!」

「ということは、《リストテール付きの線形リスト》を考えることができるんだね」

テトラ「それでもいいんですが……もっと便利なものがあります。それは《リストヘッド付き循環リスト》です」

「循環リスト?」

リストヘッド付き循環リスト

テトラ「はい。この図のように、リスト最後のノードのnextフィールドが必ずリストヘッドを指すようにするんです。そうすると、山手線のようにぐるっと回るデータ構造ができあがります。 これが《リストヘッド付き循環リスト》です。nextフィールドにnilはもう出てこなくなります」

リストヘッド付き循環リスト

「ちょっと待って。だったら、どうやってリストの終わりを判定するんだろう……ああ、リストヘッドかどうかで判定すればいいのか」

テトラ「その通りです! 《リストヘッドを指している》という状況を《nilである》という扱いにするんです」

「……」

テトラ「な、何かおかしいでしょうか?」

「いや、おかしくはないし、確かに《一様性》はわかるんだけど、それだけでそんなにシンプルになるのかなあ……」

テトラ「では問題3ですっ! プログラムを書きましょうっ!」

問題3 数列内に値が存在するかどうかの判定

問題3(数列内に値が存在するかどうかの判定)

与えられたリストヘッド付き循環リストCに含まれているノードのうち、 valueフィールドの値が、与えられたvに等しいものがあるかどうかを判定する手続きCONTAINS(C, v)を書いてください。

手続き

  • $\textbf{CONTAINS}(C, v)$

入力

  • 検索の対象となるリストヘッド付き循環リスト$C$
  • 検索する値$v$

出力

  • vに等しいvalueフィールドを持つノードが見つかった場合にはtrueを返します。
  • vに等しいvalueフィールドを持つノードが見つからなかった場合にはfalseを返します。

CONTAINS(C,v)への入力&出力例1

入力

  • $C = \LLRR{31,41,59,26,53}$
  • $v = 59$

出力

  • true(Cが表す数列の中に59が含まれているため)

CONTAINS(C,v)への入力&出力例2

入力

  • $C = \LLRR{31,41,59,26,53}$
  • $v = 99$

出力

  • false(Cが表す数列の中に99は含まれていないため)

「ああ、これは簡単だね……っとっと。いや、ちゃんと考えないと」


テトラ「……いかがでしょうか?」

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

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

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

人気の連載

おすすめ記事

アルゴリズムを基本から学ぼう!

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

hyuki 森を抜けて仕事場へ。と書きつつ今日も自宅作業。今日は毎週金曜日更新のWeb連載「数学ガールの秘密ノート」を書く一日です。最近はテトラちゃんのやさしいアルゴリズム講座が続いています😊双方向リスト〜 #cakes連載 https://t.co/js5bYvsMOC 5ヶ月前 replyretweetfavorite

aramisakihime 今回も、追うのがなかなか大変でした…でも第321回を改めて読み返すと初読時よりは読めたので、日を改めて再読しましょう。 5ヶ月前 replyretweetfavorite

santa_MixCosy あ、これね。 https://t.co/OIc0M5vQcD 5ヶ月前 replyretweetfavorite

Lsdu2DalePerry 残念ながら今回も内容を追っかけるので精一杯。でもプログラミングも面白そうだな・・・ 5ヶ月前 replyretweetfavorite