天天看點

資料結構實踐——猴子選大王(數組版)

  一群猴子,編号是1,2,3 …m,這群猴子(m個)按照1-m的順序圍坐一圈。從第1隻開始數,每數到第n個,該猴子就要離開此圈,這樣依次下來,最後一隻出圈的猴子為大王。輸入m和n,輸出猴子離開圈子的順序,從中也可以看出最後為大王是幾号猴子。

  要求采用數組作為存儲結構完成。

  在一個數組中,數組中用1表示猴子在圈中,用0表示猴子已經出圈,數組下标對應與猴子編号對應(例如數組元素p[0]值為1,表示第1隻猴子尚在圈中,即p[i]代表編号為i+1的猴子是否在圈中)。

  一隻猴子出圈,則将對應的數組值置為0;在報數過程中,要跨過值為0的猴子。

  若m=8, n=4,初始時數組如下:

資料結構實踐——猴子選大王(數組版)

  其中有3隻猴子出圈後,數組中的值如下:

資料結構實踐——猴子選大王(數組版)

  數到最後一隻猴子時需要折回到下标為0的位置,猴子出圈後,還将對應元素的值置為0。見代碼注釋。

  數組同參考解答1。在報數過程中,不再判斷為0為1,而是設定一個用于累加的變量,猴子在圈時加1相當于報數,出圈後是加0相當于沒有報數。

  用數組元素儲存猴子的編号,一隻猴子出圈,執行從數組中删除元素的操作,以此重複。

資料結構實踐——猴子選大王(數組版)
資料結構實踐——猴子選大王(數組版)

  數到最後一隻猴子時需要折回到下标為0的位置,猴子出圈後,還還要實施删除數組中元素(即将後面的資料前移)的工作。見代碼注釋。

繼續閱讀