피보나치 수열 구하기 #2
피보나치 수열이란, 첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다. 예) 0, 1, 1, 2, 3, 5, 8, 13
피보나치 수열의 n번째 수를 4,294,967,291으로 나누었을 때의 나머지를 출력하는 프로그램을 작성하시오.
정수 n이 입력으로 주어진다. (1 <= n <= 10^100000)
Sample input
5
Sample output
3
Sample input #2
1000000000000000
Sample output #2
3010145777
39개의 풀이가 있습니다.
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
-2
이게 정답이었군요 numpy 와 decimal 행렬은 쓸일이 없어 전혀 생각도 못하고 있었는데...
-
Lee SeungChan,
2014/10/27 13:37
승찬님 해법도 답을 낸다면 바른 방법일 것 같네요. 아마 점화식으로부터 직접 일반식을 유도하면 아래 식이 나오나 봐요.
-
Kim Jaeju,
2014/10/27 19:56
-1
f(0) = f(-2)+f(-1) = f(-3)+2f(-2) = 2f(-4)+3f(-3) = 3f(-5)+5f(-4) = 5f(-5)+8f(-4) ....
1 / 1 1 / 1 2 / 2 3 / 3 5 / 5 8 / 이런식으로 피보나치 수열이 다시 나오는것에 착안해보니
n이 짝수일때 f(n/2)^2+ f(n/2+1)^2 이 나왔고 홀수일때의식은 여기서 파생시켜보았습니다.
-
Lee SeungChan,
2014/10/29 14:04
#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
BigInteger를 사용해 보세요.
-
pahkey,
2015/02/23 09:58
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 이렇게나오는데 이거 해결방법이 좀 알려주세요?
Sub Main()
Dim n As Integer = CInt(Console.ReadLine())
Dim cnt As Integer = 0
Dim r As New BigInteger(0), rr As New BigInteger(1)
For i = 1 To n - 1
r += rr
rr = r - rr
Next
Dim rm As New BigInteger
BigInteger.DivRem(r, 4294967291, rm)
Console.WriteLine(rm)
Console.ReadLine()
End Sub
Ruby
최대범위를 테스트하지 않아 확인해보니 10**10000 즈음에 stack overflow 났었네요. 재귀를 until로 바꿨습니다.
require 'matrix'
pow = ->m,n { n==1? m : (pow[m,n>>1]**2).map{|_|_%4294967291} * (n&1==1?m:1) }
fibs = ->n,base=Matrix[[1,1],[1,0]] { pow[base,n][1,1] }
until로 변경.
fib = ->n { n-=1; lim=4294967291; v=m=Matrix[[1,1],[1,0]]
(m,v=(m**2).map{|_|_%lim},n&1==1?(v*m).map{|_|_%lim}:v; n>>=1) until n<1; v[1,1] }
Perfomance
Benchmark.bm do |x|
(1..5).map {|n| x.report("10**(10**#{n}): ") { fib[10**(10**n)] } }
end
user system total real
10**(10**1): 0.000000 0.000000 0.000000 ( 0.000987)
10**(10**2): 0.010000 0.000000 0.010000 ( 0.006730)
10**(10**3): 0.060000 0.000000 0.060000 ( 0.064498)
10**(10**4): 0.580000 0.000000 0.580000 ( 0.588893)
10**(10**5): 9.200000 0.160000 9.360000 ( 9.363661)
Test
expect(fib[1]).to eq 0
expect(fib[5]).to eq 3
expect(fib[10**(10**1)]).to eq 2839099801
expect(fib[10**(10**2)]).to eq 2537702751
expect(fib[10**(10**3)]).to eq 4011928622
expect(fib[10**(10**4)]).to eq 217086569
expect(fib[10**(10**5)]).to eq 1853287988
C#으로 작성했습니다.
public BigInteger FindFibonacciRemainder(int n)
{
BigInteger first = 0;
BigInteger second = 1;
BigInteger divider = 4294967291;
for (int i = 2; i < n; i++)
{
var temp = first;
first = second;
second = BigInteger.Add(temp, first);
}
return BigInteger.Remainder(second, divider);
}
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
public ulong CodingDojang070(long n)
{
ulong a = 0;
ulong b = 1;
ulong result = 0;
for(long i = 1; i <= n/2; i++)
{
a += b;
b += a;
Console.WriteLine(a);
Console.WriteLine(b);
}
if( n % 2 == 1)
{
result = b;
}
else
{
result = a;
}
return result% 4294967291;
}
쉬울거라 생각하고 이렇게 했는데.. n값이 조금만 커져도 제대로 답이 안나오네요 윗분들이 행렬등등 쓰신거보고 진작에 눈치챘어야 했음..--
C로 했더니 범위초과 문제가 있네요 ㅠ.ㅠ
일반적으로 fib을 작성하면..
int fib(int n) {
if (n < 2) return n;
return fib(n-1) + fib(n-2);
}
그런데, 이러면 너무 느리니까..
int fib(int n) {
int a = 0, b = 1, temp;
while (n-- > 0) {
temp = b;
b = a + b;
a = temp;
}
return a;
}
그런데 이것도 O(n)이니까 다른 분들의 풀이처럼 행렬 지수승으로 표시하고 이걸 다시 제곱 지수 계산으로 O(log n)을 만들어야죠.
우선 행렬로..
typedef struct mat {
int a, b, c, d;
} mat;
int fib(int n) {
mat m = {1,1,1,0};
mat x = mexp(m, n);
return x.b;
}
mat mexp(mat m, int n) {
mat x = {1,0,0,1}; // identity matrix
while (n-- > 0) {
x = mmul(x, m);
}
return x;
}
mat mmul(mat a, mat b) {
mat x = {a.a * b.a + a.b * b.c,
a.a * b.b + a.b * b.d,
a.c * b.a + a.d * b.c,
a.c * b.b + a.b * b.d};
return x;
}
이제 mexp(m,n)는 n이 짝수면 m제곱을 n/2승하고, 홀수면 m제곱의 n/2승에 m을 한번더 곱해주면 됩니다.
mat mexp(mat m, int n) {
mat x = {1,0,0,1};
while (n > 0) {
if (n % 2 == 1) {
x = mmul(x, m);
}
m = mmul(m, m);
n /= 2;
}
return x;
}
여기까지면 되는데 문제가 요구하는 값의 범위가 mmul()에서 초과하게 되니까 여기서 나머지 연산을 넣어주면 됩니다.
그래도 계속 넘어서.. 결국은 신경 안써도 되는 Haskell을 써서..
먼저 fib을 정의하면..
fib 1 = 0
fib n = let (_,x,_,_) = exp (1,1,1,0) n in x
exp는 이미 고민한 것과 같으므로..
exp _ 0 = (1,0,0,1)
exp m 1 = m
exp m n
| even n = exp (mul m m) (n `div` 2)
| otherwise = mul m (exp (mul m m) (n `div` 2))
mul은 문제가 요구하는 나머지만 유지..
m = 4294967291
mul (a,b,c,d) (e,f,g,h) =
let (w,x,y,z) = (a*e + b*g, a*f + b*h, c*e + d*g, c*f + d*h)
in (w `mod` m, x `mod` m, y `mod` m, z `mod` m)
#include <stdio.h>
void main( void )
{
int n;
double i, a = 0, b = 1;
scanf("%d", &n);
for( i = 1; i < n; i++ ) {
a += b;
b = a-b;
}
printf("%0.f\n", fmod(a, 4294967291));
return 0;
}
피보나치 수열을 재귀를 제외하고도 2가지 풀이 방법이 있다는 것을 다른 풀이들을 보고 알게됬습니다.~
#include <stdio.h>
#include <math.h>
struct matrix
{
double v[4];
};
matrix mul(matrix a, matrix b);
matrix pow(matrix a, int k);
void main() {
matrix m;
m.v[0] = 1;
m.v[1] = 1;
m.v[2] = 1;
m.v[3] = 0;
m = pow(m, n-1);
printf("0.f", fmod( m.v[1], 4294967291));
}
matrix pow(matrix a, int k) {
matrix r = a;
for(int i=0;i<k;i++)
r = mul(r, a);
return r;
}
matrix mul(matrix a, matrix b) {
matrix ret;
ret.v[0] = a.v[0] * b.v[0] + a.v[1] * b.v[2];
ret.v[1] = a.v[0] * b.v[1] + a.v[1] * b.v[3];
ret.v[2] = a.v[2] * b.v[0] + a.v[3] * b.v[2];
ret.v[3] = a.v[2] * b.v[1] + a.v[3] * b.v[3];
return ret;
}
#include <stdio.h>
#include <math>
void main( void )
{
int n;
double i, a = 0, b = 1;
scanf("%d", &n);
for( i = 1; i < n; i++ ) {
a += b;
b = a-b;
}
printf("%0.f\n", fmod(a, 4294967291));
return 0;
}
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)
import java.math.BigInteger;
public class test {
final static long DIVISOR = 4294967291L;
static long fib(String S) {
if (S == "1") {
return 0L;
}
BigInteger N = new BigInteger(S);
long t1 = 0L;
long t2 = 1L;
for (BigInteger i = new BigInteger("3"); i.compareTo(N) <= 0; i = i.add(BigInteger.ONE)) {
long t3 = (t1 + t2) % DIVISOR;
t1 = t2;
t2 = t3;
}
return t2;
}
public static void main(String[] args) {
System.out.println(fib("5"));
System.out.println(fib("1000000000000000"));
}
}
생각만큼 느리진 않은데.. 왜 답이 틀릴까요T.T
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)
m번째 피보나치 수를 n으로 나눈 나머지를 구할때 피보나치 수를 n으로 나눈 나머지의 주기성을 이용하도록 했습니다. n이 합성수일때는 조금 개선하여 중국인의 나머지정리를 통해 더 빠르게 실행이 가능할 것 같습니다. 하지만 이 문제의 경우 4294967291이 상당히 큰 소수이며, pisano(4294967291)이 매우 커서 시간이 오래걸립니다.
def fibonaccimod(m, n):
def pisano(n):
def searchplace(a, b):
place = 0
c = math.ceil(len(a) / 2)
if not (len(a) - 1):
if a[0] < b:
place += 1
elif b < a[c]:
place += searchplace(a[:c], b)
else:
place += searchplace(a[c:], b) + c
return place
result = [(0%n, 1%n, 0)]
result2 = [(0%n, 1%n, 0)]
last = (0%n, 1%n, 0)
for i in range(n*n):
last = (last[1], (last[0]+last[1])%n, i+1)
place = searchplace(result, last)
result.insert(place, last)
result2.append(last)
if result[place][:2] == result[place-1][:2]:
return result[place][2]-result[place-1][2], result[place-1][2], result2
a = pisano(n)
m = (m-a[1])%a[0]+a[1]
return a[2][m-1][0]
def fibo(n):
div = 4294967291
a={1:0,2:1, 3:1}
i=3
print(n)
#print(i,n)
if n<=3:
return [a[n-1], a[n]]
while i<n:
a[2*(i-1)-2]=(a[i-2]*a[i-2]+a[i-1]*a[i-1])%div
a[2*(i-1)-1]=(a[i-2]*a[i-1]+a[i-1]*a[i])%div
a[2*(i-1)]=(a[i-1]*a[i-1]+a[i]*a[i])%div
#print(i, n, a)
i=(i-1)*2
i=i//2+1
if (n == 2*(i-1)) or (n==2*(i-1)-1):
return [a[n-1], a[n]]
re=fibo(n-i+2)
return [(re[0]*a[i-2]+re[1]*a[i-1])%div,(re[0]*a[i-1]+re[1]*a[i])%div]
print(a[i])
fibo(1000000000000000)[1]
#include <stdio.h>
#include<stdlib.h>
long long multi(long long a, long long b) {
long long re, div = 4294967291;
re = a;
for (long long i = 0; i < (long long)(b / 10000000); i++) {
re = re+a * 10000000 % div;
}
re = re+a * (((long long)b-1) % 10000000) % div;
return re;
}
long long* fibo(long long n) {
long long div = 4294967291;
long long index=3;
long long a[3] = {0, 1, 1}, temp[6];
long long * resu = malloc(sizeof(long long)*2);
printf("%lld\n", n);
if (n == 3) {
resu[0] = a[1];
resu[1]= a[2];
return resu;
}
else if (n == 2) {
resu[0] = a[0];
resu[1] = a[1];
return resu;
}
else if (n == 1) {
resu[0] = 0;
resu[1] = 0;
return resu;
}
while (index < n) {
temp[0] = (multi(a[0], a[0]) + multi(a[1],a[1])) % div;
//printf("%lld : %lld\n", index, temp[0]);
temp[1] = (multi(a[0], a[1]) + multi(a[1], a[2])) % div;
temp[2] = (multi(a[1], a[1]) + multi(a[2], a[2])) % div;
index = (index - 1) * 2;
temp[3] = a[0];
temp[4] = a[1];
temp[5] = a[2];
a[0] = temp[0];
a[1] = temp[1];
a[2] = temp[2];
}
index = (index / 2) + 1;
if ((n == (2 * (index - 1))) ) {
resu[0] = temp[1];
resu[1] = temp[2];
return resu;
}
else if (n == (2 * (index - 1) - 1)) {
resu[0] = temp[0];
resu[1] = temp[1];
return resu;
}
long long* re;
re = fibo(n - index + 2);
resu[0] = (multi(re[0] ,temp[3]) + multi(re[1] , temp[4]) ) % div;
resu[1] = (multi(re[0] , temp[4]) + multi(re[1],temp[5]) ) % div;
return resu;
}
int main() {
long long n;
n = 1000000000000000;
long long * f;
f = fibo(n);
printf("%lld", f[1]);
free(f);
return 0;
}
import java.util.Scanner;
import java.math.BigInteger;
public class Na{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
BigInteger a = new BigInteger("0");
BigInteger b = new BigInteger("1");
BigInteger c = new BigInteger(a.add(b)+"");
int i;
long n = sc.nextLong();
i = 2;
while(i <= n){
a = b;
b = c;
c = a.add(b);
i++;
}
BigInteger d = new BigInteger("4294967291");
BigInteger e = new BigInteger(c.remainder(d)+"");
if(n == 1)
System.out.println("1");
else if(n == 2)
System.out.println("2");
else
System.out.println(e);
}
}
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
long n = sc.nextInt();
long f0 = 0;
long f1 = 1;
long f = 0;
for (long i=0; i<n; i++) {
if (n == 1) {
f = 1;
break;
}
if (i == n-1) break;
f = f1 + f0;
f1 = f0;
f0 = f;
}
System.out.println(f % 4294967291l);
} // long으로 했는데도 음수 나오넹
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
int count = 1,sum =0;
vector<int> v;
v.push_back(0); v.push_back(1);
cin >> n;
for (int i = 0; i <= n; i++)
{
sum = v[count - 1] + v[count];
v.push_back(sum);
}
cout << v[n]% 4294967291;
}
def mul2x2(a,b,c):
return ((a[0]*b[0] + a[1]*b[2])%c
, (a[0]*b[1] + a[1]*b[3])%c
, (a[2]*b[0] + a[3]*b[2])%c
, (a[2]*b[1] + a[3]*b[3])%c)
def fibo(n,c):
a = [1,1,1,0]
s = []
tmp = a[:]
while n > 1:
s.append((n>>1,n&1))
n = n>>1
while s:
if s.pop()[1]: a = mul2x2(mul2x2(a,a,c),tmp,c)
else: a = mul2x2(a,a,c)
return a[3]
print(fibo(1000000000000000,4294967291))
해쉬태이블 사용 및 재귀함수
h_table={'0':0,'1':0,'2':1}
def fibo(n,h_table):
if str(n) in h_table:
return h_table[str(n)]
else:
h_table[str(n)] = (fibo(n-1,h_table) + fibo(n-2,h_table))
return h_table[str(n)]
input_value = int(input())
print(fibo(input_value,h_table))
print(fibo(input_value,h_table)%4294967291)
%피보나치 수열,matlab 사용
n=input('수 입력: ');
a(1)=0;%첫번째항
a(2)=1;%두번째항
for i=3:n
a(i)=a(i-1)+a(i-2);%피보나치수열 점화식
if i==n
r=rem(a(i),4294967291);%나머지 구하기
fprintf('%d번째 피보나치의 수의 나머지: %d\n',n,r);
break
end
end
fprintf('\n')
python
n = int(input('1 이상의 정수를 입력하세요 (1 <= n <= 10**100000)> '))
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
if n >= 2:
return fib(n-1) + fib(n-2)
fib(n) % 4294967291 # n+1 번째 수를 4,294,967,291으로 나누었을 때의 나머지
recursion을 이용하여 피보나치 수열을 생성하는 함수를 만들었는데... python은 recursion의 횟수가 제한되어있네요...
그래서 상당히 큰 수를 입력하면 한도횟수 초과라는 error가 뜨면서 답이 나오지 않습니다... 이게 좀 아쉽군요...
maximum = int(input())
count = 0
a, b = 0, 1
box = []
while count < maximum:
if count == 0:
box.append(a)
elif count == 1:
box.append(b)
else:
box.append(box[count - 2] + box[count - 1])
count += 1
print(box)
def Fibo(num):
first=0
last=1
for i in range(num):
temp=last
last+=first
first=temp
return first
In=int(input("Sample input\n"))
fibo=Fibo(In-1)
print(fibo%4294967291)
def fibonach(n) :
a0 = 0
a1 = 1
an = 0
for i in range(n-2) :
an = a0 + a1
a0 = a1
a1 = an
return an
n = int(input())
print(fibonach(n)%4294967291)
def pivo(n):
a0=0
a1=1
k = 2
if n==1:
return 0
elif n==2:
return 1
else:
while True:
k+=1
a2=a0+a1
a0=a1
a1=a2
if k==n:
return a2
break
while True:
n =int(input("피보나치 수열의 n번쨰수 "))
if n>= 1 and n<=10**100000:
break
if pivo(n)<4294967291:
print(pivo(n))
else:
print(pivo(n)%4294967291)
연산속도가 최악인 코드가 나왔네요.. 최적화를 좀더 고민해봐야 될거 같습니다
def fibonacci(a,b,step, mod):
for _ in range(step-1):
a, b = b, (a+b)%mod
return (a, b)
#value = 5
value = 1000000000000000
step = 1000000
mod = 4294967291
a, b = 0, 1
if value > step:
f = fibonacci(0, 1, step-2, mod)
a, b = f[0], f[1]
value -= step
while value >= 100000:
step = 100000
f = fibonacci(0, 1, step, mod)
f0, f1 = f[0], f[1]
curr = 0
while value >= curr+step:
a, b = (a*f0 + b*f1)%mod, (a*f1 + b*(f0+f1))%mod
f0, f1 = (f0*f0 + f1*f1)%mod, (f0*f1 + f1*(f0+f1))%mod
curr += step
step *= 2
value -= curr
else:
value -= 3
ef = fibonacci(a, b, value+2, mod)
print(ef[1]) # 3010145777