ммм. База заданий. Линейные и разветвляющиеся
 Скачать 0.98 Mb.
|
|
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Фермер хочет построить на своей земле как можно больший по площади сарай. Но на его участке есть деревья и хозяйственные постройки, которые он не хочет никуда переносить. Для простоты представим ферму сеткой размера MxN. Каждое из деревьев и построек размещается в одном или нескольких узлах сетки. Прямоугольный сарай не должен ни с чем соприкасаться (т.е. в соседних с ним узлах сетки не может ничего быть). Найти максимально возможную площадь сарая и место, где он может размещаться. Даны последовательности x 1 , x 2 , …, x n и y 1 , y 2 , …, y m . Найти общую подпоследовательность наибольшей длины. Задан двумерный массив d[1..n, 1..m]. требуется найти такой путь из d[1,1] в d[n,m], проходящий через соседние (в строке или столбце) элементы массива, ведущий вправо или вниз, чтобы сумма пройденных элементов была минимальной. ПЕРЕБОРНЫЕ ЗАДАЧИ Построить все правильные скобочные выражения (например, ”((()())())”) длины 10, т.е. те, которые содержат по 5 левых и 5 правых круглых скобок. В данной последовательности действительных чисел a 1 , …, a n выбрать возрастающую последовательность наибольшей длины. Даны натуральные числа m, a 1 , …, a n . В последовательности a 1 , …, a n выбрать последовательность a i1 , …, a ik (0≤i 1 <…≤n), такую что a i1 + …+ a ik =m. Если такую последовательность выбрать невозможно, то следует сообщить об этом. Составить программу, которая печатает все различные представления числа N в виде всевозможных произведений K натуральных чисел (N, K - вводятся, 1 Напишите программу которая введёт числа N и K, такие , что 0 <К Лишние круглые скобки ошибкой не являются. Например: Строка 505597, R=120: ((5+0)*((5*5)-(9/7)))=120. Решить задачу, не используя рекурсию. Данные N косточек домино по правилам игры выкладываются в прямую цепочку, начиная с косточки, выбранной произвольно, в оба конца до тех пор, пока это возможно. Построить алгоритм, позволяющий определить такой вариант выкладывания заданных косточек, при котором к моменту, когда цепочка не может быть продолжена, «на руках» останется максимальное число очков. На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс. Массы всех монет разные. За наименьшее количество взвешиваний необходимо определить 64-ую монету в порядке убывания масс среди всех 128 монет. За один раз можно взвешивать две монеты и определять, которая из них тяжелее. Задано N наборов монет из различных стран. Наборы упорядочены по невозpастанию массы монет. В i-ом наборе a i монет. Необходимо за минимальное число взвешиваний на чашечных весах определить k-ую по массе монету среди всех монет. На длинной перфоленте записаны N различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память машины может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Сделайте это за небольшое количество перемоток ленты. ЗАДАЧИ ПОВЫШЕННОЙ СЛОЖНОСТИ Обезьяна находится на лестнице из n ступенек. В руках у неё k орехов, которые она исследует на прочность, бросая их через перила лестницы на пол первого этажа. Будем считать, что если прочность скорлупы орехов равна Р, то: • орехи раскалываются при сбрасывании с любой ступеньки с номером, большим Р; • орехи не раскалываются при сбрасывании со ступенек до номера Р включительно. Прочность Р изменяется в диапазоне 0 ... n. Требуется определить минимальное количество попыток, за которое обезьяна гарантировано сможет определить прочность орехов при заданных n и k, если будет действовать оптимальным способом. Игра «Быки и Коровы» Компьютер «задумывает» четырехзначное число, не содержащее двух одинаковых цифр! Вы набираете свое число, и компьютер сообщает количество плюсов (точно угаданных цифр, т.е., стоящих на своих местах) и минусов (цифр, которые есть в задуманном числе, но на другом месте). 92 93 94 95 96 97 98 99 Например, пусть задуманное число 5734, а вы набирали 0755. Результат будет 1 плюс и 2 минуса. Игра продолжается до тех пор, пока вы получите 4 плюса. Программа «Жизнь», (описывающая жизнь микроорганизмов) Введение Жили-были микробы. Жили они долго и счастливо, но вот одна беда: после жизни всегда приходит смерть. А микробы были разные: маленькие и не очень, старички и малютки – и у каждого из них был свой жизненный уровень. Так, например, у только что родившегося микробчика он был равен 1, а по мере его взросления жизненный уровень тоже рос (от 1 до 12). Когда же микроб достигал последней ступени (т.е. 12), он, увы, погибал (теперь его жизненный уровень равен 0). Если же у микроба уровень был равен 0, то он рождался заново и проходил опять жизнь бодрым шагом от 1 до 12. Всего же микробов в мире, как вы знаете, очень много, а жизнь их интересна. Поэтому появилась идея написать программу, описывающую их жизнь. Эта программа должна сообщать нам количество микробов в каждом поколении и «нарисовать» их на поле (экране). Программа должна работать следующим образом. 1. Сначала создаётся файл work.dat (жилище микробов) и файл work.out (описывающий текущее поколение микробов, их развитие). Файл work.dat состоит из различных символов, среди которых «обитают» микробы. 2. Необходимо создать массивы «настоящее» и «будущее». В массиве «настоящее» записывается текущее поколение микробов, а в файл «будущее»- следующее. Массивы создаются размером 21х21. 3. Программа выдаёт пользователю на экран запрос: «Введите количество поколений». Именно столько поколений программа будет описывать. 4. Теперь программа создаёт в файле work.out поколение под номером 1. Для этого программа открывает и проверяет на наличие микробов файл (каждый символ, среди которых может затеряться микроб). Если под символом скрывается микроб (например, символ «Х»), то в массив «настоящее» записывается единица (1, т.е. микроб только что родился), а если не микроб – то ноль (0, т. е. там никто не живёт). Теперь в массиве «настоящее» находиться поле из 1 и 0 (он состоит из новорожденных младенцев и пустых мест). Все последующие поколения тоже записываются в файл work.out. Файл work.dat закрывается, и работа теперь ведётся только с файлом work.out. 5. Теперь описывается следующее поколение. Оно создаётся после проверки массива «настоящее». Проверяются микробы и их соседи (результат записывается в массив «будущее»): - если жизненный уровень микроба от 1 до 11 то: --если соседей 2 или 3, то микроб продолжает жить и подрастает (т.е. его жизненный уровень возрастает на 1), --иначе микроб погибает (=0), т.к. он задыхается или умирает от скуки; - если жизненный уровень микроба 0, то микроб рождается заново (т.е. его жизненный уровень равен 1); - если жизненный уровень микроба равен 12, то микроб погибает (от старости). 6. После проверки подсчитывается количество жизней данного поколения (т.е. сколько единиц). Затем программа проверяет, есть ли кто «живой на поле» или все погибли (т.е. нули). 7. Теперь программа производит замену поколений: массив «будущее» становится «настоящим». 100 8. Программа продолжает работу с пункта 5 до тех пор, пока количество поколений (которые описывает программа) не станет равным введенным пользователем в пункте 3 или пока не погибнут все микробы (т.е. везде одни нули). Эмуляция развития популяций животных Задание: написать программу типа "Жизнь", но с некоторыми изменениями в начальных условиях. Условия таковы, что в эмуляции должны участвовать две популяции: хищники и травоядные, - которые взаимодействовали бы друг с другом путем поедания травоядных хищниками. Дополнительные параметры: • возраст животных • минимальный и максимальный репродуктивный возраст животных • количество пищи нужный животным для поддержания жизни • количество травы • процент восстановления травы • вероятность природных катаклизмов влияющих на популяции животных Методика взаимодействий хищника и травоядного заключается в том, что и хищники, и травоядные представлены в виде точек, которые передвигаются по экрану с шагом в один пиксель. При этом заданно условие: если в радиусе один пиксель от точки, принадлежащей хищнику, появляется точка, принадлежащая травоядному, то считается, что хищник съел травоядного. Способ передвижения точек на экране организуется по алгоритму случайного блуждания, т.е. передвижение по осям Х и Y с шагом в один пиксель выбирается случайным образом. Умершие своей смертью травоядные считаются съеденными хищниками. При недоедании обеими популяциями, особи умирают в процессе увеличения возраста, т.е. чем больше возраст животного, тем больше вероятность погибнуть от голода. Из-за больших промежуточных расчетов учет по недоеданию выбрается так, что хищники учитываются один раз в год, а травоядные - двенадцать раз в год. Программу построить на обработке массивов, имеющих следующие параметры:x - расположение по координате Х экрана, • y - расположение по координате Y экрана, • age - возраст точки, • col - цвет вывода на экран. Программа должна обеспечивать следующие операции:задание параметров популяции травоядных, • задание параметров популяции хищников, • задание параметров окружающей среды, • просмотр взаимодействия животных в графическом режиме, • индикация результатов по выходу из режима просмотра взаимодействия животных, • выход из программы. Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются. Написать алгоритм для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой. Результаты задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить. 101 102 Вводится N - количество домов и К - количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел - двумя номерами домов – концов дороги и длиной дороги. В каждом доме живет по одному человеку. Найти точку - место встречи всех людей, от которой суммарное расстояние до всех домов будет минимальным. Если точка лежит на дороге, то указать номера домов - концов этой дороги и расстояние от первого из этих домов. Если точка совпадает с домом, то указать номер этого дома. Примечание: длины дорог - положительные целые числа. БАЗЫ ДАННЫХ Список группы Составить список учебной группы, включающей 15 человек. Для каждого студента указать дату рождения, год поступления в институт, курс, группу, оценки каждого года обучения. Совокупность сведений о студентах объединить в массив. Составить программу, которая обеспечивает ввод полученной информации, распечатку ее в виде таблицы, а также распечатку информации согласно конкретному варианту. Варианты задания 1. Распечатать данные отличников. 2. Распечатать данные хорошистов. 3. Распечатать данные студентов, получивших одну тройку за все годы обучения. 4. Распечатать данные студентов, получивших в последнюю сессию двойки. 5. Распечатать данные студентов, получивших в первую сессию все пятерки. 6. Распечатать данные студентов, получивших в первую сессию все тройки. 7. Распечатать данные студентов, получивших за все время обучения одну четверку, а все остальные пятерки. 8. Распечатать список студентов, фамилии которых начинаются с буквы А, и их оценки за все время обучения. 9. Распечатать список отличников за все время обучения, в алфавитном порядке. 10. Распечатать список отличников за все время обучения и упорядочить по году рождения. 11. Распечатать список отличников за все время обучения и упорядочить по году поступления в институт. 12. Распечатать список студентов фамилия которых начинается с буквы А и упорядочить по году поступления в институт. 13. Распечатать список хорошистов за все время обучения и упорядочить по году рождения. 14. Распечатать список студентов, фамилии которых начинаются с буквы Б, и их даты рождения. 15. Распечатать оценки в последнюю сессию студентов, фамилии которых начинаются с букв В и Г. 16. Распечатать фамилии и даты рождения студентов, не получивших ни одной тройки за все время обучения. 17. Распечатать фамилии и даты рождения студентов, получивших все тройки за все время обучения. 18. Упорядочить список студентов по среднему балу и распечатать его. 19. Упорядочить список студентов по среднему балу последней сессии и распечатать его. 103 104 20. Вычислить средний балл группы и распечатать список студентов, имеющих средний балл выше среднего балла группы. 21. Вычислить средний балл группы и распечатать список студентов, имеющих средний балл ниже среднего балла группы. 22. Вычислить средний балл группы в последнюю сессию и распечатать список студентов, имеющих средний балл, равный среднему баллу группы (округлить до второго знака). 23. Упорядочить список студентов по году рождения и распечатать его. 24. Распечатать список студентов, упорядоченный по месяцу рождения. 25. Распечатать список студентов, упорядоченный по алфавиту. 26. Распечатать список отличников, упорядоченный по году рождения. 27. Распечатать список студентов, упорядоченный по дате рождения. Список товаров Данные о товаре заданы списком: название товара, цена товара, количество товара, год выпуска. Написать программу, подготавливающую данные о N товарах, упорядоченных определенным образом по заданному признаку, и программу, добавляющую к ранее введенным товарам еще М товаров. Общий список также должен быть упорядочен по указанному в варианте признаку. Если среди добавляемых товаров встречается товар, сведения о котором в файле уже есть, то необходимо их обновить, т.е. старую запись исключить. Варианты заданий представлены в таблице, где F-принцип, по которому упорядочивается товар. № вар. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 F 1 2 3 4 5 6 1 2 3 4 5 6 1 2 N 10 9 11 9 7 12 13 10 13 12 11 10 7 8 M 3 4 4 6 3 5 4 3 6 4 3 3 5 5 № вар. 15 16 17 18 19 20 21 22 23 24 25 26 27 28 F 3 4 5 6 1 2 3 4 5 6 1 2 3 4 N 7 8 9 8 8 11 11 10 9 11 9 7 12 13 M 6 5 4 6 3 5 5 4 3 6 4 5 3 3 № вар. 29 30 31 32 33 34 35 36 37 38 39 40 41 42 F 3 4 5 6 1 2 3 4 5 6 1 2 3 4 N 10 13 12 11 10 8 7 6 7 8 9 10 9 9 M 4 4 6 2 2 4 3 5 6 2 4 3 2 2 F Принцип упорядочивания N – количество товаров в первоначальном списке 1 Неубывание цены 2 Неубывание года выпуска 3 Неубывание количества M – количество добавляемых товаров 4 Невозрастание цены 5 Невозрастание года выпуска 6 Невозрастание количества Знаки Зодиака Написать программу, которая по введённой дате некоторого дня года выдаёт на экран персонального компьютера знак Зодиака, с указанием интервала действия этого знака: 20.01-18.02: Водолей 105 106 19.02-20.03: Рыбы 21.03-19.04: Овен 20.04-20.05: Телец 21.05-21.06: Близнецы 22.06-22.07: Рак 23.07-22.08: Лев 23.08-22.09: Дева 23.09-22.10: Скорпион 23.11-21.12: Стрелец 22.12-19.01: Козерог Отдел кадров Разработать программу, с помощью которой можно создать и частично корректировать базу данных, содержащую следующие сведения: 1) фамилию, имя, отчество, 2) должность, 3) образование, 4) стаж работы на предприятии, 5) количество детей. Для каждого из k сотрудников (k>10) заработная плата – массив Z(k) состоит из основной и надбавки. Числовые значения основной заработной платы Z0 (не подумайте, что реальной!) задать в интервале от 30000 до 50000 рублей с помощью встроенного генератора случайных чиcел. Рассчитать для каждого сотрудника надбавку к зарплате Zd и полную заработную плату ZZ, которая определяется по формуле ZZ = Z0 + Zd, Zd = Z0*k, где k – коэффициент надбавки, зависящий от должности и образования. Увеличение этого коэффициента в зависимости от количества детей определяется по формуле k = k+0,1*n, где n – количество детей, n не более трех. Должность Образование высшее Н/высшее Ср. спец. Н/ср. спец. Руководитель 3 2 1,8 0,5 Секретарь 1,3 1 0,5 0 Инженер 1,5 1 0,2 0 Экономист 1,8 1 0,8 0,1 Гл. бухгалтер 2 1,5 1 0,3 |