본문 바로가기

파스칼삼각형

 (3)
nCr 캐시된 재귀함수로 구하기 Python 3.4.4 (v3.4.4:737efcadf5a6, Dec 20 2015, 20:20:57) [MSC v.1600 64 bit (AMD64)] on win32Type "copyright", "credits" or "license()" for more information.>>> def nCr(n, r):if r in (n, 0);SyntaxError: invalid syntax>>> @functools.lur_cache(maxsize=200, typed=False)def nCr(n, r):if r in (n, 0):return 1return nCr(n-1, r-1) + nCr(n-1, r) Traceback (most recent call last): File "", line 1, in @fu..
[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..
[Project Euler 148] 파스칼 삼각형 mod 7 http://projecteuler.net/index.php?section=problems&id=148 파스칼 삼각형을 7번째 줄까지 써보면, 7로 나누어 떨어지는 것이 없다는 걸 알 수 있다.: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 그러나, 100번째 줄까지를 보면, 5050개의 숫자 중에서 2361개만 7로 나누어 떨어지지 않는다. 10억(109)번째 줄까지 중에서 7로 나누어 떨어지지 않는 것의 갯수를 구하라. 우선, a+b mod n = (a mod n) + (b mod n) mod n 과 같다는 걸 이용해서 그림을 그려보면, 아주 예쁜 프랙탈모양을 이룸을 알 수 있다. 그리고, 숫자를 7진수로 변환한 후 생각하면 훨씬 생각이..

티스토리툴바