Ｃ プログラミング(基礎と応用)
Ｗｉｎｄｏｗｓの基礎
●ＷｉｎｄｏｗｓＸＰの基礎(pdfファイル)１．起動と終了 １．１ 起動法 １．２ 終了法 ２．ウィンドウの基本操作 ２．１ ウィンドウの各部名称 ２．２ ウィンドウの移動 ２．３ ウィンドウ・サイズの変更 ２．４ ウィンドウの重なり ２．５ ウィンドウのスクロール ２．６ ウィンドウを閉じる ３．USBメモリ ４．トラブル対処法 ４．１ 強制終了 ５．ファイル管理 ５．１ 階層構造 ５．２ エクスプローラの使い方 ５．３ ファイルの圧縮と展開●メモ帳の使い方(pdfファイル)
１．新規ファイルの作成 ２．ファイルの修正 ３．ファイルの編集 ３．１ 文字列削除 ３．２ 文字列コピー ３．３ 文字列移動 ４．ファイルの印刷●メールの送受信(pdfファイル)
１．Active!mailとは ２．Active!mailの起動 ３．メールの受信 ４．メールの送信 ５．送信メールの確認 ６．メールの削除 ７．添付メール ７．１ 送信 ７．２ 受信
ＵＮＩＸの基礎
●ＵＮＩＸの基礎Ⅰ(pdfファイル)１．ログイン・ログアウト １．１ 端末エミュレータ（PuTTY) ２．簡単なコマンド ３．ファイル処理 ３．１ ファイル操作法 ３．２ スクリーン・エディタ(vi)の使用法 ３．２．１ 新規ファイル作成 ３．２．２ ファイルの編集 ３．２．３ 漢字入力●ＵＮＩＸの基礎Ⅱ(pdfファイル)
４．便利なコマンド ４．１ コマンド：ｆｉｎｄ ４．２ コマンド：ｇｒｅｐ ４．３ コマンド：ｍａｎ ４．４ コマンド：ｎｋｆ ４．５ コマンド：ｓｃｒｉｐｔ ４．６ コマンド：ｂｃ ５．環境変数 ５．１ 環境変数とは ５．２ 環境変数の参照と設定 ５．３ コマンドの実行と環境変数PATH ５．４ 環境設定のためのファイル ６．パーミッション ６．１ パーミッションとは ６．２ ディレクトリのパーミッションと機能一覧 ６．３ パーミッションの例●PuTTYの使い方(pdfファイル)
１．ログイン・ログアウト ２．設定の変更 ３．PuTTY のインストール●WinSCPの使い方(pdfファイル)
１．ログイン・ログアウト ２．WinSCP のインストール
Ｃ言語の基礎
●Ｃ言語の基礎Ⅰ(pdfファイル)１．はじめに １．１ 簡単な例 １．２ Ｃ言語プログラムの翻訳と実行 ２．条件分岐 ２．１ ｉｆ文 ２．２ ｓｗｉｔｃｈ文 ３．制御構造 ３．１ ｗｈｉｌｅ文 ３．２ ｆｏｒ文 ３．３ ｄｏ文 ３．４ ｃｏｎｔｉｎｕｅ文，ｂｒｅａｋ文 ４．変数、配列 ４．１ 変数 ４．２ １次元配列 ４．３ ２次元配列 ４．４ 局所変数の有効範囲
１．ポインタ変数、構造体 １.１ ポインタ変数 １.２ ポインタ変数と配列 １.３ 構造体 ２．関数 ２.１ 戻り値がない場合 ２.２ 戻り値がある場合 ２.３ 引数について ３．問題 問題１ 正整数を読み込み、含まれている数字のみを用いて最も小さい 正整数を出力せよ。 ただし、複数の正整数について行い、データの最後は0とする。 問題２ 正整数を読み込み、この正整数に含まれない数字のみを用いて最も 小さい正整数を求めよ。 ただし、複数の正整数について行い、データの最後は0とする。 問題３ 正整数を読み込み、異なる数字の個数を出力せよ。 ただし、複数の正整数について行い、データの最後は0とする。 問題４ ふたつの正整数の組を読み込み、両方に含まれている数字のみを 用いて最も小さい正整数を求めよ。そういう数字がない場合は、 0を出力すること。 ただし、複数の組について行い、データの最後は0 0とする。 問題５ ふたつの正整数の組を読み込み、一方または両方に含まれている 数字のみを用いて最も小さい正整数を求めよ。 ただし、複数の組について行い、データの最後は0 0とする。 問題６ ふたつの正整数の組を読み込み、どちらか一方にのみ含まれている 数字を用いて最も小さい正整数を求めよ。 そのような数字がない場合は、0を出力せよ。 ただし、複数の組について行い、データの最後は0 0とする。
Ｃ言語の応用
●文字列処理(pdfファイル)１．文字と文字定数 ２．文字列、文字列定数、文字列配列 ３．文字列の長さ ４．文字列の分離 ５．文字列の連結 ６．文字列関数 ６．１ 文字列の長さを求める関数 ６．２ 文字列を複写する関数 ６．３ 文字列を連結する関数 ６．４ 文字列を比較する関数 ６．５ 文字列から数値への変換 ７ 課題 ７．１ 課題１ ７．２ 課題２ ７．３ 課題３ ７．４ 課題４ ７．５ 課題５●ファイル処理(pdfファイル)
１．はじめに ２．ファイル内容の表示 ３．ファイル内容の複写 ３．１ 文字単位 ３．２ 行単位 ４．書式付き入出力 ５．文字配列への入出力 ６．ファイル圧縮・復元●ビット処理(pdfファイル)
１．ビット演算 １．１ 論理積、論理和、排他的論理和 １．２ 左シフト、右シフト ２．ビット列操作 ２．１ char型変数の表示 ２．２ int型変数の表示 ２．３ int型変数のビット数 ２．４ ビット単位の設定 ３．応用 ３．１ 文字の詰め込みと取り出し ３．２ ビット反転 ３．３ 巡回シフト ３．４ 集合表現●開発環境(pdfファイル)
１．Ｃ言語プログラムの翻訳と実行 １.１ プリプロセス １.２ アーカイブファイルとのリンク ２．実行時間測定 ２.１ ｃｌｏｃｋ関数 ２.２ ｔｉｍｅコマンド ３．ｍａｋｅコマンド ３.１ ｍａｋｅコマンドの動作確認（Makefile1） ３.２ 不要なファイルを削除する機能を追加（Makefile2） ３.３ ヘッダファイルの依存性の自動化（Makefile3) ３.４ 暗黙のルール ４．ファイルの比較と更新(diffコマンド、patchコマンド) ５．バックアップ●AWK入門(pdfファイル)
１．ＡＷＫとは
２．簡単な処理を行うプログラム
２．１ フィールドを選択して出力
２．２ レコードに行番号をつけて出力
２．３ 指定した文字列を含む行のみ出力
２．４ 指定した条件を満たす範囲の行を出力
２．５ 入力ファイル名を出力
３．加減乗除（＋−＊／）
４．書式
５．条件分岐
６．繰り返し
６．１ ｆｏｒ文
６．２ ｗｈｉｌｅ文
７．パターン
７．１ ＢＥＧＩＮ ＥＮＤ
７．２ 正規表現
８．配列
９．例題
９．１ 例題１
９．２ 例題２
９．３ 例題３
９．４ 例題４
９．５ 例題５
プログラミングの基礎
●プログラミングの基礎Ⅰ(pdfファイル)
１．プログラムの作成
１．１ 利息計算
問題１ 元金ａ円、利率ｒで、何年預けると目標金額ｂ円を越えるか。
ただし、if文、goto文を使うこと。
問題２ 元金ａ円,利率ｒで、ｎ年預けると元利合計がいくらになるか。
ただし、for文を使うこと。
問題３ 元金ａ円,積立金t円,利率ｒで、ｎ年預けると元利合計が
いくらになるか。ただし、配列を使うこと。
問題４ 利率ｒで借りたａ円を毎年一定額ｂ円返し、ｎ年で
返済するには、毎年の返済額をいくらにすればよいか。
ただし、配列を使うこと。
問題５ 複利運用早見表を作成せよ。
ただし、利率は、1%から10%、期間は1年から10年とする。
１．２ 市松模様
問題１ ８×８の市松模様を作成せよ。
１．３ 九九の表
問題１ 10進数の九九の表を作成せよ。
問題２ 16進数の九九の表を作成せよ。
１．４ 整数の分解
問題１ 整数を各桁の数字に分解し表示せよ。
１．５ 分数の問題
問題１ 分数(m/n 1≦m＜n)を小数点以下40桁までの小数として
表せ。
問題２ 分数(m/n 1≦m＜n）を小数点表示したとき循環する部分を
求めよ。
●プログラミングの基礎Ⅱ(pdfファイル)
２．プログラムの作成
２．１ コラッツ問題
自然数nから出発して、nが偶数ならば、2で割り、nが奇数ならば、
3倍して1を足す操作を行う。この操作を繰り返すと最後に1になる
と予想されている。
問題１ 自然数aの操作回数を求めよ。
問題２ 自然数aからbまでのなかで、最大操作回数となる自然数を
求めよ。
２．２ 耐久数
正整数の各桁の数字を掛け、得られた結果についても同様の操作を
繰り返す。すると、最後は１桁の数になる。
たとえば、77 -> 49 -> 36 -> 18 -> 8 より、操作回数は4となる。
この操作回数を耐久数という。
問題１ 正整数ｎを複数個読み込み、それぞれの耐久数を求めよ。
ただし、データの終わりは0とする。
問題２ 正整数b(≧10)以下の耐久数を求めよ。
２．３ ハッピーナンバー
正整数ｎの各桁の数を２乗し、その合計を求める。その合計の
各桁の数を２乗し、またその合計を求める。この計算を繰り返し
最終的に１となる正整数ｎをハッピーナンバーという。
問題１ 正整数ｎがハッピーナンバーかどうか調べるプログラムを
作成せよ。
問題２ 正整数a以上b以下のハッピーナンバーを求めるプログラム
を作成せよ。
２．４ ピタゴラス数
正整数a,b,cについて、a*a + b*b = c*c（1≦a≦b≦c）とする。
（このような正整数a,b,cをピタゴラス数という）
問題１ c*c≦nを満たすピタゴラス数をすべて求めよ。
２．５ 反復するフィボナッチ数（キース数）
k桁の正整数nについて、そのk個の数字を並べたものから始めて、
直前のk個の数値を合計したものを付け加えるという操作を繰り
返す。このとき、正整数nが再び現れるという性質をもつ数を
反復するフィボナッチ数（キース数）という。
問題１ 正整数aからbまでについてキース数を求めよ。
●数値計算の基礎(pdfファイル)１．情報落ち 計算のルールを「10進4桁、切り捨て」と仮定する。 ２つの数の加算では、まず小数点が合わされ、大きい数が優先される。 したがって、12.34 + 0.005678 は 12.34 と計算される。このように、 絶対値の小さい数を絶対値の大きい数に加えてもほとんど影響を 与えない現象を情報落ちという。 ２．オーバーフロー・アンダーフロー 計算結果の絶対値がコンピュータの処理できる最大の数を越えてしまう 現象をオーバーフローという。 計算結果の絶対値がコンピュータの処理できる最小数以下になる現象を いう。アンダーフローが生じると計算結果を０にすることが多い。 ３．桁落ち 12.34 - 12.33 = 0.01 のように、同符号で絶対値のほぼ等しい２個の 数に対して、減算を行うと有効数字が著しく減ってしまう現象をいう。 ４．丸め誤差の累積 コンピュータの内部で処理できる数値の桁数が決まっているため、 丸め（４捨５入、切り捨て、切り上げ）が起こる。このために生じる 誤差を丸め誤差という。 ５．誤差回避の実例 スターリングの公式を考察する。
プログラムの開発
●最大値探索法の開発(pdfファイル)
１．開発過程１
目標１：4個のデータの最大値を求める。
目標２：4個のデータの最大値を求める。
改良 ：多数のデータに対応するため、配列を使う。
目標３：n個のデータの最大値を求める。
改良 ：コードを簡潔に記述するため、for文を使う。
目標４：n個のデータの最大値を求める。
改良 ：プログラムをわかりやすくするため、関数を使う。
目標５：n個のデータの最大値を求める。
改良 ：処理を速くするため、最大値の位置のみを求め、
データの移動は最後に１回行う。
移動するデータ量が多いときに有効。
２．開発過程２
目標１：n個のデータから、最大値とその次の値を求める。
方法 ：a[1]に1番目のデータを格納、a[2]に2番目のデータを
格納する。
目標２：n個のデータの上位からm番目まで求める。
方法 ：a[1]に1番目のデータを格納、a[2]に2番目のデータを
格納、…、a[m]にm番目のデータを格納する。
３．開発過程３
目標１：n個のデータの上位からm番目まで求める。
準備 ：n個のデータ中、適当な値z以上の要素の集まりと、
z以下の要素の集まりに分割する。
目標２：n個のデータ中、1番目からm番目まで求める。
方法 ：a[1]〜a[m]に1番目からm番目のデータを格納する。
必ずしも、a[1]≧a[2]≧…≧a[m]とならないことに注意。
●２項係数計算法の開発(pdfファイル)１．開発方法１（階乗を用いる方法） ２．開発方法２（配列を用いる方法） ２．１ 開発方法２.１（２次元配列を用いる方法） ２．２ 開発方法２.２（１次元配列を用いる方法） ３．開発方法３（指数と仮数で表現する方法） ４．開発方法４（再帰関数を用いる方法）●数字列探索法の開発(pdfファイル)
長さnの数字列(0から9までの数字をn個並べたもの)a中に、
長さmの数字列bが最初に現れる位置を見つける問題を考察し、
プログラムを開発する。
前者を数字列、後者を探索列と呼ぶ。
数字列：１２３ ４５６ ７８９
＝＝＝ ４番目に見つけた。
探索列： ４５６
両者を配列で表し、数字列を配列a(a[i],1≦i≦n)、
探索列を配列b(b[i],1≦i≦m)に保存しておく。
１．開発過程１
方法：数字列と探索列の先頭を合わせ、先頭から対応する数字を
比較していく。途中で不一致が起こると、探索列を１文字分右
ずらし、再度、先頭から対応する数字を比較していく。
最悪の場合、n×mに比例した時間で処理が行われる。
２．開発過程２
方法：探索途中で不一致が生じたとき、探索列を１文字分右にずらし、
いつも探索列の先頭から比較を始めるのは無駄が多い。
そこで、不一致が起こったとき、探索列を右にずらす量を
あらかじめ求めておき、不一致が起こった位置から対応する
数字を比較していく。
改良：探索列を右にずらす量を効率よく求める。
３．開発過程３
方法：数字列と探索列の末尾から対応する数字を比較していく。
数字列と探索列の末尾で不一致が起こると、数字列中の
不一致文字xが、探索列中に現れる位置まで探索列を右にずらす。
数字列中の不一致文字xが、探索列中にない場合、探索列を
m文字分右にずらす。
この結果、比較回数を減らすことができ、うまくいくと、
n/mに比例した時間で処理が行われる。
改良：末尾から対応する数字を比較していく。番兵法を使って、
効率を上げる。
４．開発過程４
方法：探索列の数字をまとめて数値とし、対応する数字列の数値と
比較していく。このことから、数字列の長さnに比例した時間で
処理が行われる。
条件：m≦9 (整数が10桁程度のため）
改良：mについての条件(m≦9)を取り除いた。
●素数生成法の開発(pdfファイル)
正整数ｎ以下の素数をすべて求める問題を考察する。
まず、素朴な方法を取り上げ改良していく。
つぎに、「ふるい」という考え方を適用すると、劇的に改良されることを示す。
１．素朴な素数生成法
方法１.１
素朴な方法である。素数の候補（3以上の奇数）pを用意し、
その候補に対して、3以上p-2以下の奇数dで割っていく。
どの数でも割り切れない場合、素数とし、いずれかの数で
割り切れた場合、合成数とする。
方法１.２
改良点：方法１.１において、除数dの範囲を小さくする。
素数の候補（3以上の奇数）pを用意し、その候補に対して、
3以上[√p]以下の奇数dで割っていく。どの数でも割りきれ
ない場合、素数とし、いずれかの数で割り切れた場合、
合成数とする。ここで、［x］は実数xの整数部分を意味する。
方法１.３
改良点：方法１.２において、候補pから3の倍数を除く。
素数の候補（3の倍数を除く奇数）pを用意し、その候補に
対して、5以上［√p］以下の奇数dで割っていく。
どの数でも割りきれない場合、素数とし、いずれかの数で
割り切れた場合、合成数とする。
方法１.４
改良点：方法１.３において、除数dとしてすでに得られた
素数を使う。
素数の候補（3の倍数を除く奇数）pを用意し、その候補に
対して、すでに得られた［√p］以下の素数dで割っていく。
どの数でも割りきれない場合、素数とし、いずれかの数で
割り切れた場合、合成数とする。
２．エラトステネスの方法
方法２.１
正整数 n 以下の素数をつぎの手順で生成する。
手順（０） 2 を素数とする。
手順（１） 数列 {3,5,7,...,n} を用意する。
手順（２） 数列の中の最小値pを素数とし、その数自身と
その数の倍数（2p,3p,4p,...)
取り除き、新しい数列を構成する。
手順（３） 新しい数列が空になるまで手順（２）を繰り返す。
方法２.２ エラトステネスの方法の改良
方法２.１の手順（２）、手順（３）を改良する。
2*p,3*p,4*p,...,(p-1)*pは、すでに数列から取り除かれて
いるはずだから省略できる。
手順（０） 2を素数とする。
手順（１） 数列 {3,5,7,...,n}を用意する。
手順（２） 数列の中の最小値pを素数とし、その数自身と
その数の倍数（p*p,p*(p+1),p*(p+2),...)を
数列から取り除き、新しい数列を構成する。
手順（３） p*p が n 以下の間、手順（２）を繰り返す。
方法２.３ エラトステネスの方法の改良
方法２.２の手順（２）を改良する。
pが奇数なので、p*(p+1),p*(p+3),p*(p+5),...は偶数になり
省略できる。
手順（０） 2を素数とする。
手順（１） 数列 {3,5,7,...,n}を用意する。
手順（２） 数列の中の最小値p素数とし、その数自身と
その数の倍数（p*p,p*(p+2),p*(p+4),...)を
数列から取り除き、新しい数列を構成する。
手順（３） p*p が n 以下の間、手順（２）を繰り返す。
方法２.４ エラトステネスの方法の改良
方法２.３の手順（２）を改良する。
手順（０）2を素数とする。
手順（１）数列 {3,5,7,...,n}を用意する。
手順（２）数列の中の最小値を素数pとし、その数自身と
その数の倍数を数列から取り除き、新しい数列を
構成する。
pが6k+1の形の素数とわかったとき、取り除く倍数を、
p*p,p*(p+4),p*(p+6),p*(p+10),p*(p+12),...とする。
pが6k+5の形の素数とわかったとき、取り除く倍数を、
p*p,p*(p+2),p*(p+6),p*(p+8),p*(p+12),...とする。
手順（３） p*p が n 以下の間、手順（２）を繰り返す。
●平方根計算法(pdfファイル)１．素朴な方法（1桁ずつ求める） ２．めのこ平方 ３．漸化式 ４．２分法 ５．ニュートン法●順列生成の開発Ⅰ(pdfファイル)
１．順列生成（非再帰的方法） １．１ 非再帰的生成法１（多重ループを用いる方法） １．２ 非再帰的生成法２（配列を用いる方法） １．３ 非再帰的生成法３（辞書式順序を用いる方法） １．４ 非再帰的生成法４（階乗進数を用いる方法）●順列生成の開発Ⅱ(pdfファイル)
２．順列生成（再帰的方法） ２．１ 再帰的生成法１（素朴な方法） ２．１．１ 基本アルゴリズム ２．２ 再帰的生成法２（挿入法） ２．２．１ 基本アルゴリズム ２．２．２ スタック順列の生成 ２．２．３ キュー順列の生成 ２．３ 再帰的解法３（交換法） ２．３．１ 基本アルゴリズム●順列生成の開発Ⅲ(pdfファイル)
２．順列生成（再帰的方法）
２．４ 再帰的解法４（部分順列の生成）
２．４．１ 基本アルゴリズム
２．４．２ 辞書式順序に従う生成
２．４．３ ランダム順列の生成
２．４．４ 組合せの生成
３．各種順列生成問題
３．１ かく乱順列の生成
３．２ フィボナッチ順列の生成
●部分集合生成問題(pdfファイル)１．部分集合の個数 ２．生成法１（再帰的方法） ３．生成法２（２進数への対応） ４．生成法３（グレイコード） ５．生成法４
プログラミングの応用
●シミュレーション(pdfファイル)１．一様乱数の生成 １．１ 組み込み関数rand() １．２ 与えられた分布にしたがう乱数の生成 ２．面積計算のシミュレーション 区間[0,1]の一様乱数を２個x,y生成し、円内(x*x+y*y≦1,0≦x,0≦y)に 入る頻度を求めれば、円の面積の近似値（π/4)が得られる。 ３．破産問題のシミュレーション 10個の金貨から始める。1個の金貨を投資すると確率pで10個増える。 持ち金貨が20個か0個になったとき止めるとする。 pと破産する（持ち玉が0個）確率との関係を考察せよ。 ４．幾何的確率のシミュレーションと解析 問題１ 長さａの線分ＡＢ上に２点Ｐ，Ｑを互いに独立にとるとき、 距離ＰＱが長さｂ(＜ａ)以下になる確率を考察する。 問題２ ｘ１＋ｘ２＋ｘ３＝ａ（ｘ１＞０,ｘ２＞０,ｘ３＞０,ａ＞０）のとき、 長さｘ１，ｘ２，ｘ３で三角形を構成する確率を考察する。 ５．太郎次郎問題のシミュレーションと解析 太郎と次郎がコイン投げのゲームをした。コインを繰り返し投げ、 表がでたら1、裏がでたら0とする。このとき1と0の記号列ができるが、 先に111がでたら太郎の勝ち、一方先に101がでたら次郎の勝ちとする。 太郎の勝つ確率、次郎の勝つ確率を求めよ。 ただし、1も0もでる確率は同じとする。●あみだくじ(pdfファイル)
あみだくじについて考察する。
問題１ あみだくじ
（１）希望するあみだくじをつくる一般的な方法を考えよ。
例として、縦線の上にＡ，Ｂ，Ｃ，Ｄをこの順に並べ、縦線の下に
ａ，ｂ，ｃ，ｄを適当な順に並べる。そして、Ａを選んだ場合ａに
たどりつき、Ｂを選んだ場合ｂにたどりつき、Ｃを選んだ場合ｃに
たどりつき、Ｄを選んだ場合ｄにたどりつくようにせよ。
（２）希望するあみだくじをつくるプログラムを書け。
4 ←縦線の個数
2 1 4 3 ←最終配置
1 2 3 4
| | |--|
|--| | |
2 1 4 3
4 ←縦線の個数
4 3 2 1 ←最終配置
1 2 3 4
|--| | |
| |--| |
| | |--|
|--| | |
| |--| |
|--| | |
4 3 2 1
（３）あみだくじは初期配置を変換するルールと解釈できる。
初期配置：12...n から最終配置：b(1)b(2)...b(n) に
変換するのに必要な横線の個数について考察せよ。
問題２ あみだくじの公平性
あみだくじの公平性について考察せよ。
問題３ あみだくじの公平性
あみだくじの公平性について考察せよ。
●マッチ棒問題(pdfファイル)m×nの盤で辺に n(m+1)+(n+1)m=2mn+m+n 本のマッチ棒を並べる。 r本のマッチ棒を取り除いて、s個の正方形が残るようにする方法を考察する。 問題１ （１）m×nの盤の辺に番号をつけ、すべての長方形(正方形を含む)を 出力するプログラムを作成せよ。 （２）m×nの盤の辺に番号をつけ、すべての正方形を出力する プログラムを作成せよ。 （３）ｎ個の要素からｒ個残す組合せをすべて生成するプログラムを 作成せよ。 （４）m×nの盤で辺にn(m+1)+(n+1)m = 2mn+m+n本のマッチ棒を並べる。 r本のマッチ棒を取り除いて、s個の正方形が残るようにする方法を すべて求めるプログラムを作成せよ。 ただし、残ったマッチ棒は、他のマッチ棒と両端でつながっている ものとする。 （５）m×nの盤で辺にn(m+1)+(n+1)m = 2mn+m+n本のマッチ棒を並べる。 マッチ棒を取り除いて、正方形を破壊する方法で、最小のマッチ 棒の本数とその方法の個数を求めるプログラムを作成せよ。 ただし、残ったマッチ棒は、他のマッチ棒と両端でつながっている ものとする。●カタラン数(pdfファイル)
１．カタラン数とは
２．カタラン数が現れる例
問題１ 最短コース
道路が碁盤の目になっている町がある。切れているところは
通れないとして、左上隅の交差点aから右下隅の交差点bまでの
最短コースの数を求める問題を考察する。
問題２ バランスのとれたかっこ列
n個の左かっことn個の右かっこからなるバランスのとれた長さ2n
のかっこ列p(1)p(2)…p(2n)はつぎのように定義できる。
任意の部分列p(1)p(2)…p(k)(1≦k≦2n)において、
左かっこの個数≧右かっこの個数
が成り立つ。
（１）n個の左かっことn個の右かっこからなるバランスのとれた
長さ2nのかっこ列p(1)p(2)…p(2n)の個数は、カタラン数c(n)
になることを示せ。
（２）n個の左かっことn個の右かっこからなるバランスのとれた
長さ2nのかっこ列を列挙するプログラムを作成せよ。
問題３ カードを２段に並べる方法
1から2nまでの番号のつけられた2n枚のカードを上段にn枚、下段に
n枚並べる。ただし、並べられたカードは条件(a),(b),(c)を満たす
ものとする。
(a)上段に置かれたカードは左から右へ番号が増加している。
(b)下段に置かれたカードは左から右へ番号が増加している。
(c)上下のカードの番号は上が下より小さい。
（１）1から2nまでの番号のつけられた2n枚のカードを上段にn枚、
下段にn枚並べる。ただし、並べられたカードは条件(a),(b),
(c)を満たすものとする。
このとき、2n枚のカードの並べ方の数はカタラン数c(n)になる
ことを示せ。
（２）このようなカードの配置を列挙するプログラムを作成せよ。
問題４ 三角形の分割
凸n角形を互いに交わらない対角線によって、三角形に分割する
方法を考察する。
問題５ 円周上の2n個の点を線分で結ぶ方法
円周上に2n個の点をとり、２つずつを互いに交わらないように
線分で結ぶ方法を考察する。
（１）円周上に2n個の点をとり、２つずつを互いに交わらないように
線分で結ぶ方法はカタラン数c(n)になることを示せ。
●計算パズル集(pdfファイル)
問題１ 小町算
１から９までの９個の数字をこの順に並べ数字の間に＋と−を
うまくいれると、
１００＝１２３＋４５−６７＋８−９
＝１２３＋４−５＋６７−８９
＝１２３−４５−６７＋８９
＝１２３−４−５−６−７＋８−９
＝１２＋３＋４＋５−６−７＋８９
＝１２＋３−４＋５＋６７＋８＋９
＝１２−３−４＋５−６＋７＋８９
＝１＋２３−４＋５６＋７＋８＋９
＝１＋２３−４＋５＋６＋７８−９
＝１＋２＋３４−５＋６７−８＋９
＝１＋２＋３−４＋５＋６＋７８＋９
＝−１＋２−３＋４＋５＋６＋７８＋９
のように、和を１００にすることができる。このように与えられた
値nに対して、条件を満たす式をすべて求めるプログラムを作成せよ。
問題２ 単位分数表現
１から９までの数字をちょうど１回ずつ使った分数で、１／２を
あらわす方法をすべて見つけるプログラムを作成せよ。
[ 1] 2 × 6729 = 13458 [ 2] 2 × 6792 = 13584
[ 3] 2 × 6927 = 13854 [ 4] 2 × 7269 = 14538
[ 5] 2 × 7293 = 14586 [ 6] 2 × 7329 = 14658
[ 7] 2 × 7692 = 15384 [ 8] 2 × 7923 = 15846
[ 9] 2 × 7932 = 15864 [10] 2 × 9267 = 18534
[11] 2 × 9273 = 18546 [12] 2 × 9327 = 18654
問題３ センチュリー・パズル
１から９までの数を１回ずつ使って帯分数を作り１００を表す方法を
すべて求めるプログラムを作成せよ。
ただし、数字の並び方は任意でよい。
２１４８ １７５２ １４２８
９６-------- ９６-------- ９６--------
５３７ ４３８ ３５７
５８２３ ５７４２ １５７８
９１-------- ９１-------- ９４--------
６４７ ６３８ ２６３
５６４３ ３５４６ ７５２４
８１-------- ８２-------- ９１--------
２９７ １９７ ８３６
６９２５８ ７５２４
３---------- ８１--------
７１４ ３９６
問題４ 覆面算
アルファベットに数字をいれて計算式が成り立つようにするプログラム
を作成せよ。ただし、異なるアルファベットには異なる数字が入る。
問題５ 虫食い算
問題６ 分数式パズル
与えられた値mに対して、1から9までの数字を使って、次の計算式を
満たすものをすべて見つけるプログラムを作成せよ。ただし、1≦m≦10。
●マス目反転問題(pdfファイル)
m×nのチェス盤のマス目が適当に白と黒に塗られているとき、
１行または１列全部のマス目を反転（白→黒、黒→白）する操作のみで
すべてのマス目を白にする問題を考察する。
問題１ マス目反転問題の例
問題２ マス目反転問題
（１）４×４のチェス盤のマス目の中で1個のマス目が黒く塗られている。
すべてのマス目を白にすることはできないことを示せ。
（２）４×４のチェス盤のマス目の中で、奇数n(1,3,5,7,9,…,15)個の
マス目が黒く塗られている。
すべてのマス目を白にすることはできないことを示せ。
（３）２ｎ×２ｎのチェス盤のマス目の中で、奇数個のマス目が黒く
塗られている。すべてのマス目を白にすることはできないことを
示せ。
（４）与えられたマス目の状態から、すべてのマス目を白にできるか
できないか判定し、できる場合、その方法を示すプログラムを
作成せよ。
問題３ マス目反転問題の解析
（１）すべてのマス目を白にできるならば、次の連立方程式が成り立つこと
を示せ。
x(1)+x(4) ≡ a(1,1)
x(2)+x(4) ≡ a(1,2)
x(3)+x(4) ≡ a(1,3)
x(1)+x(5) ≡ a(2,1)
x(2)+x(5) ≡ a(2,2)
x(3)+x(5) ≡ a(2,3)
x(1)+x(6) ≡ a(3,1)
x(2)+x(6) ≡ a(3,2)
x(3)+x(6) ≡ a(3,3)
（２）(１)の連立方程式を変形して、つぎの関係を導け。
x(1)+x(4) ≡ a(1,1)
x(2)+x(4) ≡ a(1,2)
x(3)+x(4) ≡ a(1,3)
x(4)+x(5) ≡ a(1,1)+a(2,1)
0 ≡ a(1,1)+a(2,1)+a(1,2)+a(2,2) (A)
0 ≡ a(1,1)+a(2,1)+a(1,3)+a(2,3) (B)
x(4)+x(6) ≡ a(1,1)+a(3,1)
0 ≡ a(1,1)+a(3,1)+a(1,2)+a(3,2) (C)
0 ≡ a(1,1)+a(3,1)+a(1,3)+a(3,3) (D)
（３）３×３のチェス盤のマス目の中で、いくつかのマス目が黒く
塗られている。
このとき、つぎの４種類のパターンA,B,C,Dと重なる部分が
それぞれ偶数個にならなければ、すべてのマス目を白にすることは
できない。その理由を説明せよ。
（４）４×４のチェス盤のマス目の中で、いくつかのマス目が黒く塗られ
ている。このとき、つぎの９種類のパターンと重なる部分が
それぞれ偶数個にならなければ、すべてのマス目を白にすることは
できない。このパターンを求めるプログラムを作成せよ。
再帰
●再帰処理Ⅰ(pdfファイル)１．階乗関数 ２．基本演算 ２．１ 乗算 ２．２ 除算 ２．３ 剰余 ３．最大公約数 ４．フィボナッチ関数 ５．べき乗関数 ５．１ 解法１ ５．２ 解法２ ６．２項係数●再帰処理Ⅱ(pdfファイル)
７．二分探索
８．最大値探索
９．集合Tの再帰的定義
１０．集合{1,2,…,n}上の部分集合生成
●再帰処理Ⅲ(pdfファイル)
１１．ソート
１１．１ 挿入ソート
１１．２ クイックソート
１１．３ マージソート
●再帰処理Ⅳ(pdfファイル)
１．再帰曲線
１．１ ドラゴン曲線
１．２ ヒルベルト曲線
１．３ シェルピンスキー曲線
１．４ Ｃ曲線
データ構造
●配列処理Ⅰ(pdfファイル)１．配列要素の読込 １．１ 読み込む要素数が未知の場合 １．２ 読み込む要素数が既知の場合 ２．配列要素の挿入 ３．配列要素の削除 ４．配列の反転 ５．探索 ５．１ 素朴な方法 ５．２ 番兵法 ５．３ 二分探索 ５．４ ハッシュ法●配列処理Ⅱ(pdfファイル)
６．ソート ６．１ 挿入ソート ６．２ シェルソート ６．３ 分配ソート ７．マージ●配列処理Ⅲ(pdfファイル)
１．グラフ表現 １．１ 経路数 問題：隣接行列が与えられたとき、節点iから節点jへm回の 移動で移れる方法の数を求めよ。 １．２ 最短距離 問題：距離行列が与えられたとき、節点iから節点jへの 最短距離を求めよ。 １．３ 最小時間 問題：時間行列が与えられたとき、節点i(1≦i≦n-1)から節点nへの 最小移動時間を求めよ。 ２．最適経路 x座標を正の方向へnステップ、y座標も正の方向へnステップ、 合計2nステップ動くことにより、格子点Ａ(0,0)から格子点Ｂ(n,n)まで 行く経路を考える。 隣接する格子点Ｃから格子点Ｄへ移動するのに必要なコストがcost(C,D)で 与えられたとき、格子点Ａから格子点Ｂまで移動するのに必要な最小 コストを考察する。●ポインタ変数(pdfファイル)
１．ポインタ変数と変数 ２．ポインタ変数と配列 ３．ポインタ変数と構造体 ４．ポインタ変数と線形リスト ５．ポインタ変数配列 ６．ポインタ変数と関数 ６．１ 引数とポインタ変数 ６．２ 引数と配列 ６．３ 戻り値とポインタ変数 ７．問題●リストⅠ(pdfファイル)
１．再帰的なデータ構造によるリストの表現 １．１ リストの作成と表示 １．１．１ リストの先頭に追加する方法 １．１．２ リストの末尾に追加する方法 １．１．３ 昇順を保存してリストに追加する方法 １．１．４ 問題 １．２ リストの作成と表示(リストヘッドの利用) １．２．１ リストの先頭に追加する方法 １．２．２ リストの末尾に追加する方法 １．２．３ 昇順を保存してリストに追加する方法 １．２．４ 問題●リストⅡ(pdfファイル)
２．基本的な操作 ２．１ リストから要素の削除 ２．２ リストの複写 ２．３ リストの連結 ２．４ リストの併合 ２．５ 問題●リストⅢ(pdfファイル)
３．応用 ３．１ マージソート ３．２ グラフ表現 ３．３ 問題 問題１：素数生成 問題２：素数生成（高速化） 問題３：双方向リスト●スタックとキュー(pdfファイル)
１．スタック １．１ 配列によるスタックの実現 １．２ 再帰的なデータ構造によるスタックの実現 ２．キュー ２．１ 配列によるキューの実現 ２．２ 再帰的なデータ構造によるキューの実現 ３．スタックとキューの違い ４．応用問題 ４．１ 地図情報処理 ４．２ グラフ問題●ヒープ(pdfファイル)
１．ヒープとは ２．ヒープ生成法 ２．１ 具体例 ２．２ ヒープ生成法の手順 ２．３ ヒープ作成・再帰版 ２．４ ヒープ作成・非再帰版 ３．ヒープの応用 ３．１ ヒープソート・再帰版 ３．２ 問題●２分探索木Ⅰ(pdfファイル)
１．２分探索木とは ２．２分探索木の作成 ３．２分探索木の走査 ３．１ 前走査 ３．２ 中走査 ３．３ 後走査 ３．４ 問題●２分探索木Ⅱ(pdfファイル)
４．２分探索木の操作 ４．１ 要素の探索 ４．２ 要素の挿入 ４．３ 直前の要素の探索 ４．４ 直後の要素の探索 ４．５ 要素の削除●２分探索木Ⅲ(pdfファイル)
５．応用問題 ５．１ 木の深さ、平均の深さ ５．２ ２分探索木の図示
システムプログラミング
●シェルの作成Ⅰ(pdfファイル)１．シェルとは ２．シェルの作成 ２．１ シェルＡ ２．１．１ fork関数 ２．１．２ execl関数 ２．１．３ シェルＡプログラム ２．２ シェルＢ ２．２．１ 文字列の分解 ２．２．２ execv関数 ２．２．３ シェルＢプログラム ２．３ シェルＣ ２．３．１ 組み込みコマンド ２．３．２ シェルＣプログラム
ネットワークプログラミング
●クライアント・サーバプログラムⅠ(pdfファイル)１．プログラムの概要 ２．コネクション型プログラム ２．１ 方式１：反復サーバ ２．２ 方式２：並行サーバ ２．３ 方式３：複数の入出力を見張るサーバ ２．４ 方式４：ホスト名、ポート番号を指定できるクライアント
バックトラックアルゴリズム
●チェス盤経路問題(pdfファイル)１．チェス盤経路問題 １．１ 経路問題 １．２ 最短経路問題 １．３ 最長経路問題 １．４ n回曲がる最短経路問題●チェス盤最短経路問題(pdfファイル)
●チェス盤周遊問題(pdfファイル)
１．チェス盤周遊問題 １．１ 周遊問題 １．２ ナイトの周遊問題●整数分割(pdfファイル)
問題１ 正整数の和
加算の順序が異なるとき、異なるものと見なす場合、n=4では、4, 3+1,
1+3, 2+2, 2+1+1, 1+2+1, 1+1+2, 1+1+1+1 の8通りの表し方がある。
正整数nが与えられたとき、すべての表し方を求めるプログラムを
作成せよ。
問題２ 整数分割
加算の順序が異なるとき、同じものと見なす場合、n=5では、5, 4+1, 3+2,
3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1 となり、7通りの表し方がある。
正整数nが与えられたとき、すべての表し方を求めるプログラムを
作成せよ。
n=d[1]+d[2]+…+d[k] d[1]≧d[2]≧・・・≧d[k]
問題３ 整数分割
次の条件を満たす整数分割を求めるプログラムを作成せよ。
n=d[1]+d[2]+…+d[k] d[1]＞d[2]＞・・・＞d[k]
問題４ 整数分割
次の条件を満たす整数分割を求めるプログラムを作成せよ。
n=d[1]+d[2]+…+d[k] d[1]≧d[2]≧・・・≧d[k]
ただし、d[i](1≦i≦k)は奇数
問題５
r個の正整数からなる整数nの分割で、次の条件を満たすものを求める
プログラムを作成せよ。
n=d[1]+d[2]+…+d[r] d[1]≧d[2]≧・・・≧d[r]
問題６
r個の正整数からなる整数nの分割で、次の条件を満たすものを求める
プログラムを作成せよ。
n=d[1]+d[2]+…+d[r] d[1]＞d[2]＞・・・＞d[r]
●コイン配置問題(pdfファイル)問題１ （１）３×３のマス目にコインをできるだけたくさん置く方法を示せ。 ただし、どの４個のコインも正方形や長方形になってはいけない。 （２）４×４のマス目にコインをできるだけたくさん置く方法を示せ。 ただし、どの４個のコインも正方形や長方形になってはいけない。 （３）５×５のマス目にコインをできるだけたくさん置く方法を示せ。 ただし、どの４個のコインも正方形や長方形になってはいけない。 （４）６×６のマス目にコインをできるだけたくさん置く方法を示せ。 ただし、どの４個のコインも正方形や長方形になってはいけない。 （５）m×nのマス目に置けるコインの最大数を求めるプログラムを 作成せよ。 ただし、どの４個のコインも正方形や長方形になってはいけない。●畳敷詰問題Ⅰ(pdfファイル)
問題１ 畳の敷き方
（１）2×nの部屋に1×2の畳を敷く方法a(n)について、
a(n) = a(n-1) + a(n-2) (n≧2)，a(1)=１，a(0)=１
が成り立つことを示せ。
（２）3×2nの部屋に1×2の畳を敷く方法b(n)について
b(n) = 4b(n-1) - b(n-2) (n≧2), b(1)=3, b(0)=1
が成り立つことを示せ。
（３）m×nの部屋に1×2の畳を配置したとき、配置の個数 f(m,n) を
求めるプログラムを作成せよ。
●畳敷詰問題Ⅱ(pdfファイル)
問題２ 縦方向・切断線
（１）m×nの部屋に1×2の畳を配置したとき、縦方向に線を引くことを
考える。畳と交わらずに線が引けたとき、縦方向の切断線という。
m×nの部屋に1×2の畳を配置したとき、縦方向の切断線を持たない
配置の個数をg(m,n)とする。g(m,n)を求めるプログラムを作成せよ。
（２）f(m,n)とg(m,n)の関係を求めよ。
f(m,n)は、m×nの部屋に1×2の畳を配置したとき、配置の個数を
意味する。
（３）4×nの部屋の敷き方の個数をc(n)とする。c(n)が満たす漸化式を
求めよ。
問題３ 縦横方向・切断線
縦横方向の切断線をもたない配置を考察する。
（１）m×nの部屋に1×2の畳を配置したとき、縦方向の切断線と横方向の
切断線を持たない配置の個数を求めるプログラムを作成せよ。
（２）８枚の畳を正方形に敷くことを考える。
どのような敷き方に対しても、切断線があることを示せ。
（３）3×2n(n≧1)の部屋に1×2の畳を敷くことを考える。
どのような敷き方に対しても、切断線があることを示せ。
（４）4×n(n≧1)の部屋に1×2の畳を敷くことを考える。
どのような敷き方に対しても、切断線があることを示せ。
●Ｎクイーン問題(pdfファイル)１．Ｎクイーン問題 １．１ バックトラックに基づく解法 １．２ バックトラックに基づく解法の改良 １．３ 順列生成に基づく解法 ２．超Ｎクイーン問題 ３．反射するＮクイーン問題●かっこ列生成問題(pdfファイル)
問題１
'('がa個、')'がb個ある文字列をすべて生成するプログラムを作成せよ。
問題２
'('がa個、')'がb個ある文字列をランダムに生成するプログラムを
作成せよ。
問題３
バランスのとれたa対のかっこ列をすべて生成するプログラムを作成せよ。
問題４
かっこ列をランダムに生成するプログラムを作成せよ。
●渡河問題(pdfファイル)
問題１ 農夫の渡河問題
一そうのボートを使って、農夫がオオカミとヤギとキャベツを向こう
岸に運ぶことになった。ところで、ボートには農夫のほかに最大１つ
乗せることができる。また、農夫がいないとオオカミはヤギをヤギは
キャベツを食べてしまう。農夫が無事に、オオカミとヤギとキャベツ
を向こう岸に運ぶ方法を考察せよ。
農夫渡河問題を解くプログラムを作成せよ。
ただし、ボートには農夫のほかに最大１つ乗せることができる。
問題２ 宣教師と人食い人種の渡河問題
n人の人食い人種とn人の宣教師が川を渡ろうとしている。
ボートはboat人乗りで人食い人種と宣教師のどんな組合せでもこぐ
ことができる。ただし、宣教師の数が川の両岸、またボートの中でも
人食い人種より少なければ食べられてしまう。
人食い人種と宣教師が全員無事に川を渡る方法を考察せよ。
人食い人種と宣教師が全員無事に川を渡る方法をすべて見つける
プロクラムを作成せよ。
問題３ ボートに制限のある渡河問題
３人の男（Ａ,Ｂ,Ｃ）がそれぞれ砂金を持って川を渡ろうとしている。
ところが、ボートには２人の男または１人の男と砂金１袋しか乗れない。
Ａは１５㎏の砂金、Ｂは８㎏の砂金、Ｃは７㎏の砂金を持っている。
両岸、ボートの中で自分の持ち分以上の砂金を持つと逃げてしまう。
３人が川を渡るにはどうすればよいか考察せよ。
３人が最小の移動回数で川を渡る方法をすべて見つけるプロクラムを
作成せよ。
●ポリオミノ(pdfファイル)
いくつかの同じ形の正方形が辺を接して結びついているものをポリオミノという。
回転して一致したり、裏返して回転して一致するものは同じとみなす。
点だけで接していたり、辺の一部で接していたり、重なっているものは
ポリオミノではない。ｎ個の正方形から構成される場合、n-ミノという。
n-ミノをすべて求めることを目標にする。
問題１
（１）m×nの盤からマス目r個分の選び方をすべて求めるプログラムを
作成せよ。
２×３の盤の場合、マス目４個分の選び方は１５通りある。
■■■ ■■□ □■■ ■■□ ■□□ □□■
■□□ □■■ ■■□ ■□■ ■■■ ■■■
■■■ ■□■ □■■ ■■□ ■□■ □■□
□■□ ■■□ ■□■ ■■□ □■■ ■■■
■■■ ■□■ □■■
□□■ ■□■ □■■
（２）m×nの盤からマス目r個分の領域(マス目の辺同士が隣接する)
をすべて求めるプログラムを作成せよ。
３×３の盤の場合、マス目３個分の領域は２２通りある。
■■■ ■□□ □■□ □□□ □□□ □□□
□□□ ■□□ □■■ ■■■ □■■ □□■
□□□ ■□□ □□□ □□□ □■□ □■■
■■□ □■■ □■□ □□□ □□□ □□□
■□□ □■□ □■□ ■■□ □■■ □□□
□□□ □□□ □■□ ■□□ □□■ ■■■
■■□ □■■ □□■ □□□ □□□
□■□ □□■ □■■ ■■□ □■□
□□□ □□□ □□□ □■□ ■■□
■□□ □■□ □□■ □□□ □□□
■■□ ■■□ □□■ ■□□ □■□
□□□ □□□ □□■ ■■□ □■■
（３）m×nの盤からマス目r個分の領域(マス目の辺同士が隣接する)で
m×nの盤の上辺と左辺に接するものをすべて求めるプログラムを
作成せよ。
３×３の盤の場合、上辺と左辺に接するマス目３個分の領域は
６通りある。
■■■ ■■□ ■■□ ■□□ ■□□ □■□
□□□ ■□□ □■□ ■■□ ■□□ ■■□
□□□ □□□ □□□ □□□ ■□□ □□□
これらから、反転や回転で重なるものを取り除かなければならない。
（４）m×nの盤からマス目r個分の領域(マス目の辺同士が隣接する)で
m×nの盤の上辺と左辺に接し、反転や回転で重なるものが
取り除かれたものをすべて求めるプログラムを作成せよ。
（ヒント）
元の図形から反転と回転を組み合わせて7通りの図形を
構成できる。その操作を①から⑦とする。
たとえば、次の図形を元の図形とすると、
操作①から操作⑦で７通りの図形はつぎのようになる。
■■■
■
操作①：元の配置を反転し、時計回りに180°回転。
■
■■■
操作②：元の配置を反転。
■■■
■
操作③：元の配置を時計回りに180°回転。
■
■■■
操作④：元の配置を反転し、時計回りに270°回転。
■
■
■■
操作⑤：元の配置を、時計回りに270°回転。
■
■
■■
操作⑥：元の配置を、時計回りに90°回転。
■■
■
■
操作⑦：元の配置を反転し、時計回りに90°回転。
■■
■
■
●ナンバープレイス(pdfファイル)ナンバープレースというパズルを考察する。 ナンバープレイスとは、9×9盤のマス目に数字1から9を書き込むパズルである。 ただし、次の条件を満たす。 （条件１）縦の列、横の行に1から9までの数字がひとつずつ入る。 （条件２）3×3の正方形ブロック内に1から9までの数字がひとつずつ入る。 問題１ 4×4の盤のマス目に数字1から4を書き込む。 ただし、次の条件を満たすこと。 （条件１）縦の列、横の行に1から4までの数字がひとつずつ入る。 （条件２）2×2の正方形ブロック内に1から4までの数字がひとつずつ 入る。 上の条件を満たす配置をすべて求めるプログラムを作成せよ。 □□□□ □□□□ □□□□ □□□□ 問題２ 4×4の盤のマス目に数字1から4を書き込む。 ただし、次の条件を満たすこと。 （条件１）縦の列、横の行に1から4までの数字がひとつずつ入る。 （条件２）2×2の正方形ブロック内に1から4までの数字がひとつずつ 入る。 １２３４ ３４□□ □□□□ □□□□ 上の条件を満たす配置をすべて求めるプログラムを作成せよ。 問題３ 9×9の盤のマス目に数字1から9を書き込む。 ただし、次の条件を満たすこと。 （条件１）縦の列、横の行に1から9までの数字がひとつずつ入る。 （条件２）3×3の正方形ブロック内に1から9までの数字がひとつずつ 入る。 １□□７□□４□□ □２□□８□□５□ □□３□□９□□６ ７□□４□□１□□ □８□□５□□２□ □□９□□６□□３ ４□□１□□７□□ □５□□２□□８□ □□６□□３□□９ 上の条件を満たす配置をすべて求めるプログラムを作成せよ。●白玉黒玉交換問題(pdfファイル)
問題１ 2n+1個のマス目がある。左のn個のマス目に白玉n個、右のn個のマス目に 黒玉n個を並べる。つぎの４条件（ア）〜（エ）を満たしながら白玉と黒玉 を交換する方法を考察する。 （ア）白玉、黒玉は同時に１個しか動かせない。 （イ）白玉は右にだけ、黒玉は左にだけ移れる。 （ウ）白玉は右隣の空いたマス目か黒玉を１個だけ飛び越え空いた マス目に移れる。 （エ）黒玉は左隣の空いたマス目か白玉を１個だけ飛び越え空いた マス目に移れる。 （１）2n+1個のマス目がある。左のn個のマス目に白玉n個、右のn個の マス目に黒玉n個を並べる。４条件を満たしながら白玉と黒玉を 交換する方法をすべて見つけるプログラムを作成せよ。 （２）2n+1個のマス目がある。左のｎ個のマス目に白玉n個、右のn個の マス目に黒玉n個を並べる。４条件を満たしながら白玉と黒玉を 交換するとき、最小移動回数とその方法をすべて見つける プログラムを作成せよ。 問題２ （１）2n+1個のマス目がある。左のn個のマス目に白玉n個、右のn個の マス目に黒玉n個を並べる。４条件を満たしながら白玉と黒玉を 交換するとき、白玉と黒玉の総移動回数を考察する。 総移動回数≧n(n+2) （２）a+b+1個のマス目がある。左のa個のマス目に白玉a個、右のb個の マス目に黒玉b個を並べる。４条件を満たしながら白玉と黒玉を 交換するとき、白玉と黒玉の総移動回数を考察する。 総移動回数≧ab+a+b （３）a=1のとき、解の個数がフィボナッチ数になることを示せ。●物差し問題(pdfファイル)
長さnの目盛りのついていない物差しがある。1からnまでのすべての
長さが測れるようにするには、1からn-1までのすべての目盛りがつけられて
いる必要はない。最小何個の目盛りをつけたらよいか。
また、目盛りのつけ方は何通りあるかを考察する。
ただし、物差しの両端は目盛りの個数から除く。
問題１ 物差し問題
（１）集合{1,2,…,n}上のすべての部分集合を生成するプログラムを
作成せよ。
（２）物差し問題を解くプログラムを作成し、長さn(1≦n≦40)について、
目盛りの最小個数rとその方法の総数を求めよ。
（３）物差し問題プログラム(m121.c)において、すべての目盛りが
測定可能かどうか調べる部分には、工夫の余地がある。
実行時間が短かくなるように改良せよ。
●ハノイの塔問題(pdfファイル)
１．塔３本のハノイの塔問題
３本の塔a,b,cと大きさの異なるｎ枚の円盤が与えられたとき、
つぎの規則にしたがって、塔aから塔bへ円盤を移動する方法を考察する。
規則（１）１回に１枚の円盤のみ塔から塔へ移動できる。
規則（２）塔の一番上の円盤のみ移動できる。
規則（３）大きい円盤が小さい円盤の上にならない。
問題１ ３本の塔のハノイの塔問題を解くプログラム(ha111.c)を
作成せよ。
２．塔４本のハノイの塔問題
４本の塔a,b,c,dと大きさの異なるｎ枚の円盤が与えられたとき、
つぎの規則にしたがって、塔aから塔bへ円盤を移動する方法を考察する。
規則（１）１回に１枚の円盤のみ塔から塔へ移動できる。
規則（２）塔の一番上の円盤のみ移動できる。
規則（３）大きい円盤が小さい円盤の上にならない。
問題２（１）４本の塔のハノイの塔問題を解くプログラム(ha211.c)を
作成せよ。
問題２（２）塔が4本、円盤がnmax枚のとき、円盤の移動回数を求める
プログラム(ha221.c)を作成せよ。
３．塔５本のハノイの塔問題
問題３（１）塔が5本、円盤がnmax枚のとき、解法１による円盤の
移動回数を求めるプログラム(ha311.c)を作成せよ。
問題３（２）塔が5本、円盤がnmax枚のとき、解法２による円盤の
移動回数を求めるプログラム(ha321.c)を作成せよ。
４．塔ｔ本のハノイの塔問題
問題４（１）正整数mをr個の正整数に分割するプログラム(ha411.c)を
作成せよ。
問題４（２）塔が５本の時の解法２の考え方を拡張して、塔がtmax本、
円盤がnmax枚のとき、円盤の移動回数を求めるプログラム
(ha421.c)を作成せよ。
シェルプログラミング
●cshプログラミングの基礎(pdfファイル)
１．ｃｓｈとは
１．１ シェルスクリプトファイルの書き方
１．２ シェルスクリプトファイルの実行方法
２．簡単なシェルスクリプト
２．１ ｄａｔｅ, ｃａｌ
２．２ ｅｃｈｏ
２．３ リダイレクション パイプ エイリアス
３．シェル変数と演算
３．１ 文字列の代入
３．２ 数値の代入と演算
４．特別な変数
４．１ ａｒｇｖ
４．２ ＄？ ＄＃
４．３ ＄＄ ＄＜
４．４ ワイルド・カード文字
５．コマンド置換
６．入力の埋め込み
７．割り込み
８．条件分岐
８．１ ｉｆ文
８．２ ｓｗｉｔｃｈ文
９．制御構造
９．１ ｗｈｉｌｅ文
９．２ ｒｅｐｅａｔ文
９．３ ｓｈｉｆｔ文
９．４ ｆｏｒｅａｃｈ文
１０．トレース
●cshプログラミングの応用(pdfファイル)
１．課題
課題１：与えられたパス名からディレクトリ名とファイル名を分離し
出力せよ。
課題２：オプション(-in)の後に続く文字列とオプション(-out)
の後に続く文字列をそれぞれまとめる。オプションの指定が
なく文字列から始まるとき、-inを仮定する。
課題３：複数のファイルから与えられたパターンとマッチする文字列
を含む行を取り出せ。ただし、パターンは、'で囲むこと。
課題４：ファイルをコピーせよ。
課題５：標準入力からの入力をファイルに保存せよ。
課題６：あるディレクトリの直下にあるファイルをすべて表示せよ。
ディレクトリが指定されない場合、現ディレクトリとする。
課題７：あるディレクトリ以下の木構造をスタックを使って表示せよ。
課題８：コマンドを再帰的に呼び出すことができる。
再帰動作の確認をせよ。
課題９：指定されたディレクトリ以下の木構造を表示(再帰呼び出し
による)せよ。
課題１０：指定されたディレクトリ以下の木構造を表示（再帰呼び出し
による）し、通常のファイルの場合、最初の20行を表示せよ。
また、不要なファイルは削除できること。
関連知識
●エスケープシークエンスの応用(pdfファイル)
１．はじめに
２．基本機能
２．１ 画面のクリア
２．２ カーソルの位置指定と文字の色指定
２．３ 領域
３．簡単なスクリーン・エディタ
３．１ カーソルの制御、文字入力機能
３．２ １文字挿入・削除、１行挿入・削除機能
３．３ スクロール機能
４．課題
４．１ 課題１
●高精度演算(pdfファイル)１．はじめに ２．アーカイブファイル ３．定義される関数 ３．１ display関数、set関数 ３．２ add関数 ３．３ sub関数 ３．４ mul関数 ３．５ divi関数 ３．６ move関数 ４．高精度計算実行例 ４．１ アーカイブファイルの作成 ４．２ 高精度計算 ５．課題 ５．１ 課題１ ５．２ 課題２●Mule入門(pdfファイル)
１．Muleの起動と終了
２．新規ファイル作成
２．１ 日本語処理
３．ファイルの編集
４．ファイル操作
４．１ ファイル読込み
４．２ ファイル挿入
４．３ ファイル保存
５．モード
５．１ シェルモード
５．２ Diredモード
５．３ 拡張モード
５．４ mailモード
５．５ rmailモード
５．６ viモード
５．７ w3モード
６．バッファの操作
７．電子ニュース
７．１ 電子ニュースの読み方
７．２ 電子ニュースの書き方
７．３ 電子ニュースに対する返事の書き方
８．新しい関数の定義と実行
９．muleのインストール
９．１ かんなによる日本語入力
９．２ たまごによる日本語入力
●Mathematica入門(pdfファイル)１．はじめに ２．数値計算 ２．１ 四則演算と定数 ２．２ 組み込み関数 ２．３ 数の表示 ２．４ 代入 ２．５ Ｐｒｉｎｔ文 ２．６ Ｄｏ文 ２．７ Ｆｏｒ文 ２．８ Ｗｈｉｌｅ文 ２．９ Ｉｆ文 ２．１０ 和と積 ２．１１ 関数の定義 ［例２．１］1+1/2+1/3+…+1/n+…の計算 ［例２．２］πの計算 ［例２．３］２＾ｎ−１の素数 ３．ファイル処理 ３．１ ファイルからコマンド入力 ３．２ ファイルへ結果の出力 ［例３．１］ファイル処理の例 ４．数式処理 ４．１ 方程式 ４．２ 式の展開、因数分解、部分分数展開、簡約化 ４．３ 級数、微分、定積分 ４．４ 漸化式 ５．リスト処理 ５．１ リスト ５．２ 素数 ５．３ 集合 ［例５．１］素数に関する問題 ［例５．２］ピタゴラス数 ［例５．３］リスト処理 ６．グラフィックス ６．１ 関数のグラフ ６．２ データのグラフ ６．３ データファイルの読込み ［例６．１］グラフィックスの例 ７．課題 ７．１ 課題１ ７．２ 課題２ ７．３ 課題３ ７．４ 課題４
その他