nCr 캐시된 재귀함수로 구하기

Python 3.4.4 (v3.4.4:737efcadf5a6, Dec 20 2015, 20:20:57) [MSC v.1600 64 bit (AMD64)] on win32

Type "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 1

return nCr(n-1, r-1) + nCr(n-1, r)

Traceback (most recent call last):

  File "<pyshell#7>", line 1, in <module>

    @functools.lur_cache(maxsize=200, typed=False)

NameError: name 'functools' is not defined

>>> @functools.lru_cache(maxsize=200, typed=False)

def nCr(n, r):

if r in (n, 0):

return 1

return nCr(n-1, r-1) + nCr(n-1, r)

Traceback (most recent call last):

  File "<pyshell#9>", line 1, in <module>

    @functools.lru_cache(maxsize=200, typed=False)

NameError: name 'functools' is not defined

>>> import functools

>>> @functools.lru_cache(maxsize=200, typed=False)

def nCr(n, r):

if r in (n, 0):

return 1

return nCr(n-1, r-1) + nCr(n-1, r)

>>> for n in range(10):

print('\t'.join('%dC%d = %d'%(n, r, nCr(n, r)) for r in range(n+1)))

0C0 = 1

1C0 = 1 1C1 = 1

2C0 = 1 2C1 = 2 2C2 = 1

3C0 = 1 3C1 = 3 3C2 = 3 3C3 = 1

4C0 = 1 4C1 = 4 4C2 = 6 4C3 = 4 4C4 = 1

5C0 = 1 5C1 = 5 5C2 = 10 5C3 = 10 5C4 = 5 5C5 = 1

6C0 = 1 6C1 = 6 6C2 = 15 6C3 = 20 6C4 = 15 6C5 = 6 6C6 = 1

7C0 = 1 7C1 = 7 7C2 = 21 7C3 = 35 7C4 = 35 7C5 = 21 7C6 = 7 7C7 = 1

8C0 = 1 8C1 = 8 8C2 = 28 8C3 = 56 8C4 = 70 8C5 = 56 8C6 = 28 8C7 = 8 8C8 = 1

9C0 = 1 9C1 = 9 9C2 = 36 9C3 = 84 9C4 = 126 9C5 = 126 9C6 = 84 9C7 = 36 9C8 = 9 9C9 = 1

>>> for n in range(10):

print('    '.join('%dC%d = %3d'%(n, r, nCr(n, r)) for r in range(n+1)))

0C0 =   1

1C0 =   1    1C1 =   1

2C0 =   1    2C1 =   2    2C2 =   1

3C0 =   1    3C1 =   3    3C2 =   3    3C3 =   1

4C0 =   1    4C1 =   4    4C2 =   6    4C3 =   4    4C4 =   1

5C0 =   1    5C1 =   5    5C2 =  10    5C3 =  10    5C4 =   5    5C5 =   1

6C0 =   1    6C1 =   6    6C2 =  15    6C3 =  20    6C4 =  15    6C5 =   6    6C6 =   1

7C0 =   1    7C1 =   7    7C2 =  21    7C3 =  35    7C4 =  35    7C5 =  21    7C6 =   7    7C7 =   1

8C0 =   1    8C1 =   8    8C2 =  28    8C3 =  56    8C4 =  70    8C5 =  56    8C6 =  28    8C7 =   8    8C8 =   1

9C0 =   1    9C1 =   9    9C2 =  36    9C3 =  84    9C4 = 126    9C5 = 126    9C6 =  84    9C7 =  36    9C8 =   9    9C9 =   1

>>> for n in range(10):

print('    '.join('%dC%d = %-3d'%(n, r, nCr(n, r)) for r in range(n+1)))

0C0 = 1  

1C0 = 1      1C1 = 1  

2C0 = 1      2C1 = 2      2C2 = 1  

3C0 = 1      3C1 = 3      3C2 = 3      3C3 = 1  

4C0 = 1      4C1 = 4      4C2 = 6      4C3 = 4      4C4 = 1  

5C0 = 1      5C1 = 5      5C2 = 10     5C3 = 10     5C4 = 5      5C5 = 1  

6C0 = 1      6C1 = 6      6C2 = 15     6C3 = 20     6C4 = 15     6C5 = 6      6C6 = 1  

7C0 = 1      7C1 = 7      7C2 = 21     7C3 = 35     7C4 = 35     7C5 = 21     7C6 = 7      7C7 = 1  

8C0 = 1      8C1 = 8      8C2 = 28     8C3 = 56     8C4 = 70     8C5 = 56     8C6 = 28     8C7 = 8      8C8 = 1  

9C0 = 1      9C1 = 9      9C2 = 36     9C3 = 84     9C4 = 126    9C5 = 126    9C6 = 84     9C7 = 36     9C8 = 9      9C9 = 1  

>>> nCr(134, 29)

208435140221619426330073413280

>>> nCr(1340, 29)

Traceback (most recent call last):

  File "<pyshell#22>", line 1, in <module>

    nCr(1340, 29)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper

    result = user_function(*args, **kwds)

  File "<pyshell#12>", line 5, in nCr

    return nCr(n-1, r-1) + nCr(n-1, r)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper

    result = user_function(*args, **kwds)

  File "<pyshell#12>", line 5, in nCr

    return nCr(n-1, r-1) + nCr(n-1, r)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper

    result = user_function(*args, **kwds)

  File "<pyshell#12>", line 5, in nCr

    return nCr(n-1, r-1) + nCr(n-1, r)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper

    result = user_function(*args, **kwds)

  File "<pyshell#12>", line 5, in nCr

    return nCr(n-1, r-1) + nCr(n-1, r)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper

    result = user_function(*args, **kwds)

  File "<pyshell#12>", line 5, in nCr

    return nCr(n-1, r-1) + nCr(n-1, r)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper

    result = user_function(*args, **kwds)

  File "<pyshell#12>", line 5, in nCr

    return nCr(n-1, r-1) + nCr(n-1, r)

  File "D:\Python3464\lib\functools.py", line 472, in wrapper