〇　<=　宣言を書く記号 〇整数型: i 【サブルーチン】 手続き：意味のあるまとまった処理の事 　　　　～をする処理　void関数（C++など） 　関数：手続きのうち、値を返すもの 　　　　戻り値型　関数名(引数リスト); int 関数名(){ return 値;} 　引数：手続き、関数に渡すパラメータの事　 〇副プログラム: makeHeap(整数型: data[],<= 配列 整数型: heap[],<= 配列 整数型: hnum)　<= 整数変数 data[] []が付いたら配列を扱っているよ ----------------------------------------------------------- /* 文 */　<=　コメント、プログラムの説明文 　　　　　　　実際の処理には影響しない（読み飛ばし） ----------------------------------------------------------- ← <= 代入 ・ sum ← 0 /* sumを0で初期化　*/ ----------------------------------------------------------- ・　<=　処理（代入文、式、手続き、関数の呼び出し） ・sum ← sum + i /* 代入＋式 左式を右式の結果で更新 */ ・ave ← average(data, k) /* 変数aveにaverageの戻り値を代入*/ ------------------------------------------------------------ ３つの基本構造 ☆順次 　・処理１ 　・処理２ 　・処理３ ☆選択 [ 二者択一（条件で、TRUE、FALSEの時の分岐）] ▲　条件式 ｜・trueの時の処理 ＋ーー ｜・falseの時の処理 ▼ 例） ▲　i < 5 ｜・sum ← sum + 1 ＋ーー ｜・sum ← sum + i ▼ [ 二者択一のうちTRUEの時だけ実行 ] ▲　i < 5 ｜・sum ← sum + 1 ＋ーー ｜・何もしない　<= 省略可能 ▼ 　　　　↓ ▲　条件式 ｜・trueの時の処理 ▼ ▲　条件式 ｜・trueの時の処理 ＋ーー ｜▲条件式 ｜｜・trueの時の処理 ｜＋ーー ｜｜・falseの時の処理 ｜▼ ▼ 　　　　↑ 　　　条件式の入れ子構造 ☆繰り返し ＊継続条件：真の間繰り返し ＊終了条件：真になったら終了 [ 前判定型 ] while(){} 継続判定してからループの処理を実行 ■ 継続条件 ｜・繰り返す処理 ■ [ 後判定型 ] do～while(); 実行してからループの継続を判定 ■ ｜・繰り返す処理 ■ 継続条件 /* これはどうなる？ */ 〇整数: i 〇整数: sum ・i ← 1 ・sum ← 0 ■ i < 10 /* 前判定継続条件 */ ｜・sum ← sum + i ｜・i ← i + 1 ■ 処理のトレース：重要 i | i<10 | sum | sum+i | sum' | ---+-------+-----+-------+------+ 1 | true | 0 | 0 + 1 | 1 | ---+-------+-----+-------+------+ 2 | true | 1 | 1 + 2 | 3 | ---+-------+-----+-------+------+ 3 | true | 3 | 3 + 3 | 6 | ---+-------+-----+-------+------+ 4 | true | 6 | 6 + 4 | 10 | ---+-------+-----+-------+------+ 5 | true | 10 |10 + 5 | 15 | ---+-------+-----+-------+------+ 6 | true | 15 |15 + 6 | 21 | ---+-------+-----+-------+------+ 7 | true | 21 |21 + 7 | 28 | ---+-------+-----+-------+------+ 8 | true | 28 |28 + 8 | 36 | ---+-------+-----+-------+------+ 9 | true | 36 |36 + 9 | 45 | ---+-------+-----+-------+------+ 10 | false | -- |------ | -- | ---+-------+-----+-------+------+ [ カウンタ型ループ ] for(int i=0; i < 5; i=i+1) { ごにょごにょ; } ■ カウンタ変数: 初期値, 条件式, 増分 ｜・繰り返す処理 ■ 例） ■ i: 0, i<10, 1 ｜・sum ← sum + i ■ 真偽値 true, false びっくりしないように注意点 ☆突然、暗黙のルールみたいなのが現れる ・ave ← average(data, k) /* 変数aveにaverageの戻り値を代入*/ ■ i: 0, i<10, 1 ｜・sum ← sum + i ｜▲ i=5 ｜｜・break /* こんな仕様どこにもかいてないよ。。。 */ ｜▼ ■ ☆アルゴリズム＝疑似言語が出てきたら、条件式を見る！ ☆非カウンタ型ループの時は、条件を更新する式をよく見る 　条件式の更新式が穴になっていることが（とても）多い 〇副プログラム　Sort(整数:A[], 整数:N) 〇void swap(整数:X, 整数:Y) /* 配列中のXとYの要素を交換する操作 */ 〇整数: N /* 配列の要素数 */ 〇整数: A /* 配列(添え字は0～(N-1)) */ 〇整数: minj, i, j ■ i: 0, i < N, 1 ｜・minj ← i ｜■　j: i+1, j < N-1, 1 ｜｜▲ A[j] < A[minj] <-最小の値のインデックスを更新 ｜｜｜・minj ← j ｜｜▼ ｜■ ｜・swap(A[i], A[minj]) ■ for(iのループ) { for(jのループ) { } swap() } トレース 0 1 2 3 4 5 6 7 A[] 6 1 7 5 2 3 4 8 i=0, j=1(i+1) minj=1 swap(A[0], A[1]) 0 1 2 3 4 5 6 7 A[] 1 6 7 5 2 3 4 8 i=1, j=2(i+1) minj=1 swap(A[1],A[4]) 0 | 1 2 3 4 5 6 7 A[] 1 | 2 7 5 6 3 4 8 i=2, j=3(i+1) minj=2 swap(A[2],A[5)) 0 1 |2 3 4 5 6 7 A[] 1 2 |3 5 6 7 4 8 i=3, j=4(i+1) minj=3 swap(A[3],A[6]) 0 1 2 |3 4 5 6 7 A[] 1 2 3 |4 6 7 5 8 i=4, j=5(i+1) minj=4 swap(A[4],A[6]) 0 1 2 3 |4 5 6 7 A[] 1 2 3 4 |5 7 6 8 i=5, j=6(i+1) minj=5 swap(A[5],A[6]) 0 1 2 3 4 |5 6 7 A[] 1 2 3 4 5 |6 7 8 i=6, j=7(i+1) minj=6 0 1 2 3 4 5 |6 7 A[] 1 2 3 4 5 6 |7 8 i=7, j=8(i+1) minj=7 スルー 0 1 2 3 4 5 6 |7 A[] 1 2 3 4 5 6 7 |8 基本情報技術者過去問題 平成22年春期 午後問8 データ数 num個 num = 4の時 整数: list[num] {3, 5, 2, 1} Sort(list[]) => list[num]{1, 2, 3, 5} num1 = num÷２ num2 = num - (num÷2) = num - num1 Sort(list[]) {3,5 ,2,1} num = 4, num1 = 2, num = 4-2=2 slist1[num1] slist2[num2] {3,5} num=2 {2, 1} num=2 Sort(slist1[]) Sort(slist2[]) slist1[] slist2[] slist1[] slist2[] {3} num=1 {5} {2} {1} Sort(slist1[1]) 終了　　終了　　　終了 Merge(slist1, slist2, list) Merge(slist1, slist2, list) list[]={{3},{5}} list[]={{1},{2}} =>slist1 =>slist2 Merge(slist1, slist2, list) list{1, 2, 3, 5} list[7] 0 1 2 | 3 4 5 6 [5][7][4]|[2][3][8][1] slist1[3] 0 1 2 3 [5][7][4][2] slist1[0] = list[0] slist1[1] = list[1] slist1[2] = list[2] num=7 num1 = 7/2 = 3 num2 = num - num/2 = 4 0～num2=4 slist2[4] 0 1 2 3 [2][3][8][1] slist2[0] = list[3] = list[num1 + 0]= list[3+0] slist2[1] = list[4] = list[num1 + 1]= list[3+1] slist2[2] = list[5] = list[num1 + 2]= list[3+2] slist2[3] = list[6] = list[num1 + 3]= list[3+3] num=3 num1 = 3/2 = 1 num2 = 3-1 = 2 b=ウ num = 1になったら終わる num > 1 Merge slist1[] num1個 i 配列0～(num1-1) i < num1 slist2[] num2個 j j < num2 list[] num1+num2個 i+j 継続条件：i,jどっちも配列の個数内である (i < num1) and (j < num2) ↑どっちかの配列がなくなるまで slist1[]{1,3} slist2{2, 4, 5, 6} i = 2(i