|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
18.03.2014, 17:38 | #1 |
Регистрация: 05.11.2013
Сообщений: 8
|
Рекурсия в Паскале, помогите разобраться
Функция F(n) для целых неотрицательных чисел n определяется следующим образом: F(0)=0, F(1)=1, F(2n)=F(n), F(2n+1)=F(n)+F(n+1). Для заданного n нужно найти и напечатать F(n). Обязательное условие: n столь велико, что недопустимо организовывать массив из n чисел. Это ведь рекурсия? 2n - это четные числа, а 2n+1 - нечетные, я так понимаю? А если попытаться вручную вычислить значение ф-ии при n=2 и большем значении, то значение ф-ии чему будет равно-то, я не могу понять ?
|
18.03.2014, 19:26 | #2 | |
Старожил
Регистрация: 26.04.2008
Сообщений: 2,645
|
Цитата:
Это рекуррентность Значения следующие F(0)=0 F(1)=1 n=1 F(2)=F(1)=1 F(3)=F(1)+F(2)=2 n=2 аналогично F(4)=1 F(5)=3 n=3 F(6)=2 F(7)=3 n=4 F(8)=1 F(9)=4 Предложу идею. Например при n=214 для вычисления F(214) нужно знать 107 - ое значение, для 107 нужно знать 53 и 54, для них нужно знать 27+26 и 27, и т.д Таблица примерно такая: 214 107 - 53 54 26 27 13 14 6 7 3 4 1 2 То есть массив на 214 элементов тут не нужен вовсе, достаточно массива на 14 элементов. Т.е. нужен массив MAS[1..X, 1..2]. Чтобы узнать чему равен Х, можно посмотреть на 1-ый столбей таблицы - он получен путём целочисленного деления предыдущего значения на 2 (т.е., если не ошибаюсь, то не более логарифма по основанию 2 от n). И по памяти должно проходить даже при запредельных n. Поэтому чтобы не вычислять чтоже за число в массиве по конкретному адресу, можно массив на 4 элемента в строке сделать (там будет хранится не только результат операций, но и сами числа) - это сделает код более быстрым и читабельным, но увеличит память (что вообще не критично учитывая быстрое убывание логарифмической ф-ии справа на лево). Всё сказанное не проверено и за проблемы, возникающие в процессе эксплуатации, распространитель ответственности не несёт |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Рекурсия на Паскале | gronet | Помощь студентам | 1 | 24.05.2012 07:52 |
Рекурсия на паскале | Lara12 | Паскаль, Turbo Pascal, PascalABC.NET | 5 | 16.10.2011 22:41 |
Задача в паскале (рекурсия) | Feil | Помощь студентам | 2 | 25.12.2009 12:04 |
Помогите пожалуйста разобраться с массивами в паскале! | Omsk-champion | Помощь студентам | 11 | 08.04.2009 00:35 |