文字コードとN進数の話が終わったので演習。 文字コードとN進数の理解のために、atoi() , itoa() のプログラムについて説明を行う。

ポインタの理解が怪しいので、次回の後半はポインタの説明としよう。

atoi() , iota()

int atoi( char s[] ) {
int ans = 0 ;
int i ;
for( i = 0 ; s[ i ] != '¥0' ; i++ )
if ( '0' <= s[i] && s[i] <= '9' )
ans = ans*10 + (s[i] - '0') ;
return ans ;
}
char* itoa( char ans[] , int x ) {
// x は 16bit相当とする。
int i ;
for( i = 4 ; i >= 0 ; i-- ) {
int d = x % 10 ;
ans[ i ] = '0' + d ;
x /= 10 ;
}
ans[ 5 ] = '¥0' ;
return ans ;
}
void main() {
char str[ 10 ] ;
printf( "%d¥n" , atoi( "123" ) ) ;
printf( "%s¥n" , itoa( str , 1234 ) ) ;
}

課題

前述の10進数文字列と数値の相互変換のatoi,itoaを参考に、 2進数、8進数、16進数などの変換プログラムを作成する。 プログラミングに自信がある場合は、文字列の先頭が"0"なら8進、"0x"なら16進と いった自動判別をしたり、小数点を含む"1.234"を実数に変換するプログラムなどに 取り組むこと。

レポートでは、(1)プログラムリスト、(2)プログラム説明、(3)動作確認、(4)考察 を記載すること。考察では感想ではなく、プログラムで扱える数値の範囲や、 制限を超えるような使い方をしたらどういった現象が発生するのかを検証するなど、 の記載を期待する。

• ビリヤード軌道予測システム
• Google Mapで陣取りゲームの案があったけど、 参考になりそうなリアルタイム系陣取りゲーム。Qix
• 参考 RFIDタグ / NFC
• 授業支援 moodle / ポートフォリオ Mahara

前回の授業でmallocについて説明をしたので、今日は実際に使ってみるということで、 課題。課題のテーマは以下の通り。

mallocを使ったデータベースの作成

構造体を使った昨年度の課題で、例えば「名前と電話番号」で、入力データをすべて記憶し、 そのデータを検索などに取り組んだ。 今回は、これを拡張し、malloc を使ってプログラムを作成する。 例えば、名前は寿限無のような長い名前の人がいるかもしれない。 構造体の配列は1クラスの50人程度ではなくって、1000人かもしれない。 プログラムの実行の前に、想定する最大データ件数を入力してから、データを覚える。

さまざまな宣言でメモリのイメージの違い

上記課題に取り組む前に、さまざまな宣言で、データのイメージがどう違うのかを説明した。

(( 名前の配列 ))
// 基本10文字50人なら
char name[ 50 ][ 10 ] ;
// 名前に寿限無のような人がいるかも...
char *name[ 50 ] ;
for( i = 0 ; i < 50 ; i++ ) {
char buff[ 1000 ] ;
scanf( "%s" , buff ) ;
name[ i ] = (char*)malloc( strlen( buff ) + 1 ) ;
if ( name[ i ] != NULL ) {
strcpy( name[ i ] , buff ) ;
}
}
// クラスも最大何人かは、動かす時にしかわからない？
char **name ;
int  size ;
scanf("%d" , &size ) ; // データ件数を入力
name = (char**)malloc( sizeof( char* ) * size ) ;
if ( name != NULL ) {
for( i = 0 ; i < size ; i++ ) {
char buff[ 1000 ] ;
scanf( "%s" , buff ) ;
name[ i ] = strdup( buff ) ; // malloc+strcpy
}
}

構造体の場合

構造体を使う例として、複素数のデータの配列の作り方の違いも、説明。

(( 構造体を使う例 ))
struct Complex {
double re , im ;
} ;
// 基本 50 個の複素数
struct Complex array[ 50 ] ;
array[ 0 ].re = 1 ; // array[ 0 ] = 1 + j2 ;
array[ 0 ].im = 2 ;
// ポインタの配列
struct Complex *array[ 50 ] ;
array[ 0 ] = (struct Complex*)malloc(
sizeof( struct Complex ) ) ;
if ( array[ 0 ] != NULL ) {
array[ 0 ]->re = 1 ;
array[ 0 ]->im = 2 ;
}
// 配列へのポインタ
struct Complex *array ;
array = (struct Complex*)malloc(
sizeof( struct Complex ) * 50 ) ;
if ( array != NULL ) {
array[ 0 ].re = 1 ;
array[ 0 ].im = 2 ;
}

配列サイズを途中で倍にするテクニック

配列のサイズが実行中もわからない場合のテクニックとして、 配列が不足した際に、配列サイズを倍にする方法を説明。

(( 整数配列サイズがわからない場合 ))
int *array ;
int rsize = 0 ;
int msize = 10 ;
int x ;
array = (int*)malloc( sizeof( int ) * msize ) ;
while( scanf( "%d" , &x ) == 1 ) {
// 配列に入れる前に、サイズ不足の場合
if ( rsize >= msize ) {
int *n_array ;
n_array = (int*)malloc( sizeof( int ) * msize * 2 ) ;
if ( n_array == NULL )
break ;
// 倍の配列に中身をコピー
for( int i = 0 ; i < msize ; i++ )
n_array[ i ] = array[ i ] ;
// 元の配列を捨てる
free( array ) ;
// 倍の配列を使うように
array = n_array ;
msize *= 2 ;
}
// 配列に追加
array[ rsize ] = x ;
rsize++ ;
}

雑談：学生さんが、電話場号を覚える時はどうする？という話をしていたので、 int型で電話を覚えるのはアリだけど、090 とか 0778 といった番号は使えないよね… という説明をする。桁数は？というから、ダイヤルトーン使えば長い番号もあるよね〜 と説明をしたけど、今の学生さんはダイヤルトーンのピポパ音を知らない。

ということで、ダイヤルパルスの話(110番に電話したけりゃ、オンフックボタンを、 ポン、ポン、ポポポポポポポポポポ(1秒以内に10回連打)とすればかかる)とか、 DTMF音(低群と高群の2つの音の合成で、正確に2つの音を発することができればかかる)とかを説明する。

前回の授業で話せなかった浮動小数点の話の後、N進数について説明し 演習などを行う。

浮動小数点の扱い

浮動小数点で扱える数値の範囲についても解説。 科学技術計算などで小数点以下のデータを扱う場合、float(単精度実数),double(倍精度実数) を利用する。この場合、数値は仮数部と指数部で扱うことを説明。

	符号(s)	仮数部(e)	指数部(d)	意味
float	1bit	8bit	23bit
double	1bit	11bit	52bit

float型は、小数を32bitのデータで扱い、double型は64bitで扱う。このため、以下の様な プログラムを書くと、異常な値が求まるため注意が必要。

double x ;
scanf( "%f" , &x ) ; // 3を入力
printf( "%f" , x ) ; // 3は表示されない。
// double型では"%lf"を使う。

N進数

N進数の取扱いということで、 整数部はNで割った余りを下の桁から並べる方法と、 小数部はNをかけて整数部を書き並べる方法について説明する。 例として、0.1₎₁₀を2進数に変換すると無限小数になることなども説明。

さらに配布資料を元に、ASCIIコード表や文字コードを使った計算例などを示す。 特に、8進数がC言語では、0123 といった0で始まる数字で表すこと、 16進数が、0x123 といった0xで始まる数字で表すことを説明。 さらに、printfなどのフォーマット指定では、
%d(10進数),%o(8進数),%x(16進数),
%f(float型/小数点形式),%e(float型/指数形式),%g(%f,%eの分かりやすい書式を利用)
といった話を説明する。

来週は、atoi() や itoa() を説明して演習を行う予定。

でも昨日からの雨で、グランドコンディションも悪く、行進後の開会式も中央に集まったのは代表者となりました。

緊急連絡システムで、利用者からの質問が届いた。 「メールアドレスの登録で、失敗するデータがある」とのことであった。

定番の質問の「通常のメールアドレスで使えない特殊文字を使っているのか」 と対応をしていたが、どうも違う。 話を聞くと、「最近になり、iPhone利用者の登録がうまくいかないとの事例をよく聞く」 との情報も頂いた。

さらによく話を聞くと、どうも、 「送ってもらったメールのメールアドレス欄をコピー＆ペーストで張り付けているけど、 前後の名前欄の漢字を含む文字列もコピーしているのが原因らしい。」

山田太郎<tarou.yamada@example.co.jp>
# 当然入力して欲しいのは、tarou.yamada@example.co.jp の部分だけ

確か、最近の iPhone の機能の変更で、From欄に漢字などの名前情報付きで 送られるようになったのが原因で、「最近になり iPhone…」となったみたい。

ということで、メールアドレスをドラッグする際は、小なり記号<・大なり記号>の 間の部分だけを抜き出すようにお使い下さいと伝える。 メールアドレスをマウスで指して「右クリック」-「メールアドレスのコピー」 と説明したのは、うまく伝わらなかったみたい。

4年の創造工学の授業で企業から非常勤にて来て頂いている、 北野くんが仕事でベトナムに行って現地企業の方と ランチミーティングをしていたら、相手もEI-OBの ダン君だったとのこと。

彼ら同士は初面識ですが、同じ福井高専OBということで、 話がはずんだ様子ですね。 福井高専もインターナショナルになってますなぁ。

Debian/wheezyのstable化が近づき、メイン稼働でないものから、 squeeze から wheezy に切り替え作業。 といっても、ちょっと心配なので、不要パッケージを削除して、 testing 用の sources.list を加え、ひとまず stable にとどめておく。

この作業で、update したら、qmail が更新された。 しかもお堅い配布方針で qmail-src から入れるしかなかった qmail で バイナリパッケージが提供されている。しかしながら、設定の方針の違いで パッケージのインストールに失敗した。

いまどき、postfix 入れろよ…という意見もあるだろうが、ひとまずはサービス維持を優先。

qmail を更新すると、alias のグループIDが、今までは nogroup/65534 になっていたけど、 nofiles というグループを作ってそれを使えとの指示。 さらに、ホームディレクトリを /var/qmail だったのを /var/lib/qmail に変更しろとの指示。

(( /etc/group ))
nofiles:x:64011:
(( /etc/password ))
alias:x:64010:64011:qmail alias,,,:/var/lib/qmail/alias:/bin/false
qmaild:x:64011:64011:qmail daemon,,,:/var/lib/qmail:/bin/false
qmails:x:64012:64010:qmail send,,,:/var/lib/qmail:/bin/false
qmailr:x:64013:64010:qmail remote,,,:/var/lib/qmail:/bin/false
qmailq:x:64014:64010:qmail queue,,,:/var/lib/qmail:/bin/false
qmaill:x:64015:64011:qmail log,,,:/var/lib/qmail:/bin/false
qmailp:x:64016:64011:qmail pw,,,:/var/lib/qmail:/bin/false
(( /etc/init.d/qmail ))
sh -c "start-stop-daemon --start --quiet --user qmaild \
--pidfile /var/run/tcpserver_smtpd.pid --make-pidfile \
--exec /usr/bin/tcpserver -- -R -H \
-u `id -u qmaild` -g `id -g qmaild` -x /etc/tcp.smtp.cdb 0 smtp \
$rblsmtpd /usr/sbin/qmail-smtpd 2>&1 \
| $logger &"

先週でクラスの定義や、データ構造(オブジェクト)とそれに対する手続き(メソッド)を、 まとめて扱う(クラス)について紹介したので、その書き方の復習から、 コンストラクタ・デストラクタなどの説明を行う。

• Person-Complex.pdf
• ComplexOperator.pdf

配布資料として、上記のものを示し、構造体表記、クラス導入、 クラスには初期化などが重要であり、コンストラクタ・デストラクタなどの使い方を解説する。

今年は、参考としてC++による演算子オーバーライドなども紹介する。 これらの演算子の再定義は、Javaでは実装されていないし、 オブジェクト指向に必須の機能ではない。 しかし、オブジェクト指向に興味を持って参考書を読む際には、 「こんなこともできる…」という点で知っていてほしい。 さらに、オブジェクト指向に「どっぷり漬かる」のであれば、 最終的にSTLとかboostとかに興味を持ったら、読みこなすための重要な知識であろう。

最後に、複素数クラスの直交座標系データを、 利用者に解からないように内部データを極座標に書き換えることも可能という点を示す。 特に、プログラムやデータ構造をより良く書き換える作業を一般的に、 「リファクタリング」と呼ぶことを説明する。 オブジェクト指向が正しく適用されていれば、クラスの利用者側にリファクタリングしていることを 気づかせないまま、改良していくことが可能ということを解説する。

先週の再帰処理の時間分析ということで、ハノイの塔の処理ステップの 数学的帰納法による証明を説明する。この後、マージソートの分析とメモリ利用の効率 について説明を行った。

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となることを示す。

また、この結果を踏まえ、 最大選択法Tm(N)のプログラムと、クイックソートO(N×logN)処理時間はTq(N) があって、 Tm(100)=1msec , Tq(100)=2msec であったとして、 データ件数N=200の時には、どちらのアルゴリズムの方が速いか？ データ何件以上で、クイックソートを採用すべきか…といった問題について説明を行う。

メモリ利用の効率

次にメモリの利用効率の話について解説する。
例えば、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。

#define MEMBER_SIZE 50
#define NAME_LENGTH 20
char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;

しかしながら、クラスに寿限無のような名前の人がいたら、20文字では足りない。 また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の寿限無ありを考慮して、5Mbyte の配列を使うのは、 明らかにメモリの利用効率が低い。

このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。

char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ;
char *name[ 50 ] = {
array+0 , array+6 , array+14 , array+23 , ...
} ;

この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。

来週は、必要に応じてメモリを確保する、mallc() + free() を解説する予定。