본문 바로가기

프로그래밍

 (357)
[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 # ..
2의 거듭제곱 (10만승까지) 벤포드 법칙 무식쟁이 방법으로 확인. #!/usr/bin/env python # http://bomber0.byus.net/index.php/2009/07/30/1409 # brute force check twopow = 1 tenpow = 1 cnt = [ 0 for i in range(10) ] pro = [ 0 for i in range(10) ] for i in range(100000): twopow *= 2 if twopow/(tenpow*10) > 0: tenpow *= 10 #d1 = int(("%d"%twopow)[0]) d = twopow/tenpow #if d1 != d: # print twopow cnt[d] += 1 if (i+1)%1000 == 0: print (i+1) print "%d\t%d\t%d\t%d\t%d\..
[Euler Project 203] 소수제곱없는 이항계수의 합 구하기 0C0 부터 50C50 까지의 이항계수들 가운데에 소인수분해하여, 제곱이상의 인자가 없는 것들의 합을 구하는 것. 트릭은 nCr = n x ((n-1)C(r-1) / r 이라는 관계식을 이용하는 것, 수를 50이하의 소수 (15개)의 거듭제곱수의 리스트로 표현하여 곱과 나누기의 오버헤드를 줄이고, 제곱 이상의 인자가 없는지 확인하기 편하게 하는 것.아래 코드는 좀 지져분하다. #!/usr/bin/env python def MUL(l1, l2, l3): n = len(primes) #l3 = [ 0 ] * n for i in range(n): l3[i] = l1[i]+l2[i] return def DIV(l1, l2, l3): n = len(primes) #l3 = [ 0 ] * n for i in ran..
[Euler Project 101] 수열 다항식으로 근사하기 #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=101 coff = [ 0 ] * 11 def OP(ord, n): if ord == 0: return coff[0] r = OP(ord-1, n) term = coff[ord] for j in range(1, ord+1): term*=(n-j) for j in range(1, ord+1): term/= j r += term return r def f(n): return 1 - n + n**2 - n**3 + n**4 - n**5 + n**6 - n**7 + n**8 - n**9 + n**10 a = [ f(n) for n in range(1, 12) ] coff[0..
[Euler Project 188] 1777의 1885 거듭거듭제곱의 마지막 8자리 구하기 거듭거듭제곱이란 단어는 tetration의 정확한 한국어 번역어를 몰라서 내가 개발한 번역임. 정확한 정의는 검색하여 보기바람. 매우 재미있음. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=188 def phi(n0): ''' euler phi function for n, which consists of only 2 and 5 ''' n = n0 pow2 = 0 while n%2 == 0: n/=2 pow2 +=1 n = n0 pow5 = 0 while n%5 == 0: n/=5 pow5 +=1 if pow5 == 0: if pow2 == 0: return 1 else: return 2**(pow2-1) els..
[Euler Project 187] 인자가 두개인 합성수의 갯수 1억보다 작은, 소수 둘만의 곱인 합성수의 갯수를 구하라. 4나 9도 포함된다. 에라스토테네스의 체 방법으로 소수를 우선 싹 구하고 한다. 내가 가장 효율적이라고 생각했던 소수 구하는 방법은 전혀 효율적이지 않았다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=187 MAX=50000000 flags = [ 1 ] * MAX flags[0] = 0 flags[1] = 0 for n in range(2, MAX): if flags[n] == 1: m = 2*n while m < MAX: flags[m] = 0 m+=n n+=1 primes = [ ] for i in range(0, MAX): if flags[i]..
[Euler Project 091] 직각삼각형 갯수 구하기 50, 50 격자 안에서 한 꼭지점이 원점에 있고, 꼭지점이 격자점에 위치하는 직각삼각형의 갯수 구하기. 오일러 프로젝트 91번 문제이다. 직각이 원점에 있는 경우, 직각이 축에 위치하는 경우, 그리고 나머지 경우에 대해 나누어 갯수를 구했다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=91 def get_cnt_when_right_angle_is_O(max): ''' P is (0, [1 ... max]) and Q is ([1 ... max], 0)''' return max * max def get_cnt_when_right_angle_is_on_axis(max): ''' When P is (0, y), ..

티스토리툴바