〇　<=　宣言を書く記号
〇整数型: 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<num1に引っかかる）  j = 1 < num2=4
list[]{1, 2, 3, 4, 5, 6}


list[] num=6 num1=3, num2=3
3，8，2，7，5，1
| 3 8 2 | 7 5 1 | sort

| 3 | 8 2 | sort
     
    | 8 | 2 |sort
    
     | 2 8 | <-

 | 2 3 8 |<-   

         | 7 | 5 1 |sort
             
             | 5 | 1 |sort
             
              | 1  5 |<-
          
            | 1 5 7 |<-
  
   | 1 2 3 5 7 8 |<-