Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Функция#31902

Функция f(n) с натуральными аргументами и значениями определена так:

f(0) = 0

f(1) = 1

f(2n) = f(n)

f(2n + 1) = f(n) + f(n + 1)

Составить программу вычисления f(n) по заданному n.

Входные данные

Дано одно число n (1 <= n <= 10¹⁸).

Выходные данные

Выведите f(n).

Примеры

№	Входные данные	Выходные данные
1	10	3

Рекурсия

✓ 75✗ 412700средняяВойти и решать

Перебор строк №4#31900

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом. Программа не должна строить другие слова, не соответствующие условию.

Ввод	Вывод
2	KK LL MM NN

Рекурсия

✓ 59✗ 94600лёгкаяВойти и решать

Перебор строк №3#31899

В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из K букв (K<10), в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов. Программа не должна строить другие слова, не соответствующие условию.

Автор задачи: К.Ю. Поляков

Рекурсия

✓ 148✗ 204700средняяВойти и решать

Перебор строк №2#31898

В алфавите языке племени «Тумба-Юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв (n > 1), в которых вторая буква «K». Подсчитайте количество таких слов.

Примеры

№	Входные данные	Выходные данные
1	2	KK LK MK NK 4

Рекурсия

✓ 627✗ 1 150600лёгкаяВойти и решать

Ханойские башни#31845

Головоломка “Ханойские башни” состоит из трех стержней, пронумерованных числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3 за минимальное число перекладываний.

Напишите программу, которая решает головоломку; для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня с которого снимается данный диск, c — номер стержня на который надевается данный диск.

Например, строка 1 2 3 означает перемещение диска номер 1 со стержня 2 на стержень 3. В одной строке печатается одна команда. Диски пронумерованы числами от 1 до n в порядке возрастания диаметров.

Входные данные

Вводится натуральное число n ( 0 < n < 11).

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	2	1 1 2 2 1 3 1 2 3

Рекурсия

✓ 301✗ 276600лёгкаяВойти и решать

Двоичные последовательности#31843

Вводится число N (1<=N<=9). Сгенерируйте в лексикографическом порядке все последовательности длины N, состоящие из чисел 2, 4, 5, в которых количество двоек не больше двух.

В "лексикографическом порядке" обозначает, что если на первых X местах две последовательности совпадают, а на месте X+1 - различаются, то раньше должна идти та из них, в которой число на месте X+1 меньше.

Рекурсия

✓ 354✗ 694700средняяВойти и решать

Звездочки#31842

Дана строка, содержащая только английские буквы (большие и маленькие). Добавить символ ‘*’ (звездочка) между буквами (перед первой буквой и после последней символ ‘*’ добавлять не нужно).

Входные данные

Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков.

Выходные данные

Вывести строку, которая получится после добавления символов '*'.

Примеры

№	Входные данные	Выходные данные
1	LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO	LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO

Рекурсия

✓ 632✗ 445400лёгкаяВойти и решать

Количество цифр#31841

Дана строка, содержащая цифры и английские буквы (большие и маленькие). Найти и вывести количество цифр.

Входные данные

Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков.

Выходные данные

Выведите количество цифр, которые присутствуют в строке.

Примеры

№	Входные данные	Выходные данные
1	74kz31n8pn26f2iv10c7u8x356gl73jlka67i929z08i5mnn35h0n	28

Рекурсия

✓ 553✗ 402400лёгкаяВойти и решать

Наибольшая строка#31840

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

При решении этой задачи запрещено использовать циклы и слово max.

Входные данные

Вводится строка ненулевой длины. Известно также, что длина строки не превышает 1000 знаков и строка содержит только десятичные цифры.

Выходные данные

Выведите максимальную цифру, которая встречается во введенной строке.

Примеры

№	Входные данные	Выходные данные
1	11111111	1

Рекурсия

✓ 646✗ 751400лёгкаяВойти и решать

Вычисление факториала#31839

Составить программу с рекурсивной функцией для расчета факториала.

Входные данные
В первой строке вводится натуральное число N ( N<=12 ).

Выходные данные
Выведите факториал числа.
Примеры

№	Входные данные	Выходные данные
1	1	1
2	2	2

Рекурсия

✓ 737✗ 550200лёгкаяВойти и решать

Сумма битов#31838

Составить программу с рекурсивной функцией для расчета суммы битов в натуральном числе.

Входные данные
В первой строке вводится натуральное число N ( N<=10⁹ ).

Выходные данные
Выводите сумму битов.

Примеры

№	Входные данные	Выходные данные
1	16	1
2	7	3

Рекурсия

✓ 587✗ 411300лёгкаяВойти и решать

Произведение битов#31837

Составить программу с рекурсивной функцией для расчета произведения битов в натуральном числе.

Входные данные
В первой строке вводится натуральное число N ( N<=10⁹ ).

Выходные данные
Выводите произведение битов.

Примеры

№	Входные данные	Выходные данные
1	16	0
2	7	1

Рекурсия

✓ 569✗ 352300лёгкаяВойти и решать

Разложение на слагаемые#31803

Требуется вывести все различные представления натурального числа N в виде суммы натуральных чисел. Представления, отличающиеся друг от друга порядком слагаемых, не являются различными.

Входные данные

Входная строка содержит целое число N (2 ≤ N ≤ 40).

Выходные данные

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

Примеры

№	Входные данные	Выходные данные
1	4	1 1 1 1 1 2 1 1 3 2 2 4
2	5	1 1 1 1 1 1 1 1 2 1 1 3 1 2 2 2 3 1 4 5

Рекурсия

✓ 70✗ 201700средняяВойти и решать

Функция - 2*#31793

Описана рекурсивная функции с тремя параметрами F(a, b, c):

F(a, b, c) = 1, если a ≤ 0 или b ≤ 0 или c ≤ 0;

F(a, b, c) = F(20, 20, 20), если a > 20 или b > 20 или c > 20;

F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c), если a < b и b < c;

F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1) - F(a-1, b-1, c-1), во всех остальных случаях.

Входные данные

Входные данные содержат три целых числа a, b, c - параметры функции F (-10⁴ ≤ a,b,c ≤ 10⁴).

Выходные данные

В ответе выведите значение функции F(a, b, c).

Примеры

№	Входные данные	Выходные данные
1	1 1 1	2
2	2 2 2	4
3	10 4 6	523
4	50 50 50	1048576

Рекурсия

✓ 179✗ 540700средняяВойти и решать

Как поделить картошку#31792

Вася и Петя пошли копать картошку. В конце дня они накопали N мешков с картошкой весом W₁, W₂, ... W_N. Как им поделить мешки с картошкой между собой, чтобы разница масс была минимальной.

Входные данные

В первой строке записано число N – количество мешков (1 ≤ N ≤ 18). Во второй строке через пробел перечислены массы мешков W₁, W₂ , … W_N (1 ≤ W_i ≤ 10⁵).

Выходные данные

В единственную строку нужно вывести одно неотрицательное целое число – минимально возможную разницу между массами двух куч с мешками.

Ввод	Вывод
5 5 3 5 7 8	2

Рекурсия

✓ 97✗ 191700средняяВойти и решать

Это Бомба#24906

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

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

Формат входных данных

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

Формат выходных данных

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Формат выходных данных

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

Динамическое программирование: один параметр Рекурсия

✓ 25✗ 16500лёгкаяВойти и решать

Число с максимальной суммой делителей#21835

Напишите функцию, вычисляющую сумму делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным суммой делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, в котором сумма делителей числа максимальна среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 2 5 59 72 34	72
2 78 81	78

Алгоритмы обработки Задачи на процедуры и функции Линейные алгоритмы

✓ 82✗ 242700средняяВойти и решать

Число с максимальным количеством делителей#21834

Напишите функцию, вычисляющую количество делителей числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальным количеством делителей
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, в котором количество делителей максимально среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 22790 94 66 18 18	22790
2 21 46	21

Алгоритмы обработки Задачи на процедуры и функции Простые числа и разложение на множители

✓ 112✗ 236700средняяВойти и решать

Число с максимальной первой цифрой#21833

Напишите функцию, вычисляющую первую цифру числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальной первой цифрой
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100)
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, у которого первая цифра максимальна среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 43 22 11 56 10	56
2 14 22	22

Алгоритмы обработки Задачи на процедуры и функции

✓ 159✗ 283600лёгкаяВойти и решать

Число с максимальной суммой цифр#21832

Напишите функцию, вычисляющую сумму цифр числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальной суммой цифр
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, в котором сумма цифр максимальна среди всех чисел

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 43 22 11 56 10	56
2 34 12	34

Алгоритмы обработки Задачи на процедуры и функции

✓ 120✗ 240600лёгкаяВойти и решать