задачи (1)
.pdf23.Дано множество точек Ai = (xi, yi), i= 1, …, n и координаты диагонали прямоугольника d1, e1, d2, e2. Вывести все точки и закрашенный прямоугольник, определить точки, не попадающие внутрь прямоугольника, и приняв их за центр окружности, построить закрашенные окружности радиусом 3. Вывести информацию о числе точек, не попавших внутрь прямоугольника.
24.Дано множество точек Ai = (xi, yi), i = 1, …,n и координата С. Вывести все точки на экран, соединить линией наиболее удаленные точки, провести линию (С, 0)-(С, 479). Считая точки центрами прямоугольника или окружности построить закрашенные прямоугольники или окружности. Строится прямоугольник, если точка левее линии (С, 0)-(С, 479), и окружность, если правее. Вывести информацию о числе окружностей.
25.Дано множество точек Ai = (xi, yi), i = 1, …,n и координаты точки d1, e1. Вывести все точки, соединить данную точку линиями со всеми остальными, считая ее центром, построить закрашенную окружность с радиусом, равным расстоянию до ближайшей точки. Вывести информацию о величине радиуса окружности.
26.Изобразить на экране точку, пересекающую с постоянной скоростью экран справа налево параллельно его горизонтальной оси. Очередная точка начинает движение от правого края экрана в строке, выбранной с помощью датчика случайных чисел, несколько раньше, чем предыдущая точка доходит до левого края. Попытаться добиться того, чтобы одновременно на экране двигались три, четыре точки. Цвет точки может выбираться с помощью датчика случайных чисел.
27.Изобразить на экране точку, движущуюся по произвольной окружности с постоянной угловой скоростью. Составить программу для управления скоростью движения точки по окружности . Управление производится клавишами «>» (скорость несколько увеличивается) и «<» (скорость несколько уменьшается).
28.Изобразить на экране две прямые, вращающиеся в плоскости экрана вокруг одной из своих точек. Цвет прямых меняется при переходе от предыдущего положения к следующему. Составить программу для управления с клавиатуры расстоянием между центрами вращения.
29.Изобразить на экране две движущиеся точки, траектории которых являются концентрическими окружностями. Угловые скорости точек, движущихся по разным траекториям, различны. Обе точки вращаются в одном направлении (например, по часовой стрелке). Составить программу для управления с клавиатуры скоростями вращения обоих точек.
61
30.Изобразить движущуюся прямую, которая в каждый момент касается окружности данного радиуса, центр которой совпадает с центром экрана. Точка касания перемещается по окружности с постоянной угловой скоростью. Сама окружность невидима.
12.Программирование ссылочных типов данных
Задание. Составить программу с использованием ссылочных типов данных для решения одной из следующих задач.
1.Описать процедуру, которая в списке L удваивает каждое вхождение элемента Е.
2.Описать процедуру, которая вставляет в список L элемент Е1 перед каждым вхождением элемента Е.
3.Линейный список L хранит последовательность вещественных чисел. Создать список L1 из тех элементов списка L, у которых дробная часть равна 0,5.
4.Написать программу, которая заменяет в списке L все вхождения элемента Е1 на элемент Е2.
5.Составить программу, которая проверяет, упорядочены ли элементы списка L по алфавиту.
6.Написать программу, которая находит сумму последнего и предпоследнего элементов списка L.
7.Напишите процедуру, которая подсчитывает количество слов списка L, которые начинаются и оканчиваются одной и той же литерой.
8.Напишите процедуру, которая подсчитывает количество слов списка L, которые начинаются с той же буквы, что и следующее слово.
9.Напишите процедуру, которая подсчитывает количество слов списка L, которые совпадают с последним словом.
10.Написать программу, которая по списку L строит два новых списка: L1 – из положительных элементов и L2 – из остальных элементов списка L.
11.Описать процедуру, которая вставляет в список L элемент Е1 за каждым вхождением элемента Е.
62
12.Описать процедуру, которая вставляет в список L пару новых элементов Е1 и Е2 перед его последним элементом.
13.Описать процедуру, которая вставляет за каждым вхождением элемента Е один элемент, если он есть и он отличен от Е.
14.Описать процедуру, которая добавляет в конец списка L1 все элементы списка L2.
15.Описать процедуру, которая вставляет в список L за первым вхождением элемента Е все элементы списка L1, если Е входит в L.
16.Описать процедуру, которая в списке L из каждой группы подряд идущих равных элементов оставляет только один.
17.Описать функцию, которая подсчитывает число вхождений элемента Е в список L.
18.Описать процедуру, которая находит максимальный элемент непустого списка L.
19.Написать программу, которая удаляет из списка L третье вхождение элемента Е.
20.Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.
21.Текстовый файл содержит последовательность целых чисел. Создать линейный список L из элементов этого файла и подсчитать сумму элементов списка, которые кратны 5.
22.Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят хотя бы в один из списков L1 и L2.
23.Текстовый файл содержит последовательность целых чисел. Создать линейный список L из элементов этого файла и подсчитать сумму элементов списка, порядковые номера которых – четные числа.
24.Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.
25.Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, нов то же время не входят в другой из них.
26.Описать процедуру, которая печатает текст из первых букв всех слов списка L.
63
27.Описать процедуру, которая удаляет из непустых слов списка L их первые буквы.
28.Описать процедуру, которая определяет количество слов в непустом списке L, отличных от последнего.
29.Описать процедуру, которая подсчитывает количество элементов списка L, у которых равные «соседи».
30.Описать процедуру, которая в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в список не менее двух раз.
31.Описать процедуру, которая удаляет все элементы списка, которые больше своих соседей.
32.(«Считалка») N ребят располагаются по круг. Начав отсчет от первого, удаляют каждого k-го, смыкая круг после каждого удаления. Определить порядок удаления ребят из круга.
33.Дан список из различных натуральных чисел, оканчивающихся 0. Напечатать в обратном порядке все числа между наибольшим и наименьшими числами этого списка.
34.Список содержит слова произвольной длины; между соседними словами – запятая, за последним словом – точка. Напечатать все слова максимальной длины.
35.Список содержит слова произвольной длины; между соседними словами – запятая, за последним словом – точка. Напечатать все слова, указав для каждого из них число его вхождений в этот список.
36.Список содержит последовательность слов произвольной длины; между словами – пробел, за последним словом – точка. Напечатать эти слова в следующем порядке: сначала – по алфавиту все слова из одной буквы, затем – по алфавиту все двухбуквенные слова и т.д. Одинаковые слова печатать по одному разу.
37.Дано произвольное натуральное число n. Внести в список все цифры десятичной записи числа n!.
38.С помощью списка определить, симметричен ли заданный во входном файле текст (за ним следует точка).
39.Список содержит последовательность натуральных чисел. Напечатать порядковые номера тех чисел, которые имеют наибольшую величину.
64
40.Описать процедуру, которая вставляет в непустой список L, элементы которого упорядочены по возрастанию, новый элемент Е так, чтобы сохранилась упорядоченность.
41.Создать список L2, так, чтобы его элементы образовывали следующую последовательность: отрицательное число, затем положительное и т.д.
42.Список содержит положительные и отрицательные вещественные числа. Подсчитать полусумму максимального среди отрицательных и минимального среди положительных элементов списка.
43.Дан текст, оканчивающийся точкой. Среди литер этого текста особую роль играет знак #, появление которого в тексте означает отмену предыдущей литеры текста; k знаков # подряд отменяют k предыдущих литер. Используя список, напечатать данный текст, исправленный с учетом такой роли знака #. (Например, текст ХЭ#Е##НELO#LO должен быть напечатан в виде HELO).
44.Описать процедуру, которая в списке L заменяет первое вхождение списка L1 на список L2.
45.Используйте линейный список для представления многочлена от переменной x, упорядоченного по степеням x. Напишите программу для сложения двух многочленов от переменной x.
46.Используйте линейный список для представления многочлена от переменной x, упорядоченного по степеням x. Напишите программу для дифференцирования многочлена.
47.Используя представление последовательности чисел в виде линейного списка, напишите программу, решающую задачу: «Объедините две упорядоченные последовательности в одну упорядоченную последовательность (сортировка слиянием)».
48.Линейный список содержит последовательность строк. Опишите функцию, которая подсчитывает количество строк – элементов списка, которые начинаются с того же символа, что и следующая строка.
49.Линейный список содержит последовательность строк. Опишите функцию, которая подсчитывает количество строк – элементов списка, которые совпадают с последней строкой.
50.Линейный список содержит последовательность строк. Опишите функцию, которая подсчитывает количество строк – элементов списка, которые начинаются и оканчиваются одним и тем же символом.
65
13.Программирование алгоритмов поиска
вбинарном дереве
Задание. Составить программу для решения задачи на тему «Прохождение и поиск по бинарному дереву».
1.Создайте процедуру, которая преобразует дерево – формулу Т, заменяя в нем все поддеревья, соответствующие формулам
((f1±f2)*f3) и (f1*(f2±f3)), на поддеревья, соответствующие формулам
((f1*f3) ±(f2*f3)) и ((f1*f2) ±(f1*f3)).
2.Составить программу, которая присваивает параметру Е значение элемента из самого левого листа непустого дерева Т (лист — вершина, из которой не выходит ни одной ветви).
3.Создайте процедуру, которая по формуле из текстового файла f строит соответствующее дерево – формулу Т.
4.На основе одномерного массива целых чисел построить сбалансированное дерево. Затем добавить к нему элемент Е и вернуть дереву сбалансированность.
5.Напишите функцию, которая вычисляет среднее арифметическое всех элементов непустого дерева.
6.Напишите программу, которая заменяет в дереве Т все отрицательные элементы на их абсолютные величины.
7.Описать процедуру, которая меняет местами максимальный и минимальный элементы непустого дерева Т, все элементы которого различны.
8.Составить процедуру, которая печатает дерево – формулу Т в виде соответствующей формулы.
9.На основе одномерного массива целых чисел построить сбалансированное дерево Т. Удалить из дерева элемент Е и вернуть дереву сбалансированность.
10.Составьте функцию, которая печатает элементы из всех листьев дерева Т.
11.Дан одномерный массив из десяти целых чисел. Построить на основе данного массива дерево поиска и добавить в него элементы массива, умноженные на 2.
66
12.Напишите программу, которая печатает все элементы дерева Т по уровням: сначала — из корня дерева, затем (слева направо) — из вершин, дочерних по отношению к корню, затем (также слева направо) — из вершин, дочерних по отношению к этим вершинам, и т.д.
13.Создайте процедуру, которая упрощает дерево-формулу Т, заменяя в нем все поддеревья, соответствующие формулам (f+0), (0+f), (f-0), (f*1), (1*f) на поддеревья, соответствующие значению f, а поддеревья, соответствующие формулам (f*0) и (0*f), — на вершину со значением 0.
14.Опишите процедуру, которая находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с элементом Е; если Е не входит в Т, за ответ принять -1.
15.Составьте процедуру, которая подсчитывает количество вершин на n-ом уровне непустого дерева Т. (Корень считать вершиной 0-го уровня).
16.Описать логическую функцию, определяющую, есть ли в дереве Т два одинаковых по модулю элемента.
17.Напишите программу, которая по файлу f, все элементы которого различны, строит соответствующее дерево поиска Т.
18.Напишите программу, которая записывает в файл f элементы дерева поиска Т в порядке их возрастания.
19.Элементы массива A размерностью n вычисляются по формуле:
|
k |
|
|
ak = |
∑sin ki |
, где x — натуральное число. На основе этих значений |
|
i=1 |
|||
k |
|||
|
|
построить сбалансированное дерево.
20.Описать рекурсивную функцию, которая вычисляет (как целое число) значение дерева – формулы Т.
21.Построить сбалансированное дерево из неповторяющихся элементов текстового файла f.
22.Дан одномерный массив. Построить дерево поиска на основе элементов данного массива. Удалить из дерева все элементы, кратные 3.
67
23.На основе файла f построить дерево Т. Удалить из него наименьший и наибольший элементы. Дерево сбалансировать.
24.Подсчитать количество вершин в сбалансированном дереве Т, построенном на основе множества целых чисел М.
25.Построить дерево поиска из натуральных чисел от 1 до 10000, которые являются степенями цифры 2. Подсчитать количество листов в дереве.
26.Элементы массива Y размерностью n вычисляются по формуле:
yk = (−1)k (1 +kx)2k , где x — натуральное число. На основе этих значений построить дерево поиска.
27.Построить дерево поиска из элементов текстового файла. Найти в дереве максимальный элемент и разделить все листы дерева на значение этого элемента.
28.Построить дерево поиска из элементов текстового файла. Удалить из дерева значение минимального элемента и после этого сбалансировать дерево.
29.Даны два одномерных массива А и В размерности n. Получить массив С, элементы которого рассчитываются по формуле
a
cn−1 = −n−1 + , cn = 0. Построить сбалансированное дерево на bn−1 an−1 1
основе элементов массива С.
30.На основе заданного массива А построить новый массив В, элементы которого получаются по следующему правилу:
bi = ai + ai2+1 + ai2+2 , при ai+1 ai
ai ≠ 0. На основе элементов массива В построить дерево поиска.
68