프로그래밍/알고리즘 (46) 썸네일형 리스트형 [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), .. [수학] 페르마 소정리 이해를 위한 장난 rsa를 주제로 한 오일러 프로젝트 문제를 풀다가, 페르마 소정리에 대해서 감이 잘 안 와서 엑셀로 계산을 시켜봤다. p = 3, q = 7 인 상당히 간단한 경우의 계산이다. 엑셀이 상당한 프로그래밍 시간을 줄여주기는 하는데, 내 입맛에 딱 맞춰 결과를 보기에는 아직 익숙하지가 않아서 좀 고달픈 구석이 있다. [Project Euler 213] 30x30 격자 벼룩 http://projecteuler.net/index.php?section=problems&id=213 30x30 크기의 격자에 벼룩이 있다. 최초에 벼룩은 격자 하나당 하나씩 있고, 한 번 종이 울리면, 격자의 사방으로 튈 수 있다. 가장자리에 있는 벼룩은 바깥으로 나갈 수 없다. 종이 울릴 때마다 각 격자에 벼룩이 몇마리 있을지에 대한 확률분포를 색으로 표현하는 걸 만들어 봤다. 문제가 풀릴려면 부동소수점연산에 의한 오차가 문제가 될 것 같으나, 대략적인 것만 보기 위해서, 그런 건 우선 무시하고 만들어 봤다. 10번 종이 울린 후 확률 분포는 다음과 같다. 색이 흐리면 (하얀색에 가까우면) 확률이 낮은 것이다. vc6.0, mfc 로 짜봤으며, 소스는 여기 있다. 대충 짠거라 책임은 지지 않는다. .. [Projet Euler 231] 조합의 소인수분해 문제 이항계수 10C3 = 120 이다. 120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5 이고, 2 + 2 + 2 + 3 + 5 = 14 이 된다. 즉 10C3 의 소인수분해하여 나온 인자의 합은 14이다. 20000000C15000000 의 소인수분해 인자의 합을 구하라. http://projecteuler.net/index.php?section=problems&id=231 풀이법. 130! 마지막엔 0이 몇 개 있는지를 풀어내는 방법을 응용한다. 사실 동일한 거다. 일반적으로 m! 에 소수 p가 몇 개 있는지 구하는 식은 [m/p] + [m/(p*p)] + [m/(p*p*p)] + [m/(p*p*p*p)] + ... 이다. nCm = n!/((m!)((n-m)!)) 이다. 소스. 이전 1 2 3 4 5 6 다음
