microbik.ru
1 2 3 4
НАРОДНАЯ ОБРАЗОВАНИЯ РЕСПУБЛИКА УЗБЕКМСТАН

Джизакский Государственный Педагогический Институт

Им.А.Кадырий
С.М.ЖУМАБОЕВ, Г.И.НАБИРАЕВА

Основы алгоритмизации и программирования



ДЖИЗАК 2005

С.М.ЖУМАБОЕВ, Г.И.НАБИРАЕВА

Основы алгоритмизации и программирования 42ст.

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

Несмотря на определенные отличия содержания учебных программ по информатике, в этом пособие можно выделить некоторый инвариант, изучаемый всеми категориями учащихся. Предлагаемый учебная пособия по информатике является попыткой реализации указанного инварианта. Его можно использовать как основу курса для большинства специальностей высших и средних учебных заведений. Учебная пособия является не просто сборником теоретических сведений, но и платформой для формирования навыков и умений (лабораторные работы), проверки знаний (тестовая система, контрольные вопросы).

Среди особенностей учебная пособия можно выделить следующие:

  • для каждого тематического раздела составлены контрольные вопросы; 

  • вопросы могут быть изменены преподавателем;

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


Отв.редактор к.ф.н.У.Каситов.


Рецензенты:

Д.т.н. Х.О.Туракулов, к.т.н. Р.М.Юусупов.
Утверждено к печати

Ученым советом Института ГДЖПИ.

Формат бумаги А4 (210х297), 1,2

Печет плоская. Тираж 300 экз. Заказ 25.

Цена договорная.




Издательство "Педагог" ДЖГПИ.

1.Основы алгоритмизации и программирования


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

Трансляторы делятся на два типа: интерпретаторы и компиляторы.

Интерпретатор переводит в машинный код и выполняет очередной оператор (команду) программы. Если команда повторяется, то интерпретатор рассматривает ее как встреченную впервые.

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

Примерами служебных программ — интерпретаторов являются GW Basic, Лого, школьный алгоритмический язык, многие языки программирования баз данных. Компиляторами являются Turbo Pascal, С++, Delphi.

Средства создания программ


В общем случае для создания программ нужно иметь следующие компоненты

  • текстовый редактор — для набора исходного текста программы;

  • компилятор — для перевода текста программы в машинный код;

  • редактор связей — для сборки нескольких откомпилированных модулей в одну программу;

  • библиотеки функций — для подключения стандартных функций к программе.

Современные системы программирования включают в себя все указанные компоненты и называются интегрированными системами.

Исходный текст программы можно получить без записи его вручную в текстовом редакторе. Существуют системы визуального программирования — RAD-среды (Rapid Application Development), которые, не исключая возможности записи программы вручную, позволяют создавать текст программы автоматически, путем манипуляций со стандартными элементами управления, включенными в RAD-среду. Поэтому для RAD-среды понятие «программирование» часто заменяют понятием «проектирование».

По способу разработки программ можно выделить два подхода:

  • процедурное программирование — это программирование, при котором выполнение команд программы определяется их последовательностью, командами перехода, цикла или обращениями к процедурам;

  • объектно-ориентированное программирование – программирование, при котором формируются программные объекты, имеющие набор свойств, обладающие набором методов и способные реагировать на события, возникающие как во внешней среде, так и в самом объекте (нажатие мыши, срабатывание таймера, превышение числовой границы и т.д.). Таким образом, выполнение той или иной части программы зависит от событий в программной системе.

Объектно-ориентированное программирование (ООП) не исключает, а охватывает технологию процедурного программирования.

1.1 Основные системы программирования


Из универсальных языков программирования наиболее популярны следующие: Basic; Pascal; C++; Java.

Для языка Basic существует много версий, реализованных и как интерпретаторы и как компиляторы. В России Basic традиционно используется в курсе информатики средней школы. Среда визуального программирования Microsoft Visual Basic используется как программная поддержка приложений MS Office.

Язык Pascal является компилируемым и широко используется как среда для обучения программированию в ВУЗах. RAD-средой, наследующей его основные свойства, является среда Borland Delphi.

Для языка C++ RAD-средой является Borland C++ Builder. Этот компилируемый язык часто используется для разработки программных приложений, в которых необходимо обеспечить быстродействие и экономичность программы.

Язык Java — интерпретируемый язык — позволяет создавать платформно-независимые программные модули, способные работать в компьютерных сетях с различными операционными системами. RAD-средой для него является Symantec Cafe.

1.2 Основные этапы развития языков программирования


Языки программирования развивались одновременно с развитием ЭВМ. С начала 50-х годов это были низкоуровневые языки (машинные и ассемблеры). В 1956 году появился язык Фортран, а в 1960 — Алгол-60. Это языки компилирующего типа, существенно уменьшившие трудоемкость программирования. Языки ориентированы на выполнение математических вычислений. В дальнейшем возникло большое количество различных языков, претендовавших на универсальность (PL/1) или для решения конкретных задач (COBOL — для деловых задач, ЛОГО — для обучения, Пролог — для разработки систем искусственного интеллекта). С середины 60-х до начала 80-х разработаны и получили распространение языки Pascal, Basic, Си, Ада и другие.

Принципиально новым этапом в развитии языков программирования стало появление методологии непроцедурного (ООП) программирования (см. выше). Основные достоинства ООП — быстрота разработки интерфейса программного приложения, возможность наследования свойств программных объектов.

Основы алгоритмизации


Алгоритм — это предписание некоторому исполнителю выполнить конечную последовательность действий, приводящую к некоторому результату.

В программировании алгоритм является фундаментом программы, а основным исполнителем — компьютер. На стадии тестирования алгоритма исполнителем может быть сам программист.

Алгоритм может быть записан с помощью блок-схемы, текстовым предписанием, с помощью рисунков, таблично или на специальном алгоритмическом языке. Наиболее популярны блок-схемы и предписания. Преимущество блок-схем — в наглядности алгоритма.

Основными свойствами алгоритма являются:

  • дискретность — представление алгоритма в виде последовательности шагов;

  • массовость — применимость алгоритма к некоторому множеству исходных данных;

  • определенность — за конечное число шагов либо должен быть получен результат, либо доказано его отсутствие;

  • однозначность — при повторном применении алгоритма к тем же исходным данным должен быть получен тот же результат.

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



Для изображения алгоритмов будем использовать блок-схемы, формируемые из типовых блоков, показанных на рис. 1.

В теории алгоритмов доказано, что любой, сколь угодно сложный алгоритм может быть составлен из трех основных алгоритмических структур: линейной, ветвления и цикла, показанных, соответственно на рис. 2, 3, 4.



Линейная структура предполагает последовательное выполнение действий, без их повторения или пропуска некоторых действий. Обычно программисты стремятся к тому, чтобы алгоритм имел линейную структуру.

Структура "ветвление" предполагает выполнение одной из двух групп действий в зависимости от выполнения условия в блоке ветвления. На рис. 3 знаком "+" показано выполнение условия, а знаком "-" — его невыполнение. Часто используется неполная команда ветвления, когда один из блоков действия отсутствует.

Структура "цикл" имеет несколько разновидностей. На рис. 4 показан цикл типа "пока" с предусловием. Действия внутри этого цикла повторяются пока выполняется условие в блоке ветвления, причем сначала проверяется условие, а затем выполняется действие. Достаточно часто используются другие типы цикла, показанные на рис. 5 и 6.



В цикле с постусловием проверка условия выхода из цикла выполняется после очередного действия. Цикл "для" является модификацией цикла "пока" для ситуации, когда заранее известно количество повторений некоторых действий. Запись в блоке заголовка цикла на рис.6 показывает пример описания заголовка цикла, в котором действия повторяются столько раз, сколько целых значений приобретает параметр цикла i от своего начального значения 1 до конечного N с шагом 1. Обычно шаг не указывается, если он равен 1.

В языках программирования имеются команды, реализующие показанные выше структуры.

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

Пример 1

Разработать блок-схему алгоритма Евклида, определяющего наибольший общий делитель (НОД) двух натуральных чисел A и B.

В основе алгоритма Евклида лежит правило:

НОД(A,B)= НОД(min(A,B), |A-B|),

где НОД(A,B) — наибольший общий делитель двух натуральных чисел A и B.

Основной идеей решения задачи является многократное применение указанного выше правила, после которого большее из чисел очередной пары уменьшается. Решение получено, когда числа оказываются равны друг другу. Поскольку количество повторений заранее неизвестно, в алгоритме следует применить цикл "пока" с предусловием (рис. 7).


1.3 Методика разработки алгоритмов


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

При разработке алгоритма используют следующие основные принципы.

  1. Принцип поэтапной детализации алгоритма (другое название — "проектирование сверху-вниз"). Этот принцип предполагает первоначальную разработку алгоритма в виде укрупненных блоков (разбиение задачи на подзадачи) и их постепенную детализацию.

  2. Принцип "от главного к второстепенному", предполагающий составление алгоритма, начиная с главной конструкции. При этом, часто, приходится "достраивать" алгоритм в обратную сторону, например, от середины к началу.

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

Говоря о блок-схемах, как о средстве записи алгоритма, можно дать еще один совет по их разработке. Рекомендуется после внесения исправлений в блок-схему аккуратно перерисовывать ее с учетом этих исправлений. Аккуратность записи есть аккуратность мысли программиста. Аккуратно записанный и детализованный алгоритм упрощает его программирование и отладку.

1.4 Основные этапы компьютерного решения задач


Обобщим рассмотренные выше примеры и принципы разработки алгоритмов и программ и выделим главные этапы методики программирования задач.

  1. Постановка задачи. Основное требование к постановке задачи – достаточное количество информации для решения задачи. Очень часто постановка задачи выполняется не программистом, а некоторым Заказчиком. Программист является Исполнителем заказа. От него требуется добиться от Заказчика полной информации о решаемой задаче.

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

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

  3. Разработка алгоритма. Этот этап представляет собой реализацию идеи решения задачи (см. методику разработки алгоритма).

  4. Тестирование алгоритма. Этап предполагает проверку алгоритма вручную с использованием подготовленных ранее контрольных примеров. Для сложных задач этот этап может оказаться весьма трудоемким, поэтому опытные программисты пропускают его и тестируют программу. 

  1. Программирование алгоритма. Программирование является формальной записью алгоритма средствами языка программирования.

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

  3. Эксплуатация программы и интерпретация результатов. В сложных программах может быть недостаточно тестирования для устранения всех ошибок. Очень час-то они обнаруживаются на стадии эксплуатации Заказчиком. 

Успех в разработке программы зависит от двух основных факторов: соблюдения описанной выше методики и от опыта программирования. Не следует игнорировать или недооценивать этапы проектирования программы (1 – 5), выполняемые вне компьютера. "Час, потраченный на выбор алгоритма, стоит пяти часов программирования" (Д.Ван-Тассел. Стиль, разработка, эффективность, отладка и испытание программ.- М.: Мир, 1985).

Пример 2

Рассмотрим задачу с достаточно сложным алгоритмом решения для того, чтобы, во-первых, продемонстрировать этапы 1 - 3 рассмотренной методики и, во-вторых - принцип поэтапной детализации алгоритма.   

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

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

Формализация задачи. Назовем термином "потенциал поля" количество допустимых ходов коня. Введем следующие обозначения:

  • С — матрица 8*8, содержащая потенциалы полей (фрагмент C показан на рис. 13);

  • R — матрица 8*8, содержащая решение задачи в виде номеров ходов коня;

  • Sx, Sy — массивы из 8 элементов, содержащие смещения коня относительно текущей координаты, необходимые для реализации правила буквы "Г":

Sx = ( 1, 2, 2, 1,-1,-2,-2,-1);
Sy = (-2,-1, 1, 2, 2, 1,-1,-2).

  • x, y — текушие координаты коня;

  • x1,y1 — координаты поля с минимальным потенциалом для текущих (x, y);

  • m — значение минимального потенциала допустимого поля.

Будем учитывать пройденные поля путем задания соответствующим элементам матрицы C значения 9, т.е. значения вне множества допустимых потенциалов.

1.5 Разработка алгоритма решения задачи

На рис. 8 показан укрупненный алгоритм решения поставленной задачи. На рис. 9 - 12 показаны основные шаги поэтапной детализации основного алгоритма.

   

Следует обратить внимание на нумерацию блоков в детализирующих блок-схемах. Число до первой точки является номером детализируемого блока в основной схеме. Число после первой точки является номером блока в схеме детализации первого уровня и т.д.

Входы в детализирующие блок-схемы и выходы из них показаны окружностями с номерами блоков — источников информации и получателей результатов.

Значком & на рис. 11 обозначена логическая операция И.




Пример 3

Поскольку тестирование вручную алгоритма решения задачи о шахматном коне было бы достаточно громоздким, рассмотрим технологию тестирования  на примере алгоритма Евклида (рис. 14).



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

Примеры реализации программ рассмотрены в разделе "Методы процедурного программирования"

Контрольные вопросы


  1. Что такое программа?

  2. Что понимают под исполнителем?

  3. Что представляет собой машинный код?

  4. Что такое транслятор? Перечислите типы трансляторов.

  5. Как работает интерпретатор? В чем его достоинства?

  6. В чем заключается достоинство компиляторов?

  7. Какие компоненты необходимы для создания программ? Каково назначение каждого из этих компонентов?

  8. Что называется интегрированной системой программирования?

  9. Чем характеризуются системы визуального программирования?

  10. Какие подходы по способу разработки программ можно выделить? Охарактеризуйте каждый подход.

  11. Каковы основные системы программирования?

  12. Перечислите основные этапы развития языков программирования.
    Что понимают под алгоритмом?

  13. Каковы способы записи алгоритмов?

  14. В чем заключаются основные свойства алгоритма?

  15. Перечислите основные алгоритмические структуры и опишите их.

  16. Каковы основные принципы разработки алгоритмов?

  17. Назовите основные этапы составления алгоритмов.

  18. Приведите пример, реализующий этапы алгоритмизации.

  19. Каковы основные этапы решения задач с помощью ЭВМ? Дайте характеристику каждому этапу.


следующая страница >>