から




専門/H15/06

正解 Edit

4

検証 Edit

a[0] = 0,
a[i] = i+2 (1 ≦ i ≦ n-2),
a[n-1] = 1, a[n] = 2
i=2;
while(i <= n) {
	v = a[i]; j = i;
	while(a[j-1] > v) {
		a[j] = a[j-1];
		j=j-1;
	}
	a[j] = v;i = i+1;
}
  • どの式でも正となるn=3で検証する。
    i=2;
    while(i <= n) { // 2<=3 で 真
    	v = a[i]; j = i; // v = a[2] = 1; j = i = 2; 
    	while(a[j-1] > v) { // a[2-1] > v, 3 > 1 で真
    		a[j] = a[j-1]; // a[2] = a[2-1] = 3 // 1回
    		j=j-1; // j=2-1 = 1
    • while(a[j-1] > v) 2週目
      	while(a[j-1] > v) { // a[1-1] > 1 , 2 > 1 で真
      		a[j] = a[j-1]; a[1] = a[1-1] = 2 // 2回
      		j=j-1; // j = 1-1 = 0
    • while(a[j-1] > v) 3週目
      	while(a[j-1] > v) { // a[0-1] > 1 , 値なし > 1 で偽
      	}
      	a[j] = v;i = i+1; a[0] = 1;i = 2+1 = 3
  • while(i <= n) 2週目
    while(i <= n) { // 2 <= 3 で真
    	v = a[i]; j = i; / v = a[2] = 3; j = 2
    • while(a[j-1] > v) 3週目
      	while(a[j-1] > v) { a[2-1] > 3, 2 > 3で偽
      	}
      	a[j] = v;i = i+1; // a[2] = 3; i=3+1 = 4
  • while(i <= n) 3週目
    while(i <= n) { // 4 <= 3 で偽
    }

n=3で実行回数2

  1. 2n-1 = 2*3-1 = 5
  2. 2n-2 = 2*3-2 = 4
  3. 2n-3 = 2*3-3 = 3
  4. 2n-4 = 2*3-4 = 2
  5. n*(n-1)/2 = 3*(3-1)/2 = 3

Tag: C言語の実行結果



トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 下位頁新規  一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-22 Mon 23:18:33 JST (3193d)