프로그래밍을 전공하는 학생이고 처음으로 프로그래밍을 배웁니다. 선배님한테 이사이트를 알게되어 질문을 한번올려봅니다.
공부를 하다보니 pascal triangle 을 짜라는 문제가 나왔습니다. 근데 이걸 재귀로 짜고 보니까 엄청 오래걸리더라구요 좀더 효율적인 알고리즘이 없나 여쭤봅니다 ㅜㅜ
무한루프 돌지 않는 이상 그렇게 오래 걸리지 않을텐데요. 소스를 올려보시죠?
def comb(n,r): if r == 0: return 1 elif r == n: return 1 else: return comb(n-1,r-1) + comb(n-1,r)
이렇게 짰어요
이건 문자 그대로의 "구현"이군요...
주어진 문제가 "파스칼 삼각형을 출력하시오"인지, "파스칼 삼각형에서 n번째 줄의 m번재 숫자를 출력하시오"인지 구별해야 할 것 같은데요
피할 수 있을때 즐겨라! http://melotopia.net/b
중간중간에 저장해주면 잘되네요.
import array row = 35 col = 15 def pos_to_ref(x, y): return x + sum(range(1, y + 1)) def ref_to_pos(r): return [r % ((r / 2 - 1) * 2), r / 2 - 1] def comb(a, n, r): if r == 0: return 1 elif r == n: return 1 else: ref = pos_to_ref(r-1, n-1) val = a[ref] if val != 0: return val else: a[ref] = comb(a, n-1, r-1) + comb(a, n-1, r) return a[ref] ar = array.array('L', sum(range(1, row+1)) * [0]) print comb(ar, row, col) >>> 3247943160
재귀로
무한루프 돌지 않는 이상 그렇게 오래 걸리지 않을텐데요. 소스를 올려보시죠?
파이썬으로
def comb(n,r):
if r == 0:
return 1
elif r == n:
return 1
else:
return comb(n-1,r-1) + comb(n-1,r)
이렇게 짰어요
이건 문자 그대로의 "구현"이군요... 주어진
이건 문자 그대로의 "구현"이군요...
주어진 문제가 "파스칼 삼각형을 출력하시오"인지, "파스칼 삼각형에서 n번째 줄의 m번재 숫자를 출력하시오"인지 구별해야 할 것 같은데요
피할 수 있을때 즐겨라! http://melotopia.net/b
recursion이 너무 많이 중복되어서 인듯
중간중간에 저장해주면 잘되네요.
import array row = 35 col = 15 def pos_to_ref(x, y): return x + sum(range(1, y + 1)) def ref_to_pos(r): return [r % ((r / 2 - 1) * 2), r / 2 - 1] def comb(a, n, r): if r == 0: return 1 elif r == n: return 1 else: ref = pos_to_ref(r-1, n-1) val = a[ref] if val != 0: return val else: a[ref] = comb(a, n-1, r-1) + comb(a, n-1, r) return a[ref] ar = array.array('L', sum(range(1, row+1)) * [0]) print comb(ar, row, col) >>> 3247943160