поиск чисел фибоначи рекурсией, я нечего непонел и незнаю с чего начать помогите |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
поиск чисел фибоначи рекурсией, я нечего непонел и незнаю с чего начать помогите |
maksimla |
Сообщение
#1
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
Фибоначчо числа можно общетать рекурсией. Рекурсивные запросы можно увидить как на двоичном дереве
Можно увидить что некоторые Фибоначчо числа находят несколько раз, что это неэфективно. Напишите функцию на которой каждое фибоначчи число было рекурсивно общитано только один раз о его значение будущим высчитываниям было держано в массиве. непонел что надо зделать и какие значения будут в функцию поступать -------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
volvo |
Сообщение
#2
|
Гость |
Смотри, что от тебя требуется: сначала пишем обычную рекурсивную функцию, результат работы которой показан в твоем посте:
function fib_1(n: integer): integer; Запускаем ее, и смотрим, что творится: Цитата result = calculating fib_1(7) Видишь, сколько вызовов происходит впустую? А теперь - твоя задача: имея массив, написать такую рекурсивную функцию(с теми же самыми параметрами, функция, вычисляющая Фибоначчи, всегда принимает одно число, и возвращает результат), которая будет брать значение из массива, если оно уже вычислено, тем самым избавляясь от повторных вызовов функции. Вот что выдает моя функция:calculating fib_1(6) calculating fib_1(5) calculating fib_1(4) calculating fib_1(3) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(1) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(3) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(1) calculating fib_1(4) calculating fib_1(3) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(1) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(5) calculating fib_1(4) calculating fib_1(3) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(1) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(3) calculating fib_1(2) calculating fib_1(1) calculating fib_1(0) calculating fib_1(1) 13 Цитата result = calculating fib(7) Чувствуешь, насколько меньше вычислений производится, насколько разгружается стек?calculating fib(6) calculating fib(5) calculating fib(4) calculating fib(3) calculating fib(2) calculating fib(1) calculating fib(0) calculating fib(1) calculating fib(2) calculating fib(3) calculating fib(4) calculating fib(5) 13 А вот как она выглядит - я пока не покажу тебе... Попробуй подумать сам. |
maksimla |
Сообщение
#3
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
Спасибо что подсказал мне во сечас попробую сделать я дописать функцию
-------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
maksimla |
Сообщение
#4
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
я чегото неразобрался даже как эта рекурсия работает чегото и чего выводит 13 в последней строчке
-------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
volvo |
Сообщение
#5
|
Гость |
Помнишь, я давал тебе схему, как работает возведение в степень? Сделай точно такое же для этой функции, скажем для fib_1(4), чтоб очень много не рисовать, разберешься...
А 13 в последней строке - это и есть результат: 7-ое (если считать с нулевого) число Фибоначчи - 13: 0, 1, 1, 2, 3, 5, 8, 13 |
maksimla |
Сообщение
#6
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
разобрался почему она так выводит сперва левую сторону дерева счетает потом правую и когда 7 раскладывает то получается тринадцать единиц но непонел как эти тренадцать единиц записывает все и выводит
-------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
maksimla |
Сообщение
#7
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
я запутался когда она вызывается сама себя функцию и я как понимаю мне надо рекурсию в масиве без цикла сделать
-------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
maksimla |
Сообщение
#8
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
ну я чегото нечего нимогу придумать
-------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
volvo |
Сообщение
#9
|
Гость |
Ну неужели же это настолько сложно??? Смотри:
{ здесь будем хранить уже вычисленные результаты } Вот и все... Сообщение отредактировано: volvo - |
maksimla |
Сообщение
#10
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
а мочему масив до 23 ? а почему масив в самой функции нележит? мне кажется надо было чтобы массив в функции былбы
ах очень сложно мне Сообщение отредактировано: maksimla - -------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
maksimla |
Сообщение
#11
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
у меня чегото выбевает ошибка это из за того что масив от 0 до 23 а цикл от 0 до 255
Сообщение отредактировано: maksimla - -------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
maksimla |
Сообщение
#12
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
пожалста скажите как вы эти посчетали и как вывели на экран 13
то мне еще в одной рекурсии надо подсчитать и вывести сколько обращений будет к прочедуре в другом задании -------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
volvo |
Сообщение
#13
|
Гость |
Цитата а мочему масив до 23 ? Потому что начиная с 24-го значения число Фибоначчи не помещается в Integer, слишком большим становится...Цитата а почему масив в самой функции нележит? мне кажется надо было чтобы массив в функции былбы Ай-яй-яй... Нельзя этого делать, тогда весь смысл использования массива пропадает: на каждом уровне рекурсии будет создаваться своя копия массива... Либо описывать внутри функции, но как типизированную константу (это тоже имеет недостаток, если интересует - расскажу), либо глобально...Цитата у меня чегото выбевает ошибка это из за того что масив от 0 до 23 а цикл от 0 до 255 Да, я сначала делал массив от 0 до 255, потом поменял размер, а здесь изменить забыл... Поправлю. |
maksimla |
Сообщение
#14
|
Знаток Группа: Пользователи Сообщений: 324 Пол: Мужской Реальное имя: maksim Репутация: 1 |
Потому что начиная с 24-го значения число Фибоначчи не помещается в Integer, слишком большим становится... Ай-яй-яй... Нельзя этого делать, тогда весь смысл использования массива пропадает: на каждом уровне рекурсии будет создаваться своя копия массива... Либо описывать внутри функции, но как типизированную константу (это тоже имеет недостаток, если интересует - расскажу), либо глобально... раскажи какой недостаток? Сообщение отредактировано: maksimla - -------------------- Учусь первый год на программиста в колледже. Учусь на втором курсе в школе программирования при научно-исследовательском институте математики и информатики.
|
volvo |
Сообщение
#15
|
Гость |
Недостаток - это то, что надо явно инициализировать все значения. Ну ладно тут, от 0 до 23-х, всего 24 элемента. А если поменять тип на LongInt, тогда уже 46 чисел будут помещаться в этот тип, и придется написать в 2 раза больше (-1)-ниц... Но с другой стороны - есть неоспоримое преимущество: все, что уже было вычислено, второй раз вычисляться ВООБЩЕ не будет - сразу будет подставлено уже готовое значение. Особенно это эффективно, если функция вызывается не один раз, а несколько. Смотри, что будет:
function fib(n: integer): integer;fib(20) вычисляется обычно... А вот потом, когда вызывается еще fib(12) - никаких вычислений нет вообще, просто сразу возвращается значение из массива, и все... Запусти и посмотри, что будет... |
Гость |
Сообщение
#16
|
Гость |
Program pr40 (Input, Output);Теги Сообщение отредактировано: volvo - |
volvo |
Сообщение
#17
|
Гость |
Гость, "Рекуррентная" - не значит "рекурсивная". Автору нужен был "гибрид" - рекурсивно, но с хранением промежуточных значений в массиве. Вопросы еще будут?
На будущее - то, что ты, kick, постишь под "гостем" - еще не значит, что Правила Форума тебя не касаются... Теги надо использовать... И программу проверять, кстати, тоже нужно... Как вариант - попробуй запустить свою программу, и ввести 49, посмотришь, что будет... |
Текстовая версия | 6.05.2024 8:08 |