第325回 スタックとキュー(前編)

リンクを付け替えることにどんな意味があるんだろう。テトラちゃんが教えるアルゴリズム入門!

読者アンケートご回答のお願い(終了しました)

読者アンケートは終了しました。多数のご回答ありがとうございました!

こんにちは、結城浩です。

最近は、テトラちゃんがアルゴリズムを「僕」に説明する話題が展開していますが、本連載を読んでくださっている方向けに無記名のアンケートを実施しています。

今後の進め方についてテトラちゃんに伝えますので、ぜひご回答ください!

回答が必須の設問は7個だけで、すべて選択式です。

(終了しました)アルゴリズム編のWeb連載「数学ガールの秘密ノート」についてのアンケート

※アンケートの実施は2021年5月末ころまでをめどにしています。

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

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

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

登場人物紹介

:数学が好きな高校生。

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

$ \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}} \newcommand{\LNOT}{\lnot} $

間違い探し

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

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

いまは、配列から双方向リストを作るプログラムを考えていて……

配列から双方向リストを作る(NEW-LIST-FROM-ARRAY)

与えられた配列の各要素を順番にノードに持つ双方向リストを得る。

入力

  • 要素として数が格納された配列$A$
  • 配列に格納されている要素数$n$

出力

  • $\LLRR{A[1], A[2], \ldots, A[n]}$という列を表す双方向リスト。

NEW-LIST-FROM-ARRAYの実行例

  • 入力 $A[1] = 31, A[2] = 41, A[3] = 59, n = 3$
  • 出力 $D = \LLRR{31, 41, 59}$

テトラList 23NEW-LIST-FROM-ARRAYの《まちがった実装例》があります」

「《まちがった実装例》って?」

テトラ「つまり、いわゆるバグのあるプログラムです。問題7の間違い探しをしてくださいっ!」

List 23 問題7(間違い探し)

「ええと……」

List 23をていねいに読んでいく。

テトラちゃんの《講義》でわかったことがある。それは「簡単に見えるプログラムでも油断はできない」という当たり前の事実だ。

ほんのちょっとした違いでも、プログラムはおかしな動作をする。パパッと見て正確な動作を言い当てることは難しいし、 もしも思い込みがあったりしたらなおさらだ。

そして……うん、図を描こう。

テトラ「……」

「……」


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

「うん、List 23の間違いはわかったと思う。まず、基本的には、このNEW-LIST-FROM-ARRAYは動くよね。 といってもそれは『少なくとも配列から双方向リストを作ってはいる』という意味だけど、双方向リストじゃない変なものができるわけじゃない」

テトラ「はいはいっ!」

List 23の行番号でいうと、A2でリストヘッドを作る。これは、要素が0個の双方向リストといえる。その後、A3からA11までのwhileの繰り返しで、 $$ A[1], A[2], A[3], \ldots, A[n] $$ という値を双方向リストに順番に挿入している……繰り返しのたびに$k$が増えていく。1からnまで順番に」

テトラ「はい……」

「それで、A6からA9のリンクの付け替えは、これまでに練習したものと同じだから間違いはないんだけど、重大な間違いがある。このList 23のままだと『配列の要素が逆順になった双方向リスト』になってしまう。 そこが間違いだね!」

テトラ「はいっ、そうです。そこが間違いになります。先輩、大正解ですっ!」

テトラちゃんは、うれしそうに拍手してそう言った。

その瞬間、の心に深い喜びがやってきた。

新鮮な感覚だ。間違い探しで正解を出したことは、 それだけでもちろんうれしいんだけど、 こんなふうに拍手されるなんて、これまであっただろうか。

小学生のころなら、もしかしたらあったかもしれないけれど……

「……」

テトラ「正解です……よ?」

「あ、うん。いや、ありがとう、テトラちゃん」

テトラ「は、はあ」

具体的に確かめる

List 23の間違い探しがちょっと難しいのは、与えられた配列の要素が一個の場合、つまり$n = 1$の場合には間違いに気付かない点だね」

テトラ「そうですね。要素が一個なら、逆順になってもわかりませんから」

「僕は、$$ A[1] = 10,\, A[2] = 20,\, n = 2 $$ を使って、10と20を順番に入れようとしたところで気付いたよ。A6からA9は、 pが指している新たなノードを双方向リストDの《先頭》……つまりリストヘッドの次に入れる処理だから、 毎回《先頭》に入れていったら逆順になっちゃうんだね」

10と20を順番に《先頭》に入れると逆順になる

テトラ「先輩ならどう修正なさいますか?」

「うん。確保したノードを双方リストの《末尾》に入れればいいね。それには、A6からA9のnextとprevをすべて逆にすればいい!」

List 24 解答7

List 23のままでは、与えられた配列の要素が逆順になった双方向リストになってしまうので、以下のように修正する。

10と20を順番に《末尾》に入れると正しい順番になる

テトラ「はい、List 24のようにしてもいいですし、List 25のように配列の要素を逆順に入れるという手もあります」

List 25 解答7a(別解)

「なるほど。nextとprevはList 23のままにしておいて、$k$をnから1まで減らしていくんだね。確かに同じことだ」

次の問題は?

テトラNEW-LIST-FROM-ARRAY以外にも、まだまだ問題はあります。次はどんな問題がお好みでしょうか?」

「そうだなあ……リンクの付け替えでいろんなことができるのはわかってきたんだけど、これっていったんどんなふうに役立つんだろうね」

テトラSo what?(だから、何?)ですねっ!」

「ああ、確かに。テトラちゃんが出してくる《根源的な質問》に近いかも。根源的というよりも応用的かもしれないけど……」

テトラ「それでは、こんな問題はいかがでしょう!」

問題8(カッコの対応)

与えられた《文字列》に現れる「カッコ」が正しく対応しているかどうかを調べるアルゴリズムMATCHEDを考えてください。

入力

  • 文字列を一文字ずつ読めるファイル$f$(文字を読む方法は後述します)

出力

  • カッコが正しく対応してるならば、true
  • カッコが正しく対応していないならば、false

文字を読む方法

NEXT-CHARACTERという手続きを使い、以下のようにしてファイルの先頭から一文字ずつ文字を読んでいくことができます。 $$ c \leftarrow \textrm{NEXT-CHARACTER}(f) $$ もしも文字をすべて読み尽くしていたならば、終端を表す特殊な文字が得られます。

それから……

「カッコの対応を調べるアルゴリズム……なるほどね。たとえば、$$ (1 + 2) $$ のようになっていたら正しい対応になっていて、 $$ (1 + 2 $$ だったら正しくない対応という意味かな? そんなに難しくなさそう」

テトラ「それだけじゃなくてですね……」

「ああ、そうか。複数個あるのか! たとえば、$$ ((1 + 2) + 3) $$ のようになる場合があるんだね。だとすると……」

テトラ「ええ、そうなんですが……」

「うん、簡単だね。開きカッコの個数を数えるだけで済む」

テトラ「……といいますと?」

「開きカッコの個数と、閉じカッコの個数が等しくなればいいよね。まだ閉じていない開きカッコの個数を、最初は0にしておいて、 読んだ文字が開きカッコだったら1増やして、閉じカッコが来たら1減らす。 文字を読み終えたとき、閉じていない開きカッコの個数が0になっていたら正しいカッコの対応だ」

テトラ「先輩、先輩! 問題は最後まで聞いてくださいっ!」

「……はい。すみません」

反省。

これじゃはまるで、はしゃいでいる小学生だな。テトラ先生に「めっ」と怒られそうだ……

テトラ「先輩のおっしゃる《開きカッコの個数を数える》方法ではまずいことが起きます。たとえば、 $$ ))1 + 2(( $$ という文字列が与えられた場合でも、 文字を読み終えたときには閉じていない開きカッコの個数は0ですよね。 でもこれは、正しいカッコの対応とはいえません」

「確かに。文字を読んでいる途中で負になってはいけないという条件が必要だね」

テトラ「それに、カッコは一種類とは限りません。たとえば、$$ [ \{1 + 2\} + (3 - 4) ] $$ のようになっていても、正しいカッコの対応であると見なすことにします。 でも、 $$ [ ( 1 + \{ 2 + 3 ) - 4 \} ] $$ は正しいカッコの対応とは見なさないことにします。正しい入れ子になっていないからです」

「なるほど……だとすると、カッコの種類ごとに数を数える必要があるか。いや、待てよ……」

テトラ問題8を改めて示しますね」

問題8(カッコの対応)

与えられた《文字列》に現れる「カッコ」が正しく対応しているかどうかを調べるアルゴリズムMATCHEDを考えてください。

入力

  • 文字列を一文字ずつ読めるファイル$f$(文字を読む方法は後述します)

出力

  • カッコが正しく対応してるならば、true
  • カッコが正しく対応していないならば、false

文字を読む方法

NEXT-CHARACTERという手続きを使い、以下のようにしてファイルの先頭から一文字ずつ文字を読んでいくことができます。 $$ c \leftarrow \textrm{NEXT-CHARACTER}(f) $$ もしも文字をすべて読み尽くしていたならば、終端を表す特殊な文字が得られます。

文字を調べる方法

  • $\textrm{IS-OPEN}(x)$は、文字$x$が開きカッコのときにtrueで、それ以外のときにfalseとなります。
  • $\textrm{IS-CLOSE}(x)$は、文字$x$が閉じカッコのときにtrueで、それ以外のときにfalseとなります。
  • $\textrm{ARE-MATCHED}(x,y)$は、文字$x$が開きカッコで、文字$y$が閉じカッコで、$x$と$y$が対応しているときにtrueで、それ以外のときにfalseとなります。
  • $\textrm{IS-TERMINATOR}(x)$は、文字$x$が終端のときにtrueで、それ以外のときにfalseとなります。

MATCHEDは、どんなときに何を返すか

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

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

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

人気の連載

おすすめ記事

パズルとクイズでプログラミングに役立つ「考え方」を学ぼう!

プログラマの数学第2版

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

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 321回から読み返して、いちぶわからないところはあるものの、リストの付け替えに関してはなんとか理解できてきた。わかると楽しい。次はスタック。 6ヶ月前 replyretweetfavorite

hyuki 森を抜けて仕事場へ。と書きつつ今日も自宅作業。今日は最初に、毎週金曜日更新のWeb連載「数学ガールの秘密ノート」第326回をまとめましょう。なお、第325回は金曜日の朝7:00まで無料なので、ぜひお読みくださいね! https://t.co/mjKc5nM5BT 6ヶ月前 replyretweetfavorite

asangi_a4ac prev, nextがポインタの値なのかポインタの指す先のデータなのかわからなくなってきたので少し前から読みなおす https://t.co/Qs1utJSfDw 6ヶ月前 replyretweetfavorite

fall_twtr インタフェースの概念まで出てきた。 タイトルが「スタックとキュー」ながら、次回でスタックを実装… https://t.co/PKWIoGe0aB 6ヶ月前 replyretweetfavorite