python 遞歸和二分法

一 內置函數

　　1. revserd 翻轉,返回的是迭代器

# 將 s 倒置
s = '不是上海自來水來自海上'
# 方法一
print(s[::-1])
# 方法二
s1 = reversed(s)
i = ''
for el in s1:
　　i +=el
　　print(i)

　　2.slice 切片

lis = ['nishi','woshi','shuia','benjim']
s = slice(1,3)
print(lis[s])

　　3.formate

# 格式化輸出
s = "我叫{name},我想去{adress},我喜歡{hobby}.".format(name='zhangmeng',adress='上海',hobby='dance')
print(s)


# 字元串
print(format('test', '<20')) # 左對齊
print(format('test', '>20')) # 右對齊
print(format('test', '^20')) # 居中
# 數值
print(format(3, 'b')) # 二進位
print(format(97, 'c')) # 轉換成unicode字元
print(format(11, 'd')) # 十進位
print(format(11, 'o')) # 八進位
print(format(11, 'x')) # 十六進位(小寫字母)
print(format(11, 'X')) # 十六進位(大寫字母)
print(format(11, 'n')) # 和d一樣
print(format(11)) # 和d一樣
# 浮點數
print(format(123456789, 'e')) # 科學計數法. 預設保留6位小數
print(format(123456789, '0.2e')) # 科學計數法. 保留2位小數(小寫)
print(format(123456789, '0.2E')) # 科學計數法. 保留2位小數(大寫)
print(format(1.23456789, 'f')) # 小數點計數法. 保留6位小數
print(format(1.23456789, '0.2f')) # 小數點計數法. 保留2位小數
print(format(1.23456789, '0.10f')) # 小數點計數法. 保留10位小數
print(format(1.23456789e+10000, 'F')) # 小數點計數法.

　　4. type（） 返回類型    ord()  輸入字元找字元編碼的位置     chr()  輸入位置找出對應的字元    ascii()判斷給出的信息是否是ascii 

for i in range(65536):
    print(chr(i), end="")

二. 遞歸

　　函數自己調用自己,遞歸的入口(參數)  和 出口(return)

語法:

def func():
    print('我是遞歸')
    func()

func() # 官方顯示最多到1000.但不會跑到1000，實際到998

# 樹形結構的遍歷

import os
def func(lujing, n):
    lis = os.listdir(lujing) # 打開文件夾，列出文件夾內的所有文件名
    for el in lis: # el 為文件的名字
    # 還原文件路徑
    path = os.path.join(lujing,el)
    if os.path.isdir(path):# 判斷路徑是否是文件夾
        print('*' * n,el) # 顯示文件夾的名字
        func(path, n+1) # 再來一次
    else:
        print('/t'*n,el) # 顯示文件

func('f:/a', 0)

import os
def func(lujing, n):
    lis = os.listdir(lujing ) # 打開文件夾，列出文件夾內的所有文件名
    for el in lis: # el為文件名
# 還原文件的路徑
    path = os.path.join(lujing, el)
    if os.path.isdir(path): # 判斷路徑是否是文件夾
        print('*'* n, el) # 顯示文件夾名稱
        func(path, n+1) # 再來一次
    else:
        with open(path,mode='wb') as f: # 打開文件，都寫入內容
            f.write(b'123456')
              print('/t'*n, el) # 顯示文件
func('F:/a',0)

三. 二分法

# 二分法查找
lst = [1,4,6,7,9,21,23,45,67,87,65,43,89]
n = int(input('請輸入一個數：'))
lst = sorted(lst)
# print(lst)
left = 0
right = len(lst)-1
while left <= right:
    mid = (left + right)//2
    if n > lst[mid]:
        left = mid+1
    elif n < lst[mid]:
        right = mid -1
     else:
        print("存在")
        break
else:
print('不存在')

# 遞歸 切割列表

def func(n,lst):
    left = 0
    right = len(lst)-1
    if lst != []:
        mid = (left+right)//2
         if n>lst[mid]:
            func(n,lst[mid+1:])
        elif n < lst[mid]:
            func(n,lst[:mid])
        else:
            print("找到了")
            return
    else:
        print("沒找到")
        return

n = int(input('請輸入你要查找的數：'))
lst = [1,4,6,7,9,21,23,45,67,87,65,43,89]


func(n,lst)

# 遞歸2
def func(n,lst,left,right): # 遞歸找到什麼是可變的，什麼是不可變的
    if left <= right:
        mid = (left+right)//2
            if n > lst[mid]:
                left = mid+1
                return func(n,lst,left,right)
            elif n < lst[mid]:
                right = mid - 1
                return func(n, lst, left, right)
            else:
                print('找到了')
                return mid # 難點
    else:
        print('找不到')
        return -1

n = int(input('請輸入你要查找的數：'))
lst = [13,45,56,67,78,57,89,101]
ret = func(n,lst,0,len(lst)-1)
print(ret)

# 最快的查找方法

lst = [13,45,56,57,67,78,89,101]

# 找出最大的數
new_lst = []
for i in range(99):
    new_lst.append(0)

for i in lst:
    new_lst[i] = 1

i = int(input('請輸入你要找的數據：'))
if new_lst[i] == 0:
    print('不存在')
else:
    print('存在')