Числа Фибоначчи, не могу понять формулу вычисления.
Zkb  -    1705
Скажу сразу, я ни разу не программист и ни черта на разбираюсь в математике, то есть вообще полный ноль. Даже в понятии дискриминант знаю только то как он пишется... буквами. Да, даже формулу не помню. А слово "дробь" вызывает ассоциации только с охотой.
И все бы хорошо, но с недавнего времени малой начал интересоваться программированием. Да-да, я тоже предполагал что это стандартная детская отговорка, чтобы заиметь личный комп. Ну взял, ну думаю извини "рандом" в полку орущих школьников прибыло. Но, нет. Гарнитуру со змиями клянчить не начал, а сидит втыкает всякие туториалы в сети. Тут бы порадоваться, не полным дебилом вырастет. А х*р там!
Все началось с обычных чисел, вечером за ужином. Первой жертвой стала жена, пала она от понятия "действительные числа"(хотя дискриминант вычислять и умеет). Но я то не так прост, на то я и батя! Ретировался значит я в "толкан" и вооружившись гуглом смог отбить первый натиск. Лучше бы я тогда притворился мертвым...

Ладно, что то я затянул с предисловием. Как я понял(по логам истории браузера) он дошел до понятия рекурсия(чтобы это ни значило), и подошел ко мне с вопросом насчет чисел Фибоначчи. А именно с формулой:

F0=0, F1=1, Fn = Fn-1 + Fn-2, n >=2

Привычно захватив свой смартфон я удалился в свой кабинет, на "толкан". И понял что не "втыкаю", т.е. если по моей "логике"(которое я обычно применял на уроках физики) подставить вместо букв числа выходила какая то дичь. Короче просидел я на "толкане" пока жена угрозами не заставила выйти. Благо я успел нагуглить про факториалы, ими и отбился от малого. Но судя по всему малого факториалы мало устроили, я опасаюсь новой атаки и хочу восстановить свои оборонительные рубежи. Так что парни, выручайте)

Чтобы вам проще было понять где в моих суждениях закралась ошибка попробую озвучить ход своих мыслей.

1. Беру формулу Fn = Fn-1 + Fn-2, n >=2
2. Пробую воткнуть туда какое нибудь число из последовательности чисел Фибоначчи. К примеру 8
3. F8 = F8-1 + F8-2, 8>=2
4. F8 = F7 + F6, 8>=2
5. F8 = F13, 8 >=2
6. Вроде все нормально, идем дальше.
7. F13 = F13-1 + F13-2, F13>=2
8. F13 = F12 + F11, F13>=2
9. F13 = F23
10. WTF!? Должно же быть 21.
11. Такая же проблема с другими числами, кроме 8.
12. К примеру: F21 = F21-1+F21-2 = F39, а должно быть 34.

Заранее спасибо за разъяснения, и просьба сильно не макать лицом. Укажите пальцем, сам вытру.

PS: Заранее предупреждая советы отправить малого с вопросами к учителю математики. Всю эту ситуацию я воспринимаю как в своем роде игру, вызов если хотите. В котором судя по всему я в скором времени паду. Но до того момента хотелось бы продержаться самому. Сдаться всегда успеется. Да и какое никакое общение с сыном.
Ответов 26 Написать ответ
  • Alexander_A
    Alexander_A
    Андрей Александров
    8 марта 2017  

    Цитата:
    4. F8 = F7 + F6, 8>=2
    5. F8 = F13, 8 >=2

    F13 = F12 + F11
    F8 = F7 + F6
    Очевидно, что "F7 + F6 != F12 + F11" ("!=" - не равно), соответственно "F13 != F7 + F6"

    0
  • igroman
    8 марта 2017  

    это формула последовательности чисел фибоначи
    Fn = Fn-1 + Fn-2
    Fn-1=1
    Fn-2=1
    2=1+1
    3=2+1
    5=3+2
    8=5+3
    13=8+5
    21=13+8
    ...
    рекурсия это когда функция обращается сама к себе пока не будет выполнено условие

    Цитата:

    for (n=1; n>=2; n++) {
    f[n] = f[n-1] + f[n-2];
    print f[n];
    }

    примерно как то так себе представляю
    поиск без знания предыдущих числе будет посложнее

    0
  • igroman
    8 марта 2017  

    ошибочка
    for (n=0; n>=2; n++) {
    f[n] = f[n-1] + f[n-2];
    print f[n];
    }

    0
  • Andre
    8 марта 2017  

    Все достаточно запущено. Думаю малой кровью в этой битве не обойдется.

    Предлагаю помимо гугляндекса почитать литературу, пора переходить к глубокоэшелонированной затяжной обороне. Поскольку я сам отец и могу только позавидовать такой тяге ребенка, постараюсь помочь. Для начала скачай эти книжки:
    http://sup-winzpl.pusku.com/str003_02.html
    Это не учебники, книжки для детей. Прошу не обижаться и не плеваться, но там действительно в доходчивой форме описываются азы математики, а без них дальше уже ни куда. Все описано достаточно понятно и даже интересно. Дело в том, что без элементарных знаний и понятия первичных определений дальше уже не двинуться, а я или кто-либо еще, наверное не всегда и не очень быстро смогут ответить на вопросы. Про чиста Фибоначчи в "Искателях необычайных автографов", глава "Числа и кролики". Почему кролики? Потому что Фибоначчи открыл свою последовательность, пытаясь высчитать сколько у него наплодится кроликов.

    По теме. Я сам удивился, когда моему ребенку во втором классе задали определить следующий член последовательности, не объяснив при этом, что такое последовательность и в чем ее суть. Я не устаю плеваться на современную методику преподавания, но возможно ты учился уже по новой программе, поэтому начнем с самого начала. Так вот числовая последовательность - это набор чисел, каждое из которых пронумеровано и подчиняется какой-то закономерности (иногда очень запутанной). Числа в последовательности принято обозначать fn, где n - порядковый номер числа в последовательности, а не само число, а fn-1, fn+1 - это предыдущее и соответственно следующее число.
    Самым простом примером числовой последовательности является натуральный ряд. Здесь само число всегда равно его порядковому номеру (Fn = n), т.е. 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16.......и до бесконечности. Но это частный случай. В варианте с числами Фибоначчи каждый член последовательности, старше второго, равен сумме двух предыдущих, а первые два члена равны 1 и 1,
    Складывать нужно не номера чисел, а сами числа. Вот последовательность чисел Фибоначчи:
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181....до бесконечности. Тут важно понять, что первое число - единица, второе - тоже единица, а третье равно уже сумме первого и второго, т.е. двум. Четвертое равно сумме третьего и второго (1+2=3). Т.е. складывать нужно не порядковые номера чисел, а сами числа. Да с тринадцатью получаем коллизию, но она единственная во всей этой последовательности. Действительно, здесь номера членов последовательности в суме дают 13 (6+7=13) и сумма F7 + F6 = 5+8 = 13, но это не 13-й член последовательности, а восьмой (просто посчитай по порядку).

    В твоем примере с попыткой посчитать 13-е число Фибоначчи ( F13 = F13-1 + F13-2) берем не порядковый номер (13), а число под этим номером! Это 233 (не 13), числа F13-1 и F13-2, это не 12 и 11, а числа из последовательности с номерами 11 и 12, т.е. 89 и 144, а 89+144=233.

    Не уверен, что все доходчиво получилось, если не понятно почитай про кроликов, ссылку дал выше, там Лёвшин (человек с талантом объяснять сложные вещи простыми словами) все по полочкам разложил.

    0
    • Zkb
      10 марта 2017  

      Andre, огромное спасибо!!!
      Только благодаря вашим разъяснениям я смог понять где допустил ошибку.

      Цитата:
      fn, где n - порядковый номер числа в последовательности, а не само число

      Цитата:
      Складывать нужно не номера чисел, а сами числа

      Эта формула практически не давала мне покоя последние несколько дней. Сколько информации в сети я перелопатил, везде одинаковая сухая копипаста, ну или формулы еще "страшней" чем "моя") Математика это прямо иной язык!

      На всякий случай повторно изложу "исправленный" ход своих мыслей, мало ли...

      Скрытый текст

      0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
      F0, F1, F2, F3, F4, F5, F6, F7, F8, F9, F10, F11 , F12, F13, F14 , F15, F16, F17, F18, F19, F20, F21


      13 + 8
      F7 + F6
      F8= (F8-1)+(F8-2)
      F8= 21

      или

      987 + 610
      F16 + F15
      F17=(F17-1)+(F17-2)
      F18=1597


      PS: У меня остался ещё один "маленький" вопрос. В своих суждениях Fn я использовал как некую ссылку на определенное и известное мне число Фибоначчи. А как комп решает данную задачу? Он же не может как я заранее знать ответы на выражения. Неужто он каждый раз чтобы вычислить определенное число Фибоначчи вычисляет предыдущие? Не слишком ли трудозатратно?

      0
      • Alexander_A
        Alexander_A
        Андрей Александров
        10 марта 2017  

        Цитата:
        А как комп решает данную задачу? Он же не может как я заранее знать ответы на выражения.

        Zkb, число Фибоначчи можно вычислить возведением матрицы в степень.

        0
      • Andre
        10 марта 2017  

        А сколько лет ребенку?

        Существует три основных метода компьютерного расчета чисел Фибоначчи. Первый - линейный, это когда тупо считает нужное число до тех пор, пока не дойдет до n., начиная с самого начала.
        Второй - рекурсия, на числах Фибоначчи почему-то любят объяснять, как использовать рекурсию в программировании. Хотя по мне, так линейный метод проще и надежнее.
        Ну и третий, я уже не помню как это технически решается (и вспоминать, если честно,совершенно нет желания), с использованием матриц. Это уже численные методы, высшая математика, поэтому и спрашиваю сколько лет ребенку.
        В принципе первые два метода технически не сложные, если про задачку про автомат он сам решил, то и с Фибоначчи справится.

        P.S. Простите за нескромность, но любопытство заело. Каким образом жителя Нижнего Новгорода заинтересовал интернет-ресурс Якутии?

        0
    • Zkb
      10 марта 2017  

      Andre, а и да, книжки я скачал. От их объема у меня слегка отвисла челюсть, но на досуге почитаю.

      0
  • Andre
    8 марта 2017  

    Если удалось разобраться с числами Фибоначчи, предлагаю нанести контрудар.

    Думаю ребнку такая задача понравится:

    Цитата:
    Нам с Единичкой захотелось выпить чего-нибудь прохладительного, и мы отправились в буфет-автомат. Но не тут-то было! В этом буфете действовали какие-то странные правила. Вдоль стены сверкал эмалью и никелем ряд автоматов со всевозможными напитками. Опусти жетон — и пей на здоровье. В этом, конечно, нет ничего странного. Ничего странного не было и в том, что для каждого автомата полагался жетон, помеченный его номером. Странными были сами номера, написанные на автоматах.
    У первого автомата номер был, разумеется, 1. Зато у следующего — номер 4, затем 13, потом следовал номер 40, потом — 121… Что за чушь! Это уж не порядок, а беспорядок номеров!
    Единичка перепробовала напитки из автоматов под номерами 1, 4, 13, 40 и 121. Но ни один из них ей не понравился. Ей захотелось наполнить стакан из того автомата, который стоял сразу за номером 121. Но, к сожалению, номер над щелью этого автомата стёрся. (Наверное, от частого употребления — там был действительно вкусный напиток.)
    Я предложил Единичке выбрать какой-нибудь другой автомат.
    — Зачем другой? — удивилась Единичка. — Тут же всё ясно. Неужели вы не догадались, какой номер должен стоять после 121-го?
    Я стал гадать: 1, 4, 13, 40, 121… Что же дальше? Пока я раздумывал, Единичка уже опустошила свой стакан и тут же взяла ещё один жетон для меня, но опустила его в щель, так и не показав мне. Вот озорница!

    Владимир Левшин
    Путевые заметки рассеянного магистра



    Здесь заранее ответ, только сыну сразу не показывай, пусть сначала сам попробует:
    Скрытый текст
     — Леди и джентльмены, в честь новой победы президента предлагаю поднять бокалы с фруктовым соком!
    — Принято единогласно, — быстро сказал президент. — Вот и палатка недалеко…
    — Фи, сэр! — Сева с притворным ужасом закатил глаза. — Какая палатка?! Уж если пить сок, так из тех автоматов, о которых сказано у Магистра.
    Нулик надулся:
    — Воображаемые автоматы… Воображаемый сок…
    — Будет и настоящий. Дай только разобраться, каким номером был помечен автомат, стоявший после автомата под номером 121. Единичка — та сразу догадалась…
    Сева искоса посмотрел на Таню.
    — Всё дело в закономерности, — отозвалась она. — Номера автоматов — 1, 4, 13, 40 и 121. Надо выяснить, по какому закону возрастают эти числа. Попробуем вычислить разность между ними: 4–1=3, 13-4=9, 40–13=27 и 121-40=81. Здесь сразу бросается в глаза, что первая разность 3 всё время повторяется в последующих числах, но уже возведённая в степень. Сначала это 3 в квадрате (9), потом 3 в кубе (27), потом 3 в четвёртой степени (81). И вот уже перед нами довольно стройная картина: единицу можно рассматривать как 3 в нулевой степени; 4 — как единицу плюс три в первой степени. Прибавим к четырём три, взятое во второй степени (то есть 9), получим 13; затем прибавим к 13 три, взятое в третьей степени (то есть 27), получим 40…
    — А затем, — перебил Нулик (ему не терпелось показать, что он всё понял), — прибавим к 40 три в четвёртой степени, то есть 81, и получим 121. Значит, для следующего числа надо к 121 прибавить 3, взятое в пятой степени, то есть 243. 121+243=364. Вот какой номер стоял на очередном автомате.
    — Молодчина! — Таня погладила президента по взъерошенному затылку. — Может, скажешь, как решить эту задачу по-другому?
    — А разве можно?
    — Представь себе, можно. Чтобы получить любое число этого ряда, надо предыдущее умножить на три и прибавить единицу. Умножь 121 на три и прибавь единицу — получишь 364.
    — Что ж, — подытожил я, — Таня разобралась в этом вопросе ничуть не хуже Единички. А посему двинулись дальше.

    0
    • Zkb
      10 марта 2017  

      Andre, судя по всему мой контрудар оказался провальным. Спустя некоторое время, мне "это" скинули ватсапом:

      static void Main(string[] args)
      {
      int n1=1, n2=1;
      for (int i=0;i<5;i++)
      {
      int n3 = n1 + n2 * 3;
      n2 = n3;
      }
      Console.WriteLine("{0}", n2);
      Console.ReadKey();
      }

      В этом бою силы крайне неравны) Что это?

      0
      • Andre
        10 марта 2017  

        А кто скинул?

        Это программа, которая считает номер жетона из задачки.

        0
      • Борщ
        10 марта 2017  

        Zkb, это неправильно работающий говнокод на языке C#. Экспериментируй лучше на Python: он читабельные и легче для новичка (основы изучить очень легко: пару часов достаточно с абсолютного нуля). Скачай интерпретатор Python (бесплатно) и смотри видеоуроки на youtube. Вот код для твоей задачи:

        f = [0, 1]
        n = int(input('Введите кол-во чисел n = '))
        for i in range(2, n): f.append(f[i-1] + f[i-2])
        print(f)

        0
  • Борщ
    8 марта 2017  

    Цитата:
    4. F8 = F7 + F6, 8>=2
    5. F8 = F13, 8 >=2

    Ну, мужик, ты даешь :D

    Числа Фибоначчи давай без формул попробую объяснить, мб так легче воспримешь.
    первое число = 0
    второе число = 1
    третье число = второе число + первое число
    четвертое число = третье число + второе число
    пятое = четвертое + третье

    ну ты понял...

    Есть способ занять ум пацана как минимум на несколько дней. Загрузи малого задачкой о "грациозности деревьев". Формулировка предельно простая, можно объяснить младшекласснику. Только тссс, что эту гипотезу пока еще никто не смог доказать.
    https://ru.wikipedia.org/wiki/Грациозная_разметка

    0
    • Zkb
      10 марта 2017  

      Борщ, извините, видимо вы не до конца поняли мой вопрос. Логика последовательности чисел Фибоначчи мне понятна, я просто не мог скажем так правильно"прочитать" формулу. Но к моему облегчению данный вопрос для меня закрыт. Тем не менее благодарю за попытку помочь.

      0
  • тупойкачок
    8 марта 2017  

    скажи малому что он теперь умней тебя, но в жизни это мало поможет, потому что ты ему по жопке можешь надавать, а он тебе не может, поэтому пусть лучше качает бицепс

    0
    • Zkb
      10 марта 2017  

      тупойкачок, я бы не стал отвечать на этот комментарий если бы не одно забавное обстоятельство.
      Меня глубоко удивил тот факт, что мысли "тупого качка"(без обид, вы так сами представились) совпадают с мыслями моей жены(видимо еще не отошла от поражения). Ответом вам приведу наш(с женой разумеется) диалог:

      (не могу вспомнить дословно, но общий посыл был таков)

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

      0
  • prism
    10 марта 2017  

    я не стал читать все что написано сверху просто покажу как считается число фиб-чи.
    и так 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 вот первые числа фиб-чи
    делаем ф-ии

    #include <stdio.h>

    unsigned int fib(int n){
    if (n==0) return 0;
    if (n==1) return 1;
    else return (fib(n-1)+fib(n));
    return 0;
    }

    int main()
    {
    for (int i:=0;i<10;i++)
    printf("%d\n",fib(i));

    return 0;
    }

    то есть для вычисления по рекурсии нужно просто учитывать что первые 2 числа это 0 и 1

    0
    • joyful
      10 марта 2017  

      prism, при больших числах, из-за большого количества рекурсивных входов, стек будет переполняться.
      Поэтому лучше вот так:

      int fib_n(int n)
      {
          //F(n-2)
          int x = 1;
          //F(n-1)
          int y = 0;
          //F(n)
          int ans;
          for (int i = 1; i <= n; i++)
          {
              ans = x + y;
              x = y;
              y = ans;
          }
          return ans;
      }

      0
      • Alexander_A
        Alexander_A
        Андрей Александров
        10 марта 2017  

        joyful, там быстрее int уйдет в минус, чем стек переполнится.
        Но если рассматривать конкретно приведенный код, стек бы переполнился уже при n=3, потому что код зацикливается "else return (fib(n-1)+fib(n))". Но не переполнится, потому что не скомпилируется "for (int i:=0;i<10;i++)" =)

        0
        • prism
          10 марта 2017  

          else return (fib(n - 1) + fib(n - 2));
          вот так должно быть ошибся
          и объявления int i видимо путаю с каким то языком где можно объявлять где нужно

          0
  • madman
    14 марта 2017  

    Чего то сложно как то вы пишите :)
    Вот на Свифте в одну строку функцию можно описать (для положительных):

    func fib(_ n: Int) -> Int {
    return n < 2 ? n : fib(n - 1) + fib(n - 2)
    }

    0
    • Alexander_A
      Alexander_A
      Андрей Александров
      14 марта 2017  

      madman, и чем отличается от c++?
      int fib(int n){return n < 2 ? n : fib(n - 1) + fib(n - 2);}

      0
      • madman
        14 марта 2017  

        Alexander_A, я про примеры которые до этого приводили, а не про то что на другом языке так нельзя сделать.

        0
  • JoaAssiple
    13 марта  

    test

    ololo

    0
Ответ на тему: Числа Фибоначчи, не могу понять формулу вычисления.
Введите код с картинки*:  Кликните на картинку, чтобы обновить код
grinning face grinning face with smiling eyes face with tears of joy smiling face with open mouth smiling face with open mouth and smiling eyes smiling face with open mouth and cold sweat smiling face with open mouth and tightly-closed eyes smiling face with halo smiling face with horns winking face smiling face with smiling eyes face savouring delicious food relieved face smiling face with heart-shaped eyes smiling face with sunglasses smirking face neutral face expressionless face unamused face face with cold sweat pensive face confused face confounded face kissing face face throwing a kiss kissing face with smiling eyes kissing face with closed eyes face with stuck-out tongue face with stuck-out tongue and winking eye face with stuck-out tongue and tightly-closed eyes disappointed face angry face pouting face crying face persevering face face with look of triumph disappointed but relieved face frowning face with open mouth anguished face fearful face weary face sleepy face tired face grimacing face loudly crying face face with open mouth face with open mouth and cold sweat face screaming in fear astonished face flushed face sleeping face dizzy face face without mouth face with medical mask face with no good gesture face with ok gesture person bowing deeply person with folded hands raised fist raised hand victory hand white up pointing index fisted hand sign waving hand sign ok hand sign thumbs up sign thumbs down sign clapping hands sign open hands sign flexed biceps
  
Обратная связь
Предложения и замечания