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

#include <stdio.h>
int main( void )
{
 int n;
 int i, a = 0, b = 1;
 scanf("%d", &n);
 for( i = 1; i < n; i++ ) {
 a += b;
 b = a-b;
 }
 printf("%d\n", a%4294967291);
 return 0;
}

빠른 피보나치 변환을 사용했습니다. 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

펄입니다

perl -e 'use latest;use bigint;my($one,$two,$cnt,$t)=(0,1,2);until($cnt==$ARGV[0]){$t=$two;$two=$one+$two;$one=$t;$cnt++}say $two%4294967291;'

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

Java. long자료형을 사용했더니, 100000을 입력했더니 음수가 결과값으로 나오는 오류가 발생하네요 ᅲᅲ.. 도와주실분?

package h_Fibonacci2;
import java.util.Scanner;
public class Secret {
 public static void main(String[] args) {
 Scanner in=new Scanner(System.in);
 System.out.println("Input:");
 long n=in.nextLong();
 long i,a=0l, b=1l, temp=0l, c=4294967291l;
 for(i=1l;i<n;i++){
 temp=a;
 a+=b;
 b=temp; 
 }
 System.out.println("Output:"+(a%c));
 }
}

Input:
100000
Output:-3809483798

package rootcucu.codefight;
import java.math.BigDecimal;
public class FibonacciModulo {
 public static class Matrix {
 public final static Matrix ADVANCE[] = new Matrix[]{
 new Matrix(1,0,0,1),
 new Matrix(1,1,1,0),
 new Matrix(2,1,1,1),
 new Matrix(3,2,2,1),
 new Matrix(5,3,3,2),
 new Matrix(8,5,5,3),
 new Matrix(13,8,8,5),
 };
 public static Matrix IDENTITY = new Matrix(1,0,0,1);
 private BigDecimal a, b, c, d;
 Matrix(BigDecimal a, BigDecimal b, BigDecimal c, BigDecimal d){
 this.a = a;
 this.b = b;
 this.c = c;
 this.d = d;
 }
 Matrix(int a, int b, int c, int d){
 this.a = new BigDecimal(a);
 this.b = new BigDecimal(b);
 this.c = new BigDecimal(c);
 this.d = new BigDecimal(d);
 }
 Matrix multiply(Matrix m){
 return new Matrix(
 Matrix.segment(a,b,m.a,m.c),
 Matrix.segment(a,b,m.b,m.d),
 Matrix.segment(c,d,m.a,m.c),
 Matrix.segment(c,d,m.b,m.d));
 }
 Matrix square(){
 return multiply(this);
 }
 public Matrix remainder(String divisorString){
 BigDecimal divisor = new BigDecimal(divisorString);
 return new Matrix(a.remainder(divisor),
 b.remainder(divisor),
 c.remainder(divisor),
 d.remainder(divisor));
 }
 private static BigDecimal segment(BigDecimal q, BigDecimal r, BigDecimal s, BigDecimal t){
 return q.multiply(s).add(r.multiply(t));
 }
 @Override
 public String toString() {
 return "Matrix [a=" + a + ", b=" + b + ", c=" + c + ", d=" + d
 + "]";
 }
 static BigDecimal findNthFibonacciNumber(BigDecimal n){
 Matrix m = Matrix.ADVANCE[1];
 Matrix a = Matrix.IDENTITY;
 while (n.compareTo(BigDecimal.ZERO) > 0){
 if (n.remainder(new BigDecimal(2)).intValue() == 1){
 a = a.multiply(m).remainder("4294967291"); 
 }
 m = m.square().remainder("4294967291");
 n = n.divide(new BigDecimal(2), BigDecimal.ROUND_FLOOR);
 }
 // f(1) = 0, f(2)=1 일 때는 a.d를 출력.
 // f(0) = 0, f(1)=1 일 때는 a.b를 출력.
 return a.d;
 }
 static void findNthFibonacciNumber(int n){
 Matrix m = Matrix.ADVANCE[1];
 int nSave = n;
 Matrix a = Matrix.IDENTITY;
 while (n != 0){
 if (n%2 == 1){
 a = a.multiply(m).remainder("4294967291"); // 
 }
 m = m.square().remainder("4294967291");
 n/=2;
 }
 System.out.println("value = " + a.b);
 n = nSave;
 }
 }
 public static void main(String[] args){
 String[] inputs = new String[]{"5", "1000000000000000",
 "1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
 };
 for (String input:inputs){
 System.out.println("input = " + input);
 System.out.println(Matrix.findNthFibonacciNumber(new BigDecimal(input)).toPlainString());
 System.out.println();
 }
 }
}

#include <iostream>
using namespace std;
int main()
{
 unsigned long long int n1=0,n2=1,count,i=1;
 cout << "n : ";
 cin >> count;
 if (count == 1 || count ==2) {
 count == 1 ? cout << n1%4294967291 << endl : cout << n2%4294967291 << endl;
 } 
 else {
 do {
 i++;
 n2 += n1; 
 n1 = n2-n1;
 } while (i<count-1);
 cout << n2%4292967291 << endl;
 } 
}

n : 100 -1034348260 이렇게나오는데 이거 해결방법이 좀 알려주세요?