Последняя цифра большого числа Фибоначчи

@IrinaNovikova · Регистрация: 12.05.2015

Author24 — интернет-сервис помощи студентам

Помогите разобраться. Вроде все правильно и ответ правильный, но процесс решения не правильный. Не могу понять, что не так. Уже третий день голову ломаю...
Прохожу курс и там задача. Хочется уже просто понять где косяк.

Дано число 1≤n≤10^7, необходимо найти последнюю цифру n-го числа Фибоначчи.
Как мы помним, числа Фибоначчи растут очень быстро, поэтому при их вычислении нужно быть аккуратным с переполнением. В данной задаче, впрочем, этой проблемы можно избежать, поскольку нас интересует только последняя цифра числа Фибоначчи: если 0≤a,b≤9 — последние цифры чисел Fi и Fi+1 соответственно, то (a+b)mod10 — последняя цифра числа Fi+2.
Sample Input: 560233
Sample Output: 3
Мое решение

C++

#include <cassert>
#include <iostream>
 
class Fibonacci {
 public:
  static int get_last_digit(int n) {
    assert(n >= 1);
    if (n == 0 || n == 1) {
          return n;
      }
      return ((n - 1) + (n - 2))%10;
    return n;
  }
};
 
int main(void) {
  int n;
  std::cin >> n;
  std::cout << Fibonacci::get_last_digit(n) << std::endl;
  return 0;
}

Ilot · 27.11.2015, 08:30

Где-то это уже было https://www.cyberforum.ru/post7965087.html

Байт · 27.11.2015, 10:49

Сообщение от IrinaNovikova

return ((n - 1) + (n - 2))%10;

C++

1	return (get_last_digit(n - 1) + get_last_digit(n - 2))%10;

Однако, использование рекурсии в данном случае опасно из-за возможности переполнения стека. Да, в общем-то, и ни к чему.

@Dimension · 27.11.2015, 11:07

C++

#include <bits/stdc++.h>
using namespace std;
void f(int n) {
    int x = 1, y = 1,z;
    for (int i = 2;i <= n;i++) {
        z = (x + y) % 10;
        x = y;
        y = z;
    }
    cout << z;
}
int main() {
    int n;
    cin >> n;
    f(n);
    return 0;
}

@_Ivana · 27.11.2015, 16:17

Ilot, да в Симпсонах уже все было

- числа Фибоначчи

Байт, в моем коте по ссылке тоже рекурсия - и ничего, все работает. А в коде непосредствено выше, вами оплюсованном - выдает неправильный ответ. (Да, я понимаю, что это вопрос с какого числа считать.)

@IrinaNovikova · 27.11.2015, 20:37 **[ТС]**

Сообщение от Байт

Однако, использование рекурсии в данном случае опасно из-за возможности переполнения стека. Да, в общем-то, и ни к чему.

Да, вы правы выдает ошибку "Failed test #1. Run time error:".
В задаче сказано, что нужно найти последнюю цифру n-го числа Фибоначчи.
Если я правильно понимаю, то грубо говоря нужно найти последнюю цифру числа n, т.е. Input: 560233 и эта цифра ровна 3 (560233). Правильно?
В коде С++ это выражается n%10??
Немного переделала код, но выдает ошибку "Failed test #1. Run time error:". Что делать?

C++

#include <cassert>
#include <iostream>
 
class Fibonacci {
 public:
  static int get_last_digit(int n) {
    assert(n >= 1);
       if (n == 1 || n == 2) {
          return n;
      }
      return get_last_digit (n)%10;
    return n;
  }
};
 
int main(void) {
  int n;
  std::cin >> n;
  std::cout << Fibonacci::get_last_digit(n) << std::endl;
  return 0;
}

Байт · 27.11.2015, 20:42

IrinaNovikova, только я не понимаю, что делает ваш код. Имхо, он толчет воду в ступе, пока ступа не сломается. Посмотрите, что происходит, если на вход функции get_last_digit дать n=3

@IrinaNovikova · 27.11.2015, 20:43 **[ТС]**

Сообщение от Ilot

Где-то это уже было Последняя цифра чисел Фибоначчи

Сказали, что такую формулу нельзя использовать.
"Как минимум, для получения последней цифры больших чисел Фибоначчи нельзя использовать формулу "(((1+5^(1/2))/2)^d - ((1-5^(1/2))/2)^d ) / 5^(1/2)". Вычисления будут крайне неточны и так, разве что, можно получить только несколько первых цифр соответствующего числа Фибоначчи."

@Dimension · 27.11.2015, 20:44

Сообщение от IrinaNovikova

грубо говоря нужно найти последнюю цифру числа n, т.е. Input: 560233 и эта цифра ровна 3 (560233). Правильно?

да ,только вы ерунду какую-то делаете

Байт · 27.11.2015, 20:51

IrinaNovikova, а чем вас не устраивает код из поста 4 ? Он совершенно правильный. Нумерация чисел Фибоначчи там начинается с 0.
А у вас в головке небольшая путаница. Вы понимаете разницу между числом n и n-ным числом Фибоначчи?

@IrinaNovikova · 27.11.2015, 21:06 **[ТС]**

Сообщение от Байт

IrinaNovikova, а чем вас не устраивает код из поста 4 ? Он совершенно правильный. Нумерация чисел Фибоначчи там начинается с 0.
А у вас в головке небольшая путаница. Вы понимаете разницу между числом n и n-ным числом Фибоначчи?

Код из 4 поста меня устраивает, но т.к. я только начала свой путь в С++ (самоучка), то мне еще пока трудно ориентироваться в коде и особенно в чужом. У меня возникают трудности в переводе кода из 4 поста в код программы, который нам дали на курсе. Что-то понимаю, а что-то не особо.

, так что простите, если уж очень туплю.

C++

#include <cassert>
#include <iostream>
 
class Fibonacci {
 public:
  static int get_last_digit(int n) {
    assert(n >= 1);
    // put your code here
    return n;
  }
};
 
int main(void) {
  int n;
  std::cin >> n;
  std::cout << Fibonacci::get_last_digit(n) << std::endl;
  return 0;
}

@AGPro · 09.04.2016, 12:26

Сообщение от Байт

а чем вас не устраивает код из поста 4 ? Он совершенно правильный.

Failed test #1. Wrong answer
Input:
193150
Your output:
9
Correct output:
5

Добавлено через 5 минут
Вот этот правильный:

C++

#include <iostream>
#include <cmath>
long long fibb(long long n) {
    return (std::pow((1 + std::sqrt(5)) / 2 , n) - std::pow((1 - std::sqrt(5)) / 2 , n)) / std::sqrt(5);
}
long long last_number(long long n) {
    return fibb(n % 60) % 10;
}
int main() {
    int num;
    std::cin >> num;
    std::cout << last_number(num) << std::endl;;
}

Ilot · 11.04.2016, 07:26

Не по теме:

AGPro, постыдились бы. Не стоит выдавать чужой код за свой. Даже двойную точку следования в 12 строке не исправили.

zer0mail · 11.04.2016, 10:19

AGPro, а если бы требовалось не одна, а 9 цифр, то какой код правильный?

@razorvaka · 06.02.2019, 21:55

Как добавить диапазон вводимых чисел в данный код. Например от 12 до 10000

Добавлено через 31 секунду

Сообщение от Dimension

C++

#include <bits/stdc++.h>
using namespace std;
void f(int n) {
 int x = 1, y = 1,z;
 for (int i = 2;i <= n;i++) {
 z = (x + y) % 10;
 x = y;
 y = z;
 }
 cout << z;
}
int main() {
 int n;
 cin >> n;
 f(n);
 return 0;
}

Как добавить диапазон вводимых чисел в данный код. Например от 12 до 10000

@easybudda · 17.07.2019, 17:23

Сообщение от IrinaNovikova

найти последнюю цифру n-го числа Фибоначчи

C++

#include <iostream>
#include <cassert>
 
int fibo_tail(int n) {
    int head = 0, tail = 1, sum;
 
    assert(n > 0);
 
    while ( --n ) {
        sum = (head + tail) % 10;
        head = tail;
        tail = sum;
    }
 
    return tail;
}
 
int main() {
    int num;
 
    while ( std::cout << "Fibonacci order number: " && std::cin >> num ) 
        std::cout << "Last digit: " << fibo_tail(num) << std::endl;
    
    return 0;
}

Код

[andrew@andrew numbers]$ g++ -Wall LastFiboDigit.cpp 
[andrew@andrew numbers]$ ./a.out 
Fibonacci order number: 193150
Last digit: 5
Fibonacci order number:

Сообщение от Байт

Нумерация чисел Фибоначчи там начинается с 0

По условию задачи, из которой по легенде и появилась эта последовательность, начинаться с нуля она в принципе не может. Помните наверняка - про кроликов...

Сообщение от AGPro

Вот этот правильный

Только адски медленный. Если нужна последняя цифра, не за чем высчитывать число длиной в километр...

@_Ivana · 22.07.2019, 23:39

Сообщение от easybudda

Только адски медленный.

Все относительно

Например, ваш кот на вход 1000000003 выдает 7 за

Код

Compilation time: 0.43 sec, absolute running time: 4.19 sec, cpu time: 5.5 sec, memory peak: 3 Mb, absolute service time: 4,63 sec

а мой по ссылке выше ту же 7 за

Код

Compilation time: 0.33 sec, absolute running time: 0.07 sec, cpu time: 0.01 sec, memory peak: 3 Mb, absolute service time: 0,41 sec

@AlexVRud · 24.07.2019, 17:47

C++

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]))];
}

@_Ivana · 24.07.2019, 17:51

Тоже класс, все-таки кто-то не поленился и высчитал период

zer0mail 2686 / 2258 / 244 Регистрация: 03.07.2012 Сообщений: 8,219 Записей в блоге: 1
	11.04.2016, 10:19	14
	AGPro, а если бы требовалось не одна, а 9 цифр, то какой код правильный? 0

Ilot $Эксперт по математике/физике$ 2206 / 1411 / 411 Регистрация: 16.05.2013 Сообщений: 3,597 Записей в блоге: 6
	27.11.2015, 08:30	2
	Где-то это уже было https://www.cyberforum.ru/post7965087.html 0

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	27.11.2015, 16:17	5
	Ilot, да в Симпсонах уже все было - числа Фибоначчи Байт, в моем коте по ссылке тоже рекурсия - и ничего, все работает. А в коде непосредствено выше, вами оплюсованном - выдает неправильный ответ. (Да, я понимаю, что это вопрос с какого числа считать.) 0

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	27.11.2015, 20:42	7
	IrinaNovikova, только я не понимаю, что делает ваш код. Имхо, он толчет воду в ступе, пока ступа не сломается. Посмотрите, что происходит, если на вход функции get_last_digit дать n=3 0

@IrinaNovikova 9 / 4 / 0 Регистрация: 12.05.2015 Сообщений: 48
	27.11.2015, 20:43 [ТС]	8
	Сообщение от Ilot Где-то это уже было Последняя цифра чисел Фибоначчи Сказали, что такую формулу нельзя использовать. "Как минимум, для получения последней цифры больших чисел Фибоначчи нельзя использовать формулу "(((1+5^(1/2))/2)^d - ((1-5^(1/2))/2)^d ) / 5^(1/2)". Вычисления будут крайне неточны и так, разве что, можно получить только несколько первых цифр соответствующего числа Фибоначчи." 0

@Dimension Dimension 594 / 462 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	27.11.2015, 20:44	9
	Сообщение от IrinaNovikova грубо говоря нужно найти последнюю цифру числа n, т.е. Input: 560233 и эта цифра ровна 3 (560233). Правильно? да ,только вы ерунду какую-то делаете 0

Байт Диссидент 27707 / 17325 / 3810 Регистрация: 24.12.2010 Сообщений: 38,979
	27.11.2015, 20:51	10
	IrinaNovikova, а чем вас не устраивает код из поста 4 ? Он совершенно правильный. Нумерация чисел Фибоначчи там начинается с 0. А у вас в головке небольшая путаница. Вы понимаете разницу между числом n и n-ным числом Фибоначчи? 0

Ilot
	11.04.2016, 07:26 #13
	Не по теме: AGPro, постыдились бы. Не стоит выдавать чужой код за свой. Даже двойную точку следования в 12 строке не исправили. 0

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	22.07.2019, 23:39	17
	Сообщение от easybudda Только адски медленный. Все относительно Например, ваш кот на вход 1000000003 выдает 7 за Код Compilation time: 0.43 sec, absolute running time: 4.19 sec, cpu time: 5.5 sec, memory peak: 3 Mb, absolute service time: 4,63 sec а мой по ссылке выше ту же 7 за Код Compilation time: 0.33 sec, absolute running time: 0.07 sec, cpu time: 0.01 sec, memory peak: 3 Mb, absolute service time: 0,41 sec 0

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	24.07.2019, 17:51	19
	Тоже класс, все-таки кто-то не поленился и высчитал период 0