給定一個不同整數的串列（遞減順序），如果至少存在位置 p，則回傳 True，使得位置 p 處的值是 p。例如，List = [4, 3, 2, 0]，該函式回傳 true，因為 2 在索引 2 處。
我知道我們可以回圈并檢查 list[i] == i。
我想知道這是否以及如何使用分治演算法來實作？
我的基本情況是：
- L 為空，回傳 False。
- 如果 L[0] 為負，則回傳 False。由于串列是按降序排列的，所有值都是負數，所有索引都是正數。所以我們不會得到匹配。為簡單起見，我只考慮正指數。
我有點困惑如何在這里劃分串列。由于將串列拆分為 2，因此每個串列都有索引 [0:n/2]。所以比較值和索引沒有意義。
感謝一些幫助！
uj5u.com熱心網友回復：
您只需將串列的開始值和結束值與串列索引中的值進行比較，看看是否可行。
代碼
def divide_conqueer(lst, indexes = None):
if indexes is None:
indexes = list(range(len(lst))) # create list index
if not lst:
return False
elif len(lst) == 1:
return lst[0] == indexes[0]
elif lst[0] < indexes[0] or lst[-1] > indexes[-1]:
# Compare values of beginning and end of the list to the
# list indexes of the beginnning and end
# There is a matching value to index only if beginning value >= starting index and
# ending value <= ending index
return False
else:
# Divide values and intervals in half and test each half
return (divide_conqueer(lst[:len(lst)//2], indexes[:len(indexes)//2]) or
divide_conqueer(lst[len(lst)//2:], indexes[len(indexes)//2:]))
測驗
print(divide_conqueer([4, 3, 2, 1]))
# Output: True
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/490575.html
上一篇：字典是如何在這里實作的？