递归算法与项目实战 学习记录

# This is a sample Python script.
import sys

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.

# def to_str(n, base):
#     convert_string = "0123456789ABCDEF"
#     if n < base:
#         return convert_string[n]
#     else:
#         return to_str(n//base, base) + convert_string[n % base]

# frthonds3.basic import Sta
# import turtle
#
# def draw_spiral(my_tutle, line_len):
#     if line_len > 0:
#         my_tutle.forward(line_len)
#         my_tutle.right(90)
#         draw_spiral(my_tutle, line_len-50)
#
#
# my_turtle = turtle.Turtle()
# my_win = turtle.Screen()
# draw_spiral(my_turtle, 100)
# my_win.exitonclick()

# 用递归调用实现指数函数
# def exponentByIteration(a, n):
#     result = 1
#     for i in range(n):
#         result *= a
#     return result
#
# print(exponentByIteration(3, 6))

# def exponentByRecursion(a, n):
#     if n == 1:
#         return a
#     elif n % 2 == 0:
#         result = exponentByRecursion(a, n // 2)
#         return result * result
#     elif n % 2 == 1:
#         result = exponentByRecursion(a, n // 2)
#         return result * result * a
#
# print(exponentByRecursion(3, 6))
# 解释了用递归调用比用迭代调用性能高的多


# 每个递归算法都可以转换成等效的迭代算法，根据递归算法提供的思路，实现另一种迭代式的指数计算函数
# 本质上将需要计算的一系列操作存到了列表中
# def exponentWithPowerRule(a, n):
#     # 第一步判断需要执行的是什么运算
#     opStack = []
#     while n>1:
#         if n % 2 == 0:
#             opStack.append("square")
#             n = n//2
#         elif n % 2 == 1:
#             n -= 1
#             opStack.append("multiply")
#     # 第二步， 按照逆序依次执行这些计算
#     result = a
#     while opStack:
#         op = opStack.pop()
#
#         if op == "multiply":
#             result *= a
#         elif op == "square":
#             result *= result
#     return result
# print(exponentWithPowerRule(3, 6))

# 2023/12/19 递归法实现反转字符串
# def rev(theString):
#     if len(theString) == 0 or len(theString)==1:
#         # 基本情况
#         return theString
#     else:
#         head = theString[0]
#         tail = theString[1:]
#         return rev(tail) + head
# print(rev("dc_lover"))

# 递归法 判断回文字符串
# def isPalindrome(theString):
#     if len(theString) == 0 or len(theString) == 1:
#         return True
#     else:
#         head = theString[0]
#         middle = theString[1:-1]
#         last = theString[-1]
#         return head == last and isPalindrome(middle)
# print(isPalindrome("dc_loverrevol_cd"))
# print(isPalindrome("zophie"))

# 树的前序遍历
# root = {'data':'A', 'children': [{'data':'B', 'children':
# [{'data':'D','children':[]}]}, {'data':'C', 'children':
# [{'data':'E','children':[{'data':'G','children':[]},
# {'data':'H','children':[]}]}, {'data':'F','children':[]}]}] }
#
# def preorderTraverse(node):
#     print(node['data'], end='')
#     if len(node['children']) > 0:
#         for child in node['children']:
#             preorderTraverse(child)
#         return
# preorderTraverse(root)
# 前序遍历和创建这颗树的顺序好像一样

# 树的后序遍历
# root = {'data':'A', 'children': [{'data':'B', 'children':
# [{'data':'D','children':[]}]}, {'data':'C', 'children':
# [{'data':'E','children':[{'data':'G', 'children':[]},
# {'data':'H','children':[]}]}, {'data':'F', 'children':[]}]}]}
#
# def postorderTraverse(node):
#     for child in node['children']:
#         postorderTraverse(child)
#     print(node['data'], end='')
#     return
# postorderTraverse(root)

# root = {'name': 'Alice', 'children': [{'name': 'Bob', 'children':
# [{'name': 'Darya', 'children': []}]}, {'name': 'Caroline',
# 'children': [{'name': 'Eve', 'children':[{'name':'Gonzalo',
# 'children':[]}, {'name':'Hadassah', 'children':[]}]}, {'name':'Fred','children':[]}]}]}
#
# def find8LetterName(node):
#     print('Visiting node' + node['name'] + '...')
#
#     print("checking if " + node['name'] + ' is 8 letters...')
#     # 这里是基本情况
#     if len(node['name']) == 8:
#         return node['name']
#
#     # 该条判断语句的作用是 判定当前节点存在子树
#     if len(node['children']) > 0:
#          for child in node['children']:
#              returnValue = find8LetterName(child)
#              if returnValue != None:
#                  return returnValue
#
#     return None
#
# print(str(find8LetterName(root)))

# root = {'data':'A', 'children': [{'data':'B', 'children':
# [{'data':'D','children':[]}]}, {'data':'C', 'children':
# [{'data':'E','children':[{'data':'G','children':[]},
# {'data':'H','children':[]}]}, {'data':'F','children':[]}]}] }
#
#
# def getDepth(node):
#     if len(node['children']) == 0:
#         return 0
#     else:
#         maxChildDepth = 0
#         for child in node['children']:
#             childDepth = getDepth(child)
#             if childDepth > maxChildDepth:
#                 maxChildDepth = childDepth
#         return maxChildDepth + 1
#
# print(getDepth(root))

# 递归算法实现二分
# def binarySearch(needle, haystack, left=None, right=None):
#     if left is None:
#         left = 0
#     if right is None:
#         right = len(haystack)-1
#
#     if left > right:
#         return None
#     mid = (left+right)//2
#     if needle == haystack[mid]:
#         return mid
#     elif needle < haystack[mid]:
#         return binarySearch(needle, haystack, left, mid-1)
#     elif needle > haystack[mid]:
#         return binarySearch(needle, haystack, mid+1, right)
#
# print(binarySearch(13, [1,4,8,11,13,16,19,19]))

# 快速排序
# def quicksort(items, left=None, right=None):
#     if left is None:
#         left = 0
#     if right is None:
#         right = len(items)-1
#
#     if right <= left:
#         return
#
#     i = left
#     pivotValue = items[right]
#
#     for j in range(left, right):
#         if items[j] <= pivotValue:
#             items[i], items[j] = items[j], items[i]
#             i += 1
#
#     items[i], items[right] = items[right], items[i]
#
#     quicksort(items, left, i-1)
#     quicksort(items, i+1, right)
#
#
# myList = [0, 7, 6, 3, 1, 2, 5, 4]
# quicksort(myList)
# print(myList)

# 递归的获取全排列
def getPerms(chars, indent=0):
    # print('.' * indent + 'Start of getPerms ("' + chars + '")')
    if len(chars) == 1:
        # print('.' * indent + 'When chars = "'+ chars + '" base case returns', chars)
        return [chars]

    permutations = []
    head = chars[0]
    tail = chars[1:]
    tailPermutations = getPerms(tail, indent+1)

    for tailPerm in tailPermutations:
        for i in range(len(tailPerm)+1):
            newPerm = tailPerm[0:i] + head + tailPerm[i:]
            # print('.'*indent + 'New permutation:', newPerm)
            permutations.append(newPerm)

    return permutations

print(getPerms('ABCD'))