WHAT
- 介紹Python數(shù)據(jù)結(jié)構(gòu)與算法第三方庫 可用作學(xué)習(xí)也可用于直接使用算法
- 介紹pysnooper--man's debugger
algorithms
-
根據(jù)目錄學(xué)習(xí)
{075C5F19-7EAA-4CB0-B5A5-F115464FD08E}_20190827160419.jpg - 舉例學(xué)習(xí) josephus問題
算法源代碼
josephus問題相關(guān)著名的Josephus問題
"""
介紹算法解決的是什么問題
There are people sitting in a circular fashion,
print every third member while removing them,
the next counter starts immediately after the member is removed.
Print till all the members are exhausted.
For example:
Input: consider 123456789 members sitting in a circular fashion,
Output: 369485271
"""
# 具體算法
def josephus(int_list, skip):
skip = skip - 1 # list starts with 0 index
idx = 0
len_list = (len(int_list))
while len_list > 0:
idx = (skip + idx) % len_list # hash index to every 3rd
yield int_list.pop(idx)
len_list -= 1
pysooper Python運行記錄利器
- 有時候我們看到了解決思路 但是不知道具體怎么運行的 或者想不通的時候
https://github.com/cool-RR/PySnooper
import pysnooper
# 跟蹤日志記錄
@pysnooper.snoop()
def josephus(int_list, skip):
skip = skip - 1 # list starts with 0 index
idx = 0
len_list = (len(int_list))
res = []
while len_list > 0:
idx = (skip + idx) % len_list # hash index to every 3rd
res.append(int_list.pop(idx))
len_list -= 1
return res
josephus([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)
- 輸出日志
- 是否現(xiàn)在更清楚知道解決思路?
Source path:... C:/Users/74109/Desktop/MxShop-master/l.py
Starting var:.. int_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Starting var:.. skip = 3
15:52:54.569968 call 10 def josephus(int_list, skip):
15:52:54.569968 line 11 skip = skip - 1 # list starts with 0 index
Modified var:.. skip = 2
15:52:54.569968 line 12 idx = 0
New var:....... idx = 0
15:52:54.569968 line 13 len_list = (len(int_list))
New var:....... len_list = 9
15:52:54.569968 line 14 res = []
New var:....... res = []
15:52:54.569968 line 15 while len_list > 0:
15:52:54.569968 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 2
15:52:54.569968 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 4, 5, 6, 7, 8, 9]
Modified var:.. res = [3]
15:52:54.569968 line 18 len_list -= 1
Modified var:.. len_list = 8
15:52:54.569968 line 15 while len_list > 0:
15:52:54.569968 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 4
15:52:54.569968 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 4, 5, 7, 8, 9]
Modified var:.. res = [3, 6]
15:52:54.569968 line 18 len_list -= 1
Modified var:.. len_list = 7
15:52:54.569968 line 15 while len_list > 0:
15:52:54.569968 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 6
15:52:54.569968 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 4, 5, 7, 8]
Modified var:.. res = [3, 6, 9]
15:52:54.569968 line 18 len_list -= 1
Modified var:.. len_list = 6
15:52:54.569968 line 15 while len_list > 0:
15:52:54.569968 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 2
15:52:54.569968 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 5, 7, 8]
Modified var:.. res = [3, 6, 9, 4]
15:52:54.569968 line 18 len_list -= 1
Modified var:.. len_list = 5
15:52:54.570964 line 15 while len_list > 0:
15:52:54.570964 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 4
15:52:54.570964 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 5, 7]
Modified var:.. res = [3, 6, 9, 4, 8]
15:52:54.570964 line 18 len_list -= 1
Modified var:.. len_list = 4
15:52:54.570964 line 15 while len_list > 0:
15:52:54.570964 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 2
15:52:54.570964 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 2, 7]
Modified var:.. res = [3, 6, 9, 4, 8, 5]
15:52:54.570964 line 18 len_list -= 1
Modified var:.. len_list = 3
15:52:54.570964 line 15 while len_list > 0:
15:52:54.570964 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 1
15:52:54.570964 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1, 7]
Modified var:.. res = [3, 6, 9, 4, 8, 5, 2]
15:52:54.570964 line 18 len_list -= 1
Modified var:.. len_list = 2
15:52:54.570964 line 15 while len_list > 0:
15:52:54.570964 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
15:52:54.570964 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = [1]
Modified var:.. res = [3, 6, 9, 4, 8, 5, 2, 7]
15:52:54.570964 line 18 len_list -= 1
Modified var:.. len_list = 1
15:52:54.570964 line 15 while len_list > 0:
15:52:54.570964 line 16 idx = (skip + idx) % len_list # hash index to every 3rd
Modified var:.. idx = 0
15:52:54.570964 line 17 res.append(int_list.pop(idx))
Modified var:.. int_list = []
Modified var:.. res = [3, 6, 9, 4, 8, 5, 2, 7, 1]
15:52:54.570964 line 18 len_list -= 1
Modified var:.. len_list = 0
15:52:54.572959 line 15 while len_list > 0:
15:52:54.572959 line 19 return res
15:52:54.572959 return 19 return res
Return value:.. [3, 6, 9, 4, 8, 5, 2, 7, 1]
