Программирование различных типов задач
- 14 - МУНИЦИПАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ГИМНАЗИЯ №64 Программирование различных типов задач Экзаменационный реферат по информатике Медведев Александр Валерьевич, 11Б Кушникова Валерия Петровна, учитель Липецк 2007 Содержание I. Введение II. Основная часть: 1.Способы сортировки 2. Теория чисел 3. Задача «Красивые числа» III. Список используемой литературы Вступление При программировании очень важно понять, насколько мощным является то, что вы знаете. В принципе любой интересный алгоритм/программу можно написать, основываясь на тех знаниях, которые вы получили в самом начале обучения программирования. Все мощные способности современных языков не обязательны для построения интересных вещей - они нужны только для того, чтобы построить их более четко и удобно. Говоря другими словами, хорошим писателем становится не тот, кто выучил много слов из словаря, а тот, кто нашел, о чем рассказать. Для написания качественных программ, можно дать несколько простых советов: - Пишите сначала комментарии. Начинайте ваши программы и процедуры с нескольких предложений, которые объясняют то, что они должны делать. Это важно, потому что если вы не сможете с легкостью написать эти комментарии, то, вероятнее всего, вы не понимаете, что делает программа. Редактировать комментарии гораздо проще, чем редактировать программу , поэтому время, потраченное на дополнительное печатание, потрачено с большой выгодой. Конечно из-за того, что на соревнованиях обычно поджимает время, появляется привычка быть небрежным, но в этом нет ничего хорошего. - Документируйте каждую переменную. Напишите одну строку комментария для каждой переменной, чтобы бы вы знали, что она делает. И снова, если вы не можете четко это написать, то вы не понимаете, что она тут делает. Вы будете общаться с программой, по крайней мере, несколько циклов отладки, и вы оцените это скромное вложение в ее читабельность. - Используйте символьные константы. Когда бы вам ни потребовалась константа в вашей программе(размер входных данных, математическая константа, размер структуры данных и т.д.), объявляйте ее в самом начале программы. Использование противоречивых констант может привести к очень сложным и труднообнаруживаемым ошибкам. Конечно, символьное имя нужно только тогда, когда вы собираетесь его использовать в том месте, где должна быть константа - Используйте подпрограммы, чтобы избежать излишнего кода. Гораздо безопаснее написать одну подпрограмму и вызывать ее с соответствующими параметрами, чем повторять одно и тоже с разными переменными. Сортировка Сортировка является наиболее фундаментальной алгоритмической задачей в теории вычислительных машин и систем по двум различным причинам. Во-первых, сортировка - это полезная операция, которая эффективно решает многие задачи, с которыми встречается каждый программист. Во-вторых, были разработаны буквально десятки различных алгоритмов сортировки, каждый из которых основывается на определенной хитрой идее или наблюдении. Большинство примеров разработки алгоритмов ведет к интересным алгоритмам, включающим «разделяй и властвуй», рандомизацию, инкрементную вставку и продвинутые структуры данных. Из свойств этих алгоритмов следует множество интересных задач по программированию. Ключом к пониманию сортировки является понимание того, как она может быть использована для решения многих важных задач программирования. Рассмотрим некоторые случаи применения сортировки. · Проверка уникальности. Как мы можем проверить, все ли элементы данного набора объектов S являются различными? Отсортируем их либо в возрастающем, либо в убывающем порядке, так что любые повторяющиеся объекты будут следовать друг за другом. После этого один проход по всем элементам с проверкой равенства S[i]=s[i+1] для любого 1?i<n решает поставленную задачу. · Удаление повторяющихся элементов. Как мы можем удалить все копии, кроме одной, любого из повторяющихся элементов S? Сортировка и чистка снова решают задачу. Обратите внимание, что чистку проще всего производить, использую два индекса - back, указывающий на последний элемент в очищенной части массива, и i, указывающий на следующий элемент, который нужно рассмотреть. Если S[back]<>S[i], увеличиваем back и копируем S[i] в S[back]. · Распределение приоритетов событий. Предположим, что у нас имеется список работ, которые необходимо сделать, и для каждой определен свой собственный срок сдачи. Сортировка объектов по времени сдачи (или по аналогичному критерию) расположит работы в том порядке, в котором их необходимо делать. Очереди по приоритетам удобны для работы с календарями и расписаниями, когда имеется операции вставки и удаления, но сортировка удобна в том случае, когда набор событий не меняется в ходе выполнения. · Медиана/выбор. Предположим, что мы хотим найти k-й по величине объект в S. После сортировки объектов в порядке возрастания нужный нам будет находится в ячейке S[k]. В определенных случаях этот подход может быть использован для нахождения наименьшего, наибольшего и медианного объекта. · Расчет частоты. Какой элемент чаще всего встречается в S? После сортировки линейный проход позволяет нам посчитать число раз, которое встречается каждый элемент. · Восстановление первоначального порядка. Как мы можем восстановить первоначальное расположение набора объектов, после того как мы переставили их для некоторых целей? Добавим дополнительное поле к записи данных объекта, такое что i-й записи это поле равняется i. Сохранив это поле во время всех перестановок, мы сможем отсортировать по нему тогда, когда нам потребуется восстановить первоначальный порядок. · Создание пересечения/объединения. Как мы можем рассчитать пересечение или объединение двух контейнеров? Если они оба отсортированы, мы может объединить их, если будем выбирать наименьший из двух ведущих элементов, помещать его в новое множество, если хотим, а затем удалять из соответствующего списка. · Поиск необходимой пары. Как мы можем проверить, существуют ли два целых числа x,yS таких ,что x+y=z для какого-то заданного z? Вместо того, чтобы перебирать все возможные пары, отсортируем числа в порядке возрастания. С ростом S[i], при увеличении I, его возможный партнер j, такой что S[j]=z-S[i], уменьшается. Таким образом, уменьшая j соответствующим образом при увеличении I, мы получаем изящное решение. · Эффективный поиск. Как мы можем эффективно проверить, принадлежит ли элемент s множеству S? Конечно, упорядочивание множества с целью применения эффективного бинарного поиска - это, наверное, наиболее стандартное приложение сортировки. Просто не забывайте остальные! Рассмотрим несколько достаточно поучительных алгоритмов сортировки Сортировка пузырьком Расположим массив сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию... Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию. Type arrType = Array[1 .. n] Of Integer; Procedure Bubble(Var ar: arrType; n: integer); Var i, j, T: Integer; Begin For i := 1 To n Do For j := n DownTo i+1 Do If ar[Pred(j)] > ar[j] Then Begin { < } T := ar[Pred(j)]; ar[Pred(j)] := ar[j]; ar[j] := T End End; Сложность этого метода сортировки составляет О(n^2) Пузырьковая сортировка с просеиванием Аналогичен методу пузырьковой сортировки, но после перестановки пары соседних элементов выполняется просеивание: наименьший левый элемент продвигается к началу массива насколько это возможно, пока не выполняется условие упорядоченности. Преимущество: простой метод пузырька работает крайне медленно, когда мин/макс (в зависимости от направления сортировки) элемент массива стоит в конце, этот алгоритм - намного быстрее. const n = 10; var x: array[1 .. n] of integer; i, j, t: integer; flagsort: boolean;
procedure bubble_P; begin repeat flagsort:=true; for i:=1 to n-1 do if not(x[i]<=x[i+1]) then begin t:=x[i]; x[i]:=x[i+1]; x[i+1]:=t; j:=i;
while (j>1)and not(x[j-1]<=x[j]) do begin t:=x[j]; x[j]:=x[j-1]; x[j-1]:=t; dec(j); end; flagsort:=false; end; until flagsort; end; Тестировалось на массиве целых чисел (25000 элементов). Прирост скорости относительно простой пузырьковой сортировки - около 75%... Метод последовательного поиска минимумов Теория: Просматривается весь массив, ищется минимальный элемент и ставится на место первого, "старый" первый элемент ставится на место найденного type TArr = array[1..100] of integer;
var mass1 : TArr; n : integer;
procedure NextMinSearchSort(var mass:TArr; size:integer); var i, j, Nmin, temp: integer; begin for i:=1 to size-1 do begin nmin:=i; for j:=i+1 to size do if mass[j]<mass[Nmin] then Nmin:=j;
temp:=mass[i]; mass[i]:=mass[Nmin]; mass[Nmin]:=temp; end; end; Сортировка вставками Сортировка простыми вставками в чем-то похожа на вышеизложенные методы. Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность... Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы. Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется. Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда 1. Hайден элемент, меньший x или 2. Достигнуто начало последовательности. Type arrType = Array[1 .. n] Of Integer;
Procedure Insert(Var ar: arrType; n: Integer); Var i, j, T: Integer; Begin For i := 1 To n Do Begin T := ar[i]; j := Pred(i); While (T < ar[j]) and (j > 0) Do Begin ar[Succ(j)] := ar[j]; Dec(j); End; ar[Succ(j)] := T; End; End; Сложность О(n^2) Распределяющая сортировка - RadixSort - цифровая - поразрядная Пусть имеем максимум по k байт в каждом ключе (хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки. Разрядность данных (количество возможных значений элементов) - m - также должна быть известна заранее и постоянна. Если мы сортируем слова, то элемент сортировки - буква, m = 33. Если в самом длинном слове 10 букв, k = 10. Обычно мы будем сортировать данные по ключам из k байт, m=256. Пусть у нас есть массив source из n элементов по одному байту в каждом. Для примера можете выписать на листочек массив source = <7, 9, 8, 5, 4, 7, 7>, и проделать с ним все операции, имея в виду m=9.
Страницы: 1, 2
|