Code-Live.ru

Портал о программировании

Ряд Фибоначи в цикле, помогите понять

Ребят, поясните плиз,желательно графически,этот пример нахождения в цикле члена ряда Фибоначи. Попытался читая книгу выполнить на бумаге цикл, ничего не понял. Запутался окончательно.
Вот код и описание из книги:

5: #include <iostream.h>
6:
7:
8: int fib(int position);
9: 
10: int main()
11: {
12:    int answer, position;
13:    cout << "Which position? ";
14:    cin >> position;
15:    cout << "\n";
16:
17:    answer = fib(position);
18:    cout << answer << " is the ";
19:    cout << position << "Fibonacci number.\n";
20:    return 0;
21: }
22:
23: int fib(int n)
24: {
25:    int minusTwo=1, minusOne=1, answer=2;
26:
27:    if (n < 3)
28:      return 1;
29:
30:    for (n -= 3; n; n--)
31:    {
32:      minusTwo = minusOne;
33:      minusOne = answer;
34:      answer = minusOne + minusTwo;
35:    }
36:
37: return answer;
38: }

"В строке 13 пользователю предлагается ввести порядковый номер искомого члена ряда Фибоначчи. Для нахождения этого значения используется функция fib(), в качестве параметра которой передается введенный порядковый номер. Если он меньше трех, функция возвращает значение 1. Для вычисления значений, порядковый номер которых превышает 2, используется приведенный ниже алгоритм.
1. Пpиcвaивaютcянaчaльныeзнaчeнияпepeмeнным:minusTwo=1, minus0ne=1, answer=2. Значение переменной, содержащей номер искомой позиции, уменьшается на 3, поскольку две первые позиции обрабатываются выше.
2. Для каждого значения n вычисляем значение очередного члена последовательности. Делается это следующим образом:
• переменной minusTwo присваивается значение переменной minusOne;
• переменной minusOne присваивается значение переменной answer;
• значения переменных minusOne и minusTwo суммируются и записываются в answer;
• значение n уменьшается на единицу.
3. Как только n достигнет нуля, возвращается значение переменной answer.
Следуя описанному алгоритму, можно воспроизвести на листе бумаги ход выполнения программы. Для нахождения, к примеру, пяти первых членов последовательности на первом шаге записываем
1, 1, 2,
Остается определить еще два члена ряда. Следующий член будет равен (2+1=3), а для вычисления искомого члена теперь нужно сложить значения только что полученного члена и предыдущего — числа 2 и 3, в результате чего получаем 5. В сущности, на каждом шаге мы смещаемся на один член вправо и уменьшаем количество искомых значений.
"

Как для меня не очень понятным языком описано.
Все понятно, кроме тела функции))

Заранее спасибо.

Пояснить графически у меня вряд ли получится — ascii-art'ом никогда не увлекался. Попробую словами ))

Ряд Фибоначчи начинается с 1, 1 (члены ряда с номерами 1 и 2). Это отрабатывает оператор 

27:    if (n < 3)
28:      return 1;

Следующий член ряда (номер 3) — 2. Цикл for (n -= 3; n; n--) {...} не выполняется ни разу, поскольку при инициализации цикла n становится равным 0: при вызове ф-ции n = 3, после n -= 3 становится равным 0, условие продолжения цикла ложно, цикл не выполняется. Этот хитрый for эквивалентен
for (int i = n - 3; i != 0; i--) { ... }. Поскольку цикл не выполняется, то ф-ция возвращает значение answer, полученное при инициализации, т.е. 2.

Далее, для следующих членов ряда (член номер 4 и далее) переменные minusTwo и minusOne в цикле «скользят» по членам ряда. Как известно, следующий член ряда Фибоначчи является суммой двух предыдущих членов. Вышеозначенные переменные и являются этими двумя предыдущими членами: minusOne — предыдущим, а minusTwo — пред-предыдущим. Соответственно answer — текущий вычисленный член ряда. Здесь

31:    {
32:      minusTwo = minusOne;
33:      minusOne = answer;
34:      answer = minusOne + minusTwo;
35:    }

в строке 32 minusTwo сдвигается на следующий член, в строке 33 minusOne также сдвигается на следующий член, который был вычислен на предыдущей итерации цикла, и в строке 34 вычисляется новый член ряда. Так они и бегут по ряду: «паровозик» — answer, и за ним два вагончика minusOne и minusTwo.

Соответственно, когда счётчик (переменная n) обнулится, цикл завершится, а переменная answer будет содержать член ряда с нужным порядковым номером.

PS. Какой удод написал книгу? Код в общем нормальный, но описание кода меня просто убило. Яркий пример того, как не надо писать комментарии к коду.

Кстати, 5: #include <iostream.h> — сомнительно, что будет работать. Должно быть 5: #include <iostream>. Видимо автор использовал совсем древнюю версию STL. using namespace std; — туда же.

Да и для цикла я бы не стал заворачивать такое: модификация переменной при инициализации цикла и неявное приведение значения целой переменной к логическому значения в условии продолжения цикла. Оно, конечно, круто, в духе C времён Кернигана & Ричи, но лучше придерживаться более понятного стиля написания кода, тем более в учебнике. IMHO.

PPS. Интересно, почему здесь, на code-live, почти ни кто не пользуется отладчиком? Религия не позволяет?

А можно всю эту музыку записать и ещё короче (и современнее):

#include <iostream>

using namespace std;

int fib(int position);

int main()
{
    int position;
    cout << "Which position? ";
    cin >> position;
    cout << "\n";

    cout << fib(position) << " is the " << position << " Fibonacci number.\n";
    return 0;
}

int fib(int n)
{
    int minusTwo, minusOne = 1, answer = 1;

    for (int i = n - 3; i >= 0 ; i--)
    {
        minusTwo = minusOne;
        minusOne = answer;
        answer = minusOne + minusTwo;
    }

    return answer;
}

Cпасибо! Немного разъясняется. Только непонятно это:
«Соответственно, когда счётчик (переменная n) обнулится, цикл завершится, а переменная answer будет содержать член ряда с нужным порядковым номером.»
У нас же «for (int i = n — 3; i != 0; i--)» где n — начальное значение счетчика. Оно проверяется только один раз, при первом «чтении» цикла. Далее работают только условие продолжения цикла и декремент.
То есть, допустим, нужно найти член ряда под номером 7.
for(int i = 7 — 3; i != 0; i--) или for(int i = 4; i != 0; i=4)

Первый проход цикла:
minusTwo =1
minusOne =2
answer = 1+2 (3)
сработал декремент i=3

Второй проход цикла:
for(int i = 4; i != 0; i=3)
minusTwo =2
minusOne =3
answer = 2+3 (5)
сработал декремент i=2

Третий проход цикла:
for(int i = 4; i != 0; i=2)
minusTwo =3
minusOne =5
answer = 3+5 (8)
сработал декремент i=1

Четвертый проход цикла:
for(int i = 4; i != 0; i=1)
minusTwo =5
minusOne =8
answer = 5+8 (13)
сработал декремент i=0

Пятый проход цикла:
for(int i = 4; i != 0; i=0)
Условия не соблюдается. Цикл не выполняется. Возвращается значение answer.

7 член ряда Фибоначи = 13.

Правильно я расписал работу цикла?

PS. Какой удод написал книгу?
ЛИБЕРТИ Д.

PPS. Интересно, почему здесь, на code-live, почти ни кто не пользуется отладчиком?
то за отладчик? Мне религия позволяет пользоваться всем, для изучения С++ !!!

Цикл расписал правильно.

Только непонятно это:
«Соответственно, когда счётчик (переменная n) обнулится, цикл завершится, а переменная answer будет содержать член ряда с нужным порядковым номером.»

«Это» относится к оператору for в виде for (n -= 3; n; n--).

PS. Какой удод написал книгу?
ЛИБЕРТИ Д.

В печку её, Зина, сейчас же! (с) проф. Преображенский

Из книг рекомендую:

  • Х. Дейтел, П. Дейтел. Как программировать на C++.
  • Полный справочник по C++. Герберт Шилдт.
  • Н.Джосьютис. С++ Стандартная библиотека. Для профессионалов.

Поищи в сети.

Отла́дчик (деба́ггер, англ. debugger) — компьютерная программа, предназначенная для поиска ошибок в других программах, ядрах операционных систем, SQL-запросах и других видах кода. Отладчик позволяет выполнять трассировку, отслеживать, устанавливать или изменять значения переменных в процессе выполнения кода, устанавливать и удалять контрольные точки или условия остановки и т.д. — цитата из Википедии.

Если ты пользуешься IDE, то поищи в меню слова «Отладка». «Debug», «Debugger». Если ты придерживаешься старой школы, то отладчик должен быть в виде отдельного приложения либо в комплекте компилятора, либо (возможно) как утилита твоей ОС.

Как правило, отладчик позволяет установить по исходному тексту отлаживаемой программы «точки останова» (breakpoint) в которых выполнение программы прерывается и управление передаётся отладчику (или IDE). Из-под отладчика можно выполнять программу в пошаговом режиме, т.е. оператор за оператором. Можно посмотреть и (иногда) изменить значения переменных и содержимое областей памяти. Можно... в общем, «можно» ещё много чего. Конкретные «можно» зависят от самого отладчика и языка программирования.

Спасибо за инфу о отладчике. Я использую компилятор MinGW. Ну иногда и от Microsoft Visual, но тут стандарт 2011 не полностью поддерживается.

В печку пока не брошу)) Мне нравится доступность объяснения языка, ну правда есть моменты кривые, как с этим рядом Фибоначи и циклом. Там есть еще пример этого ряда с рекурсивной функцией, так вроде все понятно написано. + есть еще домашки.
Пробовал еще читать Страуструпа — очень тяжело написано, для продвинутых. Пока отложил.

Спасибо за рекомендуемую литературу, непременно скачаю.

В MinGW есть отладчик gdb. Если используешь MinGW с CodeBlocks или Dev-C++ — лучше использовать доступ к отладчику через IDE.

Стандарт C++11 — от Лукавого.

В Visual Studio тоже есть свой отладчик. Кстати гораздо удобнее, чем CodeBlocks и Dev-C++. Впрочем, дело вкуса.

Книга Х. Дейтел, П. Дейтел. Как программировать на C++ тоже написана очень понятным языком, почему и стоит в списке первой. Плюс упражнения для самопроверки с ответами, плюс упражнения без ответов, плюс врезки-советы:

  • Типичная ошибка программирования
  • Хороший стиль программирования
  • Совет по повышению эффективности
  • Замечание по технике программирования
  • Замечание по мобильности

Страуструп в чтении тяжеловат. Согласен. Но изучение C++ без Страуструпа — как научный коммунизм без чтения Ленина )).

Череп, какие отзывы о Стивене Пратта «Язык программирования С++»?

Alf, я читал немного, ничем не отличается от обычной книги.

Cranium, вашу фразу про изучение С++ без Страуструпа я распечатаю и повешу на стену :)

А где же исходники и, все-таки, ответы к Дейтелу???

Полагаю, что исходники находятся на CD, который продаётся вместе с книгой ;-)

А ответы... К примеру, глава 3: на стр. 241 есть «Упражнения для самопроверки», а на стр. 244 есть «Ответы на упражнения для самопроверки», а далее, со стр. 247 идут упражнения без ответов в количестве 59 штук.

А чего там реально полезного?

Variadic template, decltype, noexcept, constexpr, универсальная инициализаци, поддержка многопоточности, семантика перемещения. Мало?

Для начала, оговорюсь, что реально фичи стандарта C++11 я не использовал, поскольку (а) не было жизненной необходимости и (б) под рукой нет компилятора с полной реализацией стандарта '11. Поэтому данная дискуссия для меня является больше теоретической, что не уменьшает её ценности ))

Ещё одна оговорка: я никого не призываю и не агитирую использовать или не использовать новые возможности языка. Всё строго IMHO.

Преамбула

Тезис 1. По моему глубокому убеждению, язык программирования должен быть понятным для программиста.

Т.е. человек должен легко понимать что и как происходит в любом месте программного кода. В противном случае отладка и сопровождение кода становится проблематичной.

С каждым следующим стандартом С++ текст программ становится всё менее удобопонимаемым. А в некоторых конструкциях вообще сложно представить что происходит на самом деле, поскольку детали реализации скрыты в недрах иерархии мозгодробительных шаблонных классов. В итоге приходится полагаться на мастерство авторов STL, а в комментарии к собственному коду писать сакраментальную фразу «Так надо, Вася!».

Тезис 2. Язык программирования должен быть прост, логичен и непротиворечив.

На мой взгляд, с течением времени C++ становится похожим на коллекцию костылей. Причём костылей стандартизованных. По моему интуитивному ощущению, развитие C++ идёт в неправильном направлении.

Шаблоны и иже с ними

Шаблоны — зло. Также, как и макросы. Изначально, идея была достаточно аппетитная (как и то самое яблочко): с помощью препроцессора реализовать первичный уровень абстракции на уровне программного кода. За более чем сорокалетнюю историю (начиная с С), примитивные макросы эволюционировали в «язык над языком» полный по Тьюрингу, вплоть до того, что некоторые [ненормальные] программисты стали писать на нём программы, например «крестики-нолики».

Шаблоны, в том виде, как они сейчас реализованы в C++ противоречат тезисам 1 и 2.

Введение variadic template, decltype, auto и пр. только усугубляют ситуацию.

Вопрос на засыпку: какой тип у f?

int c = 0;
decltype((c)) f;

constexpr — костыль, облегчающий жизнь только компилятору.

Семантика перемещения

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

Универсальная инициализация

Тоже вещь вроде полезная. Но реализация... Я вообще плохо понимаю этот приём: вводить в язык новые синтаксические конструкции за реализацию которых отвечают библиотечные шаблоны (в данном случае initializer_list<T>). Т.е. STL становится частью языка?

Поддержка многопоточности

Редкостное по красоте собрание костылей, замешанное на шаблонах и завязанное на STL. После прочтения пары статей на Хабре, лично у меня нет никакого желания использовать этот механизм.

Поддержка многопоточности на уровне языка — это здорово. Но реализовано должно быть как-то по другому.

Мало?

For-цикл по коллекции Такой цикл будет работать и, например, с C-like массивами, т.к. C++11 вводит искусственно для них необходимые псевдометоды (begin, end и некоторые другие). (с) Википедия

Замечательно! Что там ещё C++11 вводит неявно?

Лямбда-функции Идея хорошая, но опять реализация подкачала. Нелогичный и неудобоваримый синтаксис. Впрочем указатели на функции в нетривиальных случаях ни чуть не лучше...

Идентификаторы override и final имеют специальное значение только при использовании в определённых ситуациях. В остальных случаях они могут использоваться в качестве нормальных идентификаторов (например, как имя переменной или функции). (c) Википедия

Ключевые слова, которые как бы и не ключевые. Маразм крепчал?

Не всё так печально

Однако есть и светлые стороны. Немного, но есть.

  • Регулярные выражения
  • nullptr
  • Расширение применения ключевого слова explicit на операторы преобразования
  • Перечисления со строгой типизацией

Вопрос на засыпку: какой тип у f?

int c = 0;
decltype((c)) f;

int &

Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.

Ответить

Вы можете использовать разметку markdown для оформления комментариев и постов. Используйте функцию предпросмотра для проверки корректности разметки.

Пожалуйста, оформляйте исходный код в соответствии с правилами разметки. Для того, чтобы вставить код в комментарий, скопируйте его в текстовое поле ниже, после чего выделите то, что скопировали и нажмите кнопку «код» в панели инструментов. Иначе ваш код может принять нечитаемый вид.

Либо производите оформление кода вручную, следующим образом:

``` #include <iostream> using namespace std; int main() { // ... } ```

Предпросмотр сообщения

Ваше сообщение пусто.