4302

Разработка блок-схемы алгоритма решения задачи

Практическая работа

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

Разработка блок-схемы алгоритма решения задачи Цель работы: изучение графического способа описания алгоритма решения задачи. Задачи работы: ознакомиться с основными способами представления алгоритмов освоить графический способ опи...

Русский

2012-11-16

312 KB

727 чел.

Разработка блок-схемы алгоритма решения задачи

Цель работы: изучение графического способа описания алгоритма решения задачи.

Задачи  работы:

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

1.1. Порядок выполнения работы

  1.  Изучите теоретические сведения по теме данного раздела (п. 1.2)
  2.  Ознакомьтесь с постановкой задачи (п. 1.3).  Вариант задания соответствует вашему номеру в списке группы.
  3.  Разработайте блок-схему алгоритма решения поставленной задачи.
  4.  Ответьте на контрольные вопросы.
  5.  Подготовьте отчет о выполнении практической работы, который должен содержать:
  •  титульный лист;
  •  цель практической работы;
  •  постановку задачи;
  •  блок-схему алгоритма решения поставленной задачи;
  •  ответы на контрольные вопросы;
  •  выводы по практической работе.

1.2. Общие сведения

Одним из наиболее трудоемких этапов решения задачи на ЭВМ является разработка алгоритма.

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

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

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

Выделяют следующие типы вычислительных процессов:

  1.  Линейный вычислительный процесс.

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

  1.  Разветвленный вычислительный процесс.

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

  1.  Циклический вычислительный процесс

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

В свою очередь, существуют также несколько типов циклического вычислительного процесса, а именно:

  1.  Счетные циклы (циклы с заданным количеством повторений) –  это циклические процессы, для которых количество повторений известно.
  2.  Итерационные циклы – это циклические процессы, завершающиеся по достижении или нарушении некоторых условий.
  3.  Поисковые циклы – это циклические процессы, из которых возможны два варианта выхода:

- выход по завершению процесса;

- досрочный выход по какому-либо дополнительному условию.

По типу вычислительного процесса, реализуемого алгоритмом, различают:

- алгоритмы линейной структуры;

- алгоритмы разветвленной структуры;

- алгоритмы циклической структуры.

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

К изобразительным средствам описания алгоритмов относятся следующие основные способы их представления:

- словесный ( записи на естественном языке);

- структурно-стилизованный (записи на алгоритмическом языке и псевдокод);

- графический ( изображение схем и графических символов);

- программный (тексты на языках программирования).

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

Пример 1.1. 

Алгоритм сложения двух чисел (a  и  b).

  1.  Спросить, чему равно число a.
    1.  Спросить, чему равно число b.
    2.  Сложить a и b, результат присвоить с.
    3.  Сообщить результат с.

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

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

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

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

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

Блок-схема алгоритма – это графическое представление хода решения задачи. Блок-схема состоит из блоков, соединенных линиями, а блоки изображаются в виде геометрических фигур, называемых символами. Внутри символов записываются указания о выполняемых блоком функциях –  формулы, текст, логические выражения. Вид символов и правила выполнения блок-схем стандартизированы – ГОСТ 19.701-90 содержит перечень символов, их наименования, отображаемые функции, формы и размеры, а также  правила выполнения схем. При разработке алгоритма каждое действие обозначают соответствующим блоком, показывая их последовательность линиями со стрелками на конце. Названия, обозначения и назначение элементов блок-схем приводится на рис. 1.1.

Рисунок 1.1 – Основные блоки

Следует упомянуть некоторые основные правила выполнения блок-схем, которыми надлежит руководствоваться при графическом описании алгоритмов. Начало алгоритмов отмечается символом  "Терминатор", из которого выходит одна линия. В нем записывается слово "Пуск" ("Начало"). Конец алгоритма отмечается этим же символом, в котором записывается слово "Останов" ("Конец"). В этом случае данный символ не имеет ни одной выходной линии, а на него может замыкаться одна или более линий. Символ “Процесс” может иметь одну или несколько входных линий и только одну выходную. Внутри символа может быть записано несколько предписаний – в этом случае они выполняются в порядке записи. Представление отдельных операций достаточно свободно. Для обозначения вычислений можно использовать математические выражения, для пересылки данных – стрелки, для других действий – пояснения на естественном языке, например, А: = Х + 4;   i: = i + 1,  < A >  ––>  B.

Линии потока должны быть параллельны сторонам листа. Основные направления линий потока – сверху вниз и слева направо – стрелкой не обозначаются. В других случаях на конце линии потока ставится стрелка, а в месте слияния линий ставится точка. Если блок-схема не умещается на одном листе, используют соединители. При переходе на другой лист или получении управления с другого листа в комментарии указывается номер листа, например "с листа 3" "на лист 1".

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

  1.  следование - обозначает последовательное выполнение действий (рис. 1.2, а);
  2.  ветвление - соответствует выбору одного из двух вариантов действий (рис. 1.2, б);  
  3.  цикл-пока - определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 1.2, в).

Рисунок 1.2 – Базовые алгоритмические структуры

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

  1.  выбор - выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 1.3, а, б);
  2.  цикл-до - повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 1.3, в, г);
  3.  цикл с заданным числом повторений (счетный цикл) повторение некоторых действий указанное число раз (рис. 1.3, д, е).  

Рисунок 1.3 – Реализация дополнительных алгоритмических структур

через базовые структуры

Рассмотрим примеры графического описания алгоритмов различных типов: линейного, разветвляющегося, циклического и комбинированного (рис. 1.4 – 1.7).

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

Алгоритм вычисления значения выражения K=3b+6а (рис. 1.4) .

Рисунок 1.4 – Пример блок-схемы линейного алгоритма  

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

Алгоритм, определяющий, пройдет ли график функции y=3x+4 через точку с координатами x1,y1 (рис. 1.5).

Рисунок 1.5 – Пример блок-схемы разветвляющегося алгоритма  

Пример 1.4. Циклический алгоритм.

Алгоритм, определяющий факториал натурального числа n (рис. 1.6):

n! = 1*2*3*….*(n-1)*n

0!=1

5!=1*2*3*4*5=120

Рисунок 1.6 – Пример блок-схемы циклического алгоритма  

Пример 1.5. Комбинированный алгоритм.

Необходимо определить наибольший общий делитель двух натуральных чисел А и В.

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

Пример (а): А=225, В=125. Применяя алгоритм Евклида, получаем  для А и В наибольший общий делитель, равный 25.

Пример (б): А=13, В=4. В этом случае наибольший общий делитель А и В равен 1.

a)

A

B 

 

225

125

 

 

225-125=100

125

 

 

100

25-100=25

 

 

100-25=75

25

 

 

75-25=50

25

 

 

50-25=25

=25

 

б)

A

B

 

 

13

4

 

 

13-4=9

4

 

 

9-4=5

4

 

 

5-4=1

4

 

 

1

4-1=3

 

 

1

3-1=2

 

 

=1

2-1=1

Блок-схема алгоритма Евклида для нахождения наибольшего общего делителя двух натуральных чисел показана на рис. 1.7.

Рисунок 1.7 – Пример блок-схемы комбинированного алгоритма  

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

Пример 1.6. Описание алгоритма Евклида на псевдокоде.

Алгоритм Евклида:

Ввести А,В

цикл-пока А ≠ В

если А > В

то А := А - В

иначе В := В - А

все - если

все-цикл 

Вывести А

Конец алгоритма. 

Таблица 1.1 – Пример псевдокода для записи базовых алгоритмических структур

Структура

Псевдокод

Структура

Псевдокод

Следование

<действие 1>

Выбор

Выбор <код>

<действие 2>

<код1>: <действие 1>

 

<код2>: <действие 2>

 

...

 

Все-выбор

Ветвление

Если <условие>

Цикл с

заданным

количеством повторений

Для <индекс> =

то <действие 1>

<n>,<k>,<h>

иначе <действие 2>

<действие>

Все - если

Все-цикл

Цикл-пока

Цикл-пока

<условие>

Цикл-до

Выполнять

<действие>

<действие>

Все-цикл

До <условие>

1.3. Задачи для составления блок-схем алгоритмов

  1.  Дано целое число m>1.

Получить наименьшее целое k, при котором 4k>m.

  1.  Дано натуральное число n. Вычислить произведение.
  2.  Дано натуральное число n.

Вычислить произведение

  1.  Дано целое число n.

Получить наименьшее число вида 2r , превосходящее n (r - натуральное).

  1.  Даны целые числа n, k (n  k  0).

Вычислить .

  1.  Дано натуральное число n и действительное число a.

Вычислить произведение .

  1.  Дано натуральное число n.

Вычислить сумму .

  1.  Дано натуральное число n.

Вычислить сумму n первых слагаемых

  1.  Даны последовательность чисел  , число n – количество элементов последовательности и число x. Определить количество вхождений числа x в заданную последовательность.
  2.  Дано натуральное число n. Вычислить:
  3.  Даны действительное число а, натуральное число n.

Вычислить:

  1.  Даны последовательность чисел  и число n – количество элементов последовательности. Найти количество отрицательных элементов последовательности.
  2.  Даны действительное число а, натуральное число n.

Вычислить сумму:

  1.  Пусть . Найти первый член yn, для которого выполняется неравенство , где – заданное действительное положительное число.
  2.  Даны действительные числа a и h, натуральное число n.

Вычислить

  1.  Дано натуральное число n. Вычислить:
  2.  Даны последовательность чисел  и число n – количество элементов последовательности. Найти сумму положительных элементов последовательности.
  3.  Даны натуральное n, действительное х.

Вычислить .

  1.  Даны последовательность чисел  и число n – количество элементов последовательности. Найти произведение отрицательных элементов последовательности.
  2.  Даны действительное число х и натуральное число n.

Вычислить, не используя операцию возведения в степень.

  1.  Даны действительное число х и натуральное число n.

Вычислить, не используя операцию возведения в степень.

  1.  Дано натуральное число n.

Вычислить сумму:

  1.  Даны действительные числа x и a, натуральное n.

Вычислить:

  1.  Пусть последовательность чисел образована по следующему закону: =1; ak=k*ak-1+1/k; k=1,2,... Дано целое число n. Получить an.
  2.  Дано натуральное число n. Найти количество цифр этого числа и их сумму.
  3.  Пусть n— натуральное число. Вычислить сумму .
  4.  Дано действительное число х.

Вычислить:

  1.  Даны натуральные числа n, m. Получить сумму m последних цифр числа n.
  2.  Пусть n— натуральное число. Вычислить сумму.
  3.  Дано натуральное число n.

Вычислить сумму:

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

  1.  Дайте определение алгоритма.
  2.  Перечислите основные свойства алгоритмов и раскройте их сущность.
  3.  Как подразделяются алгоритмы по типу реализуемого вычислительного процесса?
  4.  Какие способы описания алгоритмов вам известны?
  5.  Что понимается под графическим способом описания алгоритмов? В чем состоит преимущество данного способа перед словесным описанием алгоритма?
  6.  Назовите базовые алгоритмические структуры и поясните их назначение.
  7.  Каково назначение дополнительных алгоритмических структур? Каким образом они связаны с базовыми алгоритмическими структурами?

PAGE  16


нет

да

ачало

Ввод x1,y1

y1:=3x1+4

Конец

Вывод:

Не принадлежит

Вывод:

Принадлежит

Да

Нет

Начало

Ввод n

F:=1

F := F*I

I <= n

I:=1

I := I+1

Вывод F

Конец


 

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

29346. Phonetic Expressive Means and Stylistic Devices 18.9 KB
  This is the way a word a phrase or a sentence sounds. The sound of most words taken separately will have little or no aesthetic value. The way a separate word sounds may produce a certain euphonic impression but this is a matter of individual perception and feeling and therefore subjective. In poetry we cannot help feeling that the arrangement of sounds carries a definite aesthetic function.
29347. Lexical Expressive Means and Stylistic Devices 21.57 KB
  By being forcibly linked together the elements acquire a slight modification of meaning. The elevated ancestors simile unhallowed disturb in the now obsolete meaning of tear to pieces are put alongside the colloquial contraction the Country's the country is and the colloquial done for. Interaction of different of different types of lexical meaning Words in context as has been pointed out may acquire additional lexical meanings not fixed in dictionaries what we have called contextual meanings. The latter may sometimes deviate from...
29348. Interaction of primary and derivative logical meanings. Stylistic Devices Based on Polysemantic Effect, Zeugma and Pun 23.92 KB
  Epithet is a stylistic device based on the interplay of emotive and logical meanings in an attributive word emotionally colored attitude of the speaker to the object he describes. 1 – refer the mind to the concept due to some quality of the object it is attached to. 2 – attributes used to characterize the object by adding a feature unexpected in it. One of the two members of oxymoron illuminates the feature observed while the other one offers a purely subjective individual perception of the object.
29349. Syntactical expressive means and stylistic devices 23.95 KB
  Its expressive effect may be based on the absence of logically required components of speech parts of the sentence formal words or on the other hand on a superabundance of components of speech; they may be founded on an unusual order of components of speech the change of meaning of syntactical constructions and other phenomena. The object is placed at the beginning of the sentence: Talent Mr. The adverbial modifier is placed at the beginning of the sentence: My dearest daughter at your feet I fall. However in modern English and American...
29350. Particular ways of combining parts of the utterance 16.65 KB
  Particular ways of combining parts of the utterance Asyndeton Asyndeton that is connection between parts of a sentence or between sentences without any formal sign becomes a stylistic device if there is a deliberate omission of the connective where it is generally expected to be according to the norms of the literary language. Polysyndeton Polysyndeton is the stylistic device of connecting sentences or phrases or syntagms or words by using connectives mostly conjunctions and prepositions before each component part as in: The heaviest...
29351. Functional Styles 19.61 KB
  Therefore functional style of language is a historical category. Thus the FS of emotive prose actually began to function as an independent style after the second half of the 16th century; the newspaper style budded off from the publicistic style; the oratorical style has undergone considerable fundamental changes and so with other FSs The development of each style is predetermined by the changes in the norms of standard English. The BellesLetters Style We have already pointed out that the belleslettres style is a generic term for three...
29352. Functional Styles. Newspaper Style 33.05 KB
  Not all the printed materials found in newspapers come under newspaper style. Only materials which perform the function of informing the reader and providing him with an evaluation of information published can be regarded as belonging to newspaper style. English newspaper style can be defined as a system of interrelated lexical phraseological and grammatical means which is perceived by the community as a separate linguistic unity that serves the purpose of informing and instructing the reader.
29353. General Notes on Stylistics. It’s subject and Object 40.48 KB
  It deals mainly with two interdependent tasks: The investigation of the inventory of special language media which secure the desirable effect of the utterance The investigation of certain types of texts which are distinguished due to the choice and arrangement of language means. The types of texts that are distinguished by the pragmatic aspect of communication are called functional styles of language FS; the special media of language which secure the desirable effect of the utterance are called stylistic devices SD and expressive means...
29354. Expressive means and stylistics devices 24 KB
  All stylistic means of a language can be divided into expressive means which are used in some specific way and special devices called stylistic devices. The expressive means of a language are those phonetic means morphological forms means of wordbuilding and lexical phraseological and syntactical forms all of which function in the language for emotional or logical intensification of the utterance. These intensifying forms of the language have been fixed in grammars and dictionaries. The most powerful expressive means of any language...