Задана программа реализующая рекурсивный алгоритм на алгоритмическом языке

Рекурсия — это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта.

Для того, чтобы задать рекурсию, необходимо описать:

— условие остановки рекурсии (базовый случай);

В программировании если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным.

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

Классическим примером рекурсивного алгоритма является описание вычисления факториала:

Рекурсивные алгоритмы вычисления одной функции

Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми ре­кур­рент­ны­ми со­от­но­ше­ни­я­ми:

Пошаговое объяснение рекурсивной функции Фибоначчи

Чему равно зна­че­ние функ­ции F(6)?

В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.

По­сле­до­ва­тель­но на­йдём зна­че­ния функции от базового случая F(1) до искомого значения F(6):

Рекурсивные алгоритмы вычисления нескольких функций

Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:

G(n) = F(n–1) + 2*G(n–1), при n >=2

Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.

По­сле­до­ва­тель­но на­йдём зна­че­ния функций от базового случая F(1), G(1) до искомых значений F(5), G(5):

F(2) = F(1) – G(1) = 1 – 1 = 0;

G(2) = F(1) + 2*G(1) = 1+2 = 3;

F(3) = F(2) – G(2) = 0 – 3 = -3;

G(3) = F(2) + 2*G(2) = 0+6 = 6;

F(4) = F(3) – G(3) = -3 – 6 = -9 ;

G(4) = F(3) + 2*G(3) = -3+12 = 9;

F(5) = F(4) – G(4) = -9 – 9 = -18;

G(5) = F(4) + 2*G(4) = -9+18 = 9.

Рекурсивные алгоритмы выполнения процедур

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F.

Бей­сик

Python

PRINT n

END IF

Пас­каль

Ал­го­рит­ми­че­ский язык

begin

writeln(n);

begin

end

нач

вывод n, нс

все

Си

Чему равна сумма всех чисел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(1)?

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

F (1) выполнит следующие действия : Вывод числа 1, F(2), F(4)

F (2) выполнит следующие действия : Вывод числа 2, F(3), F(5)

F (4) выполнит следующие действия : Вывод числа 4, F(5), F(7)

F (3) выполнит следующие действия : Вывод числа 3, F(4), F(6)

F (5) выполнит следующие действия : Вывод числа 5

F (5) выполнит следующие действия : Вывод числа 5

F (7) выполнит следующие действия : Вывод числа 7

F (4) выполнит следующие действия : Вывод числа 4, F(5), F(7)

Рекурсивные алгоритмы

F (6) выполнит следующие действия : Вывод числа 6

F (5) выполнит следующие действия : Вывод числа 5

F (7) выполнит следующие действия : Вывод числа 7

Просуммируем все числа, выведенные на экран: 1+2+4+3+5+5+7+4+6+5+7 = 49

Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­ны две ре­кур­сив­ные функ­ции (процеду­ры): F и G.

Сколь­ко сим­во­лов «звёздоч­ка» будет на­пе­ча­та­но на экра­не при вы­пол­не­нии вы­зо­ва F(11)?

Выпишем последовательно все действия, которые выполнят запускаемые процедуры:

F(11) G(10) * F(7) G(6) * F(3) G(2) * F(-1)

Всего на экране будет напечатано 3 «звездочки».

Дан рекурсивный алгоритм:

procedure F(n: integer);

begin

writeln(‘*’);

if n > 0 then begin

F(n-3);

F(n-2);

F(n div 2);

F(n div 2);

end

end;

Сколько символов «звездочка» будет напечатано на экране при выполнении вызова F(6)?

Для наглядности изобразим схему работы алгоритма в виде дерева:

Причем, распишем до конца каждое значение F(n) только один раз. Например, расписав один раз F(1), мы видим, что она напечатает в результате 5 звездочек. Т.е. F(1) = 5.

Проанализировав дерево, видим, что

F(3) = 1 + F(0) + 3*F(1) = 1 + 1 + 15 = 17

F(4) = 1 + F(1) + 3*F(2) = 1 + 5 + 3*13 = 45

F(6) = 1 + 3*F(3) + F(4) = 1 + 3*17 + 45 = 46 + 51 = 97

Ты нашел то, что искал? Поделись с друзьями!

Благодарим за то, что пользуйтесь нашими материалами. Информация на странице «Задача №11. Использование рекурсивных алгоритмов.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к ЕГЭ и ОГЭ. Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими статьями из разделов нашего сайта.

Публикация обновлена: 07.06.2023

Источник: ege-study.ru

Задана программа реализующая рекурсивный алгоритм на алгоритмическом языке

Тысячи правильных ответов на различные тесты

Тысячи проверенных ответов

Вопрос теста:

Задана программа, реализующая рекурсивный алгоритм на алгоритмическом языке. Программа состоит из головной программы и подпрограммы (функции). В программе вычисляется(-ются)…

• сумма геометрической прогрессии
• факториал
• сумма арифметической прогрессии
• числа Фибоначчи

Задание

Функции Graphic(x,0)=2, Graphic(x,1)=2, Graphic(x,2)=-1. Тогда Analiz:=2-2-1=-1. Обратите внимание, что в составленной таким образом функции Graphic() результат всегда определяется только работой последнего оператора IF.

В объектно-ориентированном программировании понятию объекта соответствует схема …

Объект — это совокупность свойств (структур данных, характерных для этого объекта), методов их обработки (подпрограмм изменения свойств) и событий, на которые данный объект может реагировать и которые приводят, как правило, к изменению свойств объекта.

Задана программа, реализующая рекурсивный алгоритм на алгоритмическом языке. Программа состоит из головной программы и подпрограммы (функции). В программе вычисляется(-ются) …

В языках программирования рекурсивной программой называется программа, которая обращается сама к себе (подобно тому, как в математике рекурсивная функция определяется через понятия самой этой функции). Рекурсивная программа не может вызывать себя до бесконечности, следовательно, в ней должно быть предусмотрено условие завершения, позволяющее программе прекратить вызывать себя. Факториал определяется соотношением

или по рекуррентной формуле . В программе это реализовано рекурсивным обращением подпрограммы-функции с именем rcrs к самой себе (прямая рекурсия): rcrs=N*rcrs(N-1). При выполнении рекурсивной подпрограммы сначала происходит «рекурсивное погружение», а затем «возврат вычисленных результатов». Например, вычисление 5! при помощи вызова rcrs(5) будет происходить следующим образом:

Независимую связь между несколькими парами компьютеров в сети не обеспечивают …

сетевой шлюз

сетевой разветвитель

модем

Протоколы, которые работают на прикладном уровне модели OSI, — это …

Сетевая модель OSI — это абстрактная сетевая модель для коммуникаций и разработки сетевых протоколов. Представляет уровневый подход к сети. Каждый уровень обслуживает свою часть процесса взаимодействия. Верхний уровень модели прикладной. Он обеспечивает взаимодействие пользовательских приложений с сетью.

Этот уровень позволяет приложениям использовать сетевые службы, такие как удаленный доступ к файлам и базам данных, пересылка электронной почты. Также отвечает за передачу служебной информации, предоставляет приложениям информацию об ошибках и формирует запросы к уровню представления. Протоколы, которые работают на этом уровне, — HTTP, SMTP, Telnet, FTP.

Адрес сервера описывает такая часть электронного адреса ресурса (URL) http://www.rambler.ru/history/napoleon1812.html, как …

Стадии жизненного цикла классической троянской программы («троянского коня») включают в себя …

«Троянский конь», «троян» – это программа, содержащая в себе некоторую разрушающую функцию, которая активизируется при наступлении некоторого условия срабатывания. Такие программы выполняют на компьютерах несанкционированные пользователем действия. Например, уничтожают информацию на дисках, приводят систему к зависанию, воруют конфиденциальную информацию.

Большинство троянских программ предназначено для сбора конфиденциальной информации. Их задача, чаще всего, состоит в выполнении действий, позволяющих получить доступ к данным, которые не подлежат широкой огласке. К таким данным относятся пользовательские пароли, регистрационные номера программ, сведения о банковских счетах и т.д. При этом «трояны» не являются вирусами в традиционном понимании этого термина. Они не создают копий, не заражают другие программы и, как правило, не способны самостоятельно проникать на компьютеры, а маскируются под какие-нибудь полезные утилиты, например, под игровые или развлекательные программы, и наносят вред под красивые картинки или музыку.

распространение копий

создание копий

активацию

проникновение на чужой компьютер

выполнение вредоносных действий

Абитуриенты сдают четыре экзамена в форме ЕГЭ. Сообщение «Зачислить» придет тем абитуриентам, у которых: – баллы по каждому предмету выше «порогового» значения (по математике – более 24 баллов, по физике – более 28 баллов, по информатике – более 25 баллов, по русскому языку – более 34 баллов); – сумма баллов по всем предметам не меньше 240. Остальные абитуриенты получат сообщение «Отказать». Введите в электронную таблицу исходные данные (слова можно сокращать).

Значения в столбце F рассчитываются по формуле (для строки 3): =СУММ(B3:E3) Значения в столбце G рассчитываются по формуле (для строки 3): =ЕСЛИ(И(B3>24;C3>28;D3>25;E3>34;F3>=240); «Зачислить»;»Отказать») Значения в ячейках B14, C14, D14, E14 рассчитываются соответственно по формулам: =СРЗНАЧ(B3:B12), =СРЗНАЧ(C3:C12), =СРЗНАЧ(D3:D12), =СРЗНАЧ(E3:E12), После выполнения расчетов исходная таблица примет вид: Таким образом, Баев Е. набрал 222 балла, Голубева В. – 246 баллов, Чернова П. – 268 баллов.

синий По данным исходной таблицы установите соответствие между фамилиями абитуриентов: Бондарева А., Скворцов А., Варшавская Е. – и цветами графиков, построенных по полученным ими баллам. «Лишний» график имеет ______________ цвет.

Допустим, что Вы устраиваетесь на работу. Среди требований к претенденту одним из главных является его ИКТ-компетентность. На собеседовании Вы должны продемонстрировать знания, умения и навыки при работе с графическим и текстовым редакторами, уверенное использование Интернета. Цветной рисунок из режима 256 цветов был преобразован в черно-белую картинку с градациями серого цвета и 8-битным кодированием цвета точки. При этом объем видеопамяти, необходимый для хранения этого рисунка, …

В текстовом процессоре MS Word виды указателя мыши А и Б служат для обозначения операции …

А – перемещения выделенного фрагмента текста вниз

А – выделения столбца таблицы

Б – выделения ячейки и/или текста в ячейке таблицы

Б – выделения строки таблицы

В строфе 117 символов (включая пробелы и символы перевода каретки). Если один символ кодируется 16 битами, то размер письма в битах будет составлять бит. Так как 1 байт = 8 бит, то в байтах размер сообщения будет равен: байта. , то есть SMS-сообщение будет разделено на 4 части. Ответ: 4.

Зарегистрированные сигналы – это …

В ходе тестирования было установлено, что средняя скорость чтения у учеников 11-го класса составляет 160 слов в минуту. За 4 часа непрерывного чтения ученик получает _____ Кбайт информации. Считать, что 1 слово в среднем содержит 6 символов, а количество информации, которое несет 1 символ, равно 8 битам.

Источник: studfile.net