アルゴリズムとデータ構造

アルゴリズムと
データ構造
第3回
基本的なデータ構造（２）:
配列
1
前回の復習



アルゴリズムの計算量
最悪（最大）計算量
計算量の漸近的評価（オーダ）




多項式時間アルゴリズム（polynomial time algorithm）
指数時間アルゴリズム（exponential time algorithm）
配列
ポインタの復習
2
演習問題の答え
第1問
次のような計算量T(n)について、そのオーダを求めなさい

O(n3)
T(n) = 1.5n2+0.6n3 + 8.3n
(b) T(n) = 4logn + 8n
O(n)
(c) T(n) = 3n2 + 7nlog3n = 3n2 + 7n2log3
= (3+7log3) n2
(a)
(d)T(n)
= 2n + 3n5
O(2n)
O(n2)
注意：2nのような「２」は定数倍ではない。nの
関数に『掛け算』されている『数』が無視の対
象
手順： (1)定数倍を無視
(2)最も大きくなるnの項だけを残す
3
演習問題の答え
第2問
計算量T(n)= 2n+1のとき、そのオーダは2nといえるか。また、
T(n)=22nのときはどうか示しなさい。

解答：
∵T(n) = 2n+1 = 2・2n
∴T(n) のオーダは2nと言える
T(n)＝22nのとき、定義を用いて証明する
①．この定義に従い、Ｔ（ｎ）＝22nがＯ（2n）であると仮定する。
②．2つの正の定数n0とcが存在して、ｎ≧n0なるすべてのｎに対して、22n≦c2nが
成り立つ。
③．この不等式の両辺を2nで割ると、2n≦ｃとなる。
④．ここで、ｎが大きくなったとき、この式の左辺は無限大になるが、右辺は定数
である。
⑤．これは、この不等式が成り立つことに矛盾している。
4
したがって、T(n)= 22nのときのオーダは2nとはいえない。
演習問題の答え
第2問
計算量T(n)= 2n+1のとき、そのオーダは2nといえるか。また、
T(n)=22nのときはどうか示しなさい。

解答：（解法２）
極限理論を用いて証明する
T(n)
lim
＝
𝑛→∞ G(n)
定数 T n のオーダはG n のオーダと等しい
∞ T n のオーダはG n のオーダより大きい
20n+1 T n のオーダはG n のオーダより小さい
∵ lim n ＝2
𝑛→∞ 2
∴ T 𝑛 2=2n2n+1のオーダはO(2n)
∵ lim n ＝∞
といえる
𝑛→∞ 2
5
動的メモリ管理

今までのメモリを割り当てる方法



int a; →1個しか割り当てられない
int a[10]; →あらかじめ割り当てる個数（たとえば10個）が決まってい
ないとダメ
要らなくなったとき解放できない
動的なメモリ割り当て/解放
malloc(), calloc(,)関数
free()関数を使う
6
動的メモリ管理

動的メモリ管理とは



プログラム実行中に、記憶域を必要な分確保
不要になった記憶域は開放
動的メモリ管理でできること


プログラム開始後に配列領域の大きさを決定
関数内で新規作成したデータの返却
7
動的メモリ管理

記憶域の確保
• 必要な時に、必要な分だけメモリを割り当てる．
• 割り当ての結果，空っぽの配列が生成される．
• 書式：void *malloc(unsigned int size)
引数：割り当てるバイト数
返り値：割り当てた領域の先頭ポインタ（失敗すればNULL）
• 例）ポインタpを先頭に100byte割り当てるときには？
任意の型 *p; //先頭ポインタp定義
p=malloc(100); //100byte割り当て
8
mallocの使い方の例（１）
念のためchar * 型にキャストする
char *x;
x=(char *) malloc(1000*sizeof(char));
処理をする
free(x); // 解放する
1000 byte分のメモリを確保する
char は1バイトを取る
①②③④
…
1000 byte分のメモリを確保する
→x[1000]が確保された！
9
補足: キャストとsizeof演算子

キャスト演算子
データ型を変換する操作
float x;
書式：（型）式
int y;
「式」で示すデータが「型」に変換される
型が違うものを代入するときなどに使用
y=(int) x;

sizeof演算子
引数の型のサイズをbyte数で返す
sizeof(int) = 4
sizeof(char) = 1
10
mallocの使い方の例（2）
int * 型にキャストする
int *y;
y=(int *) malloc(1000*sizeof(int));
処理をする
4000 byte分のメモリを確保する
free(y);
// 解放する
int は４バイトを取る
①
②
③
…
4＊1000＝4000 byte分のメモリを確保する
→y[1000]が確保された！
11
動的メモリ管理

記憶域の確保
 calloc関数

void *calloc(size_t nmemb, size_t size)
sizeで指定したバイト数を単位として、要素nmemb個の記憶域を
確保して返す
確保された記憶域は0初期化される
確保に失敗するとNULLが返される
12
動的メモリ管理

記憶域の開放

free関数
 不要になったときメモリを解放し，他のプログラムで使
えるようにする．
 書式： void free(void *ptr)


引数：解放するメモリのポインタ
返り値：なし(void)
 例）ポインタpから始まる，malloc/callocで割り当てした
領域を解放するには？
free(p); //pから始まる領域解放
13
動的メモリ管理

動的配列の確保
char *str;
str = calloc(100, sizeof(char));
scanf(“%s”, str);
printf(“%s\”, str);
free(str);
・ char型100個分の領域を確保
・不要になったらfreeで開放するのを忘れずに
14
動的メモリ管理

動的配列の確保
int *make_array(int n) {
return (calloc(n, sizeof(int)));
}
・ n個の要素を持つint型配列を返す関数
・確保に失敗した場合はNULLが返される
・この関数を呼んだ方で、使用後freeを実行する必要あり
15
整数の動的生成
実行結果
*x = 57
16
配列の動的生成
実行例
入力
要素数：4
4個の整数を入力してください。
a[0]: 10
a[1]: 73
a[2]: 2
a[3]: -5
出力
各要素の値は以下のとおりです。
a[0] = 10
a[1] = 73
a[2] = 2
a[3] = -5
17
配列要素の最大値

要素3の配列の最大値
int a[3];
int max;
max = a[0];
If (a[1] > max) max = a[1];
If (a[2] > max) max = a[2];
18
配列要素の最大値

要素nの配列の最大値
int a[n];
int max;
/* 便宜上の宣言例 */
max = a[0];
If (a[1] > max) max = a[1];
If (a[2] > max) max = a[2];
・・・
If (a[n - 1] > max) max = a[n - 1];
19
配列要素の最大値

要素nの配列の最大値
int a[n];
int max, i;
/* 便宜上の宣言例 */
max = a[0];
for (i = 1; i < n; i++)
If (a[i] > max) max = a[i];
20
フローチャート
開始
a[0] → max
走査
i : 1, 1, n-1
Yes
a[i] > max
a[i] → max
No
走査
終了
21
配列要素の最大値を求める関数
22
配列要素の最大値を求めるメイン処理
実行例
人数：5
5人の身長を入力してください。
height[0]: 172
入力 height[1]: 153
height[2]: 192
height[3]: 140
height[4]: 165
出力最大値は192です。
23
配列要素の並びの反転
22
5
11
32
120
68
70
120
68
22
120
5
22
11
5
22
交換
70
5
11
32
n / 2回
交換
70
68
11
32
交換
70
68
120
32
24
配列要素の並びの反転

アルゴリズムの流れ
1.
2.
3.
先頭と最後尾を交換
それぞれ1つずつ内側を交換
以下中央に来るまで繰り返し
for (i = 0; i < n / 2; i++)
a[i] と a[n - i - 1] を交換
25
配列要素の並びの反転

2値の交換

作業用に同じ型の変数を介して交換
xとyを交換するとき、作業用変数tを用意した場合：
1.
xの値をtに代入
2.
yの値をxに代入
3.
tの値をyに代入
26
配列要素の並びの反転

反転プログラム
int i;
for (i = 0; i < n / 2; i++) {
int t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
27
配列要素の並びの反転関数
28
配列要素の並びの反転メイン処理
実行例
入力
要素数：5
5個の整数を入力してください。
x[0]: 10
x[1]: 73
x[2]: 2
x[3]: -5
x[4]: 42
出力
配列の要素の並びを反転しま
した。
x[0] = 42
x[1] = -5
x[2] = 2
x[3] = 73
29
x[4] = 10
基数変換

10進整数からn進整数へ

変換する数をnで割った剰余を求める


剰余を求めたら商に対して順次繰り返し
商が0になったら終了
上位桁
下位桁
2
10
6
9
1
1962
10
196 2
10
19 6
10
1 9
0 1
1962(10)
8
1962
16
1962
8
245 2
16
122 10
8
30 5
16
7 10
8
3 6
0 7
0 3
3652(8)
7AA(16)
30
基数変換関数
31
基数変換メイン処理
実行例
入力
10進数を基数変換します。
変換する非負の整数： 59
何進数に変換しますか (2-36）： 2
出力
2進数では111011です。
入力
32
もう一度しますか（1---はい/0---いいえ）：
0
まとめ


動的メモリ管理
配列の応用
 整数の動的生成
 配列要素の最大値を求める関数
 配列要素の並びの反転
 基数変換
予習：
次回は、多次元配列、構造体、配列によるリスト
33

Download Report