본문 바로가기

이항계수

 (3)
[Python] 이항분포 그래프 그리기 import sys from functools import lru_cache import math import numpy as np import matplotlib.pyplot as plt @lru_cache(None) def ncr(n, r): """조합. 재귀식을 이용함. n이 커지면 스택오버플로우 발생. """ if r in (0, n): return 1 return ncr(n - 1, r) + ncr(n - 1, r - 1) def bidist(n, p): """이항분포""" q = 1 - p dist = np.array([ncr(n, k) * (p ** k) * (q ** (n - k)) for k in range(n + 1)]) return dist def bicoeff(n): """이항계수...
[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 123] (p-1)^n + (p+1)^n % p^2 http://projecteuler.net/index.php?section=problems&id=123 pn 이 n번째 소수 ( 2, 3, 5, 7, 11, ..., )이고, r이 (pn1)n + (pn+1)n 를 pn2으로 나눈 나머지라고 하자. 예를 들어, n = 3, p3 = 5 이고, 43 + 63 = 280 5 mod 25 이다. 이 나머지가 109을 넘는 가장 작은 n은 7037이다. 나머지가 1010을 넘는 가장 작은 n을 구하라. #!/usr/bin/env python # Project Euler Problem 123 def remainder0(p, n): return ((p-1)**n + (p+1)**n)%(p*p) def remainder(p, n): ''' p is a prime. r..

티스토리툴바