1 2 3 4 5 6 7 |
int fibo_tail(int n) { int fs[] = {0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1}; return fs[n % (sizeof(fs) / sizeof(fs[0]))]; } |
Given a number ‘n’, write a function that prints the last digit of n’th (‘n’ can also be a large number) Fibonacci number.
Examples :
Input : n = 0 Output : 0 Input: n = 2 Output : 1 Input : n = 7 Output : 3
Method 1 : (Naive Method)
Simple approach is to calculate the n’th Fibonacci number and printing the last digit.
C++
#include <bits/stdc++.h>
using
namespace
std;
typedef
long
long
int
ll;
void
multiply(ll F[2][2], ll M[2][2]);
void
power(ll F[2][2], ll n);
ll fib(
int
n)
{
ll F[2][2] = {{1, 1}, {1, 0}};
if
(n == 0)
return
0;
power(F, n - 1);
return
F[0][0];
}
void
power(ll F[2][2], ll n)
{
if
(n == 0 || n == 1)
return
;
ll M[2][2] = {{1, 1}, {1, 0}};
power(F, n / 2);
multiply(F, F);
if
(n % 2 != 0)
multiply(F, M);
}
void
multiply(ll F[2][2], ll M[2][2])
{
ll x = F[0][0] * M[0][0] +
F[0][1] * M[1][0];
ll y = F[0][0] * M[0][1] +
F[0][1] * M[1][1];
ll z = F[1][0] * M[0][0] +
F[1][1] * M[1][0];
ll w = F[1][0] * M[0][1] +
F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
int
findLastDigit(
int
n)
{
return
fib(n) % 10;
}
int
main()
{
ll n = 1;
cout << findLastDigit(n) << endl;
n = 61;
cout << findLastDigit(n) << endl;
n = 7;
cout << findLastDigit(n) << endl;
n = 67;
cout << findLastDigit(n) << endl;
return
0;
}
Java
class
GFG
{
static
long
fib(
long
n)
{
long
F[][] =
new
long
[][] {{
1
,
1
}, {
1
,
0
}};
if
(n ==
0
)
return
0
;
power(F, n -
1
);
return
F[
0
][
0
];
}
static
void
multiply(
long
F[][],
long
M[][])
{
long
x = F[
0
][
0
] * M[
0
][
0
] +
F[
0
][
1
] * M[
1
][
0
];
long
y = F[
0
][
0
] * M[
0
][
1
] +
F[
0
][
1
] * M[
1
][
1
];
long
z = F[
1
][
0
] * M[
0
][
0
] +
F[
1
][
1
] * M[
1
][
0
];
long
w = F[
1
][
0
] * M[
0
][
1
] +
F[
1
][
1
] * M[
1
][
1
];
F[
0
][
0
] = x;
F[
0
][
1
] = y;
F[
1
][
0
] = z;
F[
1
][
1
] = w;
}
static
void
power(
long
F[][],
long
n)
{
if
( n ==
0
|| n ==
1
)
return
;
long
M[][] =
new
long
[][] {{
1
,
1
}, {
1
,
0
}};
power(F, n /
2
);
multiply(F, F);
if
(n %
2
!=
0
)
multiply(F, M);
}
long
findLastDigit(
long
n)
{
return
(fib(n) %
10
);
}
public
static
void
main(String[] args)
{
int
n;
GFG ob =
new
GFG();
n =
1
;
System.out.println(ob.findLastDigit(n));
n =
61
;
System.out.println(ob.findLastDigit(n));
n =
7
;
System.out.println(ob.findLastDigit(n));
n =
67
;
System.out.println(ob.findLastDigit(n));
}
}
Python3
def
fib(n):
F
=
[[
1
,
1
], [
1
,
0
]];
if
(n
=
=
0
):
return
0
;
power(F, n
-
1
);
return
F[
0
][
0
];
def
multiply(F, M):
x
=
F[
0
][
0
]
*
M[
0
][
0
]
+
F[
0
][
1
]
*
M[
1
][
0
];
y
=
F[
0
][
0
]
*
M[
0
][
1
]
+
F[
0
][
1
]
*
M[
1
][
1
];
z
=
F[
1
][
0
]
*
M[
0
][
0
]
+
F[
1
][
1
]
*
M[
1
][
0
];
w
=
F[
1
][
0
]
*
M[
0
][
1
]
+
F[
1
][
1
]
*
M[
1
][
1
];
F[
0
][
0
]
=
x;
F[
0
][
1
]
=
y;
F[
1
][
0
]
=
z;
F[
1
][
1
]
=
w;
def
power(F, n):
if
( n
=
=
0
or
n
=
=
1
):
return
;
M
=
[[
1
,
1
], [
1
,
0
]];
power(F,
int
(n
/
2
));
multiply(F, F);
if
(n
%
2
!
=
0
):
multiply(F, M);
def
findLastDigit(n):
return
(fib(n)
%
10
);
n
=
1
;
print
(findLastDigit(n));
n
=
61
;
print
(findLastDigit(n));
n
=
7
;
print
(findLastDigit(n));
n
=
67
;
print
(findLastDigit(n));
C#
using
System;
class
GFG
{
static
long
fib(
long
n)
{
long
[,]F =
new
long
[,] {{1, 1}, {1, 0}};
if
(n == 0)
return
0;
power(F, n - 1);
return
F[0, 0];
}
static
void
multiply(
long
[,]F,
long
[,]M)
{
long
x = F[0, 0] * M[0, 0] +
F[0, 1] * M[1, 0];
long
y = F[0, 0] * M[0, 1] +
F[0, 1] * M[1, 1];
long
z = F[1, 0] * M[0, 0] +
F[1, 1] * M[1, 0];
long
w = F[1, 0] * M[0, 1] +
F[1, 1] * M[1, 1];
F[0, 0] = x;
F[0, 1] = y;
F[1, 0] = z;
F[1, 1] = w;
}
static
void
power(
long
[,]F,
long
n)
{
if
( n == 0 || n == 1)
return
;
long
[,]M =
new
long
[,] {{1, 1}, {1, 0}};
power(F, n / 2);
multiply(F, F);
if
(n % 2 != 0)
multiply(F, M);
}
static
long
findLastDigit(
long
n)
{
return
(fib(n) % 10);
}
public
static
void
Main()
{
int
n;
n = 1;
Console.WriteLine(findLastDigit(n));
n = 61;
Console.WriteLine(findLastDigit(n));
n = 7;
Console.WriteLine(findLastDigit(n));
n = 67;
Console.WriteLine(findLastDigit(n));
}
}
PHP
<?php
function
fib(
$n
)
{
$F
=
array
(
array
(1, 1),
array
(1, 0));
if
(
$n
== 0)
return
0;
power(
$F
,
$n
- 1);
return
$F
[0][0];
}
function
multiply(&
$F
, &
$M
)
{
$x
=
$F
[0][0] *
$M
[0][0] +
$F
[0][1] *
$M
[1][0];
$y
=
$F
[0][0] *
$M
[0][1] +
$F
[0][1] *
$M
[1][1];
$z
=
$F
[1][0] *
$M
[0][0] +
$F
[1][1] *
$M
[1][0];
$w
=
$F
[1][0] *
$M
[0][1] +
$F
[1][1] *
$M
[1][1];
$F
[0][0] =
$x
;
$F
[0][1] =
$y
;
$F
[1][0] =
$z
;
$F
[1][1] =
$w
;
}
function
power(&
$F
,
$n
)
{
if
(
$n
== 0 ||
$n
== 1)
return
;
$M
=
array
(
array
(1, 1),
array
(1, 0));
power(
$F
, (int)(
$n
/ 2));
multiply(
$F
,
$F
);
if
(
$n
% 2 != 0)
multiply(
$F
,
$M
);
}
function
findLastDigit(
$n
)
{
return
(fib(
$n
) % 10);
}
$n
= 1;
echo
findLastDigit(
$n
) .
"n"
;
$n
= 61;
echo
findLastDigit(
$n
) .
"n"
;
$n
= 7;
echo
findLastDigit(
$n
) .
"n"
;
$n
= 67;
echo
findLastDigit(
$n
) .
"n"
;
Javascript
<script>
function
fib(n)
{
let F = [[1, 1], [1, 0]];
if
(n == 0)
return
0;
power(F, n - 1);
return
F[0][0];
}
function
multiply(F, M)
{
let x = F[0][0] * M[0][0] +
F[0][1] * M[1][0];
let y = F[0][0] * M[0][1] +
F[0][1] * M[1][1];
let z = F[1][0] * M[0][0] +
F[1][1] * M[1][0];
let w = F[1][0] * M[0][1] +
F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
function
power(F, n)
{
if
( n == 0 || n == 1)
return
;
let M = [[1, 1], [1, 0]];
power(F, parseInt(n / 2, 10));
multiply(F, F);
if
(n % 2 != 0)
multiply(F, M);
}
function
findLastDigit(n)
{
return
(fib(n) % 10);
}
let n;
n = 1;
document.write(findLastDigit(n) +
"</br>"
);
n = 61;
document.write(findLastDigit(n) +
"</br>"
);
n = 7;
document.write(findLastDigit(n) +
"</br>"
);
n = 67;
document.write(findLastDigit(n));
</script>
Output:
1 1 3 3
Complexity: O(Log n).
Limitation of this implementation:
Fibonacci numbers grow exponentially fast. For example, the 200’th Fibonacci number equals 280571172992510140037611932413038677189525. And F(1000) does not fit into the standard C++ int type.
To overcome this difficulty, instead of calculating n’th Fibonacci number, there is a direct algorithm to just calculate its last digit (that is, F(n) mod 10).
Method 2 : (Direct Method)
Look at the final digit in each Fibonacci number – the units digit:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
Is there a pattern in the final digits?
0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, ...
Yes!
It takes a while before it is noticeable. In fact, the series is just 60 numbers long and then it repeats the same sequence again and again all the way through the Fibonacci series – for ever. The series of final digits repeats with a cycle length of 60 (Refer this for explanations of this result).
So, instead of calculating the Fibonacci number again and again, pre-compute the units digit of first 60 Fibonacci number and store it in an array and use that array values for further calculations.
C++
#include<bits/stdc++.h>
using
namespace
std;
typedef
long
long
int
ll;
ll fib(ll f[], ll n)
{
f[0] = 0;
f[1] = 1;
for
(ll i = 2; i <= n; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
return
f[n];
}
int
findLastDigit(
int
n)
{
ll f[60] = {0};
fib(f, 60);
return
f[n % 60];
}
int
main ()
{
ll n = 1;
cout << findLastDigit(n) << endl;
n = 61;
cout << findLastDigit(n) << endl;
n = 7;
cout << findLastDigit(n) << endl;
n = 67;
cout << findLastDigit(n) << endl;
return
0;
}
Java
class
GFG
{
void
fib(
int
f[])
{
f[
0
] =
0
;
f[
1
] =
1
;
for
(
int
i =
2
; i <=
59
; i++)
f[i] = (f[i -
1
] + f[i -
2
]) %
10
;
}
int
findLastDigit(
long
n)
{
int
f[] =
new
int
[
60
];
fib(f);
int
index = (
int
)(n % 60L);
return
f[index];
}
public
static
void
main(String[] args)
{
long
n;
GFG ob =
new
GFG();
n =
1
;
System.out.println(ob.findLastDigit(n));
n =
61
;
System.out.println(ob.findLastDigit(n));
n =
7
;
System.out.println(ob.findLastDigit(n));
n =
67
;
System.out.println(ob.findLastDigit(n));
}
}
Python3
def
fib(f, n):
f[
0
]
=
0
;
f[
1
]
=
1
;
for
i
in
range
(
2
, n
+
1
):
f[i]
=
(f[i
-
1
]
+
f[i
-
2
])
%
10
;
return
f;
def
findLastDigit(n):
f
=
[
0
]
*
61
;
f
=
fib(f,
60
);
return
f[n
%
60
];
n
=
1
;
print
(findLastDigit(n));
n
=
61
;
print
(findLastDigit(n));
n
=
7
;
print
(findLastDigit(n));
n
=
67
;
print
(findLastDigit(n));
C#
using
System;
class
GFG {
static
void
fib(
int
[]f)
{
f[0] = 0;
f[1] = 1;
for
(
int
i = 2; i <= 59; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
}
static
int
findLastDigit(
long
n)
{
int
[]f =
new
int
[60];
fib(f);
int
index = (
int
)(n % 60L);
return
f[index];
}
public
static
void
Main()
{
long
n;
n = 1;
Console.WriteLine(findLastDigit(n));
n = 61;
Console.WriteLine(findLastDigit(n));
n = 7;
Console.WriteLine(findLastDigit(n));
n = 67;
Console.WriteLine(findLastDigit(n));
}
}
PHP
<?php
function
fib(&
$f
,
$n
)
{
$f
[0] = 0;
$f
[1] = 1;
for
(
$i
= 2;
$i
<=
$n
;
$i
++)
$f
[
$i
] = (
$f
[
$i
- 1] +
$f
[
$i
- 2]) % 10;
return
$f
[
$n
];
}
function
findLastDigit(
$n
)
{
$f
=
array_fill
(0, 60, 0);
fib(
$f
, 60);
return
$f
[
$n
% 60];
}
$n
= 1;
print
(findLastDigit(
$n
) .
"n"
);
$n
= 61;
print
(findLastDigit(
$n
) .
"n"
);
$n
= 7;
print
(findLastDigit(
$n
) .
"n"
);
$n
= 67;
print
(findLastDigit(
$n
) .
"n"
);
?>
Javascript
<script>
function
fib(f)
{
f[0] = 0;
f[1] = 1;
for
(let i = 2; i <= 59; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
}
function
findLastDigit(n)
{
let f =
new
Array(60);
f.fill(0);
fib(f);
let index = (n % 60);
return
f[index];
}
let n;
n = 1;
document.write(findLastDigit(n) +
"</br>"
);
n = 61;
document.write(findLastDigit(n) +
"</br>"
);
n = 7;
document.write(findLastDigit(n) +
"</br>"
);
n = 67;
document.write(findLastDigit(n) +
"</br>"
);
</script>
Output:
1 1 3 3
Complexity: O(1).
This article is contributed by Rahul Agrawal .If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Last Updated :
09 Dec, 2021
Like Article
Save Article
Есть задача «Требуется найти последнюю цифру n-го числа Фибоначчи.» по адресу http://acmp.ru/?main=task&id_task=623
Мое решение такое ( не знаю насколько этично выкладывать код решения в паблик )
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int a=1, b=1, c=a+b, n;
cin >> n;
if (n <= 1)
c = 1;
else
for (int i = 2; i <= n; i++){
c = (a + b) % 10;
a = b;
b = c;
}
cout << c % 10;
return 0;
}
Результат: Время выполнения 0,858 Память 772 Кб
Согласно таблице на странице http://acmp.ru/index.asp?main=bstatus&id_t=623&lang=CPP за счет небольшого увеличения расхода памяти как то умудряются вложиться в 1-2 секунды. С одной стороны может быть мне подсунули входное число 1000, а другим 10.
Есть идеи по повышению производительности?
Harry
214k15 золотых знаков117 серебряных знаков229 бронзовых знаков
задан 2 ноя 2015 в 19:04
4
Очевидные простые улучшения:
- Можно заменить взятие остатка на сравнение с 10 и вычитание 10 (т. к. результат гарантированно меньше 20). По идее, операция деления более тяжёлая.
- Можно подсчитать lookup-таблицу
(a, b) -> c
, она по идее небольшая. Но вряд ли двойной lookup будет существенно быстрее пары сложений/вычитаний. - Алгоритмическое улучшение: поскольку следующий член последовательности зависит лишь от двух предыдущих, то последовательность обязательно зациклится. Причём поскольку всего пар цифр не более 100, длина цикла не более 100. Найдите заранее длину цикла (отдельной программой), теперь число
n
можно брать по модулю длины цикла. - Комбинируя 2 и 3, можно подсчитать заранее ответы для
n
от 0 до 99, и согласно 3 этого достаточно. Итого решение за O(1).
ответ дан 2 ноя 2015 в 19:38
VladDVladD
206k27 золотых знаков289 серебряных знаков521 бронзовый знак
4
Цитата из википедии
Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность: 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)
В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
Что такое период Пизано понятно из таблицы для π(4):
n | 1 2 3 4 5 6 | 7 8 9 ...
F(n) | 0 1 1 2 3 5 | 8 13 21 ...
F(n) mod 4 | 0 1 1 2 3 1 | 0 1 1 ...
То есть π(4) = 6, а именно: остатки от деления чисел Фибоначчи на 4 повторяются с периодом 6.
Как это применить для решения задачи подумайте сами.
ответ дан 3 ноя 2015 в 8:11
CerboCerbo
6,8532 золотых знака23 серебряных знака43 бронзовых знака
Возводя матрицу
1 1
1 0
В степень бинарным возведением, беря ее элементы по модулю 10, можно решать эту задачу за O(logN).
Даже можно не ограничиваться модулем 10.
ответ дан 4 ноя 2015 в 19:50
Тут выше уже написали, но самой лучшей оптимизацией будет именно использование матрицы, а точнее возведение ее в степень того номера, который ищите. Про реализацию можете ознакомиться на хабре, там на питоне все очень понятно.
С теоретическим обоснованием можете ознакомиться в книге Д.Кнута, где, собственно, впервые и приводится объяснение эффективности решения
ответ дан 9 ноя 2015 в 9:38
LescottLescott
3231 золотой знак3 серебряных знака10 бронзовых знаков
Untitled
a guest
Apr 17th, 2019
1,398
0
Never
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
-
«»»
-
Задача на программирование: последняя цифра большого числа Фибоначчи.
-
Дано число 1≤n≤10e7, необходимо найти последнюю цифру n-го числа Фибоначчи.
-
Как мы помним, числа Фибоначчи растут очень быстро, поэтому при их вычислении нужно быть аккуратным с переполнением. В данной задаче, впрочем, этой проблемы можно избежать, поскольку нас интересует только последняя цифра числа Фибоначчи: если 0≤a,b≤9 — последние цифры чисел Fi и Fi+1 соответственно, то (a+b)mod10 — последняя цифра числа Fi+2.
-
«»»
-
def fib_digit(n):
-
prev, cur = 0, 1
-
for _ in range(n — 1):
-
prev, cur = cur % 10, (prev + cur) % 10
-
return cur
-
def main():
-
n = int(input())
-
print(fib_digit(n))
-
if __name__ == «__main__»:
-
main()
-
«»»
-
Задача на программирование повышенной сложности: огромное число Фибоначчи по модулю.
-
Даны целые числа 1≤n≤10e18 и 2≤m≤10e5, необходимо найти остаток от деления n-го числа Фибоначчи на m.
-
«»»
-
n, m = map(int, input().split())
-
period = [0, 1]
-
i = 2
-
while i < m * 6:
-
period.append((period[i — 1] + period[i — 2]) % m)
-
if period[i] == 1 and period[i — 1] == 0:
-
break
-
i += 1
-
print(period[n % (len(period) — 2)])
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(Время: 2 сек. Память: 16 Мб Сложность: 23%) | |
Вам наверняка знакомы числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21… Они определяются рекуррентным соотношением: Fn = Fn-1 + Fn-2, F0 = F1 = 1. | |
Требуется найти последнюю цифру n-го числа Фибоначчи. | |
Входные данные | |
Во входном файле INPUT.TXT содержится одно целое число n (0 ≤ n ≤ 108). | |
Выходные данные | |
В выходной файл OUTPUT.TXT необходимо вывести одно число — последнюю цифру числа Fn. | |
def f(n): | |
if n == 0: | |
return 1 | |
elif n == 1: | |
return 1 | |
else: | |
f1 = 1 | |
f2 = 1 | |
for i in range(1, n): | |
f = (f1 + f2) % 10 | |
f1 = f2 | |
f2 = f | |
return f | |
def main(): | |
input_file = open(«input.txt», «r») | |
output_file = open(«output.txt», «w») | |
line = input_file.readline().split() | |
n = int(line[0]) | |
ans = f(n) | |
print(ans) | |
sr = str(ans) | |
answ = sr[-1] | |
output_file.write(str(answ) + ‘n’) | |
input_file.close() | |
output_file.close() | |
if __name__ == «__main__»: | |
main() |