UVa120 煎餅(選擇排序思想)

2021 年 8 月 29 日
筆記
Python, 數據結構, 演算法, 紫書

題目背景

給你一迭薄煎餅，請你寫一個程式來指出要如何安排才能使這些薄煎餅由上到下依薄煎餅的半徑由小到大排好。所有的薄煎餅半徑均不相同。

要把薄煎餅排好序需要對這些薄煎餅做翻面（flip）的動作。方法是以一抹刀插入一迭薄煎餅中，然後做翻面的動作（也就是說在抹刀上面的薄煎餅經翻面後，會依相反的次序排列）。若一迭共有n個薄煎餅，我們定義最底下的薄煎餅的位置為1，最上面的薄煎餅位置為n。當抹刀插入位置為k時，代表從位置k到位置n的薄煎餅要做翻面的動作。

一開始時，這迭薄煎餅隨意堆放，並以半徑大小來表示。例如：以下3迭薄煎餅（最左邊那一迭8是最上面一個薄煎餅的半徑）

 8           7           2
 4           6           5
 6           4           8
 7           8           4
 5           5           6
 2           2           7

對最左邊那迭薄煎餅，如果我們把抹刀插在位置3（就是半徑為7的那塊薄煎餅的下面）的地方做翻面，就會得到中間那迭，如果我們再把抹刀插在位置1（就是半徑為2的那塊薄煎餅的下面）的地方做翻面，就會得到最右邊那迭。

Input

每組測試資料一行，內容為這一迭薄煎餅一開始的狀態。每列開始的整數（介於1到100之間）代表位於最上方薄煎餅的半徑，依此類推。薄煎餅的數目介於1到30之間。請參考輸入樣例。

Output

對每一組測試資料輸出2列。第一列為原來那迭薄煎餅。第2列則為要使這迭薄煎餅由小到大排列所做的翻面的動作。數字代表抹刀所插入的位置。（0代表已完成）。如果已經排好了，則不需再有翻面的動作。請參考輸出樣例。

輸入輸出樣例

輸入

1 2 3 4 5
5 4 3 2 1
5 1 2 3 4

輸出

題解

如果我們設題目輸入數組為\(A\)，長度為\(n\)。那麼我們需要注意的一點是，\(A[0]\)對應一疊煎餅的頂端，\(A[n-1]\)對應一疊煎餅的底部。如下圖所示：

故要想將數組倒數第\(i\)個位置及其之前的元素(即\(A[0:n-i]\))翻轉，我們輸出的抹刀插入位置為\(i\)。
採用選擇排序的思想，按從大到小的順序依次把元素移動到正確位置，一共\(n\)輪，其中第\(i\)輪(\(i=1,2,…,n\))排序把數組\(A[0:n-i]\)中最大的元素移動到下標\(n-i\)處(如果本身就在下標\(n-i\)處則跳過)。
不過這裡我們只能翻轉一個序列，故我們需要用到一個技巧，就是分兩步走：
① 先將\(A[0:n-i]\)中最大的元素「翻」到最左端的下標\(0\)處(如果本身就在下標\(0\)處則跳過)。
② 然後再將它「翻」到正確位置即下標\(n-i\)處。
設數組\(A[0:n-i]\)中數組最大元素的下標為\(maxs\)，前者需要將\(A[0:maxs]\)(即倒數第\(n – maxs\)個位置及其之前的元素)翻轉，此時輸出的抹刀插入位置應為\(n-maxs\)；後者需要將\(A[0:n-i]\)(即倒數第\(i\)個位置及其之前的元素翻轉，此時輸出的抹刀插入位置應為\(i\)。
根據以上的分析，我們的演算法如下：

'''
Descripttion: 選擇排序思想
Version: 1.0
Author: ZhangHongYu
Date: 2021-08-12 15:54:27
LastEditors: ZhangHongYu
LastEditTime: 2021-08-28 22:01:07
'''
while True:
    try:
        A = list(map(int, input().strip().split()))
        t = A.copy()
        res = []
        n = len(A)
        # 排序趟數
        for i in range(1, n+1):

            # 獲取A[0:n-i]中最大元素的下標
            max_v = max(A[: n - i + 1])
            maxs = A[: n - i + 1].index(max_v)

            # 如果最大元素還未翻到下標n-i處
            if maxs != n - i:
                # 如果最大元素還未翻到下標0處
                if maxs != 0:

                    # 將A[0:maxs]翻轉
                    A[: maxs + 1] = list(reversed(A[: maxs + 1]))
                    # 此時抹刀插入位置應為 n - maxs
                    res.append(n - maxs)  # 
                
                # 將A[0:n-i]翻轉
                A[: n - i + 1] = list(reversed(A[: n - i + 1]))
                # 此時抹刀插入位置應為i
                res.append(i)

        res.append(0)
        print(" ".join(map(str, t)))
        print(" ".join(map(str, res)))
    except EOFError:
        break

Tags: Python 數據結構演算法紫書