python 귀속 연습

1. 한노타 문제:

 ：
f(n)=f(n-1)+1+f(n-1)
n ：2^n-1 

def func(n,fromm,to,help):
    if n==1:
        print("move"+" "+str(1)+" "+"from"+" "+fromm+" "+"to"+" "+to)#base case
    else:
        func(n-1,fromm,help,to)    # n-1 fromm help
        print("move"+" "+str(n)+" "+"from"+" "+fromm+" "+"to"+" "+to) # n 
        func(n-1,help,to,fromm)    # n-1 help 
func(3,"left","right","mid")

2. 인쇄 문자열의 하위 시퀀스: (순서가 같고 연속되지 않을 수 있음)

def func(arr,i,pre):
    if (i==len(arr)):
        if pre!="":
            print(pre)
        return
    func(arr,i+1,pre+arr[i])
    func(arr,i+1,pre)
arr="abc"
arr="".join(arr)
func(arr,0,"")

3. 인쇄 문자열의 전체 배열: (리셋) 사상: i위치는 (i, n-1) 위치의 모든 문자를 한 번 시도(각 위치와 교환), 위치 이후의 무작위 배열

def printAllPermutation(arr,i):
    if i==len(arr):
        print((''.join(arr)))
    m=[]  # 
    for j in range(i,len(arr)):
        if arr[j] not in m:  # 
            m.append(arr[j]) # 
            arr[i],arr[j]=arr[j],arr[i]
            printAllPermutation(arr,i+1)
            arr[i], arr[j] = arr[j], arr[i]

arr1=list("abc")
arr2=list("acc")
printAllPermutation(arr1,0)
print("----------")
printAllPermutation(arr2,0)

4. 문제: 암소 한 마리가 있는데 1년에 암소 한 마리를 낳고 새 암소는 3년 후에 1년에 암소 한 마리를 낳고 암소는 6년 후에 죽는다. N년 후에 암소가 몇 마리 있습니까?사고방식: f(n)=f(n-1)+f(n-3)-2*f(n-6)#6년 전 암소 개수와 아이 개수를 빼고 2코드를 곱하기:

def count(n):
    if n<1:
        return 0
    if n<=3:
        return n
    if n<6:
        return  count(n-1)+count(n-3)
    return count(n-1)+count(n-3)-2*count(n-6)
print(count(7))

5, 역순 한 창고 (추가 공간을 차지하지 않음)

def getandremovelastElement(stack): # 
    result=stack.pop()
    if not stack:
        return result
    else:
        last=getandremovelastElement(stack)
        stack.append(result)
        return last
def reverse(stack):   
    if not stack:
        return
    i=getandremovelastElement(stack)
    reverse(stack)
    stack.append(i)
s=[3,2,1]
reverse(s)
print(s)