_AProg2010/ex06
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
*応用プログラミング演習 2010年度 第6回 [#bebe2b15]
//&color(#ff0000){工事中};
#contents
**注意 [#i749b259]
-演習のすすめ方について [[AProg2010/ex01#note]]
-Linux環境での操作についてはわからないことがあったら [[Docs/4UNIXBeginners]]
**課題N この課題には点数はつきません [#j9f65946]
+[[AProg2009]]の前半（高橋担当分）の出席回数と評点の相関データ [[AProg2009/result]] のページの真ん中あたりにある．これを理解しよう
+講義資料の kenshin2.c を作って動作確認しなさい
+講義資料の kenshin4.c を作って動作確認しなさい
+typedefを使って kenshin4.c を書き換えてみなさい
+講義資料の scanftest.c を作って動作確認しなさい
**課題A 締切: 今回の演習終了時 [#ma58609e]
***step1 [#t716d2cc]
前回いくつかのファイルをとってきたディレクトリ /home/sample/takataka/aprog2010/ に，data4ex06a.txt という名前のテキストファイルがおいてある．
cpコマンドを使ってこれを自分の aprog2010 ディレクトリにコピーし，内容を less で確認しなさい．
このファイルには，「名前」，「年齢」，「視力」という3つの情報が一組になって書き込まれている．
よく見ると一部おかしなところがあるが，以下ではそのまま扱ってみよう．
***step2 [#ffc074ba]
data4ex06a.txt の内容を読み込み，次のような出力をするプログラムを作成しよう．
#pre{{
$ ./ex06a
4件のデータを読み込んだで
Hogeo 38 1.5
Henako 18 5.0
Fugayo 20 0.1
Piyochan 67 1.0
}}
ただし，次の指示に従うこと
-ソースファイル名は ex06a.c とすること（ソースファイルはこれひとつでよい）
-一組のデータを格納する構造体を自分で定義し，その構造体の配列を用いること
-次のようにNを定義し，これを↑の配列の大きさとすること
#define N 100
//-自分で定義した構造体に，typedef を用いて適当な型名をつけること
-データの読み込みの際にはfscanf()の戻り値を利用してデータ件数をプログラム自身に数えさせること．最大N件読み込めるようにすること
-上記の実行例で「4件のデータを読み込んだで」と出力されている理由を考えること
**課題B 締切: 次回の演習終了30分前 [#z2d4cd97]
郵便番号簿探索プログラムを作ろう．この課題には通常の課題の2倍の点数がつきます．
***step1 [#la1cd9bd]
ディレクトリ /home/sample/takataka/aprog2010/ に，
-zipdata100 100件分の郵便番号データから成るテキストファイル
-zipsearch.h zipsearch.o用のヘッダファイル
-zipsearch.o 探索の関数などをコンパイルして作られたオブジェクトファイル
という3つのファイルが置いてある．
これらを自分の aprog2010 ディレクトリにコピーし， zipsearch.o 以外のファイルの内容を less で確認しなさい（zipsearch.o はオブジェクトファイルなので less では普通の人は読めません．試してみると面白いかもしれませんが）．
***step2 [#p00dca95]
上記のファイルを利用して，zipdata100 に含まれるデータを読み込んで探索するプログラムを作りなさい．
-mainを含むソースファイルの名前は ex06b.c とすること
-前回出てきた zssample と同様の動作をするように作ること．ただし，以下の2つの機能は実現しなくともよい（もちろんできる人は実現したらよい）．
--探索回数の表示
--データの配列中での位置の表示（zssampleでは [] で囲んでそれを表してます）
-まずは線形探索するプログラムを作り，うまくいったら，二分探索の関数を使うように改造すること（&color(#00a000){二分探索するためにはデータをあらかじめソートしておく必要があることに注意};）
***step3 [#h4483976]
zipdata100 はデータが100件しかなくておもしろくないので，13万件弱のデータを含むファイルを使ってためそう．
このファイルはサイズが大きい（約4MB）ので，各自のディレクトリにファイルをコピーするともったいない．次のように fopen するようにしたらよい．
fopen("/home/sample/takataka/aprog2010/zipdata", "r");
このように，fopenの引数には，ファイル名だけではなく，ディレクトリ名も含めた&color(#00a000){パス};を指定することができる．
構造体の配列の大きさも大きくしなければならないことに気をつけよう．
もしかすると，配列のサイズを大きくすると，プログラムが正しく書けているのに実行すると Bus Error となってしまうかもしれない．
その場合は，配列の宣言の頭に static をつけて，
static ZIP_DATA hoge[....];
のようにするとよい（どうしてこうするとよいか気になる人は，高橋に尋ねてください）．
**課題C（おまけ） 締切: 次回の演習終了30分前 [#kadaiC]
以下のことをやってみよう．
+課題Bのプログラムで探索回数（キー値とデータとの比較の回数）を表示できるようにし，線形探索と二分探索でどのくらい探索回数が違うかいろいろ試してみなさい．
+二分探索とはどのようなアルゴリズムであるか調べ，高橋に説明しなさい．
+郵便番号簿を郵便番号の昇順にソートした結果を出力するプログラムを作りなさい．
ただし，課題Bで与えられたソート関数を呼ぶのでは面白くないので，ソート関数を自分で作ろう．ソートアルゴリズムは好きなものを使ったらよい（なるべく計算量の少ないアルゴリズムの方がかっちょいいでせう）．
**課題T-ほげとは？ [#t939b454]
TAさんが作ってくれたおまけ課題です．
是非挑戦してください．
「ほげ」は作成してくれたTAさんの名前です．
注意：
-今回の[[課題C>./#kadaiC]]を締切までに仕上げた上でさらにこれらの課題も1つ以上できた場合，おまけ点にさらにおまけ点をつけます
-締切は「次回の演習終了30分前」です
-チェックは出題したTAさんにしてもらってください．質問予約時にどの課題のチェックをしてほしいのかわかるようにしてください．
**課題T-木村 [#hfda38cb]
>
本問題は[[ACM-ICPC>http://www.acm-japan.org/icpc-j.html]]というプログラミングの国際大会の
[[ACM-ICPC OB/OG会>http://acm-icpc.aitea.net/index.php?FrontPage]]による
模擬国内予選問題を参考にして作成しています。
興味を持ったら来年のICPCに出場してみたらいいかも。
2005年ICPC模擬国内予選 Problem A "Keitai Message"より。
<
ある携帯電話での文字の入力が、数字ボタンを複数回押すことによって入力文字を決定する仕組みとなっているとする。
ボタンの押され方をもとにして、この携帯電話で入力されたメッセージを再現するプログラムを作ってみよう。
ただし、携帯電話は以下のような仕様になっているとする。
携帯電話の数字ボタンの文字の割り当て
#pre{{
1: . , ! ? (スペース)
2: a b c
3: d e f
4: g h i
5: j k l
6: m n o
7: p q r s
8: t u v
9: w x y z
0: 確定ボタン
}}
-1文字の入力が終わるごとに確定ボタンを押すことになっているとする。
-何もボタンが押されていないときに確定ボタンが押されても、文字は出力されない。
-同じボタンを押し続けていると変化する文字がループする。(a→b→c→a→b…)
実行例
#pre{{
$ ./a.out
803307777080 ← キーボードからの入力．最後にEnter
test ← プログラムの出力
$ ./a.out
44033055505550666011011111090666077705550301110 ← キーボードからの入力．最後にEnter
hello, world! ← プログラムの出力
$ ./a.out
444440666040330440666040330 ← キーボードからの入力．最後にEnter
hogehoge ← プログラムの出力
$ ./a.out
000333000088888888888040000222222200000000 ← キーボードからの入力．最後にEnter
fuga ← プログラムの出力
}}
繰り返しキーボードから入力出来るようにしても良い。
-hint1:入力の受け取りは文字列を使うのがいいかも（大きさは100ぐらいで）
-hint2:ボタンに対応するchar型の配列を使えば楽かも
-hint3:文字の'0'は整数型だと0とは違う値だから…
-hint4:ループはボタンが何回押されたら起こるのかな？
終了行:
*応用プログラミング演習 2010年度 第6回 [#bebe2b15]
//&color(#ff0000){工事中};
#contents
**注意 [#i749b259]
-演習のすすめ方について [[AProg2010/ex01#note]]
-Linux環境での操作についてはわからないことがあったら [[Docs/4UNIXBeginners]]
**課題N この課題には点数はつきません [#j9f65946]
+[[AProg2009]]の前半（高橋担当分）の出席回数と評点の相関データ [[AProg2009/result]] のページの真ん中あたりにある．これを理解しよう
+講義資料の kenshin2.c を作って動作確認しなさい
+講義資料の kenshin4.c を作って動作確認しなさい
+typedefを使って kenshin4.c を書き換えてみなさい
+講義資料の scanftest.c を作って動作確認しなさい
**課題A 締切: 今回の演習終了時 [#ma58609e]
***step1 [#t716d2cc]
前回いくつかのファイルをとってきたディレクトリ /home/sample/takataka/aprog2010/ に，data4ex06a.txt という名前のテキストファイルがおいてある．
cpコマンドを使ってこれを自分の aprog2010 ディレクトリにコピーし，内容を less で確認しなさい．
このファイルには，「名前」，「年齢」，「視力」という3つの情報が一組になって書き込まれている．
よく見ると一部おかしなところがあるが，以下ではそのまま扱ってみよう．
***step2 [#ffc074ba]
data4ex06a.txt の内容を読み込み，次のような出力をするプログラムを作成しよう．
#pre{{
$ ./ex06a
4件のデータを読み込んだで
Hogeo 38 1.5
Henako 18 5.0
Fugayo 20 0.1
Piyochan 67 1.0
}}
ただし，次の指示に従うこと
-ソースファイル名は ex06a.c とすること（ソースファイルはこれひとつでよい）
-一組のデータを格納する構造体を自分で定義し，その構造体の配列を用いること
-次のようにNを定義し，これを↑の配列の大きさとすること
#define N 100
//-自分で定義した構造体に，typedef を用いて適当な型名をつけること
-データの読み込みの際にはfscanf()の戻り値を利用してデータ件数をプログラム自身に数えさせること．最大N件読み込めるようにすること
-上記の実行例で「4件のデータを読み込んだで」と出力されている理由を考えること
**課題B 締切: 次回の演習終了30分前 [#z2d4cd97]
郵便番号簿探索プログラムを作ろう．この課題には通常の課題の2倍の点数がつきます．
***step1 [#la1cd9bd]
ディレクトリ /home/sample/takataka/aprog2010/ に，
-zipdata100 100件分の郵便番号データから成るテキストファイル
-zipsearch.h zipsearch.o用のヘッダファイル
-zipsearch.o 探索の関数などをコンパイルして作られたオブジェクトファイル
という3つのファイルが置いてある．
これらを自分の aprog2010 ディレクトリにコピーし， zipsearch.o 以外のファイルの内容を less で確認しなさい（zipsearch.o はオブジェクトファイルなので less では普通の人は読めません．試してみると面白いかもしれませんが）．
***step2 [#p00dca95]
上記のファイルを利用して，zipdata100 に含まれるデータを読み込んで探索するプログラムを作りなさい．
-mainを含むソースファイルの名前は ex06b.c とすること
-前回出てきた zssample と同様の動作をするように作ること．ただし，以下の2つの機能は実現しなくともよい（もちろんできる人は実現したらよい）．
--探索回数の表示
--データの配列中での位置の表示（zssampleでは [] で囲んでそれを表してます）
-まずは線形探索するプログラムを作り，うまくいったら，二分探索の関数を使うように改造すること（&color(#00a000){二分探索するためにはデータをあらかじめソートしておく必要があることに注意};）
***step3 [#h4483976]
zipdata100 はデータが100件しかなくておもしろくないので，13万件弱のデータを含むファイルを使ってためそう．
このファイルはサイズが大きい（約4MB）ので，各自のディレクトリにファイルをコピーするともったいない．次のように fopen するようにしたらよい．
fopen("/home/sample/takataka/aprog2010/zipdata", "r");
このように，fopenの引数には，ファイル名だけではなく，ディレクトリ名も含めた&color(#00a000){パス};を指定することができる．
構造体の配列の大きさも大きくしなければならないことに気をつけよう．
もしかすると，配列のサイズを大きくすると，プログラムが正しく書けているのに実行すると Bus Error となってしまうかもしれない．
その場合は，配列の宣言の頭に static をつけて，
static ZIP_DATA hoge[....];
のようにするとよい（どうしてこうするとよいか気になる人は，高橋に尋ねてください）．
**課題C（おまけ） 締切: 次回の演習終了30分前 [#kadaiC]
以下のことをやってみよう．
+課題Bのプログラムで探索回数（キー値とデータとの比較の回数）を表示できるようにし，線形探索と二分探索でどのくらい探索回数が違うかいろいろ試してみなさい．
+二分探索とはどのようなアルゴリズムであるか調べ，高橋に説明しなさい．
+郵便番号簿を郵便番号の昇順にソートした結果を出力するプログラムを作りなさい．
ただし，課題Bで与えられたソート関数を呼ぶのでは面白くないので，ソート関数を自分で作ろう．ソートアルゴリズムは好きなものを使ったらよい（なるべく計算量の少ないアルゴリズムの方がかっちょいいでせう）．
**課題T-ほげとは？ [#t939b454]
TAさんが作ってくれたおまけ課題です．
是非挑戦してください．
「ほげ」は作成してくれたTAさんの名前です．
注意：
-今回の[[課題C>./#kadaiC]]を締切までに仕上げた上でさらにこれらの課題も1つ以上できた場合，おまけ点にさらにおまけ点をつけます
-締切は「次回の演習終了30分前」です
-チェックは出題したTAさんにしてもらってください．質問予約時にどの課題のチェックをしてほしいのかわかるようにしてください．
**課題T-木村 [#hfda38cb]
>
本問題は[[ACM-ICPC>http://www.acm-japan.org/icpc-j.html]]というプログラミングの国際大会の
[[ACM-ICPC OB/OG会>http://acm-icpc.aitea.net/index.php?FrontPage]]による
模擬国内予選問題を参考にして作成しています。
興味を持ったら来年のICPCに出場してみたらいいかも。
2005年ICPC模擬国内予選 Problem A "Keitai Message"より。
<
ある携帯電話での文字の入力が、数字ボタンを複数回押すことによって入力文字を決定する仕組みとなっているとする。
ボタンの押され方をもとにして、この携帯電話で入力されたメッセージを再現するプログラムを作ってみよう。
ただし、携帯電話は以下のような仕様になっているとする。
携帯電話の数字ボタンの文字の割り当て
#pre{{
1: . , ! ? (スペース)
2: a b c
3: d e f
4: g h i
5: j k l
6: m n o
7: p q r s
8: t u v
9: w x y z
0: 確定ボタン
}}
-1文字の入力が終わるごとに確定ボタンを押すことになっているとする。
-何もボタンが押されていないときに確定ボタンが押されても、文字は出力されない。
-同じボタンを押し続けていると変化する文字がループする。(a→b→c→a→b…)
実行例
#pre{{
$ ./a.out
803307777080 ← キーボードからの入力．最後にEnter
test ← プログラムの出力
$ ./a.out
44033055505550666011011111090666077705550301110 ← キーボードからの入力．最後にEnter
hello, world! ← プログラムの出力
$ ./a.out
444440666040330440666040330 ← キーボードからの入力．最後にEnter
hogehoge ← プログラムの出力
$ ./a.out
000333000088888888888040000222222200000000 ← キーボードからの入力．最後にEnter
fuga ← プログラムの出力
}}
繰り返しキーボードから入力出来るようにしても良い。
-hint1:入力の受け取りは文字列を使うのがいいかも（大きさは100ぐらいで）
-hint2:ボタンに対応するchar型の配列を使えば楽かも
-hint3:文字の'0'は整数型だと0とは違う値だから…
-hint4:ループはボタンが何回押されたら起こるのかな？
ページ名:
![[PukiWiki]](image/blackuni3-80x80.png "[PukiWiki]")
