蓝桥杯真题（Python）每日练Day3

题目

题目分析

1. 为了找到满足条件的放置方法，可以带入总盘数为2和3的情景，用递归做法实现。
   2.== A中存在1 2两个盘，为了实现最少次数放入C且上小下大，先将1放入B，再将2放入C，最后将1放入C即可。同理当A中存在1 2 3 三个盘时，可将1 2盘看成整体，再理解整个过程可以发现，把N个圆盘的问题递归成N-1个圆盘的问题即可。==

题解1（递归）

#可联想两个盘和三个盘的时候摆放的过程
def hanio(x,y,z,n):
  global sum#设置全局变量sum统计移动次数
  if (n==1):#当移动到A柱只有一个盘子的时候
    sum+=1
    if(sum==m):#此时如果要满足题目要求条件，当移动到A柱只有一个盘子的时候，A的最后一个盘子必须移动到C柱
      print(f"#{n}: {x}->{z}")
  else:#A的最后一个盘子的上一个盘子一定是移动到B
      hanio(x,z,y,n-1)#一定是从A移动到B
      sum+=1
      if sum==m:
        print(f"#{n}: {x}->{z}")
      hanio(y,x,z,n-1)#此时是最后一步把B柱的盘放到C柱
n,m=map(int,input().split())
sum=0
hanio('A','B','C',n)
print(sum)

题解2（栈）

1. 利用栈实现。

st =  [[0 for i in range(30000)] for i in range(4)]#创建一个二维数组[[],[],[],[]]
sum,m = 0,0
def move(x, y, n):
    global sum,m#定义全局变量
    element = st[x].pop()#pop方法移出并返回值
    st[y].append(element)
    sum +=1
    a,b ='',''    
    if x==1: a='A'
    if x==2: a='B'
    if x==3: a='C'
    if y==1: b='A'
    if y==2: b='B'
    if y==3: b='C'
    if sum == m: print('#',n,': ',a,"->",b, sep="")# sep=""表示后面没空格
def hanoi(n,x, y, z):    
    if (n == 1): move(x,z,n)
    else:
        hanoi(n-1,x, z, y)
        move(x,z,n)
        hanoi(n-1,y, x, z)        
n, m = map(int, input().split())
for i in range(n):  st[1].append(i)#初始化栈，st[1]表示A
hanoi(n,1,2,3)
print(sum)