数据结构处算法python--第四章课后练习题

#4.1
# 时间复杂度和空间复杂度都是O(n)
# def search_bigvalue(s,n):
#     if n==1:
# #这其实就是m的值，s[n-1]是上一个值，当每一次调用函数一直被悬挂，直到最后n==1,说明其中只有一个元素
# # 就返回这个值，然后s[n-1] if s[n-1]>m else m在这里进行比较，返回大的，又回到上一级的函数
# # 进行比较，直至比完所有元素。
#         return s[0]
#     m=search_bigvalue(s,n-1) #这里是n-1还是n,下面那个函数的index,减不减1取决于
# #它的值是多少，这里n最小是1，所以减一，就可以取到第一个值，下面那个默认是0，本身
# #就会取到第一个值。
#     print(s[n - 1],'sdf')
#     # print(m,'lsdmmmmmm')
#     return s[n-1] if s[n-1]>m else m
# seq=[10,2,4,5,4,3,6,7,3]
# n=len(seq)
# print(search_bigvalue(seq,n))

# def findmax(s,index=0):
#     if index==len(s)-1:
#         return s[index]
# #函数下来之后，一直在这里循环，直至长度为1，减1为0就返回s[index],这里递归调用完结了
# #，但只有最后一个函数返回了，其他的还没有，这时执行下面的if语句，跟函数每一次的返回值比较
#     print(index)
#     m=findmax(s,index+1)
#     print(index)  #两个打印的数值顺序正好是相反的，上面的是升序，下面的是降序
# #因为是上面的递归调用完了之后，到了最后一层，下面的再依次往上比
# #m是最后一个值
#     if m>s[index]:
#         return m
#     return s[index]
# print(findmax([10,1,2,4,5,4,3,6,7,3]))

#4.2
# def power(x,n):
#     if n==0:
#         return 1
#     else:
#         return x*power(x,n-1)
# print(power(2,3))
# (power(2,3)
# (power(2,2)
# (power(2,1)
#(power(2,0)
# 顺序是上面那样，达到最大递归深度，这时n==0,它返回了1，
#求的是2的3次幂，当n为0时，return了1，此时2*1，值为2，然后往上面一层返回，
#x*power(x,n-1)就成了2*2，因为power(x,n-1)返回来的值是2，以此类推，将4又返回
#上面的2*4算出结果。

#4.4
# def reverse(s,start,stop):
#     if start len(A)/4 -> …->
# len(A)/2**r，即 n/2* *r<1，r>logn,r=floor(logn)+1,复杂度
# 为logn，所以总的复杂度为O(nlogn)
# def add_num(n):
#     temp = []
#     if len(n)==1:
#         return n[0]
#     for i in range(len(n)//2):
#         temp.append(n[i*2]+n[i*2+1])
#     n=temp
#     return add_num(n)
# print(add_num([1,2,3,4,5,6,7,8,9,10,23,4,2,4,4,5,]))

#4.9
#这是判断出最小的元素，求最大的元素将小于号改成大于号就行
# def find_minmax(d,start=0):
#     if start==len(d)-1:
#         return d[start]
#     return d[start] if d[start]0:
#         draw_interval(center_length-1)
#         draw_line(center_length)
#         draw_interval(center_length-1)
# def draw_ruler(num_inches,major_length):
#     draw_line(major_length,'0')
#     for j in range(1,1+num_inches):
#         draw_interval(major_length-1)
#         draw_line(major_length,str(j))
# print(draw_ruler(4,5))

#4.14
# def move(n,a,b,c):
#     if n==1:
#         print(a,'-->',c)
#     else:
#         move(n-1,a,c,b)
#         print(a,'-->',c)
#         move(n-1,b,a,c)
# print(move(3,'A','B','C'))


#这一道题的要点在于，总共只有三个柱子，当盘子在a上面时，要先将N-1个盘子挪到
# b上，第N个盘子就可以放到C上了，这时N-1个盘子在B上，又要将N-1-1个盘子先挪到A上，
# B上的第N-1个盘子就可以挪到C上，注意这时候所有的盘子又回到了A上，程序的状态又回到了开始
# 这便是递归的意义所在，不断的重复一个过程，等于是一个圆，当又转到开始的那个点时，此时数据
# 已得到了一定的处理，但数据的状态又跟开始的时候一样(但数据规模小了一圈)，此时将函数又一次调用，
# 重新处理这些数据，直到达到要求的状态。

#4.15
#这是书本上4-16的例子，O(2^n)时间复杂度
# def unique3(S,start,stop):
#     # print(unique3(S,start,stop))
#     if stop-start<=1:
#         print(S, stop, start,'最后')
#         return True
#     elif not unique3(S,start,stop-1):
#         print( start, stop,'stop-1')
#         return False
#     elif not unique3(S,start+1,stop):
#         print(start, stop,'start+1')
#         return False
#     else:
#         return S[start]!=S[stop-1]
# print(unique3([1,2,3,4,5,6,6,7,8,9,10,],0,10))


#4.15
# def subs(l):
#     if len(l) == 1:
#         return [l]
#     res = []
#     for sub in subs(l[0:-1]):
#         res.append(sub)
#         res.append([l[-1]])
#         res.append(sub+[l[-1]])
#     return res
# li = [1,2,3]
# print(subs(li))

# def get_subset8(mylist):
#     res = []
#     n = len(mylist)
#     def helper(i, tmp):
#         res.append(tmp)
#         for j in range(i, n):
#             helper(j + 1, tmp + [mylist[j]])
#     helper(0, [])
#     print(res)
# get_subset8([1,2,3])

#4.16
# def reversed_string(st,index=0):
#     if index==len(st)-1:
#         return st[index]
#     return reversed_string(st,index+1)+st[index]
# print(reversed_string('1234456'))

#4.17
# def just_is_palindromic(st):
#     if len(st)==1 or len(st)==0:
#         return True
#     if st[0]==st[-1]:
#         return just_is_palindromic(st[1:-1])
#     else:
#         return False
# print(just_is_palindromic('abcba'))
#方法二
# def just_is_palindromic(st):
#     temp=''
#     for i in st[::-1]:
#         temp+=i
#     if st==temp:
#         return True
#     return False
# print(just_is_palindromic('abcba'))
#方法三
# def just_is_palindromic(st):
#     return st==st[::-1]
# print(just_is_palindromic('abcba'))
#方法四
# def just_is_palindromic(st):
#     for i in range(len(st)):
#         if st[i]!=st[-(i+1)]:
#             return False
#     return True
# print(just_is_palindromic('asdgbcba'))

#4.18
# def just_vowel_more(st,a=0,b=0,c=0):
#     if a==len(st)-1:
#         return True if b>c else False
#     if st[a]in 'aeiouAEIOU':
#         b+=1
#     elif st[a].lower() in 'bcdfghjklmnpqrstvwxyz':
#         c+=1
#     return just_vowel_more(st,a+1,b,c)
# print(just_vowel_more('ouAfghjklm'))

#4.19
# def just_even_and_odd(st,index=0,temp=[]):
#     if index==len(st):
#         return temp
#     if st[index]%2==0:
#         temp.insert(0,st[index])
#     else:
#         temp.append(st[index])
#     return just_even_and_odd(st,index+1,temp)
# print(just_even_and_odd([1,2,3,4,5,6,7,8,9,0]))
#方法二
# a=[1,2,3,4,5,6,7,8,9,0]
# length=len(a)
# temp=[]
# for i in range(length):
#     if a[i]%2==0:
#         temp.insert(0,a[i])
#     else:
#         temp.append(a[i])
# print(temp)

#4.20
#时间复杂度是O(n)
# a=[1,2,3,4,5,6,7,8,9,0]
# def order(arr,k,index=0,temp=[]):
#     if index==len(arr):
#         return temp
#     if arr[index]