アルゴリズムと データ構造 第 3 回 基本的なデータ構造（２） : 配列 1. 前回の復習 アルゴリズムの計算量 最悪（最大）計算量 計算量の漸近的評価 （オーダ）  多項式時間アルゴリズム（ polynomial time algorithm ）  指数時間アルゴリズム（ exponential.

Presentation on theme: "アルゴリズムと データ構造 第 3 回 基本的なデータ構造（２） : 配列 1. 前回の復習 アルゴリズムの計算量 最悪（最大）計算量 計算量の漸近的評価 （オーダ）  多項式時間アルゴリズム（ polynomial time algorithm ）  指数時間アルゴリズム（ exponential."— Presentation transcript:

1 アルゴリズムと データ構造 第 3 回 基本的なデータ構造（２） : 配列 1

2 前回の復習 アルゴリズムの計算量 最悪（最大）計算量 計算量の漸近的評価 （オーダ）  多項式時間アルゴリズム（ polynomial time algorithm ）  指数時間アルゴリズム（ exponential time algorithm ） 配列 ポインタの復習 2

3 演習問題の答え 第 1 問 次のような計算量 T(n) について、そのオーダを求めなさい (a) T(n) = 1.5n 2 +0.6n 3 + 8.3n (b) T(n) = 4logn + 8n (c) T(n) = 3n 2 + 7nlog3 n (d) T(n) = 2 n + 3n 5 手順： (1) 定数倍を無視 (2) 最も大きくなる n の項だけを残 す = 3n 2 + 7n 2 log3 = (3+7log3) n 2 注意： 2 n のような「２」は定数倍ではない。 n の関数に『掛け算』されている『数』が 無視の対象 O(n 3 ) O(n) O(n 2 ) O(2 n ) 3

4 演習問題の答え 第 2 問 計算量 T(n)= 2 n+1 のとき、そのオーダは 2 n といえるか。 また、 T(n)=2 2n のときはどうか示しなさい。 解答： T(n) ＝ 2 2n のとき、定義を用いて証明する ①．この定義に従い、Ｔ（ｎ）＝ 2 2n がＯ（ 2 n ）であると仮定する。 ②． 2 つの正の定数 n 0 と c が存在して、ｎ≧ n 0 なるすべてのｎに対して、 2 2n ≦ c2 n が成り立つ。 ③．この不等式の両辺を 2 n で割ると、 2 n ≦ｃとなる。 ④．ここで、ｎが大きくなったとき、この式の左辺は無限大になるが、右 辺は定数である。 ⑤．これは、この不等式が成り立つことに矛盾している。 したがって、 T(n)= 2 2n のときのオーダは 2 n とはいえない。 4

5 演習問題の答え 第 2 問 計算量 T(n)= 2 n+1 のとき、そのオーダは 2 n といえるか。 また、 T(n)=2 2n のときはどうか示しなさい。 解答：（解法 ２） 極限理論を用いて証明する 5

6 動的メモリ管理 今までのメモリを割り当てる方法  int a; →1 個しか割り当てられない  int a[10]; → あらかじめ割り当てる個数（たとえば 10 個）が決ま っていないとダメ 要らなくなったとき解放できない 動的なメモリ割り当て / 解放 malloc(), calloc(,) 関数 free() 関数を使う 6

7 動的メモリ管理 動的メモリ管理とは  プログラム実行中に、記憶域を必要な分確保  不要になった記憶域は開放 動的メモリ管理でできること  プログラム開始後に配列領域の大きさを決定  関数内で新規作成したデータの返却 7

8 動的メモリ管理 記憶域の確保 必要な時に、必要な分だけメモリを割り当てる． 割り当ての結果，空っぽの配列が生成される． 書式： void *malloc(unsigned int size) 引数：割り当てるバイト数 返り値：割り当てた領域の先頭ポインタ（失敗すれば NULL ） 例）ポインタ p を先頭に 100byte 割り当てるときに は？ 任意の型 *p; // 先頭ポインタ p 定義 p=malloc(100); //100byte 割り当て 8

9 malloc の使い方の例（１） char *x; x=(char *) malloc(1000*sizeof(char)); 処理をする free(x); 念のため char  型にキャストする // 解放する 1000 byte 分のメモリを確保する ①②③④ →x[1000] が確保された！ … char は 1 バイトを取る 9

10 補足 : キャストと sizeof 演算子 キャスト演算子 データ型を変換する操作 float x; int y; y=(int) x; sizeof 演算子 引数の型のサイズを byte 数で返す sizeof(int) = 4 sizeof(char) = 1 書式： （型）式 「式」で示すデータが「型」に変換される 型が違うものを代入するときなどに使用 書式： （型）式 「式」で示すデータが「型」に変換される 型が違うものを代入するときなどに使用 10

11 malloc の使い方の例（ 2 ） int *y; y=(int *) malloc(1000*sizeof(int)); 処理をする free(y); int  型にキャストする // 解放する 4000 byte 分のメモリを確保する 4 ＊ 1000 ＝ 4000 byte 分のメモリを確保する →y[1000] が確保された！ … ①②③ int は４バイトを取る 11

12 動的メモリ管理 記憶域の確保  calloc 関数 void *calloc(size_t nmemb, size_t size) size で指定したバイト数を単位として、要素 nmemb 個の記憶 域を確保して返す 確保された記憶域は 0 初期化される 確保に失敗すると NULL が返される 12

13 動的メモリ管理 記憶域の開放 free 関数  不要になったときメモリを解放し，他のプログラ ムで使えるようにする．  書式： void free(void *ptr) 引数： 解放するメモリのポインタ 返り値： なし (void)  例）ポインタ p から始まる， malloc/calloc で割り当 てした領域を解放するには？ free(p); //p から始まる領域解放 13

14 動的メモリ管理 動的配列の確保 char *str; str = calloc(100, sizeof(char)); scanf(“%s”, str); printf(“%s\”, str); free(str); ・ char 型 100 個分の領域を確保 ・ 不要になったら free で開放するのを忘れずに 14

15 動的メモリ管理 動的配列の確保 int *make_array(int n) { return (calloc(n, sizeof(int))); } ・ n 個の要素を持つ int 型配列を返す関数 ・ 確保に失敗した場合は NULL が返される ・ この関数を呼んだ方で、使用後 free を実行する必要あり 15

16 整数の動的生成 実行結果 *x = 57 16

17 配列の動的生成 実行例 入力 要素数： 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

18 配列要素の最大値 要素 3 の配列の最大値 int a[3]; int max; max = a[0]; If (a[1] > max) max = a[1]; If (a[2] > max) max = a[2]; 18

19 配列要素の最大値 要素 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

20 配列要素の最大値 要素 n の配列の最大値 int a[n];/* 便宜上の宣言例 */ int max, i; max = a[0]; for (i = 1; i < n; i++) If (a[i] > max) max = a[i]; 20

21 フローチャート 開始 a[0] → max 終了 i : 1, 1, n-1 走査 Yes No a[i] > max a[i] → max 21

22 配列要素の最大値を求める関数 22

23 配列要素の最大値を求めるメイン処理 実行例 入力 人数： 5 5 人の身長を入力してくださ い。 height[0]: 172 height[1]: 153 height[2]: 192 height[3]: 140 height[4]: 165 出力 最大値は 192 です。 23

24 配列要素の並びの反転 22511321206870 交換 70511321206822 交換 70681132120522 交換 70681203211522 n / 2 回 24

25 配列要素の並びの反転 アルゴリズムの流れ 1. 先頭と最後尾を交換 2. それぞれ 1 つずつ内側を交換 3. 以下中央に来るまで繰り返し for (i = 0; i < n / 2; i++) a[i] と a[n - i - 1] を交換 25

26 配列要素の並びの反転 2 値の交換  作業用に同じ型の変数を介して交換 x と y を交換するとき、作業用変数 t を用意した場合： 1. x の値を t に代入 2. y の値を x に代入 3. t の値を y に代入 26

27 配列要素の並びの反転 反転プログラム 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 配列要素の並びの反転関数 28

29 配列要素の並びの反転メイン処理 実行例 入力 要素数： 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 x[4] = 10 29

30 基数変換 10 進整数から n 進整数へ  変換する数を n で割った剰余を求める 剰余を求めたら商に対して順次繰り返し 商が 0 になったら終了 101962 10196 1019 101 0 2 6 9 1 1962(10) 81962 8245 830 83 0 2 5 6 3 3652(8) 161962 16122 167 0 10 7 7AA(16) 2691 下位桁 上位桁 30

31 基数変換関数 31

32 基数変換メイン処理 実行例 入力 10 進数を基数変換します。 変換する非負の整数： 59 何進数に変換しますか (2-36 ）： 2 出力 2 進数では 111011 です。 入力 もう一度しますか（ 1--- はい /0--- いい え）： 0

33 まとめ 動的メモリ管理 配列の応用  整数の動的生成  配列要素の最大値を求める関数  配列要素の並びの反転  基数変換 33 予習： 次回は、多次元配列、構造体、配列によるリスト