計算機言語 I 第 7 回関数

計算機言語 I ^第 7 ^{回 関数}

この資料: http://www.math.u-ryukyu.ac.jp/~suga/gengo/2021/07.pdf

レポートへのツッコミ ( ^{というより} , ^{対称群の話} )

前回のレポートの「置換」に関する補足です.   τ ∈ S_n をn 次対称群の元とするとします. 数列, τ(1), τ(2), . . . , τ(n)をバブルソートで整列する(1,2, . . . , nの順に並べ替える)のは, 隣接置換(i, i+ 1)を 右からτに掛けて行って,恒等写像(Snの単位元)を得る手順になっています.

実際,バブルソートは,

τ(i)> τ(i+ 1)となるiを見つけたら,τ(i)とτ(i+ 1)を入れ替える

を組織的に実行して,整列をするというアルゴリズムです. 上の操作は,群の積τ◦(i, i+ 1)の写像を計算して いることと同等です. (対称群の積は写像の合成なので,τ◦(i, i+ 1)(i) =τ(i+ 1),τ◦(i, i+ 1)(i+ 1) =τ(i)).

従って,バブルソート実行中の入れ替えが起こる場所を,i1, i2, . . . , ikとすると, τ◦(i1, i1+ 1)◦(i2, i2+ 1)◦ · · · ◦(ik, ik+ 1) = id

となって, 両辺に左からτ⁻¹を書けることにより, τ⁻¹の隣接互換の積への分解が得られるのです. これは, Snが隣接互換で生成されるという証明の一つでもあります. アルゴリズム的なので,具体的に任意の互換を隣 接互換で書き下す証明よりは,明解さに欠ける感はありますが...

report 6-2ですが, 置換の符号の計算は,次でできることに気づいて下さい.

int sign = 1;

if (a[i} > a[i+1]){

a[i] と a[i] の入れ替えのコード(略);

sign * = -1;

}

置換の転倒数

置換τ に対して, i < jかつτ(i)> τ(j)となる対(i, j)の数をτの転倒数といいます. 簡単な考察から,隣

接互換(i, i+ 1)を右から掛けると,転倒数は, 1増えるか1減るかしかありません. 従って,置換τを隣接互

換の積に直すには,転倒数の個数だけ隣接互換を使うことになります. また,最も沢山の隣接互換を必要とする 置換は, 1,2, . . . , nを逆順に並べた次の置換になります. (転倒数は, n(n−1)/2 =nC2.)

( 1 2 · · · n

n n−1 · · · 1 )

1

教科書 6 ^章の補足

教科書に書かれていない事を補足します.

関数の返り値(教科書では型,英語ではreturn value)として使えるのは,これまでに出てきた, (unsigned, signed) char, int, float, double

とこれから出てくる,ポインタ型, 構造体,共用体で, 配列を関数の返り値にはできません.

関数を利用する最も大きな理由は,「プログラムを適当な大きさに分割して書く」です. 処理の長さが100行 を超えるくらいから,その処理を人間が追うのは難しくなることが知られています. そこで,関数を利用してプ ログラムを小さく分割して書いていく様にします.

教科書, p. 86は正確でないところがあります. 関数の使い方なのですが, Cの正確な仕様は,

C

,

.

です. 上のことを実現するには,次のいずれかの方法をとる必要があります. 1. その関数呼び出しの前にその関数自体を記述してしまう.

2. 関数呼び出しの前に,その関数のプロトタイプ宣言を記述する(教科書 p. 86).

教科書には, 1. の方法が書いてありませんが, そのようなプログラムを書いても大丈夫です. コンパイラは 関数の素性(返り値,引数の型)を用いることにより,機械語を効率よく作成できますが, これがないと, どのよ うな機械語を作り出して良いかがわかりません. そのために,上のような仕様があります.

2

レポート問題

締切は, 6月7日10:00 (JST).

• 次の様なプログラムを作れ. (件名: gengo2021 report 7)

– Heronの公式により3角形の3辺からその面積を計算する関数heron を書く

関数heron では, 3つのdouble型の引数(3辺の値)を取り, 面積の値をdouble型で返す. ただし, 3つの引数の値が3角形を作らないときには, 0以下の値を返す(値は,何でも良い).

– main関数では, 3つのdoubleを標準入力から読み取り,関数heronを利用して,それらが3角形 を作ればその面積,作らなければ「入力した3数は3角形を作りません」を出力する.

Heronの公式の特性をうまく利用したプログラムを書いてください.

3