[Python] 하노이 탑 경로, 이동 횟수 구하기

하노이 탑의 경로와 이동 횟수를 알기 위해선 시작점과 끝점 뿐만 아니라 어디를 거쳐서 이동하는지도 고려해야한다. n번 원판이 가장 아래 있기 때문에 이 원판을 옮기기 위해선 그 위에 있는 n-1개의 원판을 다른 곳으로 이동 시켜야 한다. 시작 : a(파이썬에서 from 이미 모듈을 가져오는데 사용되므로 a로 변수명을 정하였다.) 거쳐가는 곳 : by 끝: to 알고리즘은 다음과 같다. n-1개의 원판을 by에 옮긴다. n번째 원판을 to로 옮긴다. by에 있는 n-1개의 원판을 to로 옮긴다. 이 알고리즘을 바탕으로 다음과 같이 코드를 작성해 볼 수 있다. def hanoi (a ,by,to,n): if n==1: print("1: "+a+" --> "+to) return 1 ans=0 ans+=hano..

• format_list_bulleted Python
• · 2020. 4. 1.
• textsms

[Python] N개의 수의 최대 공약수, 최소 공배수 구하기

최대공약수 먼저 두 수의 최대공약수를 구하는 알고리즘은 다음과 같다. def gcd_(a, b): while b>0: a,b=b,a%b return a arr[0]~arr[N-1] N개의 수가 주어졌을 때 최대 공약수를 구해보자 arr[0]과 arr[1]의 최대공약수 gcd라고 하면, gcd를 gcd와 arr[2]와의 최대공약수로 갱신해주고, 다시 gcd와 arr[3]의 최대공약수를 구하는 것을 반복 해 주면 된다. def gcd_N(arr): gcd=arr[0] for item in arr: gcd=gcd_(gcd,item) return gcd 최소공배수 먼저 두 수의 최소공배수를 구하는 알고리즘은 다음과 같다. def lcm_(a, b): return a*b//gcd(a,b) arr[0]~arr[N-..

• format_list_bulleted Python
• · 2020. 3. 25.
• textsms