程式迴圈的執行順序

請問各位高手大大~

我看到一個副程式如下:

void merge_sort(int *A, int left, int right)

{

int half;

if (left<right)

{

half=(left+right)/2;

merge_sort(A, left, half);----1

merge_sort(A, half+1, right);-----2

merge(A, left, A, left, half, A half+1, right);

}

}

我的問題是這樣子的,這個程式中,又2次呼叫了自己,

那麼執行時是怎麼跑得呢?ex: left=0, right=19

step1: half=(0+19)/2=10, 接下來又呼叫自己本身1,所以

step2. half=(0+10)/2=5 同上,

step3, half=(0+5)/2=3 同上

step4. half=(0+3)/2=2 同上

step5 half=(0+2)/2=1 同上

step6 half=(0+1)/2=1........??

那麼什麼時候才會跑到呼叫自己本身2??

而且若half=1結束,跑2的話, left會變為half+1=1+1=2,right一樣是19....是嗎??

對於像這樣連續引用自己本身的副程式令我很難理解,

請各位高手大大幫忙囉~3Q~

3 個解答

評分
  • 9 年前
    最佳解答

    >> if (left

    merge(A, 0, 10)

    2. half = 5 => merge(A, 0, 5)

    3. half = 2 => merge(A, 0, 2)

    4. half = 1 => merge(A, 0, 1)

    5. half = 0 => merge(A, 0, 0) ------> if 不成立, 結束了。

    2011-08-09 23:34:22 補充:

    ===

    再開始做 2 部份

    merge(A, 11, 19)...

    ===

    先仔細思考合併排序法整個流程步驟為佳。

    2011-08-12 19:59:41 補充:

    void merge_sort(int *A, int left, int right)

    {

    int half;

    if (left<right)

    {

    half=(left+right)/2;

    merge_sort(A, left, half);

    merge_sort(A, half+1, right);

    merge(A, left, A, left, half, A half+1, right);

    }

    }

    1. merge(A, 0, 10)

    2. half = 5 => merge(A, 0, 5)

    3. half = 2 => merge(A, 0, 2)

    4. half = 1 => merge(A, 0, 1)

    5. half = 0 => merge(A, 0, 0) ------> if 不成立, 結束了。

    再開始做 2 部份

    merge(A, 11, 19) .... (下略)

    先仔細思考合併排序法整個流程步驟為佳。

    2011-08-12 20:00:52 補充:

    補一下後來的問題

    >> ....(left+right) / 2

    答案只會是「整數」而已,不會是「小數 (浮點數) 」,

    這部份應在一般課本第 2 章,資料型態那裡會說明。

  • 9 年前

    sorry,因為主程式和merge的程式我沒有問題,所以沒打出來....

    Edison, 哆謝你的回覆啦, 因為不是很懂合併排序法實際執行的流程,所以想從程式執行的流程中去了解,卻卡住了.....

    所以依你的意思是:

    第一次跑到呼叫自己的程式時會一直跑到條件不成立才接下去跑到第二次呼叫自己的程式是吧...

    而且....(left+right)/2是取整數而不是四捨五入是吧?!

    這樣我有概念啦~3Q~

  • 9 年前

    妳的主程式與副程式merge 跑哪了?!

還有問題?馬上發問,尋求解答。