[ 0 ] a [ 1 ]

アルゴリズム論１第1回　授業の目標
1. 典型的なデータ構造を理解し、使いこなせる。
! データ構造：
" 配列（線形リスト）
" 連結リスト
! 操作：　作成、要素の挿入、削除、線形探索
2. 探索とソートのアルゴリズムを理解し、使いこなせる。
3. アルゴリズムの検証をC++言語で行なうことができる。
! 探索
"
! ソート
"
"
"
2分探索
選択ソート
バブルソート
クイックソート
Itsuo Umebu
成績評価とレポートの提出
! 評価
出席（レポート）期末試験　の総合評価
60点以上合格
! レポートの提出
"プログラム：電算センターのサーバにファイル転送
iis1, iis2, iis3, peace1, peace2, ..., peace8
"フローチャート：手書きで提出
! 約束：分からないところは、必ずその週の内に解決
遠慮せず、聞きにきてください。318号室です。
Itsuo Umebu
「基本データ型」
数値型
なぜ、「型」の
区別が必要な
んだろう？
値
整数型
2004
i
1.8
x
変数名
u
浮動小数点型
c
文字型
Itsuo Umebu
「配列」
配列
データの型は一つ
の配列では皆同じ
data0 data1 data2 data3
a[0] a[1] a[2] a[3]
アドレスは順番
になっている
配列は何のた
めに使うの？
Itsuo Umebu
「クラス」
様々な「基本データ型」の変数を組み合わせて一つのデータ型を作る
全体に一つの名前を付ける。
その名前（クラス名）が
新しい「データ型」となる
クラスの仲間を
「メンバー変数」
という
学生番号
氏　名
アルゴリズム
システムＢ
平均点
a602200
楳生逸雄
80
85
82.5
文字型
文字型
整数型
整数型
浮動
小数点型
Itsuo Umebu
「クラス」と「配列」の組み合わせ配列はカッコイイ
「クラス」を要素にもつ配列を作ることができる。
が不便なところも
あるんだ
新しい名前（クラス名）が
新しい「データ型」となる
学生番号
氏　名
アルゴリ
ズム
システム
Ｂ
平均点
list[0]
a603200
楳生逸雄
80
85
82.5
list[1]
a603201
a603202
ドラエモン
のびた
100
60
95
75
97.5
67.5
list[2]
list[3]
クラスにはデータを納めたり、取り出したり、
表示したり、探したりなど操作を含める。
「メンバー関数」で行う。
Itsuo Umebu
「配列」と「連結リスト」　ーメモリ内のデータの配置
配列
連結リスト
a_0
a_2
a[0] a[1] a[2] a[3]
a_1
a_3
! 配列では各要素は隣り合って
置かれる
! 隣の住所は自動的に分かる
（+1すればよい）
! 要素数は固定。
! 各要素はメモリ内の空いたところにある
! 各要素が互いにつながるためには
自分の次の要素の住所を知ってい
る必要がある
! 要素数の増減や順序の変更簡単
Itsuo Umebu
「町内会の回覧板」と「学校の連絡網」
町内会回覧板
三宅8丁目
小泉
藪
学校の連絡網
三宅
小泉
海老園
楳生
楳生布施
藪
廿日市
回覧板は、住所や電話番号
を知らなくとも隣に送ればよい
布施
呉
隣同士でなくとも住所や
電話番号で連絡がとれる
Itsuo Umebu
課題の提出方法
ノートPC
大学のサーバ
ftp
/*a60..
/*a60..
プログ
プログ
ラム
ラム
% ftp iis1
IDとPWD入力
% cd ~iu-ed/指定ディレクトリ
% put ファイル名学生番号
% bye
学生番号は小文字の a から初めてください
Itsuo Umebu
C++ プログラムの作成～実行その１
実行形式ファイルを残す必要が無い場合
入力コマンド
ファイル名は
「・・・・・.cc」とする
・・・・・.cc からa.out
というファイルが自
動的に作られる
a.out は計算機が
実行できる機械語
プログラム
プログラム作成
vi ファイル名
コンパイル
g++ ファイル名
実
行
./a.out
Itsuo Umebu
C++ プログラムの作成～実行その２
実行形式のファイルを残したいとき
入力コマンド
プログラム作成
コンパイル
実
行
vi ファイル名
g++ ファイル名 -o 実行形式ファイル名
./実行形式ファイル名
Itsuo Umebu
フローチャートとプログラムの作成ー復習その1
プリントの問題を考えてください。
プログラムの言語は、CでもC++でもよい。
Itsuo Umebu
配列に対する基本操作
課題1　下記のプログラムを作れ。
・配列の各要素に　0～200　までの整数を順に1個づつ入れる。
全て入れ終わった後、全要素を表示する
・キーボードから　0～200　の間の偶数を入力する
・それが何番目の要素かを表示する
（入力した数字と配列要素がもっている数を比較して、
一致したらその要素の添え字を表示すること）
提出先ディレクトリ： algo1
“プログラムの先頭に、学生番号を必ず入れること !!”
提出の仕方は先の図のとおりとする
Itsuo Umebu
配列に対する基本操作　1
配列に整数を詰める
開始
ループ 1
n : 0, 1, 200
n→a[n]
ループ 1
/*学生番号*/
// hairetsu no sosa
#include　<iostream>　using namespace std;
main( )
{
int x, a[201],n,m,i;
for (n = 0; n <= 200; n++ ){
a[n] = n;
}
Itsuo Umebu
配列に対する基本操作　2
配列要素を表示
ループ 2
m : 0, 1, 200
a [ m ] 出力
for( m = 0; m <= 200; m++ ){
cout << a[m] << endl;
}
ループ 2
Itsuo Umebu
配列に対する基本操作　3
入力した数と配列要素の比較
x 入力
ループ 3
i : 0, 1, 200
cin >> x;
for( i = 0; i < = 200; i ++ ){
if ( x == a[i] ){
cout << i << endl;
}
}
return 0;
yes
x = a [ i ]?
i 出力
no
ループ 3
}
終了
Itsuo Umebu
配列に対する基本操作　解答例
開始
配列に整数挿入・表示
x 入力
ループ
i :0, 1, 200
yes
x = a [ i ]?
/*学生番号*/
#include　<iostream>　using namespace std;
// exercise 1 and 2
main( )
{
int x, a[201],n,m,i;
for(n=0;n<=200;n++){
a[n]=n;
}
for(m=0;m<=200;m++){
cout<<a[m]<<endl;
}
i 出力
no
cin>>x;
for(i=0;i<=200;i++){
if(x==a[i]){
cout << i <<endl;
}
}
return 0;
ループ
終了
}
Itsuo Umebu
出席の登録
手順
1. Web ブラウザを立ち上げる
http://www.iis.it-hiroshima.ac.jp/att/
2. アルゴリズム論Ⅰ [水・3,4時限] B班　選択
3. 最初だけ、新規学生登録　送信
4. 次回からは出席登録
5. 毎回、指示された数字を入力する
1回目 38
Itsuo Umebu

Download Report