Задача №1. Длинная последовательность из 0 и 1

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

Требуется подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие три единицы не стоят рядом.

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

На вход программы поступает целое число N (3<=N<=50)

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

Выведите количество искомых последовательностей.

 

Задачи к теме

«Использование таблиц при решении подзадач. Метод динамического программирования»

Задача №2. Взрывоопасность

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число безопасных стопок.

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

Вводится одно число 1 <= N <=20.

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

Одно число — количество безопасных вариантов формирования стопки.

Пример

 

 

 

Задача №3. Взрывоопастность-2

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Для заданного количества контейнеров N определить число безопасных стопок.

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

В единственной строке входных данных записано натуральное число n (1≤n≤20).

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

Одно число — количество безопасных вариантов формирования стопки.

Пример

 

 

 

Задача №4. Платная лестница

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

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

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

В первой строке входного файла вводится одно натуральное число N≤100 — количество ступенек.
В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

 

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

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

Пример

 

 

 

Задача №5. Калькулятор

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

Ограничение по времени: 3 сек
Имеется калькулятор, который выполняет три операции:

1. Прибавить к числу X единицу.

2.  Умножить число X на 2.

3. Умножить число X на 3.

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

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

Программа получает на вход одно число, не превосходящее 10⁶.   

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

Одно число: наименьшее количество искомых операций.

Пример

 

 

 

Задача №6. Калькулятор с восстановлением ответа

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

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

1. Прибавить к числу X единицу.

2. Умножить число X на 2.

3. Умножить число X на 3.

Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.

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

Программа получает на вход одно число, не превосходящее 10⁶.   

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

Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. 

Пример

 

 

 

 

Кошманов В.А. 10 «A» класс

МБОУ СОШ №27 
с углубленным изучением отдельных предметов