Partition Function (2) 썸네일형 리스트형 [Euler Project 078] 분할함수 (Partition Function) 76, 77번을 풀었던 방법으로 풀었는데, 끝까지 계산하지 못하고 오버플로우가 났다. 삼각형 형태로 메모리가 늘어나서 13000 까지 찍고 죽는 것이었다. 그래서 위키백과의 점화식을 이용하여 푸는 코드를 짜서 풀었다. 점화식은 2차원인 아닌 1차원으로 기억하고 있으면 되서 답을 내 줬다. 죽는 코드와 죽는 모습 #!/usr/bin/env python # euler 78 P = [] n = 0 P.append([]) P[n].append(0) # P[0][0] n = 1 P.append([]) P[n].append(0) # P[1][0] P[n].append(1) # P[1][1] n = 2 while 1: cnt = 0 P.append([]) for i in range(n+1): if i == 0: cn.. [Euler Project 077] 소수의 합으로 표현하는 가짓수 스프레드시트로 표현한 배열이랑, 코드에서 구하는 배열이랑 의미가 조금 다르다. 아래 코드에서는 누적값을 구한다. 그래서 계산의 summation 루프를 줄인다. 위 그림은 이해를 좋게 하기 위해 누적으로 표현하지 않았다. 가로축은 합이 되는 수, 세로축은 소수이다. 2, 2 는 2를 2를 최소한 한번 포함하여 2 이하의 소수들의 합으로 표현하는 갯수로 1이다. 10, 5 는 10을 5를 최소한 한번 포함하여 5 이하의 소수들의 합으로 표현하는 갯수이다. 5+5와 5+3+2가 있는데, 최대 소수인 5를 10에서 뺀 나머지인 5에 대해 경우의 수를 summation 하여 구할 수 있다. 아래는 파이썬 코드. 2차원 배열이 위 스프레드시트의 것과 다른 점 주의하라. #!/usr/bin/env python # .. 이전 1 다음
