34645

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

Реферат

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

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

Русский

2013-09-08

90 KB

106 чел.

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

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

  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. Дано трехзначное число. Найти число, полученное при прочтении его цифр справа налево.

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


 

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

33521. Тема революции в поэме С. Есенина «Анна Снегина» 18.29 KB
  Есенина Анна Снегина. Поэма Анна Онегина написанная незадолго до смерти поэта в 1924 году явилась своеобразным обобщением размышлений Есенина об этом драматическом и противоречивом времени и вобрала в себя многие мотивы и образы его лирики. Это ощущение усиливается в поэме тем что на её страницах в качестве олицетворения его юности появляется Анна Снегина – первая любовь девушка в белой накидке которая ласково сказала: Нет Несмотря на былые воспоминания автор прекрасно понимает что прошлое вернуть невозможно:...
33522. Творчество В.Набокова (роман по выбору). Проблематика, конфликты, герои 16.5 KB
  Защита Лужина Роман Защита Лужина привлекает и своим заглавием и своим содержанием писатель неоднократно объяснял его замысел: Русское заглавие этого романа – Защита Лужина – относится к шахматной защите будто бы придуманной моим героем сочинять книгу было нелегко надо был ввести роковое предназначение в жизнь Лужина и придать очертанию сада поездки событиям подобие замысловатой игры а в последних главах – настоящей шахматной атаки разрушающей до основания здоровье моего героя. У Лужина неожиданно счастливая семейная жизнь...
33523. Особенности композиции и система образов в романе М. Булгакова «Мастер и Маргарита» 22.64 KB
  Особенности композиции и система образов в романе М. Булгакова Мастер и Маргарита Роман в романе М. Сожженное в печи произведение Мастера так называемый внутренний роман возрождается будто Феникс из пепла так как он связан с персонажами романа внешнего. С внешним романом его соединяет образ Алоизия Могарыча предателя которого Мастеру изображать неинтересно поэтому что уже был в его творчестве Иуда.
33524. Проблематика романа «Мастер и Маргарита» 16.97 KB
  Более всего тема угнетения преследования неординарной талантливой личности государством присутствует в судьбе Мастера. Маргарита громит квартиру критика Латунского погубившего Мастера но отвергает предложение уничтожить своего врага. После бала у Сатаны героиня в первую очередь просит за страдающую Фриду забывая о собственном страстном желании вернуть Мастера. Именно Воланд приводит Мастера и его подругу в их вечный дом даруя им покой.
33525. Тема репрессий в поэме А.Ахматовой «Реквием» 17.6 KB
  Ахматова начала писать свою поэму Реквием в 1935 году когда ее единственный сын Лев Гумилев был арестован. Как и другие матери жены сестры Ахматова много часов стояла в молчаливой очереди что вела к петербургской тюрьме Кресты. Только в 1940 году Ахматова завершила свое произведение опубликовано же оно было в 1987 году много лет спустя после смерит автора. Ахматова рассказывает об истории создания поэмы.
33526. Роман-антиутопия Е.Замятина «Мы» (жанровые и художественные особенности) 17.26 KB
  У Замятина мы не масса а социальное качество. Заветная идея сталинизма – не человек но винтик в гигантском государственном механизме который подчинен твердой руке машиниста у Замятина показана осуществленной. Особенности жанра При чтении толкования термина антиутопия все его особенности прослеживаются в романе Евгения Замятина Мы: это и изображение тоталитарного государства и острый конфликт Чтобы возникла художественность нужен романный конфликт. Он должен пережить это сомнение как кульминацию своей жизни пусть даже...
33527. «Чевенгур» Платонова как роман-предупреждение 14.06 KB
  Чевенгур Платонова как романпредупреждение. прочитав роман “Чевенгур†писал Платонову: “Человек вы талантливый это бесспорно бесспорно и то что вы обладаете очень своеобразным языком. Платонов же посылая Горькому рукопись “Чевенгура†писал что “в романе содержится честная попытка изобразить начало коммунистического обществаâ€. Роман “Чевенгур†это энциклопедия социальных инициатив в их взаимодействии с реальной плотью жизни.
33528. Проблематика романа Б. Пастернака «Доктор Живаго», значение лирического дневника в идейной концепции романа 20.46 KB
  Пастернака Доктор Живаго значение лирического дневника в идейной концепции романа. Пастернак начал писать роман “Доктор Живаго†в 1945 году и закончил его в декабре 1955 года.Лихачев уверен что автор Пастернак пишет о самом себе но пишет как о постороннем он придумывает себе судьбу в которой можно было бы наиболее полно раскрыть перед читателем свою внутреннюю жизнь что жизнь Юрия Андреевича Живаго – это альтернативный вариант жизни самого Пастернака. Доктор Живаго – выразитель сокровенного лирический герой Пастернака который...
33529. Литературный процесс 30-х годов (ведущие темы, основные имена) 13.59 KB
  Печатались новые произведения Н. Новые сферы жизни человека новые конфликты новые характеры видоизменение традиционного литературного материала привели к появлению новых героев к возникновению новых жанров новых приемов стихосложения к поискам в области композиции и языка.