金沢大学 自然科学研究科 電子情報通信学専攻 2022年8月実施 専門科目 アルゴリズムとデータ構造

标签：

• 金泽大学
• 链表
• 队列
• 汉诺塔

Author

祭音Myyura

Description

以下の設問に答えなさい。

問1

図1は，線形リストを用いてデータの集まりを操作する処理を，C 言語の記法に則り記述している。

#include <stdio.h>
#include <stdlib.h>

struct nd {
    char data;
    struct nd *next;
};

struct tag {
    struct nd *head;
    struct nd *tail;
};

void input(char data, struct tag *list) {
    struct nd *new = malloc(sizeof(struct nd));
    new->data = data;
    new->next = NULL;

    if (list->head == NULL && list->tail == NULL) {
        list->head = new;
        list->tail = new;
    } else {
        list->tail->next = new;
        list->tail = new;
    }
}

char output(struct tag *list) {
    struct nd *tmp;
    char data = '\0';

    if (list->head != NULL) {
        data = list->head->data;
        tmp = list->head;
        list->head = list->head->next;
        if (list->head == NULL) list->tail = NULL;
        free(tmp);
    }

    return data;
}

int main(void) {
    struct tag list;
    char x;

    list.head = NULL; list.tail = NULL;  // ①
    input('a', &list);                   // ②
    input('b', &list);                   // ③
    input('c', &list);                   // ④
    x = output(&list);                   // ⑤
    x = output(&list);                   // ⑥

    return 0;
}

(1) 図1のプログラムを実行すると，プログラム中の ①〜⑥ の処理によって，線形リストの構造がどのように変化するか，①〜⑥ の各処理が終了した直後の構造を，図を用いて説明しなさい。

(2) 図1に示す input と output の二つの操作を持つデータ構造の名称を答えなさい。

(3) このデータ構造は配列でも実現できるが，線形リストを用いた場合との違いを説明しなさい。

(4) このようなデータ構造は，どのようなデータ処理で利用されているか，一例を挙げなさい。

問2

図2は固定された 3 本の棒 A, B, C のいずれかに，中心に穴が空いた大きさの異なる $n$ 枚の円盤すべてを大きい円盤が下となるように重ねた様子を表している。図2の例では 3 枚の円盤を，棒 A に重ねている。

題面の説明に基づく初期配置の模式図（原図の複製ではない）：

     |             |             |
    [1]            |             |
   [ 2 ]           |             |
  [  3  ]          |             |
-----A-------------B-------------C-----

これら $n$ 枚の円盤を以下のルールに従って，移動することとする。

一回の移動では，1 枚の円盤を必ず棒 A〜C のいずれかに移動する。 動かせる円盤は，一番上の円盤だけとする。動かす円盤は，どの棒から選んでもよい。 小さい円盤の上に大きな円盤を重ねてはならない。

$n$ 枚のうち $m$ 番目に小さい円盤 $(1\leq m\leq n)$ が棒 $X$ の一番上にあるとき，その円盤を棒 $Y$ に移動する操作を

move(m,X,Y)

$n$ 枚の円盤すべてを棒 $X$ から棒 $Y$ に最小回数で移動する操作を

trans(n,X,Y)

と定義する。ただし $X,Y$ は，棒 A, B, C の任意の2つを表す。

(1) 図2に示した 3 枚の円盤に対し，$\mathrm{trans}(3,A,B)$ を行う手順を，$\mathrm{move}(m,X,Y)$ を用いて示しなさい。

(2) $\mathrm{trans}(n,X,Y)$ に必要な移動回数を $a_n$ としたとき，$a_1$ の値および $n\geq 2$ における $a_n$ と $a_{n-1}$ の関係式を求めなさい。

(3) (2) で求めた関係式を用いて $a_n$ を $n$ で表しなさい。

题目描述

回答下列问题。

1. 图 1 用接近 C 语言的写法给出一个以链表操作数据集合的程序：

   #include <stdio.h>
   #include <stdlib.h>
   
   struct nd {
       char data;
       struct nd *next;
   };
   
   struct tag {
       struct nd *head;
       struct nd *tail;
   };
   
   void input(char data, struct tag *list) {
       struct nd *new = malloc(sizeof(struct nd));
       new->data = data;
       new->next = NULL;
   
       if (list->head == NULL && list->tail == NULL) {
           list->head = new;
           list->tail = new;
       } else {
           list->tail->next = new;
           list->tail = new;
       }
   }
   
   char output(struct tag *list) {
       struct nd *tmp;
       char data = '\0';
   
       if (list->head != NULL) {
           data = list->head->data;
           tmp = list->head;
           list->head = list->head->next;
           if (list->head == NULL) list->tail = NULL;
           free(tmp);
       }
   
       return data;
   }
   
   int main(void) {
       struct tag list;
       char x;
   
       list.head = NULL; list.tail = NULL;  // ①
       input('a', &list);                   // ②
       input('b', &list);                   // ③
       input('c', &list);                   // ④
       x = output(&list);                   // ⑤
       x = output(&list);                   // ⑥
   
       return 0;
   }

   （1）执行该程序时，画图说明语句 ① 至 ⑥ 各自执行完毕后链表结构如何变化。

   （2）写出具有图中 input 和 output 两种操作的数据结构名称。

   （3）该数据结构也可用数组实现。说明数组实现与链表实现的区别。

   （4）举出一种会使用该数据结构的数据处理场景。

2. 图 2 中有固定的三根柱 A、B、C，$n$ 个中心有孔且大小各异的圆盘全部按大盘在下的顺序叠在其中一根柱上；图示例为三个圆盘叠在 A 上。移动圆盘须遵守：

   • 每次必须把一个圆盘移动到 A、B、C 中的一根柱上；
   • 只能移动某根柱最上方的圆盘，且可从任意柱选取；
   • 不得把大圆盘放在小圆盘上。

   若第 $m$ 小的圆盘（$1\leq m\leq n$）位于柱 $X$ 顶部，把它移到柱 $Y$ 的操作记作

   move(m, X, Y)

   把全部 $n$ 个圆盘以最少次数从柱 $X$ 移到柱 $Y$ 的操作记作

   trans(n, X, Y)

   其中 $X,Y$ 是 A、B、C 中任意两根不同的柱。

   （1）对图 2 的三个圆盘，用 move(m, X, Y) 写出执行 $\operatorname{trans}(3,A,B)$ 的步骤。

   （2）令 $a_n$ 为执行 $\operatorname{trans}(n,X,Y)$ 所需的移动次数。求 $a_1$，并对 $n\geq2$ 给出 $a_n$ 与 $a_{n-1}$ 的递推关系。

   （3）利用第（2）问的递推式，用 $n$ 显式表示 $a_n$。

Kai

問1

(1)

① 実行直後

list.head = NULL
list.tail = NULL

head
 ↓
NULL

tail
 ↓
NULL

まだノードは存在しない。

② input('a', &list) 実行直後

head ─┐
      ↓
    +---+------+
    | a | NULL |
    +---+------+
      ↑
tail ─┘

データ 'a' を持つノードが 1 個作られる。head と tail は同じノードを指す。

③ input('b', &list) 実行直後

head
 ↓
+---+------+     +---+------+
| a | next | ──> | b | NULL |
+---+------+     +---+------+
                   ↑
                  tail

④ input('c', &list) 実行直後

head
 ↓
+---+------+     +---+------+     +---+------+
| a | next | ──> | b | next | ──> | c | NULL |
+---+------+     +---+------+     +---+------+
                                      ↑
                                     tail

⑤ x = output(&list) 実行直後

head
 ↓
+---+------+     +---+------+
| b | next | ──> | c | NULL |
+---+------+     +---+------+
                   ↑
                  tail

⑥ x = output(&list) 実行直後

head ─┐
      ↓
    +---+------+
    | c | NULL |
    +---+------+
      ↑
tail ─┘

(2)

• キュー
• FIFO
• 待ち行列

(3)

配列でキューを実現する場合，データを格納する領域をあらかじめ確保しておく必要がある。そのため，配列の大きさを超えるデータを格納することはできない。

一方，線形リストを用いた場合は，必要に応じてノードを動的に確保するため，メモリが許す範囲でデータ数を増減できる。

また，配列で単純に先頭要素を削除すると，残りの要素を前に詰める処理が必要になる場合がある。これに対して，線形リストでは head の指す位置を次のノードに変更すればよいので，先頭からの取り出しを効率よく行うことができる。

ただし，線形リストでは各ノードに next ポインタが必要であり，ポインタ分のメモリが余分に必要となる。また，各ノードがメモリ上に連続して配置されるとは限らないため，配列のような添字による直接アクセスはできない。

配列でも循環バッファを用いれば、要素を詰め直さず、挿入と取り出しをともに $O(1)$ で実装できる。動的配列なら容量も拡張できるが、その際は再確保とコピーが必要になる。

(4)

キューは，先に到着したデータを先に処理する場面で利用される。

例として，プリンタの印刷待ち行列が挙げられる。複数の印刷要求が発生したとき，先に送られた印刷データから順に処理するため，キューが利用される。

ほかにも，以下のような処理で利用される。

• OS におけるプロセスの待ち行列
• ネットワーク通信におけるパケットのバッファ
• 幅優先探索における探索待ち頂点の管理

問2

(1)

3 枚の円盤を棒 A から棒 B へ移動する。 補助の棒として C を用いる。

手順は次の通りである。

move(1, A, B)
move(2, A, C)
move(1, B, C)
move(3, A, B)
move(1, C, A)
move(2, C, B)
move(1, A, B)

したがって，trans(3,A,B) は上の 7 回の move によって実現できる。

(2)

まず，円盤が 1 枚の場合は，その 1 枚を棒 $X$ から棒 $Y$ に移動すればよい。 したがって，

$$a_1 = 1$$

である。

次に，$n$ 枚の円盤を棒 $X$ から棒 $Y$ に移動する場合を考える。残りの棒を $Z$ とする。 $n$ 枚の円盤を移動するには，次の 3 段階が必要である。

• 上の $n-1$ 枚を棒 $X$ から棒 $Z$ に移動する。
• 一番大きい円盤を棒 $X$ から棒 $Y$ に移動する。
• 棒 $Z$ にある $n-1$ 枚を棒 $Y$ に移動する。

したがって，必要な移動回数は

$$a_n = a_{n-1} + 1 + a_{n-1} = 2a_{n-1} + 1 \quad (n \ge 2)$$

となる。

(3)

$$a_n = 2^n - 1$$