Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
William Blake
10 / 10 / 2
Регистрация: 09.08.2010
Сообщений: 321
1

Составить формулу рекуррентного соотношения

06.02.2018, 04:30. Просмотров 426. Ответов 2
Метки нет (Все метки)

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

Алгоритм описан следующим образом:

F#
1
2
3
4
5
6
7
8
9
10
s = doSum(mas, 1, n)
 
func doSum(mas, left, right):
if (left == right) then
   return mas[left]
else
   center = (left + right) div 2
   s1 = doSum(mas, left, right, center)
   s2 = doSum(mas, center + 1, right)
   return s1 + s2
Мастер-теорема выглядит так: T(n) = a*T(n/b) + f(n), где a >= 1, b > 1 - некоторые константы, f - некоторые нерекуррентные вычисления.

Мой вопрос относится к нахождению функции f(n). Думаю, что f(n) равна нечто вроде (2*n/c + n/c), где 2 и c - некоторые константы, которые можно опустить, и, таким образом, получить в итоге f(n) = n. Правильно ли это? Если нет, то почему и чему тогда равно f(n)?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.02.2018, 04:30
Ответы с готовыми решениями:

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

Составить программу вычисления суммы ряда с использованием рекуррентного соотношения
Цикл с параметром.Составить программу вычисления суммы ряда с использованием рекуррентного...

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

Составление рекуррентного соотношения
http://padaread.com/?book=15274&pg=121 последний абзац обьясните пожалуйста как можно подробнее...

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

2
Shamil1
Модератор
2448 / 1660 / 368
Регистрация: 26.03.2015
Сообщений: 6,068
06.02.2018, 08:47 2
Цитата Сообщение от William Blake Посмотреть сообщение
Мой вопрос относится к нахождению функции f(n).
f(n) = константа
0
ili1
Заблокирован
07.02.2018, 09:37 3
William Blake,
мне кажется, что алгоритм должен выглядеть так:
1. вы задаете функцию с параметрами типа f(mas, n)
2. и алгоритм
если n = 1, то f = mas(1)
иначе
f = f(mas, n - 1) + mas(n)
...
это надо оформить в виде рекурсивной функции
(язык F# я не знаю)
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2018, 09:37

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

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

Реализация рекуррентного соотношения Мюллера
Вопрос про реализацию рекуррентного соотношения Мюллера. Полная статья здесь. Вкратце: если...


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

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

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