Python 분 치 법 정의 및 응용 실례 상세 설명

본 논문 의 사례 는 Python 분 치 법의 정의 와 응용 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
분 치 법 이 해결 할 수 있 는 문 제 는 일반적으로 다음 과 같은 몇 가지 특징 을 가진다.
1)이 문제 의 규 모 를 어느 정도 축소 하면 쉽게 해결 할 수 있다
2)이 문 제 는 몇 개의 규모 가 작은 똑 같은 문제 로 나 눌 수 있다.즉,이 문 제 는 가장 좋 은 서브 구조 성 을 가진다.
3)이 문제 로 분 해 된 하위 문제 의 해 를 이용 하여 이 문제 의 해 로 합 칠 수 있다.
4)이 문제 에서 분 해 된 각 하위 문 제 는 서로 독립 된 것 이다.즉,하위 문제 사이 에 공공 하위 문 제 를 포함 하지 않 는 다.
첫 번 째 특징 은 절대 다수의 문제 가 모두 만족 할 수 있다 는 것 이다.왜냐하면 문제 의 계산 복잡성 은 일반적으로 문제 규모 의 증가 에 따라 증가 하기 때문이다.
두 번 째 특징 은 분 치 법 을 응용 하 는 전제 이자 대부분 문제 가 만족 할 수 있다 는 것 이다.이 특징 은 재 귀 사상의 응용 을 나타 낸다.
세 번 째 특징 은 관건 이다.분 치 법 을 이용 할 수 있 느 냐 없 느 냐 는 문제 가 세 번 째 특징 을 가지 고 있 느 냐 에 달 려 있다.만약 에 첫 번 째 와 두 번 째 특징 을 가지 고 세 번 째 특징 을 가지 지 않 으 면 욕심 법 이나 동태 계획 법 을 사용 하 는 것 을 고려 할 수 있다.
제4 조 특징 은 분 치 법의 효율 과 관련된다.만약 에 각 서브 문제 가 독립 되 지 않 으 면 분 치 법 은 불필요 한 일 을 많이 하고 공공 서브 문 제 를 반복 적 으로 풀 어야 한다.이때 분 치 법 을 사용 할 수 있 지만 보통 동태 계획 법 을 사용 하 는 것 이 좋다.
제목 1.순서 표를 정 하고 최대 값 을 구 하 는 분할 알고리즘 을 작성 합 니 다.

#      （          2  ）
def get_max(max_list):
  return max(max_list) #      ！
#        
def solve(init_list):
  n = len(init_list)
  if n <= 2: #           2，    
    return get_max(init_list)
  #   （       2，        1）
  temp_list=(init_list[i:i+2] for i in range(0, n, 2))
  #   ，  
  max_list = list(map(get_max, temp_list))
  #   （ ）
  solve(max_list)
#        
def solve2(init_list):
  n = len(init_list)
  if n <= 2: #           2，  
    return get_max(init_list)
  #   （       n/2）
  left_list, right_list = init_list[:n//2], init_list[n//2:]
  #   （ ），  
  left_max, right_max = solve2(left_list), solve2(right_list)
  #   
  return get_max([left_max, right_max])
if __name__ == "__main__":
  #     
  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]
  #     
  print(solve(test_list)) # 67
  print(solve2(test_list)) # 67

제목 2.순서 표를 정 하여 어떤 요소 가 그 안에 있 는 지 판단 한다.

#      （       1）
def is_in_list(init_list, el):
  return [False, True][init_list[0] == el]
#    
def solve(init_list, el):
  n = len(init_list)
  if n == 1: #         1，    
    return is_in_list(init_list, el)
  #   （       n/2）
  left_list, right_list = init_list[:n//2], init_list[n//2:]
  #   （ ），  ，  
  res = solve(left_list, el) or solve(right_list, el)
  return res
if __name__ == "__main__":
  #     
  test_list = [12,2,23,45,67,3,2,4,45,63,24,23]
  #   
  print(solve2(test_list, 45)) # True
  print(solve2(test_list, 5)) # False

제목 3.서열 중의 k 작은 요 소 를 찾 아 선형 시간 을 요구한다.

#   （     pivot），  ：     
def partition(seq):
  pi = seq[0]              #     
  lo = [x for x in seq[1:] if x <= pi] #       
  hi = [x for x in seq[1:] if x > pi]  #       
  return lo, pi, hi
#     k     
def select(seq, k):
  #   
  lo, pi, hi = partition(seq)
  m = len(lo)
  if m == k:
    return pi        #   ！
  elif m < k:
    return select(hi, k-m-1) #   （ ），  
  else:
    return select(lo, k)   #   （ ），  
if __name__ == '__main__':
  seq = [3, 4, 1, 6, 3, 7, 9, 13, 93, 0, 100, 1, 2, 2, 3, 3, 2]
  print(select(seq, 3)) #2
  print(select(seq, 5)) #2

제목 4.빠 른 정렬

#   （     pivot），  ：     
def partition(seq):
  pi = seq[0]              #     
  lo = [x for x in seq[1:] if x <= pi] #       
  hi = [x for x in seq[1:] if x > pi]  #       
  return lo, pi, hi
#     
def quicksort(seq):
  #          1，  
  if len(seq) <= 1: return seq
  #   
  lo, pi, hi = partition(seq)
  #   （ ），  ，  
  return quicksort(lo) + [pi] + quicksort(hi)
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(quicksort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

제목 5.병합 정렬(이분 정렬)

#     
def mergesort(seq):
  #   （    ）
  mid = len(seq) // 2
  left_seq, right_seq = seq[:mid], seq[mid:]
  #   （ ），  
  if len(left_seq) > 1: left_seq = mergesort(left_seq)
  if len(right_seq) > 1: right_seq = mergesort(right_seq)
  #   
  res = []
  while left_seq and right_seq:     #        
    if left_seq[-1] >= right_seq[-1]: #        ，  
      res.append(left_seq.pop())
    else:
      res.append(right_seq.pop())
  res.reverse()             #   
  return (left_seq or right_seq) + res  #           seq
seq = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]
print(mergesort(seq)) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

제목 6.한 노 타

#    
def move(n, a, buffer, c):
  if n == 1:
    print(a,"->",c)
    #return
  else:
    #   （  ）
    move(n-1, a, c, buffer)
    move(1, a, buffer, c) #   ：print(a,"->",c)
    move(n-1, buffer, a, c)
move(3, "a", "b", "c")

계단 을 오르다
만약 당신 이 계단 을 오 르 고 있다 고 가정 하면 n 걸음 이 있어 야 정상에 도착 할 수 있 습 니 다.그러나 매번 한 걸음 이나 두 걸음 만 올 라 갈 수 있다.당신 은 몇 가지 다른 방법 으로 옥상 까지 올 라 갈 수 있 습 니까?

#    
def climb(n=7):
  if n <= 2:
    return n
  return climb(n-1) + climb(n-2) #          ！
print(climb(5)) # 8
print(climb(7)) # 21

문제 8.평면 에 n 개의 점 을 정 하고 그 중의 한 쌍 의 점 을 찾 아 n 개의 점 의 모든 점 에서 이 점 이 맞 는 거 리 를 최소 화 합 니 다.(질문

from math import sqrt
#    
def solve(points):
  n = len(points)
  min_d = float("inf") #     ：   
  min_ps = None    #     
  for i in range(n-1):
    for j in range(i+1, n):
      d = sqrt((points[i][0] - points[j][0])**2 + (points[i][1] - points[j][1])**2) #     
      if d < min_d:
        min_d = d            #       
        min_ps = [points[i], points[j]] #       
  return min_ps
#      （  ！）
def nearest_dot(seq):
  #   ：seq    x    
  n = len(seq)
  if n <= 2: return seq #         2，    
  #   （     n/2）
  left, right = seq[0:n//2], seq[n//2:]
  print(left, right)
  mid_x = (left[-1][0] + right[0][0])/2.0
  #   ，  
  lmin = (left, nearest_dot(left))[len(left) > 2]  #       
  rmin = (right, nearest_dot(right))[len(right) > 2] #       
  #   
  dis_l = (float("inf"), get_distance(lmin))[len(lmin) > 1]
  dis_r = (float("inf"), get_distance(rmin))[len(rmin) > 1]
  d = min(dis_l, dis_r)  #       
  #            （    ）
  left = list(filter(lambda p:mid_x - p[0] <= d, left))  #        <=d  
  right = list(filter(lambda p:p[0] - mid_x <= d, right)) #        <=d  
  mid_min = []
  for p in left:
    for q in right:
      if abs(p[0]-q[0])<=d and abs(p[1]-q[1]) <= d:   #        p  (d,2d)  
        td = get_distance((p,q))
        if td <= d:
          mid_min = [p,q]  #   p，q  
          d = td      #       
  if mid_min:
    return mid_min
  elif dis_l>dis_r:
    return rmin
  else:
    return lmin
#     
def get_distance(min):
  return sqrt((min[0][0]-min[1][0])**2 + (min[0][1]-min[1][1])**2)
def divide_conquer(seq):
  seq.sort(key=lambda x:x[0])
  res = nearest_dot(seq)
  return res
#   
seq=[(0,1),(3,2),(4,3),(5,1),(1,2),(2,1),(6,2),(7,2),(8,3),(4,5),(9,0),(6,4)]
print(solve(seq)) # [(6, 2), (7, 2)]
#print(divide_conquer(seq)) # [(6, 2), (7, 2)]

문제 9.배열 seq 에서 s 와 의 수치 조합 을 찾 으 면 몇 가지 가능성 이 있 습 니까?

'''
     ：N  ，   M              X。   M      。
  ：
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 #  
          ：
5+9, 6+8
1+4+9, 1+5+8, 1+6+7, 2+3+9, 2+4+8, 2+5+7, 3+4+7, 3+5+6
1+2+5+6, 1+3+4+6, 1+2+4+7, 1+2+3+8, 2+3+4+5
  15 
'''
#    （   ）
def find(seq, s):
  n = len(seq)
  if n==1:
    return [0, 1][seq[0]==s]
  if seq[0]==s:
    return 1 + find(seq[1:], s)
  else:
    return find(seq[1:], s-seq[0]) + find(seq[1:], s)
#   
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 #  
print(find(seq, s)) # 15
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 #  
print(find(seq, s)) #8
#     （  ）
def find2(seq, s, tmp=''):
  if len(seq)==0:  #     
    return
  if seq[0] == s:        #     ， 
    print(tmp + str(seq[0])) #   
  find2(seq[1:], s, tmp)               #     ---   seq[0]    
  find2(seq[1:], s-seq[0], str(seq[0]) + '+' + tmp)  #     ---  seq[0]    
#   
seq = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s = 14 #  
find2(seq, s)
print()
seq = [11,23,6,31,8,9,15,20,24,14]
s = 40 #  
find2(seq, s)

더 많은 파 이 썬 관련 내용 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.