2014年10月24日 20:32

Kim Jaeju

edited: 2014年10月24日 21:02

import numpy as np
from decimal import Decimal
def mat_power(m, p, ulimit):
 if p == 0:
 return 1
 value = np.matrix([[1, 0], [0, 1]])
 while p != 0:
 if p & 1 == 1:
 value = value * m % ulimit
 m = m * m % ulimit
 p >>= 1
 return value
def fibonacci(n):
 if n == 1:
 return(0)
 first = np.matrix([[1, 0]], Decimal)
 mat = np.matrix([[1, 1], [1, 0]], Decimal)
 return (first * mat_power(mat, (n - 1), 4294967291)).tolist()[0][1]
n = Decimal(raw_input())
print fibonacci(n) % 4294967291

빠른 피보나치 변환을 사용했습니다. 1천만 정도만 돼도 계산시간이 꽤 나와서 행렬 곱셈하는 부분에서 한계값으로 나눈 나머지만 사용하도록 추렸더니 제법 빨라집니다. 그런데 10^100000는 자비심이 없네요...

LIMIT = 4294967291 # 4294967291
def multiple(x, y):
 a, b, c, d = x
 i, j, k, l = y
# return (a*i + b*k), (a*j+b*l), (c*i+d*k), (c*j+d*l)
 return (a*i + b*k) % LIMIT, (a*j+b*l)% LIMIT, (c*i+d*k)% LIMIT, (c*j+d*l)% LIMIT
def pow(x, n):
 if n is 0:
 return (1, 0, 0, 1)
 if n is 1:
 return x
 y = (1, 0, 0, 1)
 while n > 1:
 if n % 2 == 1:
 y = multiple(x, y)
 n = n - 1
 else:
 x = multiple(x, x)
 n = n // 2
 return multiple(x, y)
def fast_fib(n):
 if n is 1:
 return 0
 if n < 4:
 return 1
 a, b, c, d = pow((0, 1, 1, 1), n-3)
 return c + d
def do(n):
 return fast_fib(n) % 4294967291
%time print(do(1000000000000000))
3010145777
Wall time: 0 ns

def core01(n,m):
 temp=[0,1]
 for i in range(n-1):
 temp=[temp[1]%4294967291,(temp[0]+temp[1])%4294967291]
 return temp
def core04(n,m):
 lim=100
 if n>=lim:
 temp=core04(n//2, n//2+1)
 if n%2==0:
 return [(temp[0]**2+temp[1]**2)%4294967291,(2*temp[0]*temp[1]+temp[1]**2)%4294967291]
 elif n%2==1:
 return [(2*temp[0]*temp[1]+temp[1]**2)%4294967291, (temp[0]**2+2*temp[0]*temp[1]+2*temp[1]**2)%4294967291]
 elif n<lim:
 return (core01(n,m))
def core05(n):
 return sum(core04(n-2,n-1))%4294967291
a=core05(1000000000000000)
print(a)

python 3.4 기준입니다.

core04 입력단이 n,m 으로 되어있지만 실제 쓰는건 n 만사용합니다..

하지만 왠지 출력이 2개면 입력도 2개지 않으면 햇갈려서;;;ᅮ.ᅮ

그리고 core05(10**297) 넘어가면.. 재귀함수 호출횟수를 초과했다며 죽어버리는군요..

아마 파이썬 한계인듯합니다.

def MatMulCut2x2(A, B, cutNum):
 a1, a2, a3, a4 = A
 b1, b2, b3, b4 = B
 return ((a1 * b1 + a2 * b3) % cutNum
 , (a1 * b2 + a2 * b4) % cutNum
 , (a3 * b1 + a4 * b3) % cutNum
 , (a3 * b2 + a4 * b4) % cutNum)
def MatPowCut2x2(A, n, cutNum):
 if 1 >= n:
 return A
 R = (1, 0, 0, 1)
 while(1 < n):
 if 0 == n & 1:
 A = MatMulCut2x2(A, A, cutNum)
 n = n / 2
 else:
 R = MatMulCut2x2(R, A, cutNum)
 n -= 1
 return MatMulCut2x2(R, A, cutNum)
def MatFiboCut(num, cutNum):
 if 1 >= num:
 return 0
 return MatPowCut2x2((1, 1, 1, 0), num, cutNum)[3]
print MatFiboCut(1000000000000000, 4294967291)
print MatFiboCut(10**100000, 4294967291)

출력은

3010145777

1853287988

행렬 계산식이고 재귀함수없이 루프로 풀었습니다. 계산하는데 한 40초 걸리네요.

처음엔 위의 코드가 어려워 해멨는데 고민해서 짜고 나니 위 Jaeju 님과 거의 비슷해졌어요. ᅮ

python 2.7.6 32bit

n = input("Enter number: ")
num_pre = -1L
def fibonacci(x,y):
 global num_pre
 if num_pre == -1L:
 num_pre = 1L
 temp = (num_pre + x)%4294967291
 num_pre = x
 return temp
fibo_n = reduce(fibonacci,[0]*n)
print fibo_n

Python 3.4.4

너무 오래 걸리네. 행렬를 이용해서 처리해도.. 너무 느리네

def fibonacci(n):
 output = [1, 1, 1, 0]
 matrix = [1, 1, 1, 0]
 data = [1, 1, 1, 0] 
 for i in range(1, n - 2):
 output = [(data[0] * matrix[0] + data[1] * matrix[2]) % 4294967291, \
 (data[0] * matrix[1] + data[1] * matrix[3]) % 4294967291, \
 (data[2] * matrix[0] + data[3] * matrix[2]) % 4294967291, \
 (data[2] * matrix[1] + data[3] * matrix[3]) % 4294967291]
 data = output.copy()
 return output[0] % 4294967291
while True:
 try:
 count = int(input("\nSample input\n").split()[0])
 print("\nSample output\n%d" % fibonacci(count))
 except IndexError:
 break

a = 1
b = 1
x = int(input("몇 번째 피보나치 수열의 숫자?"))
xsum = a + b
oldsum = 1
for x in range(int(x / 2)):
 oldsum = a + b
 xsum = oldsum - a
 b = a + b
 a = a + b
print(xsum % 4294967291)

def f(num1):
 arr1 = [0,1]
 while (num1-2)>0:
 arr1 = arr1 + [arr1[-2] + arr1[-1]]
 arr1 = arr1[-2:]
 num1 -= 1
 print(arr1[-1]%4294967291)
f(5)
f(1000000)

l,n,d = int(input("몇번째인지 입력하세요")),int(input("나눌 값을 입력하세요")),[0,1]
for c in range(0, l-2):
 x = d[0] + d[1]
 d.append(x)
 del d[0]
x = d[1]%n
print(x)

파이선 3.6

n = int(input("n = "))
count,tmp = 1,[0,1]
while count != n:
 tmp.append(sum(tmp))
 count += 1
 del tmp[0]
print(tmp[0]%4294967291)