 |
Графические программы с применением массивов.
|
|
|
|
Рассмотрите приведенный ниже пример.
Задача. Нарисовать олимпийский флаг. Обеспечьте в программе ввод радиуса колец (R) и расположение флага на экране, задавая координаты его верхнего правого угла (Х, Y). Для хранения цветов колец использовать массив.
| Program Flag; Uses Graph; Var... U, V, X, Y, R, A, B, L, i: integer; Palitra: array [1..5] of integer; Begin write('R='); readln (R); write('X='); readln (X); write('Y='); readln (Y);...{Инициализация графического режима} Palitra [1]:= LightBlue; Palitra [2]:= Black; Palitra [3]:= Red; {Задание цветов колец} Palitra [4]:= Yellow; Palitra [5]:= Green; A:= 7*R; B:= 5*R; {Вычисление размера флага} L:= 2*R-round(R/4); {Вычисление расстояния между кольцами} SetFillStyle(1, 15); Bar (X, Y, X+A, Y+B); {Рисование белого флага} SetLineStyle(0, 1, 3); U:= X+Round (1.75*R); {Координаты первого верхнего кольца} V:= Y+L; for i:= 1 to 5 do {Рисование пяти колец} begin if i=4 Then Begin U:= X+Round(2.65*R); {Координаты первого нижнего кольца} V:= Y+3*R; End; SetColor(Pal[i]); {Задание цвета i-го кольца} Circle(U, V, R); {Рисование кольца} U:= U+L; {Расположение следующего кольца} end; readln; CloseGraph; End. |
Выберите самостоятельно задачу из ниже предложенного перечня:
- Нарисовать радугу в нижней части экрана.
- Вывести разноцветные концентрические кольца с центром в середине экрана. Обеспечить диалоговый ввод последовательности меняющихся цветов колец и контроль выхода за границы экрана.
- Модифицировать задачу 2 для рисования разноцветных неконцентрических колец, цвета которых вводятся в диалоге.
- Нарисовать шахматную доску. Расставить шашечную позицию, которая запрашивается с экрана. Расположение шашки задается парой чисел: номером клетки по вертикали и по горизонтали.
- Нарисовать схему расположения городов, которые отмечаются на экране кружочками. Координаты городов предварительно вводятся с клавиатуры.
- Модифицировать предыдущую задачу, предполагая, что размер кружка зависит от численности населения города.
- Изобразить на экране движение шара по биллиардному столу с лузами. Расположить лузы по краям биллиардного стола, задав их координаты в диалоге. Движение шара прекращается при попадании его в лузу.
- Получить мультфильм "Круги на воде", используя концентрические окружности. Центры окружностей должны быть совмещены с центром экрана. Иллюзия движения создается последовательной сменой цветов всех окружностей, начиная с внутренней и кончая внешней. Обеспечить ввод максимального и минимального радиусов в диалоге, а также количество волн и последовательность сменяющихся цветов.
- Промоделировать работу светофора без учета дорожной обстановки. Обеспечить ввод временных интервалов смены цветов. Для обеспечения временной задержки используйте процедуру Delay.
- Нарисовать поле размером 10х10 для игры в "Морской бой". На нем с помощью датчика случайных чисел расставить 10 однопалубных кораблей, чтобы они не соприкасались друг с другом. Изобразить позицию на экране компьютера.
Сортировка массива. Способы сортировки массива.
|
|
|
Для решения многих задач удобно сначала упорядочить данные по определенному признаку, так можно ускорить поиск некоторого объекта. Например, в преферансе игроки раскладывают карты по мастям и по значению. Так легче определить, каких карт не хватает. Или возьмем любой энциклопедический словарь - статьи в нем упорядочены в алфавитном порядке.
Перегруппирование заданного множества объектов в определенном порядке называют сортировкой.
Почему сортировке уделяется большое внимание? Вы это поймете, прочитав цитаты двух великих людей.
"Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования." /Д. Кнут/
|
|
|
"Создается впечатление, что можно построить целый курс программирования, выбирая примеры только из задач сортировки." /Н. Вирт/
Отличительной особенностью сортировки является то обстоятельство, что эффективность алгоритмов, реализующих ее, прямо пропорциональна сложности понимания этого алгоритма. Другими словами, чем легче для понимания метод сортировки массива, тем ниже его эффективность.
Сегодня существует множество методов сортировки, но для понимания сути сортировки рассмотрим некоторые из них.
Но прежде чем перейти к рассмотрению конкретного алгоритма той или иной сортировки немного вспомним материал, который пригодится нам в дальнейшем.
Задача. Даны две целочисленные переменные х и y. Составить фрагмент программы, после выполнения которого значения этих переменных распределяются в порядке убывания.
Обмен значений переменных нужно производить лишь в том случае, если х<у. Для того чтобы не потерять начальное значение переменной х, введем дополнительную переменную t.
| if x<y then begin t:=x; x:=y; y:=t; end; |
Задача. Составить фрагмент программы поиска максимального числа из трех введенных с клавиатуры чисел.
Пусть а, b, c - вводимые с клавиатуры числа, Max - максимальное из их значений. На первом шаге предположим, что а - максимальное из чисел и поэтому Max:=a. Затем сравним значение предполагаемого максимума со значениями переменных b и с. Если значение m окажется меньше, чем значение очередной переменной, то переопределим значение максимума.
| ... m:=a; if m<b then m:=b; if m<c then m:=c;... |
Задача. Дан массив а, состоящий из 10 элементов. Составить программу поиска максимального элемента массива.
Используем идею предыдущей задачи. Перед началом поиска выберем условно в качестве максимального первый элемент массива Max:=a[1]. Затем по очереди каждый элемент массива сравним со значением переменной m. Если он окажется больше, то изменим значение Max. После анализа всех элементов массива переменная Max содержит значение максимального элемента массива.
| ... Max:=a[1]; for i:= 2 to 10 do if Max<a[i] then Max:= a[i];... |
До написания программ Вам необходимо выполнить некоторую подготовительную работу - написать шаблон программы следующего содержания:
|
|
|
| Рrogram Sorting; Сonst n =...; {количество элементов в массиве} Type TArray = array [1..n] of integer; Procedure FillArray (Var a: TArray); Var i: integer; Begin for i: = 1 to n do a [i]:= Random(100); End; {конец процедуры} Procedure PrintArray (a: TArray); Var i: integer; Begin for i: = 1 to n do write (a [i]: 3, ' '); writeln; End; Begin {Главная программа} writeln('Сортировка МЕТОДОМ...'); writeln('Заполняем исходный массив: '); FillArray (a); PrintArray (a); AnySort (a, b);{имя процедуры, реализующей данный метод} writeln('Отсортированный массив: '); PrintArray (b); End. |
Для реализации различных методов сортировки Вам необходимо подготовить несколько вспомогательных процедур и функций.
- Функция, которая ищет минимальный элемент правее некоторого заданного и возвращает его номер в качестве результата. Аргументами функции являются номер элемента массива и обрабатываемый массив;
- Большинство методов сортировок основаны на обмене двух чисел. Для этой цели предназначена процедура, которая в качестве параметров берет два числа и меняет их значения;
- Также Вам пригодится процедура, которая берет элемент с индексом i, перемещает его на место элемента с номером j. А все элементы, которые имеют индексы от j до i-1 сдвигает на одну позицию вправо.
Задание. Подготовьте программу-шаблон, содержащую все рассмотренные выше процедуры и функции.
Сортировка вставкой. Сортировка выбором.
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
- количество присваиваний;
- количество сравнений.
Все методы сортировки можно разделить на две большие группы:
- прямые методы сортировки;
- улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
- сортировка вставкой (включением);
- сортировка выбором (выделением);
- сортировка обменом (так называемая "пузырьковая" сортировка).
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса
|
|
|
Рассмотрим сортировку методом вставки.
Принцип метода заключается в следующем:
Массив разделяется на две части: отсортированную и не отсортированную. элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной - все остальные элементы.
Таким образом, алгоритм будет состоять из (n-1)-го прохода (n - размерность массива), каждый из которых будет включать четыре действия:
- взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;
- поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
- сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;
- вставка взятого элемента в найденную i-ю позицию.
Для реализации данного метода можно предложить несколько алгоритмов, которые будут отличаться способом поиска позиции вставки.
Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:
| Procedure Vstavka(Var a: Array1); Var i, j,e,g:integer; Begin for i:=2 to c do begin e:=A[i]; j:=1; while (e>a[j]) do Inc(j); for g:=i-1 downto j do a[g+1]:=a[g]; a[j]:=e; end; End; |
Задание. Составьте программу сортировки одномерного массива рассмотренным методом.
Сортировка выбором
Принцип метода:
Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.
Рассмотрите схему алгоритма прямого выбора.
Сортировка методом простого обмена. Рекурсивная сортировка.
Принцип метода:
Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.
После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.
Задание. В тетради начертите схему работы рассмотренного алгоритма произвольно выбранного массива.
|
|
|
Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:
| Procedure Obmen(Var a: Array1); Var i,j,f,g:integer; Begin for i:=n downto 2 do for j:=1 to i-1 do if a[j]>a[j+1] then begin f:=a[j]; a[j]:=a[j+1]; a[j+1]:=f; end; End; |
Задание. Составьте программу сортировки одномерного массива рассмотренным методом.
|
|
|
