Книга "Алгоритмы и программы решения задачпо информатике"

Рубрика эта появилась в связи с выходом в свет моей книги.

"Алгоритмы и программы решения задач по информатике"

Издательско – книготорговая фирма «Константа-И»
Директор Иссерт Константин Ильич
Украина, 69039, г. Запорожье, ул. Украинская, 143
тел.: (0612) 62-50-70
факс : (0612) 13-75-06
E – mail: oleg@konst.marka.net.ua

С ноября 2001 г. у нас будет новый адрес:
69095, г. Запорожье, проспект Ленина, 142

Содержание

Введение

Основы решения задач

Задача о нахождении наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК)

Битовые операции

Not – логическое отрицание

Or – логическое сложение

And – логическое умножение

Xor – операция, исключающая «или»

Одномерные булевы массивы

Двухмерные и многомерные булевы массивы (или размещение многомерных массивов в одномерных)

Задача о подсчете числа единиц в двоичной записи числа

Задача о выводе числа в произвольной системе счисления

Задача о простых делителях числа

Задача о простых числах

Задача об арифметической прогрессии

Динамические информационные структуры

Стеки
Очереди
Деки
Списки
Представление разреженных матриц в виде списков

Вычисление арифметических выражений и связанные с этим задачи

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

Рекурсия и уход от нее

Задача «Снежинка»
Задача о генерации всех возможных перестановок натуральных чисел
Задача о генерации полного набора подмножеств
Задача о генерации всех возможных сочетаний натуральных чисел
Задача о лабиринте
Задача о заливке

Сортировка и поиск

Задача об упорядочивании элементов массива
Задача о сортировке сверхбольших объемов данных
Задача об упорядочивании двухмерного массива
Задача о быстром поиске в упорядоченном массиве
Задача о подсчете количества одинаковых элементов массива

Заключение

Введение

В книге рассмотрены типичные и базовые алгоритмы, которые помогут при решении разнообразных задач по информатике. Приведенные примеры призваны научить правильно и быстро составлять каждый из рассмотренных алгоритмов. Это должно стать тем теоретическим и практическим фундаментом, основываясь на котором в дальнейшем можно решить намного более широкий спектр проблем. Как правило, все достаточно сложные задачи разбиваются на несколько элементарных подзадач, каждая из которых решается уже намного проще.

Книга рассчитана на тех, кто владеет одним из языков программирования: Си или Паскаль. Среднего уровня будет вполне достаточно. Материал построен таким образом, чтобы помочь человеку, совершенно не знакомому с правилами и методами построения алгоритмов, научиться решать не только учебные, но и сложные комплексные задачи программирования.

В начале каждой главы рассмотрен перечень теоретических вопросов, основываясь на которых строятся алгоритмы решения задач.

Условия задачи формулируются так, что в них содержится вся необходимая информация для реализации программы решения. Четко оговорены ограничения на значения переменных. Это позволяет оценивать степень продуктивности алгоритма, призванного решать поставленную задачу, а также формат вводимых данных и результатов. Решение каждой задачи разбито на три этапа. На первом рассматривается, каким образом предложенная в начале главы теория применима к каждой конкретной задаче. Далее следует подробное описание каждой из логически завершенных частей программы и принцип их совместного взаимодействия. В некоторых случаях предложены аналитический и логический методы построения алгоритмов. Каждый из них имеет свои преимущества и больше подходит для людей определенного склада ума. Одним удобнее представлять себе алгоритм в виде формулы, а другим - в виде логически связных заключений и словесно описанных элементарных действий. Затем приведены тексты программ с комментариями на языках программирования Си и Паскаль. Комментарии поясняют смысл выполняемых на том или ином участке программы действий. Если в строке записан оператор закрытия файла, то комментарии отсутствуют. Однако, перед каждой процедурой или функцией находится описание выполняемых ими действий, а также смысл и формат входных данных и результатов. Комментарии помещены перед некоторыми циклами и в трудных для понимания местах программы. Тексты программ оформлены однообразно и в соответствии с общепринятыми правилами написания программ. Каждый оператор записывается с новой строки, кроме тех случаев, когда несколько операторов выполняют одно единственное логическое действие. Тело цикла и ветвления пишутся с отступом в два пробела и т.д.

Все программы, приведенные в книге, проверены на работоспособность. Примеры программ для Паскаля успешно работают в среде Turbo Pascal 7.0/7.1 и Borland Pascal 7.0, а программы на Си оптимизированы для Borland C++ 3.1 и выше.

Существует несколько иных подходов к изложению подобного материала. В большинстве книг условия задач не оговаривают предельные значения параметров, формат входных и выходных данных. Это дает некоторую свободу при решении задачи, но при этом человек, как правило, пользуется стандартным набором принципов ввода и вывода информации. Это существенно снижает степень свободы владения языком программирования. Отсутствие ограничений на входные данные не дает возможности оценить степень эффективности предложенного алгоритма решения. Все алгоритмы делятся на два класса – те, что решают задачу, и те, что ее не решают. Это не стимулирует совершенствовать найденные методы решения задач.

В некоторых книгах программы решения задач приводятся на алгоритмическом языке. Считается, что этот язык удовлетворяет всем требованиям реального языка программирования, но часто оказывается, что это не так. В таких случаях встают проблемы, когда некоторые функции алгоритмического языка не могут быть реализованы в реальном языке, или человек просто не знает, как это сделать. С другой стороны, примеры решения задач на реальных языках лишний раз помогают поднять уровень владения языком программирования, изучить новые его возможности.

Часто рассматривается несколько задач, каждая из которых является видоизмененной версией какой-то одной базовой задачи. В книге сразу рассматривается именно эта базовая задача. Зная алгоритмы и методы решения общих проблем, всегда можно их адаптировать и локализовать для решения какой-то их части. Рассматривая решение задачи методом последовательного приближения к ее окончательной формулировке, мы как бы сводим эту задачу к частному случаю, который может быть представлен в нескольких вариантах. Эта книга предоставляет возможность изучить базовые алгоритмы и методы решения задач, основываясь на которых впоследствии будут решаться гораздо более сложные проблемы методом комбинирования их из простейших алгоритмов.

Встречаются книги, в которых в качестве решения задачи приводится отрезок кода программы, решающий проблему, но не оговорены способы взаимодействия этого отрезка программы с остальной ее частью. Такой алгоритм трудно преобразовать в полноценно работающую программу, так как не приведены методы интеграции его в реальную программу (в каком виде и как необходимо задать исходные данные; где и как формируется результат). Этот подход исключает возможность показать способы комбинирования алгоритмов.

Практика показала: лучше привести в пример работающую программу, чем десять раз рассказать, как она должна работать.

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

Материалы книги могут быть положены в основу факультатива по информатике, для занятий по подготовке к олимпиадам или конкурсам. Их достаточно для успешного участия на олимпиадах районного и областного уровней.