Summer/2006-04 の履歴(No.3)

• 履歴一覧
• 差分 を表示
• 現在との差分 を表示
• ソース を表示
• Summer/2006-04 へ行く。
  • 1 (2006-09-10 (日) 15:04:26)
  • 2 (2006-09-10 (日) 16:59:37)
  • 3 (2006-09-16 (土) 09:38:49)

第4日午後　アルゴリズムとC言語実習†

目次†

上級課題†

時間の余った人やさらに勉強したい人は、以下の問題を読んでC言語のプログラムを作ってみなさい。プログラムは下記のアドレスにメールで提出してください。

hi-shiozawa＠engs.tamagawa.ac.jp

注意！ 上のアドレスは，＠マークを半角文字（@）にしないと送れません。

線形探索（逐次探索）†

配列の中からある値を探し出すときのことを考えてみよう。まず、誰でも思いつくのは、配列の先頭から順に値と比較していく方法である。これは線形探索といい、もっとも素朴で確実な探索の方法である。

【問1】 キーボードから、10個の整数を要素とする配列aと、整数xを読み込み、xがaに含まれているかどうか調べて結果を表示するプログラムを作成しなさい。

   i→                      →|    iを0から9まで変化させる
   0  1  2  3  4  5  6  7  8  9
a [__|__|__|__|__|__|__|__|__|__]

          a[i]とxを比較

スタック†

スタックとは、先入れ後出し方式のデータ構造である。データを上に積み重ねていくような形式のデータ構造であり、一番最後に積んだデータを一番最初に取り出すことができる。一番最初に積んだデータは、後から積んだデータを全部取り出さないと、取り出すことができない。ここでは、段階的にスタックを作ってみよう。

【問2a】 キーボードから100個以内の正の整数を読み込んでいき、0以下の数が入力された時点で終了として、それまでに入力された整数をすべて表示するプログラムを作成しなさい。

【問2b】 次のような動作をするプログラムを作成しなさい。前項との違いは最後に逆順に表示することだけである。

1. 100個の整数を保存しておくための配列stackを用意する。
2. キーボードから整数xを読み込む。
3. xの値を判定し：
   • x>0ならば、xをstackの最後に追加して（積んで）2.に戻る。
   • そうでなければ、stackの中身を逆順にすべて表示して、プログラムを終了する。

                次の空き
                ↓
       0  1  2  3  4  5  6  7  8  9
stack [●|●|●|__|__|__|__|__|__|__|....
                ↑
                xを積む（push）

                   次の空き
                   ↓
       0  1  2  3  4  5  6  7  8  9
stack [●|●|●|ｘ|__|__|__|__|__|__|....

【問2c】 以下に示すような動作をするプログラムを作成しなさい。

1. 100個の整数を保存しておくための配列stackを用意する。
2. キーボードから整数xを読み込む。
3. xの値を判定し：
   • x>0ならば、xをstackに積んで2.に戻る（push）。
   • x<0ならば、stackに最後に積んだ値を表示して、それをstackから取り除き、2.に戻る（pop）。
   • x=0ならば、stackの中身を逆順にすべて表示して、プログラムを終了する。

                         次の空き
                         ↓
       0  1  2  3  4  5  6  7  8  9
stack [●|●|●|●|●|●|__|__|__|__|....
                      ↓
                      取り出す（pop）

                      次の空き
                      ↓
       0  1  2  3  4  5  6  7  8  9
stack [●|●|●|●|●|__|__|__|__|__|....

なお、スタックにデータをしまう操作をpushといい、データを取り出す操作をpopという。また、スタックの現在の最後の位置（または次の空きの位置）を保存する変数をスタックポインタという。