２００５年度・計算機数学１・第８回実習
1
● 先週の授業のキーポイント
【配列】
•
「配列」とは,同じ型を持つ要素を１個以上まとめて扱うデータ構造である.• C
において, 配列を定義するにはint a[10]
とすればよい. これによって変数名
a
を持つint
型の要素を持つ,要素数10
の配列が定義で きる.•
配列を扱う上での注意事項には以下のようなものがある.–
配列の定義において指定する要素数は「定数式」でなければならない.したがって,要素数の指定に（たとえ事前に値が入っていたとしても）変数を指定すること はできない. （gccでは,要素数の指定に変数を利用しても,文法エラーとは判断しない1の で,注意が必要である.）しかし, “
2+1 ”
が定数式であるので,a[2+1]
は正しい定義である.–
配列要素は,必ず添字0
から始まる. したがって, 10個の要素を持つ配列の有効な添字の範 囲は0
から9
までである.–
配列要素は添字をつけて参照できる. すなわち, 10個の要素を持つ配列a
の1
番目の要素 の値はa[0]
で参照できる.–
配列要素が有効な範囲を超えていても,コンパイラ等はそれをチェックしない. 実行時にエ ラーが生じるかどうかもわからない. 例えば, 10個の要素を持つ配列a
に対して,a[100] , a[-10]
はともに文法的には正しい.–
配列は,メモリ上では,連続して確保され,先頭に1
番目の要素が確保される.–
配列の初期化は,初期化子を利用してint a[3]={1,2,3}
という形で行うことができる. し かし,実行文中でこのような「一括代入」はできない.–
初期化子を利用した配列の初期化では,int a[]={1,2,3}
という形も可能である. この場 合には, 配列の要素数は初期化子中に記述された要素数で決定される. すなわち,この場合 は「要素数は3」となる.
また,int a[5]={1,2,3}
とすると,最初の3
つの要素だけが初 期化される. しかし,int a[2]={1,2,3}
のように初期化子中の要素数の方が多いのはエ ラーとなる.【マクロ定義】
• C
では,#
で始まる行は,前処理命令と呼ばれ, 処理系の最初の段階で所定の「置き換え」を行 う命令である. この処理が終わった後に, プログラムは翻訳系に渡される.•
前処理命令の例としては, 次の2
つが多用される.– “ #include <xxxx> ”
処理系で定義された場所にある
xxxx
というファイルの中身を読み込む.– “ #define XXX yyyy ”
プログラム中にあわられる
XXX
というトークン（単語）をyyyy
に置き換える.1正しくは....
「gccでは,要素数の指定に変数を利用しても,文法エラーとは判断しない」というのはガセ？
-pedantic
オプションをつけてコンパイルすると警告対象となる.緒川たまきさんに「ウソつき」と言われてしまう....ex08.tex,v 1.7 2005-06-06 16:32:33+09 naito Exp
2
２００５年度・計算機数学１・第８回実習∗ “ #define N 100 ”
とすると,プログラム中にあらわれるN
というトークンが,全て100
に置き換えられる. これは,配列の要素数,データの個数など,プログラム中で重要な意 味を持つ定数等を記述するために用いられることが多い.∗
ただし, “#define N 10+1 ”
としたときに,プログラム中でN*2
と書くと,10+1*2
と展 開されるため,意図した振舞いと異なる結果となることがある. そのためには, “#define N (10+1) ”
とすればよい.【エラトステネスのふるい】
•
「エラトステネスのふるい」(sieve of Eratosthenes)
とは,素数を求めるアルゴリズムである.•
エラトステネスのふるいは,通常以下のように表現される. 以下では, 30までの素数をエラトス テネスのふるいを用いて求めることを考えてみよう.– 2
から30
までの数を書き並べる.2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 –
先頭の2
にマークをつけ, 2の倍数を全て消去する.2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
–
マークのついていない先頭にマークをつけ, その倍数を全て消去する.2 3 5 7
11 13 17 19
23 25 29
–
以後,マークのついていない先頭の数値が√
30
以下である間これを繰り返す.–
その結果,以下のような表を得る.2 3 5 7
11 13 17 19
23 29
ここに残った数が
30
以下の全ての素数である.–
この表でマークがついていない数が素数であることは次のようにして示すことができる.その数
n
が合成数であると仮定する. そのとき, 少なくともひとつは√
n
以下の素因数p
を持たなくてはならない. しかし,上の「ふるい」の過程で,p
の倍数は既に除かれている.したがって
n
は素数であることがわかる.•
エラトステネスのふるいのアルゴリズムは, 次のように書くことができる.N
以下の全ての素数を求める.1. T
1= { 2 } ∪ { 3
以上N
以下の奇数} , p
1= 2, t = 1
と置く.2. p
2t≤ N
である間, 以下を繰り返す.(a) p
t+1= min {T
t∩ {p
t+ 1 , . . . , N }} ,
(b) T
t+1= T
t\ { 2 p
t+1, . . . , kp
t+1: kp
t+1≤ N} , (c) t ← t + 1.
これが終了したとき,
T
tはN
以下の素数の集合と一致する.ex08.tex,v 1.7 2005-06-06 16:32:33+09 naito Exp
２００５年度・計算機数学１・第８回実習
3
•
エラトステネスのふるいによってN
以下の素数を求めることができる証明の基本方針は次の 通り.1. P ( N )
をN
以下の素数の集合とする. 以下の3
つの条件が,外側のループ(2)
の不変的な 主張であることを帰納的に示す.(a) P ( N ) ⊂ T
t,
(b)
小さい順にt
個の素数はp
1, . . . , p
tである,(c) T
t は{p
j}
tj=1 の倍数を含まない.これらが証明できると,アルゴリズムが終了した時点で
