Работа над проектами

Этапы работы над проектом:

1. Проанализировать условие задачи

2. Найти условия, которые позволят установить начальные значения рекуррентной величины;

3. Исходя из специфики задачи, ввести корректное рекуррентное соотношение;

4. Проверить правильность рекуррентного соотношения для значений, просчитанных вручную или вспомогательными программами;

5. Написать программу реализации данного проекта

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

7. Подготовить презентацию проекта

8. Защитить проект

Темы проектов к модулю1:

1. Двойные единицы  

Найти  количество F  всех   n – битных    двоичных  чисел,  у  которых в двоичной записи  нет подряд идущих двух единиц. (N≤30).

2. Без двух нулей подряд

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

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

Во входном файле INPUT.TXT записаны два натуральных числа N и K в десятичной системе счисления (2 ≤ K ≤ 10; 2 ≤ N; 4 ≤ N+K ≤ 18).

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

В выходной файл OUTPUT.TXT необходимо вывести целое число в десятичной записи – ответ на задачу.

3. Ступеньки

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

4. Зайчик на лесенке

На  вершине  лесенки, содержащей N ступенек, находится зайчик,  который начинает прыгать по ним вниз, к основанию. Зайчик  может прыгнуть на следующую  ступеньку, на ступеньку через  1 или 2. Определить число всевозможных “маршрутов”  зайчика с вершины на землю.

5*.Фишка на поле  

Фишка может двигаться по полю длины N   только вперед. Длина хода фишки не  более  K.   (N, K ≤16).   Найти количество   различных путей,  по   которым фишка  может пройти поле  от  позиции  1   до   позиции N.

6. Метод Динамического программирования. Поиск в сети InterNet

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

 Проект1. Веревочный мост

Однажды N путешественников решили ночью пересечь по веревочному мосту быструю горную речку. Без освещения перейти мост невозможно. К счастью, у одного из них оказался с собой фонарик. Известно, что мост выдерживает только двоих, а скорости людей могут различаться. Если мост пересекают два человека с разной скоростью, то они вынуждены двигаться со скоростью самого медленного из них. Скорость движения каждого из путников известна.

Помогите путешественникам как можно быстрее перебраться через мост. Требуется написать программу, определяющую минимальное время, которое потребуется для такого перехода. Например, если N=4, а время, требуемое для перехода по мосту для каждого, составляет 5, 10, 20 и 25 минут соответственно, то наименьшее время, требуемое для пересечения моста, составит ровно 60 минут.

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

В первой строке входного файла INPUT.TXT содержится натуральное число N – количество путешественников (N <= 10⁵). Во второй строке располагаются N натуральных чисел – скорости всех путников, разделенные пробелом и не превосходящие 10⁶. Здесь под скоростью человека понимается время в минутах, необходимое для перехода через мост.

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

В выходной файл OUTPUT.TXT выведите одно целое число – минимально возможное время, необходимое путникам для пересечения моста.

Примеры

Темы проектов к модулю2:

Проект2 Ход конем

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

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

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

Входной файл INPUT.TXT содержит натуральное число N (N <= 20).

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

Примеры

Проект 3. Игра в монеты

Однокопеечные монеты   разложены в  n  стопок  (в стопках может быть различное количество монет),  и стопки поставлены на столе в ряд слева направо. Двое игроков по очереди   делают ходы. Ход состоит в том, что один из игроков берет слева направо несколько стопок подряд, не меньше одной,  но не более чем перед этим  взял его соперник. Первый игрок своим первым ходом берет не более  k  стопок. Игра заканчивается, когда все стопки будут взяты. Требуется составить программу, определяющую максимальное число монет, которое может получить первый игрок после окончания игры, если второй игрок тоже старается ходить так, чтобы получить как можно больше монет.

Исходная информация  хранится в файле  ‘input.txt’, состоящем из одной строки чисел. В  строке находится число стопок n, за ним  идут  n  чисел − количество монет в стопках слева направо, затем в строке записано число k.  Числа разделены пробелами.

Ограничения:  1 ≤ n ≤ 100, 1 ≤ k ≤ 50, количество монет в стопках не более 10000, время выполнения программы  1 секунда.

Программа должна вывести ответ − максимальное число монет, которое может получить первый игрок,  в файл ‘output.txt’.

Пример.  Пусть в файле ‘input.txt’ записана строка чисел:

                        7 5 7 2 3 8 9 3 2.

Тогда программа запишет в файл ‘output.txt’  число  24

 

Проект4. Количество путей в лабиринте

Карта лабиринта представляет собой квадратное поле размером NxN. Некоторые квадраты этого поля запрещены для прохождения. Шаг в лабиринте – перемещение из одной разрешенной клетки к другой разрешенной клетке, смежной с первой по стороне. Путь – это некоторая последовательность таких шагов. При этом каждую клетку, включая начальную и конечную, можно посещать несколько раз.

Требуется написать программу, которая подсчитает количество различных путей из клетки (1, 1) в клетку (N, N) ровно за K шагов (то есть оказаться в клетке (N, N) после K-го шага).

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

Входной файл INPUT.TXT содержит в первой строке числа N и K, разделенные пробелом (1 < N <= 15, 0 < K <= 30). Следующие N строк, по N символов в каждой, содержат карту лабиринта, начиная с клетки (1, 1). Символ «0» означает не запрещенную для прохождения клетку, а символ «1» - запрещенную. Начальная и конечная клетки всегда разрешены для прохождения.

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

Выходной файл OUTPUT.TXT должен содержать количество возможных различных путей длины K. Во всех тестах это значение не будет превышать 2147483647.

Проект5. Робот

В исследовательской лаборатории фирмы Robots&Co разработали новую модель робота. Главной особенностью данной модели робота является то, что он работает по заранее заданной программе, в которой могут присутствовать команды: сделать шаг на Юг, на Север, на Восток или на Запад. Робот исполняет программу строго последовательно и, дойдя до конца программы, останавливается. Специалисты из Robots&Co заинтересовались вопросом, сколько существует различных программ, состоящих из K инструкций, таких, что робот, выйдя из начала координат, придет в точку с координатами (X, Y). Оси координат располагаются параллельно сторонам света, и единица измерения, соответствует одному шагу робота. Напишите программу, которая дает ответ на этот вопрос.

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

Во входном файле находятся три числа K, X и Y (0 <= K <= 16, |X|, |Y| <= 16), разделенные пробелами. 

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

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

Проект. Сказка

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

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