Индуктивное определение объектов информатика егэ - Помощь в подготовке к экзаменам и поступлению

Всего: 163 1–20 | 21–40 | 41–60 | 61–80 …

Добавить в вариант

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

Бейсик	Python
SUB F(n)     IF n > 3 THEN          F(n 2)          F(n − 2)     END IF     PRINT N END SUB	def F(n):     if n > 3:         F(n // 2)         F(n − 2)     print(n)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     if n > 3 then begin         F(n div 2);         F(n − 2);     end;     write(n); end;	алг F(цел n) нач     если n > 3 то         F(div(n,2))         F(n − 2)     все     вывод n кон
С++
void F (int n) {      if (n > 3) {         F (n / 2);         F (n − 2);     }     std::cout << n; }

Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

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

Бейсик	Python
SUB F(n)     IF n > 2 THEN          F(n − 2)          PRINT n;          F(n 2)     END IF END SUB	def F(n):     if n > 2:         F(n − 2)         print(n, end=»)         F(n // 2)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     if n > 2 then begin         F(n − 2);         write(n);         F(n div 2);     end; end;	алг F(цел n) нач     если n > 2 то         F(n − 2)         вывод n         F(div(n,2))     все кон
С++
void F (int n) {      if (n > 2) {         F (n − 2);         std::cout << n;         F (n / 2);     } }

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

Бейсик	Python
DECLARE SUB F(n) SUB F(n)     IF n > 2 THEN         PRINT n         F(n — 3)         F(n – 4)     END IF END SUB	def F(n):     if n > 2:         print(n)         F(n — 3)         F(n – 4)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     if n > 2 then begin         writeln(n);         F(n — 3);         F(n – 4)     end end;	алг F(цел n) нач     если n > 2 то         вывод n, нс         F(n — 3)         F(n – 4)     все кон
Си
void F(int n) {     if (n > 2) {         cout << n;         F(n — 3);         F(n – 4);     } }

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

Источник: Демонстрационная версия ЕГЭ—2017 по информатике.

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

Бейсик	Python
SUB F(n)     IF n > 3 THEN          F(n − 2)          F(n 2)     END IF     PRINT N END SUB	def F(n):     if n > 3:         F(n − 2)         F(n // 2)     print(n)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     if n > 3 then begin         F(n − 2);         F(n div 2);     end;     write(n); end;	алг F(цел n) нач     если n > 3 то         F(n − 2)         F(div(n,2))     все     вывод n кон
С++
void F (int n) {      if (n > 3) {         F (n − 2);         F (n / 2);     }     std::cout << n; }

Обозначим через a mod b остаток от деления натурального числа a на натуральное число b. Алгоритм вычисления значения функции F(n), где n  — натуральное число, задан следующими соотношениями:

F(0) = 0;

F(n) = n + F(n − 3), если n mod 3  =  0, и n > 0;

F(n) = n + F(n − (n mod 3)), если n mod 3 > 0.

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

F(0) = 0;

F(n) = n + F(n − 3), если n mod 3  =  0, и n > 0;

F(n) = n + F(n − (n mod 3)), если n mod 3 > 0.

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

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

Бейсик	Паскаль
SUB F(n)   IF n > 0 THEN     F(n — 4)     F(n 3)     PRINT n   END IF END SUB	procedure F(n: integer); begin   if n > 0 then   begin     F(n — 4);     F(n div 3);     writeln(n)   end end;
Си++	Алгоритмический язык
void F(int n) { if (n > 0)   {     F(n — 4);     F(n / 3);     cout << n << endl;   } }	алг F(цел n) нач   если n > 0 то     F(n — 4)     F(div(n, 3))     вывод n, нс   все кон
Python
def F(n):     if n > 0:         F(n — 4)         F(n // 3)         print(n)

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

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

F(n) = 2 при n ≤ 2;

F(n) = F(n − 1) + 2 · F(n − 2) при n > 2.

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

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Сибирь. Вариант 1.

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

F(n) = 2 при n ≤ 2;

F(n) = 2 · F(n − 1) + F(n − 2) при n > 2.

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

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Сибирь. Вариант 2.

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

F(n) = n + 4 при n ≤ 2;

F(n) = F(n − 1) + F(n − 2) при n > 2.

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

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Урал. Вариант 2.

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

F(n) = 2 при n ≤ 2;

F(n) = F(n − 1) × F(n − 2) при n> 2.

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

Источник: ЕГЭ по информатике 08.07.2013. Вторая волна. Вариант 802.

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

Бейсик	Python
SUB F(n)     IF n > 0 THEN          PRINT N          F(n − 4)          F(n 2)     END IF END SUB	def F(n):     if n > 0:         print(n)          F(n − 4)          F(n // 2)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     if n > 0 then begin         write(n);         F(n − 4);         F(n div 2);     end end;	алг F(цел n) нач     если n > 0 то         вывод n         F(n − 4)         F(div(n,2))     все кон
С++
void F (int n) {      if (n > 0) {         std::cout << n;         F (n − 4);         F (n / 2);     } }

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

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

Бейсик	Python
SUB F(n)     IF n > 0 THEN          PRINT N          F(n 2)          F(n − 4)     END IF END SUB	def F(n):     if n > 0:         print(n)          F(n // 2)          F(n − 4)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     if n > 0 then begin         write(n);         F(n div 2);         F(n − 4);     end end;	алг F(цел n) нач     если n > 0 то         вывод n         F(div(n,2))         F(n − 4)     все кон
С++
void F (int n) {      if (n > 0) {         std::cout << n;         F (n / 2);         F (n − 4);     } }

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

F(1) = 5;F(2) = 5;

F(n) = 5*F(n − 1) − 4*F(n − 2) при n >2.

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

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

F(n) = 2 при n ≤ 2;

F(n) = F(n − 1) + 3 · F(n − 2) при n > 2.

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

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Сибирь. Вариант 5.

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

F(n) = n при n ≤ 2;

F(n) = F(n − 1) + 2×F(n − 2) при n > 2.

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

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Урал. Вариант 4.

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

F(n) = n + 3 при n ≤ 2;

F(n) = F(n − 1) + F(n − 2) при n > 2.

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

Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Центр. Вариант 2.

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

F(n) = 2 при n = 1;

F(n) = F(n − 1) · n при n ≥ 2.

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

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

Источник: ЕГЭ по информатике 05.05.2014. Досрочная волна. Вариант 1.

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

Бейсик	Python
SUB F(n)     PRINT n     IF n < 5 THEN         F(n + 1)         F(n + 2)     END IF END SUB	def F(n):     print(n)     if n < 5:         F(n + 1)         F(n + 2)
Алгоритмический язык	Паскаль
алг F(цел n) нач     вывод n, нс     если n < 5 то         F(n + 1)         F(n + 2)     все кон	procedure F(n: integer); begin     writeln(n);     if n < 5 then     begin         F(n + 1);         F(n + 2)     end end
Си
void F(int n) {     cout << n;     if (n < 5)     {         F(n + 1);         F(n + 2);     } }

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

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

Бейсик	Python
FUNCTION F(n)     IF n > 3 THEN          F = F(n-2) + F(n2)      ELSE          F = n     END IF END FUNCTION	def F(n):     if n > 3:         return F(n-2) + F(n//2)     else:         return n
Паскаль	Алгоритмический язык
function F(n: integer): integer; begin     if n > 3 then         F := F(n-2) + F(n div 2)     else         F := n end;	алг цел F(цел n) нач     если n > 3         то          знач := F(n-2) + F(div(n,2))         иначе             знач := n     все кон
Си
int F(int n) {     if (n > 3)         return F(n-2) + F(n/2);     else         return n; }

Чему будет равно значение, вычисленное при выполнении вызова F(9)?

Всего: 163 1–20 | 21–40 | 41–60 | 61–80 …

Источник

Чтобы ввести определения ряда понятий чаще всего в математике используют термин «индуктивное определение». Давайте рассмотрим некоторый пример:

Дж. Пеано писал, что натуральные числа – это:

число нуль;
числа, которые стоят правее натурального;
если же натуральное число равно следующему последовательному числу, то оно равно и предыдущему;
нуль – это первое натуральное число.

Введите ответ в поле ввода

Решение
→

Источник

Взрослым: Skillbox, Хекслет, Eduson, XYZ, GB, Яндекс, Otus, SkillFactory.
8-11 класс: Умскул, Лектариум, Годограф, Знанио.
До 7 класса: Алгоритмика, Кодланд, Реботика.
Английский: Инглекс, Puzzle, Novakid.

Индуктивное определение объектов

Обычно индуктивное определение объектов K производится следующим образом:

Необходимо задать класс простейших объектов A из класса К, подлежащего определению [Базис индуктивного определения];
Формируется свод правил R, согласно которым возможно строить новые объекты класса К из уже определённых [Шаг индуктивного определения];
К объектам определяемого класса К относятся только такие объекты, которые получаются согласно пунктам 1 и 2 данного определения.

Индуктивное определение объектов тесно связано с понятием обобщённого принципа индукции, который формулируется следующим образом: «Для доказательства, что любой объект класса, заданного индуктивным определением, обладает неким свойством Р, достаточно сначала узнать, что исходный объект, заданный пунктом 1 правила, имеет свойство Р [Базис индукции]. После этого требуется доказать, что свойство Р будет иметь любой объект, полученный по правилам индуктивного определения из объектов, у которых уже имеется данное свойство [Шаг индукции]».

Приведём несколько примеров работы этого определения.

Пример 1. Индуктивное определение класса высказывательных формул в математической логике

Предположим, что у нас есть множество высказывательных переменных (p₁, p₂, …, p_n) и символы математических операций (^ – конъюнкция, ˅ – дизъюнкция, ¬ – отрицание, → – импликация, ↔ – эквивалентность). Далее необходимо дать следующее индуктивное определение:

Высказывательные переменные p₁, p₂, …, p_n мы считаем атомарными формулами [Базис индуктивного определения].
Если Φ и Ψ являются уже построенными высказывательными формулами, то все возможные формальные выражения (Φ ^ Ψ, Φ ˅ Ψ, Φ → Ψ, Φ ↔ Ψ, ¬ Φ) также являются высказывательными формулами.
К высказывательным формулам относятся только те формальные выражения, которые можно построить согласно пунктам 1 и 2 данного определения.

Пример 2. Индуктивное определение класса термов (терм – формальный аналог имени существительного)

Предположим, что у нас есть попарно непересекающиеся множества:

Множество предметных переменных (х₁, х₂, …, х_n)_;
Множество предметных констант (с₁, с₂, …, с_n);
Для каждого целого положительного n нам дано множество символов n-местных функций

Далее необходимо дать индуктивное определение класса термов:

Предметные переменные и константы считаются атомарными термами [Базис индуктивного определения].
Для любых целых положительных n и k, если t₁, t₂, …, t_n – какие-либо n уже построенных термов, то формальное выражение также является термом.
Термами считаются только те формальные выражения, которые мы получаем, опираясь на пункты 1 и 2 определения.

Это определение достаточно часто применяется при создании грамматик языков программирования.

Взрослым: Skillbox, Хекслет, Eduson, XYZ, GB, Яндекс, Otus, SkillFactory.
8-11 класс: Умскул, Лектариум, Годограф, Знанио.
До 7 класса: Алгоритмика, Кодланд, Реботика.
Английский: Инглекс, Puzzle, Novakid.

Источник

Индуктивное определение объектов

Индуктивные определения обычно используются в математике для точного определения ряда основных понятий. В качестве примера рассмотрим определение понятия натурального числа, предложенное итальянским математиком Дж. Пеано:

«0» есть натуральное число;
если п – натуральное число, то следующее непосредственно за ним число n‘ также будет натуральным числом;
никаких других натуральных чисел, кроме тех, которые образуются с помощью правил 1 и 2, нет;
для любых натуральных чисел выполняется условие: если последующие их числа равны, т. е. m‘=n‘, то равны и предыдущие числа, m=n.
нуль не следует ни за каким натуральным числом.

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

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

Источник

Разбор 11 задания ЕГЭ 2017 года по информатике из проекта демоверсии. Это задание базового уровня сложности. Примерное время выполнения задания 5 минут.

Проверяемые элементы содержания: умение исполнить рекурсивный алгоритм.
Элементы содержания, проверяемые на ЕГЭ: индуктивное определение объектов.

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

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

Ответ: ________

Разбор 11 задания ЕГЭ 2017:

procedure F(n: integer);
begin
if n > 2 then begin
writeln(n);
F(n — 3);
F(n – 4)
end
end;

После каждого вызова на экран выводится значение параметра функции, если выполняется условие n>2.

Запишем все вызовы в виде дерева.

Складываем все значения параметров, которые больше 2.

Получаем ответ: 10+7+4+3+6+3=33

Ответ: 33

Опубликовано: 04.10.2016
Обновлено: 12.03.2020

Источник

Задание №11.
Умение исполнить рекурсивный алгоритм. Уровень сложности задания — базовый, максимальный балл за выполнение — 1, примерное время выполнения задания — 5 минут.
Знать: индуктивное определение объектов.
Уметь: строить информационные модели объектов, систем и процессов в виде алгоритмов.

Задание относится к базовому уровню сложности и обычно не вызывает у учащихся особых хлопот, но бывают задания более сложные и, из-за невнимательности, можно потерять драгоценные баллы.

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

Пример задания. Дан рекурсивный алгоритм F. Приведите последовательность чисел (без пробелов и разделителей), которые будут напечатаны на экране при выполнении вызова F(4).

procedure F(n: integer);
begin
write (n);
if n > 1 then
begin
F(n — 1) ;
F(n — 2)
end
end;

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

1. Начинаем с функции, которая стоит у нас в условии — F(4) и прогоняем весь наш алгоритм от первой до последней строчки.

F(4) выводит на экран 4, затем проверяется условие n > 1, так как оно истинно вызывается F(3), вызывается F(2). Мы не знаем, что выведет на экран F(3) и F(2), следовательно их тоже прогоним через алгоритм.

F(3) выводит на экран 3, затем проверяется условие n > 1, так как оно истинно вызывается F(2), вызывается F(1).
F(2) выводит на экран 2, затем проверяется условие n > 1, так как оно истинно вызывается F(1), вызывается F(0). Мы ещё не знаем, что выводят F(1) и F(0), так что продолжаем.

F(1) выводит на экран 1, затем проверяется условие n > 1, но 1 не больше 1 и это условие ложно, на этом шаге процедура заканчивает свою работу.
F(0) выводит на экран 0, затем проверяется условие n > 1, но 0 не больше 1 и это условие ложно, на этом шаге процедура заканчивает свою работу.

Теперь мы все делаем в обратном порядке, записывая полученные результаты, пока не дойдем до процедуры F(4).

F(0) выводит на экран 0
F(1) выводит на экран 1
F(2) выводит на экран 210
F(3) выводит на экран 32101
F(4) выводит на экран 432101210

Ответ: 432101210.

Пример задания. (задания взяты с сайта К.Ю. Полякова http://kpolyakov.spb.ru)

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

F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно.

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

Решение. Такого типа задания довольно легко решаются вручную на бумаге, но это сделать довольно просто, если мы ищем значение функции F от небольшого значения переменной n. А если нас попросят найти значение функции F(100), что тогда? На бумаге и вручную будет затрачено довольно много времени. Выход есть, даже два! Можно решить задание с помощью процессора электронных таблиц, например Microsoft Excel, а ещё можно написать программу и программа эта не так уж и сложна. Мы разберём второй вариант.

Сначала опишем функцию:
function F(n:integer):integer;

begin
if n = 1 then
    F := 1
else if n mod 2 = 0 then
    F:= n + F(n-1)
else
    F:= 2 * F(n-2);
end;

Теперь нам просто надо вызвать функцию F(n) с нужным нам параметром.

begin
writeln(F(26));
end.

Полный текст программы:

function F(n:integer):integer;

begin
if n = 1 then
    F := 1
else if n mod 2 = 0 then
    F:= n + F(n-1)
else
    F:= 2 * F(n-2);
end;

begin
writeln(F(26));
end.

Ответ: 4122.

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

F(1) = G(1) = 1
F(n) = 3·F(n–1) + G(n–1) – n + 5, если n > 1
G(n) = F(n–1) + 3·G(n–1) – 3·n, если n > 1

Чему равно значение F(14) + G(14)?

Решение. Особых отличий в написании программы для этого примера нет. Просто тут у нас две функции – F(n) и G(n).

Сначала опишем функцию F(n):

function F(n:integer):integer;
begin
if n = 1 then
F := 1
else if n > 1 then
F:= 3*F(n-1) + G(n-1) — n + 5;
end;

Теперь опишем функцию G(n):

function G(n:integer):integer;
begin
if n = 1 then
G := 1
else if n > 1 then
G:= F(n-1) + 3*G(n-1) — 3 * n;
end;

Напишем саму программу

begin
writeln(F(14) + G(14));
end.

Запускаем и видим, что программа не «пошла». А вся причина в том, что функции «друг друга не видят». Для исправления данной ошибки в самом начале программы добавим несколько строк кода:

function F(n:integer):integer;
forward;
function G(n:integer):integer;
forward;

forward – это процедурная директива (предописание), другие процедуры и функции могут вызывать предописанную подпрограмму, делая возможной взаимную рекурсию.

Полный текст программы:

function F(n:integer):integer;
forward;
function G(n:integer):integer;
forward;

function F(n:integer):integer;
begin
if n = 1 then
F := 1
else if n > 1 then
F:= 3*F(n-1) + G(n-1) — n + 5;
end;

function G(n:integer):integer;
begin
if n = 1 then
G := 1
else if n > 1 then
G:= F(n-1) + 3*G(n-1) — 3 * n;
end;

begin
writeln(F(14) + G(14));
end.

Ответ: 37282721.

Источник