ДРУГИЕ ЗАДАЧИ ПО ПРОГРАММИРОВАНИЮ

Задача 1.

Методом трапеций вычислите площадь круга радиусом 1, определите значение числа π.

Площадь единичного круга равна учетверенному значению интеграла

Значение интеграла может быть найдено методом трапеций по следующей формуле:

Используемая программа ПР-1 приведена ниже. При ее запуске на экране получается следующее значение: 3,1415926164.

Программа ПР-1.

Задача 2.

Напишите программу, переводящую десятичное число в шестнадцатиричную систему счисления.

Программа ПР-2 работает так. Десятичное число, которое необходимо перевести в шестнадцатиричную систему счисления, присваивается переменной a. В начале цикла значение переменной a присваивается переменной b, а переменной a присваивается целая часть от деления a на 16. После этого определяется разность b - 16 * a, соответствующая цифра записывается в младший разряд. После этого все повторяется снова.

Программа ПР-2.

Задача 3.

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

Используется программа ПР-3. Последовательность команд исполнителя записана в виде: a:='drd . . . luld'. При этом u - вверх, d - вниз, r -вправо, l - влево. Программа содержит цикл, в котором вырезается по одному символу, в результате чего светящаяся точка на экране монитора смещается с некоторым шагом вверх, вниз, вправо или влево.

Программа ПР-3.

Задача 4.

Напишите тестирующую программу, проверяющую умение решать примеры по арифметике.

Используемая программа ПР-4 содержит цикл, в котором задаются случайные значения переменных a и b и генерируется пример типа a * b = ?. Тестируемый вводит ответ n, компьютер сравнивает его с правильным ответом c = a * b. Определяется число правильных ответом, ставится оценка.

Программа ПР-4.

Задача 5.

Археологи А, Б и В нашли монету. Каждый высказал по 2 предположения: 1) А сказал: монета греческая, V век; 2) Б сказал: монета испанская, III век; 3) В сказал: монета не греческая, IV век. Каждый из археологов прав только в одном из двух предположений. Где и когда была выпущена монета?

Обозначим простые высказывания: G = 1 - монета греческая, I = 1 - монета испанская, P = 1 - пятый век, C = 1 - четвертый век, T = 1 - третий век. Каждый из археологов прав только в одном из двух предположений, поэтому высказывания 1, 2, и 3 приводят к следующим логическим уравнениям:

1) G not(P) + not(G) P = 1,
2) I not(T) + not(I) T = 1,
3) not(G) not(C) + G C = 1.

Монета не может быть изготовлена в двух государствах и двух веках:

GI=0, PC=0, PT=0, CT=0.

Решением этой задачи является программа ПР-5. В ней автоматически перебираются все возможные варианты и находится такой, при котором истинны все 7 уравнений. Число истинных уравнений обозначено через k. Необходимо запустить программу и найти строчку, для которой k=7.

Программа ПР-5.

Задача 6.

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

Кластеризация иерархического типа состоит в последовательном объединении групп объектов, начиная с самых близких и похожих друг на друга. Рассмотрим множество из n объектов O1 (x1, y1), O2 (x2, y2), ..., On (xn, yn), каждый из которых характеризуется двумя признаками X и Y. В пространстве признаков XOY каждому объекту соответствует точка. В качестве меры близости двух объектов Oi и Oj обычно выбирают геометрическое расстояние между этими точками:

На начальном этапе считают, что каждый объект образует кластер с массой 1. Для каждой пары точек определяют меру близости Si,k и, сравнивая их друг с другом, находят наиболее близко расположенные объекты, которые объединяются в один кластер с массой 2. Координаты нового кластера вычисляются как средние взвешенные координат объединенных кластеров. Затем процесс повторяется. При слиянии двух кластеров Oi и Oj (i меньше j) c весовыми коэффициентами pi и pj получается кластер Oi, имеющий следующие координаты и весовой коэффициент соответственно:

В результате N-Ch_kl шагов, на каждом из которых два кластера объединяются в один, получается разбиение на Ch_kl кластеров. Результат использования программы ПР-6 для кластеризации 30 двумерных объектов представлен на рис. 1. Если отключить графический режим, закомментировать соответствующие операторы и раскомментировать другие, то на экран будет выведен список объектов с указанием класса, к которому он отнесен.

Программа ПР-6.

Рис. 1. Результат классификации объектов на 3 группы

Задача 7.

Напряжение изменяется по периодическому закону U=U(t). Напишите программу, осуществляющую разложение функции U=U(t) в ряд Фурье. Восстановите функцию и постройте график.

Формулы для разложения периодической функции в ряд Фурье имеют вид:

В предлагаемой программе методом прямоугольников вычисляются постоянная составляющая U0, косинусоидальные и синусоидальные члены ряда a[n] и b[n] для двадцати первых гармоник. По результатам строят график восстановленного сигнала (рис. 2).

Программа ПР-7.

Рис. 2. Разложение в ряд Фурье

Задача 8.

Методом динамического программирования найдите наиболее короткий путь из города 1 в город 2 (рис. 3), если длины дорог, соединяющих города, известны.

Рис. 3. К вычислению наикратчайшего пути

На рис. 3 изображен граф, - вершины - города, ребра - дороги. Решение задачи "в лоб" предполагает перебор всех возможных вариантов путей из 1 в 2 с целью нахождения оптимального пути. Это неудобно, так как вариантов очень много. Поэтому будем использовать метод динамического программирования. Процесс выбора того или иного пути будем считать управляемым. В данном случае выигрыш (или проигрыш) управляемого процесса складывается из выигрышей на каждом шаге (выборе следующего города). Как известно, планируя многошаговый процесс и выбирая управление на каждом шаге, следует учитывать все его последствия на предстоящих шагах. Управление на данном шаге выбирают так, чтобы выигрыш на этом и всех последующих шагах был максимален.

Используемый алгоритм состоит в следующем. Путник идет из 1 в 20, поэтому начнем рассмотрение с конца пути - с вершины 20. Программа обходит вершины 19, 18, 17 и сохраняет в массиве минимальную длину пути до пункта 20. Затем она обходит вершины 16, 15, 14, 13 и сохраняет в соответствующих элементах массива минимальное расстояние до конца пути - города 20. Например, у города 18 put[18] = 13, у города 19 put[19] = 14. Из рис. 3 видно, что из города 15 наикратчайший путь в город 20 - 15 - 18 - 20 равен 22. Это значение и следует сохранить в массиве: put[15] = 22. В другом массиве traek[i] в виде символьной переменной следует сохранять наикратчайший путь (последовательность пройденных городов) из данного пункта i до пункта 20. После обхода всех вершин в обратном порядке 20 - 1 для каждой вершины графа определяется минимальная длина пути put[i] до города 20 и оптимальный маршрут traek[i]. Используется программа ПР-1, результаты выводятся на экран. С целью удобства перед всеми расчетами создается массив, соответствующий графу (рис. 3); он тоже выводится на экран.

Программа ПР-8.

В результате работы программы на экран выводится массив s[i,j] и список городов с расстояниями put[i] до города 20 и траекторией. Первая строчка соответствует решению задачи: из пункта 20 в пункт 1 можно попасть по пути: 20-18-15-11-7-4-1, его общая длина 58 единиц.

Задача 9.

Напишите программу, которая работает так: компьютер случайно загадывает число от 1 до 256. Вы пытаетесь угадать. Компьютер отвечает: "больше" или "меньше".

Тексты программ находятся в zip-архиве, файл gl-18.pas.


ВВЕРХ

Майер, Р. В. Задачи, алгоритмы, программы / Р. В. Майер [Электронный ресурс]. - Глазов: ГГПИ, 2012 // Web-site http://maier-rv.glazov.net .

Сайт управляется системой uCoz