Программирование различных типов задач

МУНИЦИПАЛЬНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ГИМНАЗИЯ №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? После сортировки линейный проход позволяет нам посчитать число раз, которое встречается каждый элемент.

· Восстановление первоначального порядка. Как мы можем восстановить первонача

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать