Задания обычной сложности

1. В городе имеется 2 склада муки и 2 хлебозавода. Ежедневно с 1-го склада вывозится 50 т муки, а со второго – 70. Эта мука доставляется на хлебозаводы, причем 1-й завод получает 40 т, а второй – 80. Перевозка одной тонны муки с первого склада на первый завод стоит с₁₁, с первого склада на второй – с₁₂, со второго склада на первый завод – с₂₁, а со второго склада на второй завод – с₂₂. Как нужно спланировать перевозки, чтобы их стоимость была минимальной?

2. Фабрика выпускает стулья двух видов. На изготовление одного стула первого типа, стоящего с1, расходуется m1 метра досок, n1 м2 обивочной ткани и р1 человека-часа рабочего времени. Аналогично для второго стула – с2, m2, n2, p2. В распоряжении М метров досок, N – ткани, Р – рабочего времени. Какие стулья и в каком количестве выпускать, чтобы стоимость продукции была максимальной? Результаты представить графически.

3. Написать программу кодирования текста с использованием алгоритма Фано (см. пп. 6.2.3 [6])

4. Для уравнений x3­–4x2+10x–10=0 и x+1–1/x=0 построить графики, отделить корни уравнений и уточнить их с точностью до 10-3 (см. [5])

5. Составить программу построения аппроксимирующего полинома степени m по n заданным точкам (n>m). Использовать метод Гаусса или Гаусса-Зейделя [5]

6. Написать программу кодирования текста с использованием алгоритма Хаффмана (см. пп. 6.2.5 [6])

7. Написать программу сжатия текста с использованием алгоритма Лемпела - Зива (см. пп. 6.4.3 [6])

8. Написать программу распаковки текста с использованием алгоритма Лемпела - Зива (см. пп. 6.4.3 [6])

9. Расставить на шахматной доске 8 ферзей, чтобы ни один не был под ударом.

10. Используя методы приближённого вычисления определенных интегралов (формулу прямоугольников и формулу Симпсона) [5] найти с точностью 10-4 число π по формуле:

11. Построить по точкам график функции

(0≤ x ≤ 2π)

При решении использовать методы приближённого вычисления определенных интегралов (формулу Симпсона) [5]. Принять

12. Два игрока одновременно загадывают по четырехзначному числу. В каждом из чисел не должно быть повторяющихся цифр. Для того чтобы отгадать эти числа, игроки поочередно называют предполагаемые числа. В ответе указывается количество цифр, которые оказались и в загаданном и в названном числе (коровы), и количество цифр, которые оказались в одних и тех же позициях (быки). Написать программу, играющую за одного из игроков.

13. «Удав». Некоторое время назад пользовалась популярностью игра «УДАВ». На игровом поле 25*25 клеток расположен удав и бонус. Удав представляет собой несамопересекающуюся последовательность клеток, каждая из которых имеет общую сторону со следующей. Начальная клетка последовательности – голова, конечная – хвост. Остальные образуют туловище. Бонус - специальным образом помеченная клетка поля.

За каждый ход голова удава может двигаться на свободную клетку вперед, вправо и влево. Одновременно, следующая за головой, занимает место головы, следующая за ней клетка встает на ее место и т.д. Клетка хвоста – свободна. Если голова удава пересечет бонус, то его туловище удлиняется на одну клетку. Если удав «натыкается» на границу игрового поля, то он погибает.

14. Построить правильные многоугольники вписанные и описанные около заданной окружности.

15. «Бильярд». В программе необходимо изобразить бильярдный стол, шар и кий. Направления движения шара зависит от угла поворота кия. Поворот осуществляется с помощью клавиш  и . Удар производится при нажатии клавиши Enter. Указать траекторию движения шара.

16. Решить систему нелинейных уравнений методом Ньютона с точностью =10-5. Начальное приближение оценить графически. Построение графиков осуществлять программно.

17. «Преследование». Нарисовать траекторию движения собак, находящихся в углах квадрата и начинающих бежать друг к другу по кратчайшему расстоянию по часовой стрелке. Причем первая собака бежит ко второй, вторая к третьей, третья к четвертой и четвертая к первой.

18. Задано m пар неповторяющихся символов, воспринимаемых как скобочные пары, т.е. если (a, b) – одна из пар, то a – левая скобка, b – соответствующая правая скобка. Вводится текст, состоящий из любой последовательности символов и пробела. Текст считается корректным, если соблюдаются скобочные правила: за левой скобкой рано или поздно следует соответствующая правая скобка. Предусмотреть произвольную вложенность скобок. Надо определить корректность любого введенного текста.

И текст и пары скобок считать из входных файлов. В программе использовать стек. Проиллюстрировать решение анимацией.

19. Построить графики функций.

При вычислении интеграла использовать метод Симпсона [5]. Количество точек разбиения вводить в диалоге.

20. Дельта волна. На треугольном поле, устроенном так, как показано на рис. 1, клетки пронумерованы последовательными натуральными числами от единицы до бесконечности. (Рис. 1).

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

Во входном файле содержатся числа M и N, разделенные одним или несколькими пробелами. Числа M и N - натуральные, не менее единицы и не более одного миллиарда.

Программа должна показать на экране кратчайший маршрут из N в M, а в выходной файл длину записать его длину.

21. Пусть на плоскости заданно конечное множество М точек в декартовой системе координат. Правильной выпуклой оболочкой множества М называется минимальное по включению выпуклое множество, содержащее М и ограниченное замкнутой ломанной, звенья которой либо параллельны одной из осей координат, либо наклонены к ним под углом в 45 градусов.

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

Разработайте входного формат, который должен содержать координаты множества точек.

Программа должна на экране отобразить точки и многоугольник, построенный по правилам, определенным у условии задачи.

22. Аналитически любой граф может быть задан списком ребер, т.е. набором пар (ui, vi), i=1,…,m номеров вершин, инцидентных i-ому ребру. В памяти этот список хранится в виде двумерного массива mx2.

Другой способ аналитического задания графа – список смежностей – перечень вершин, смежных с каждой j-ой вершиной. В памяти такой список хранится в виде массива однонаправленных динамических списков (рис.2):

Каждый элемент списка содержит 2 поля: а) номер данной смежной вершины; б) указатель на следующий элемент списка.

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

2. Определить степень каждой вершины графа, по списку смежностей.

23. Манипуляции с графом (см. условие предыд. задания):

1. Создать список смежностей неориентированного графа;

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

3. Составить процедуру добавления в этот список вершины с заданным номером.

24. Из заданного на плоскости множества точек (их координаты вводить из файла) выбрать те, которые образуют треугольники и нарисовать их.

25. Заданы n пар точек на плоскости, являющихся концами отрезков. Определить количество треугольников, получающихся при пересечении этих отрезков. Хранение данных организовать в виде списка, результат проиллюстрировать графически.

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

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

Требуется для заданной системы шестерен определить, будет ли система работоспособной или ее заклинит.

Входные данные находятся в текстовом файле input.txt. Разработать формат этого файла. Он должен содержать информацию: скорость и направление вращения соответствующей шестерни, сообщаемое ей двигателем. Например, положительные числа обозначают вращение по часовой стрелке, отрицательные – против, а если к шестерне не подсоединен мотор, соответствующее число равно нулю. Входной файл также должен содержать информацию о том, с какими шестернями соприкасается данная шестерня.

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

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

• добавлять элементы, устанавливая необходимые связи;

• осуществлять поиск элементов по имени и по таким параметрам, как курс, факультет, группа, специальность;

• распечатывать списки по курсам, по факультетам, по группам, по специальностям;

29. Прямоугольники. На плоскости задано несколько прямоугольников со сторонами, параллельными координатным осям (рис. 3). Координаты вершин прямоугольников (x,y) – целые числа.

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

Входные данные. В каждой из строк исходного файла – 4 числа - координаты 2-х противоположных вершин прямоугольника.

30. Ломаная. Координаты ломаной линии, заданные целыми числами (в пикселях экрана) считать из файла и прорисовать линию на экране. Отметить цветом точки пересечения отрезков ломаной.

31. Буквы в квадрате. Заполнить квадрат буквами по спирали.

32. Игра «Жизнь» Клетка рождается, если имеет 3-х соседей, живет, если имеет 2-3 соседей, погибает в противном случае.

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

• добавлять элементы, устанавливая необходимые связи. Добавление предусмотреть как с терминала, так и из файла;

• осуществлять поиск элементов по имени, по возрасту, по полу, по лечащему врачу и распечатывать найденные элементы.

34. Из заданного на плоскости множества точек (считать из файла) выбрать 3 такие, которые составляют треугольник наибольшего периметра.

35. * Калькулятор. Организовать работу калькулятора для вычисления значений арифметических выражений, в которых используются 4 основные операции +,–,*,/ и скобки. Вложенность скобок неограниченна. Например:

6*((30+6,5)/53-40*7/(2-7,2))