34645

Понятие алгоритма. Свойства, способы описания

Реферат

Информатика, кибернетика и программирование

Понятие алгоритма и способы его описания; Типы алгоритмов; Блоксхемы; Базовые структуры применяемые при создании алгоритмов. Иначе говоря блоксхема служит для графического изображения структуры алгоритма. Последовательность действий в соответствии с блоксхемой указывается с помощью стрелок соединяющих отдельные блоки и показывающих какой блок и вслед за каким должен выполняться. В ходе изучения данной дисциплины будут рассматриваться алгоритмы описанные при помощи языка программирования и при помощи специальных схем...

Русский

2013-09-08

90 KB

103 чел.

исциплина «Основы алгоритмизации и программирование»  Понятие алгоритма. Свойства, способы описания.

Понятие алгоритма. Свойства, способы описания.

  1.  Понятие алгоритма и способы его описания;
  2.  Типы алгоритмов;
  3.  Блок-схемы;
  4.  Базовые структуры, применяемые при создании алгоритмов.

1. Понятие алгоритма и способы его описания

Одним из основных данной дисциплины является понятие алгоритма. В основе каждой программы заложен свой алгоритм.

Но алгоритм  встречается во многих областях деятельности человека.

Пример: Кулинарная книга,  аэробика, как найти дорогу.   

Алгоритм это конечная последовательность команд исполнителю, направленная на достижение определенной цели.

Цель это достижение желаемого результата.

Исполнителем может быть человек, живое существо, автоматическое устройство которое способно к восприятию и исполнению команд.  

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

Каждый  алгоритм предназначен для определенного исполнителя.

Исполнять алгоритм начинают с первой команды. После ее исполнения переходят ко второй и так далее до конца.

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

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

Алгоритмический язык — формальный язык, предназначенный для записи алгоритмов. Алгоритмический язык задается набором основных символов (алфавитом), системой точных правил построения текстов (синтаксисом) и соответствием синтаксически допустимых текстов языка описываемым объектам и действиям (семантикой). Многие языки программирования, используемые при решении задач на ЭВМ, являются алгоритмическими языками.

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

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

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

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

1) наличие ввода исходных данных;

2) наличие вывода результата выполнения;

3) однозначность — компьютер «понимает» только однозначные инструкции;

4) общность — алгоритм предназначен для решения не одной задачи, а целого класса задач;

5) корректность — алгоритм должен давать правильное решение задачи;

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

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

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

Существует ряд мер, которые рекомендуют для повышения эффективности.

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

2. Блок-схемы

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

Начало и конец алгоритма.

 

Между этими блоками и помещаются все остальные, образующие алгоритм.

Операторный блок(блок действия)

(открыть зонт)

Блок проверки условия. Этот блок предполагает два варианта дальнейшего выполнения алгоритма, в зависимости от того, выполнено ли поставленное условие. Если место в маршрутке есть то я еду домой, если нет, то жду следующую.

Блок ввода или вывода.

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

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

3. Типы алгоритмов

Линейный алгоритм.

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

Набрать 8,

дождаться гудка,

набрать код,

набрать номер телефона.

Разветвляющиеся алгоритмы.

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

1. Проверить условие «Идет дождь» Если условие выполняется перейти к команде 2. Если нет то к команде 3.

2. Взять с собой зонт

3. Оставить зонт на месте.

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

Циклические алгоритмы

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

Например Красить дощечки забора до тех пор пока он не будет покрашен.  Способ организации таких алгоритмов называется повторением.

Повторение – это набор команд, который выполняется до тех пор, пока выполняется некоторое условие.

Алгоритмы, содержащие команду повторения, -  циклические алгоритмы (алг.   с повторениями). 

Красить дощечки – тело цикла.

Пока забор не покрашен, повторять – команда цикла.


4. Базовые структуры, применяемые при создании алгоритмов.

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

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

Конструкция сочленения соответствует линейному алгоритму. Каждая из операций  S1, S2, ..., Sn может быть представлена как последовательность

конечного числа более простых операций.

Конструкция выбора соответствует разветвляющемуся алгоритму. Она полезна в тех случаях, когда некая операция состоит в выборе одной из двух более простых операций S1 или S2 по условию. Блок  B определяет условие выбора.

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

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

  1.  переменная хранит не более 1 значения;
  2.  переменная способна хранить значения только одного и того же типа;
  3.  переменная хранит значение до тех пор, пока в нее не поместят новое значение, при этом предыдущее содержимое переменной стирается;
  4.  значение переменной может быть вызвано для использования сколько угодно раз без изменения оригинала;
  5.  к началу выполнения программы содержимое переменной считается неопределенным; ячейки памяти, отведенные под переменную путем ее описания, заполняются значениями в ходе выполнения программы с помощью оператора присваивания; этим переменная отличается от константы, которой значение присваивается до выполнения основной программы, в разделе определения констант.

Рассмотрим пример разработки программы с применением метода пошаговой детализации. Задача: Составить программу определения максимального из трёх чисел входа. Сразу же можно предложить следующую абстрактную программу решения поставленной задачи:

Эта программа содержит абстрактную операцию max(a,b,c). В этой связи выполним следующую детализацию блока 2:

  •  

Очевидно, что блоки 2.2 и 2.3 нуждается в дальнейшей детализации:

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

Примечание: Существует и другой вариант детализации блока 2.

После детализации блоков 2.1 и 2.2 нового варианта детализации блока 2 и соответствующей сборки мы получим ещё один вариант программы:


Домашнее задание:

Составить блок-схемы для решения следующих задач:

1. Ввести сторону квадрата. Найти и вывести его площадь и периметр.

2. Дано вещественное число А. Не пользуясь никакими арифметическими операциями, кроме умножения, получить:

  1) А^6 за три операции;

  2) А^7 за четыре операции;

  3) А^8 за три операции;

  4) А^9 за четыре операции;

  5) А^13 за пять операции;

3. Поменять местами содержимое двух переменных

4. Дано трехзначное число. Найти число, полученное при прочтении его цифр справа налево.

  •  Дано трехзначное число. Найти сумму его цифр;
  •  Дано трехзначное число. Найти произведение его цифр;


 

А также другие работы, которые могут Вас заинтересовать

62441. Моделирование и изготовление формы 1.2 MB
  Поверхность может иметь покрытие глазурью ценинный изразец не иметь покрытия терракотовый изразец. Недаром само слово изразец это то что вырезано обработано.
62443. КУЛЬТУРА ЗАПАДНОЙ ЕВРОПЫ В РАННЕЕ СРЕДНЕВЕКОВЬЕ 20.44 KB
  Ознакомить с искусством рукописной книги в частности книжной миниатюры. Влияние христианства на развитие культуры в области литературы образования искусства рукописной книги. Карл I и его семья придворные в Аахене образовали такой кружок где читали и обсуждали церковные книги...
62444. Виды треугольников. Углы равнобедренного треугольника 25.06 KB
  опросы для проверки устно: Какой треугольник называется прямоугольным Какой треугольник называется равнобедренным А какой равносторонним Как называются стороны прямоугольного треугольника Какие стороны равнобедренного треугольника называются боковыми...
62445. СОЦИАЛЬНЫЕ НОРМЫ. СОЦИАЛЬНЫЙ КОНТРОЛЬ 18.57 KB
  Социальные нормы определяют границы допустимого поведения людей применительно к конкретным условиям их жизнедеятельности. превосходства; 3 моральные обеспечиваются авторитетом общественного мнения; 4 корпоративные нормы или нормы общественных объединении...
62446. Ангобирование 1017.39 KB
  Цветными ангобами расписывают изделия имеющие самое разнообразное назначение: посуду подсвечники броши кулоны бусы и многое другое. Нанесение ангоба Цветные ангобы наносят на поверхность изделия кистью рожком воронкой резиновой грушей пластмассовым пузырьком и пипеткой.
62448. Present Continuous Tense. Future Simple Tense. Оборот to be going to + глагол 37.07 KB
  Употребление настоящего продолженного времени (Present Continuous Tense) для обозначения действия в будущем Оборот to be going to + глагол Будущее простое время (Future Simple Tense) Количественные слова a lot (of), many, much, little, a little, few, a few...
62449. Внутреннее строение листа 19.04 KB
  Цель урока: Продолжить изучение листа в связи с выполняемыми функциями и приспособленностью растений и родным условием среды. Образовательная задача: Познакомить учащихся с особенностями клеточного строения листа в связи с его функциями обеспечить закрепление биологических понятий...