Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/2: Рейтинг темы: голосов - 2, средняя оценка - 5.00
Andreyphisicist
0 / 0 / 0
Регистрация: 24.02.2015
Сообщений: 29
1

Построение и решение рекуррентного соотношения

11.07.2015, 14:36. Просмотров 425. Ответов 4
Метки нет (Все метки)

Добрый день. Я изучаю книгу А.Левитина "Алгоритмы: Введение в разработку и анализ" и пытаюсь решать задачки после каждой главы. И вот с одной задачкой возникла проблема. Проверьте у меня пожалуйста эту задачку. Задача номер 3 к упражнению главы 2.4. Я решил данную задачу пока что под буквой а).

Я выложу условие задачи фоткой (фотку у меня не получилось свернуть). Если так нельзя делать, вы мне скажите, и я больше не буду. Просто я новичок на этом форуме.

Решение для буквы а):

Основной операцией данного алгоритма, насколько я понял, является умножение.

http://www.cyberforum.ru/cgi-bin/latex.cgi?S(n)=S(n-1)+n^3<br />

Основное рекуррентное соотношение:
http://www.cyberforum.ru/cgi-bin/latex.cgi?M(n)=M(n-1)+3

http://www.cyberforum.ru/cgi-bin/latex.cgi?M(1) = 1  граничное условие , т.к. при 1 умножение не производится.

http://www.cyberforum.ru/cgi-bin/latex.cgi?M(n) = M(n-1) + 3 = M(n-2) + 2*3 = M(n-3) + 3*3 = M(n-i) + 3*i

И подставляя в данное выражение http://www.cyberforum.ru/cgi-bin/latex.cgi?i=n-1 и учитывая граничное условие, получаем следующее:

http://www.cyberforum.ru/cgi-bin/latex.cgi?M(n) = M(n-(n-1)) + 3(n-1) = M(1) + 3(n-1) = 3n - 3 + 1 = 3n - 2

Таким образом, данный алгоритм является линейным алгоритмом
http://www.cyberforum.ru/cgi-bin/latex.cgi?M(n) \in \Theta (n)
0
Миниатюры
Построение и решение рекуррентного соотношения  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2015, 14:36
Ответы с готовыми решениями:

Составить формулу рекуррентного соотношения
Дан рекуррентный алгоритм суммирования чисел массива mas. Начальный индекс массива равен 1, массив...

Решение рекуррентного соотношения
Помогите, пожалуйста, решить следующее рекуррентное соотношение: an+2 + 9an = 0 где: a0 = a1 = 1.

Решение рекуррентного соотношения
Не знаю с какого бока подойти к решению, прошу помощи. Вот само соотношение - Q0 = a Q1 = b Qn =...

Решение рекуррентного соотношения
Привет. Подскажите, пожалуйста, как решить реккуретное соотношение и оценить степень роста...

Общее решение рекуррентного соотношения
Нашел корни характеристического уравнения. x1=-2 x2=1 x3=-1 x4=2 x5=7 Как записать общее...

4
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
11.07.2015, 17:49 2
Если Вы считаете количество умножений, то:
а) M(1) = 0; M(n) = M(n-1) + 2; M(n) = 2*(n-1)
b) M(n) = 2*n // n чисел возводим в куб, затрачивая по 2 умножения на каждое число
0
Andreyphisicist
0 / 0 / 0
Регистрация: 24.02.2015
Сообщений: 29
11.07.2015, 18:17  [ТС] 3
Да точно M(1) = 0 и количество умножений равно двум. Что-то я поторопился.

У меня вот есть еще один вопрос. В данном случае я же правильно выбрал базовую операцию (умножение), по которой оценивал эффективность алгоритма? Всегда же выбирают в качестве базовой операции ту операцию, количество применений раз которой наибольшее. Правильно?
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,504
11.07.2015, 23:07 4
Полагаю, что в качестве базовой операции выбирают основную и/или самую дорогую.
ИМХО умножение в данном случае вполне подходит.
0
Andreyphisicist
0 / 0 / 0
Регистрация: 24.02.2015
Сообщений: 29
12.07.2015, 07:53  [ТС] 5
Спасибо за помощь)
0
12.07.2015, 07:53
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.07.2015, 07:53

Решение рекуррентного соотношения 5-го порядка
Помогите найти решение рекуррентного соотношения 5-го порядка f(n+5) = 2*f(n+4) + 6*f(n+3) +...

Найти общее решение рекуррентного соотношения 5-го порядка
И снова в бой. На этот раз рекуррентные соотношения. ...

Найти общее решение рекуррентного соотношения и сделать проверку
f(n+2)-4f(n+1)+13f(n)=0 f(n+2)=4f(n+1)-13f(n) {2}^{n+2}=4*{2}^{n+1}+13*{2}^{n} а дальше как?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru