14724

Схемы алгоритмов

Лабораторная работа

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

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

Русский

2013-06-09

76 KB

25 чел.

Контрольная работа. Схемы алгоритмов

Цель работы

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

Содержание отчета

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

  1.  Титульный лист.
  2.  Цель работы.
  3.  Текст задания (Вариант задания соответствует порядковому номеру по списку группы).
  4.  Решение задачи, представленное с помощью схемы.
  5.  Выводы.

Теоретические сведения

Для спецификации процессов используют различные средства, в том числе граф-схемы (блок-схемы или просто схемы) алгоритмов, каждая из которых представляет собой граф. Элементарный граф дополнен надстройкой, которая задает вычисления, каждому из которых соответствует путь в этом графе и последовательность меток узлов, лежащих на этом пути. Узлы графа, с помощью введения типизации, интерпретируются как действия, а дуги задают порядок передачи управления. Для каждого алгоритма существует одна начальная дуга и одна или множество конечных.  представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

Таблица .

Символ

название

интерпретация

данные

данные, носитель данных неопределен

процесс

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

предопределенный процесс

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

Подготовка

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

Решение

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

граница цикла

начало и конец цикла; обе части имеют один и тот же идентификатор; условия инициализации, приращения, завершения, и т.д. помещаются внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие

соединитель

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

терминатор

выход во внешнюю среду и вход из внешней среды (начало и конец программы)

линия

поток данных или управления; для направлений справа-налево и снизу-вверх добавляются стрелки

пунктирная линия

используется для обведения аннотируемого участка

комментарий

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

пропуск

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

Приведем основные свойства граф-схем.

  1.  Графическое представление.
  2.  Поддержка описания управляющей части алгоритма.
  3.  Возможность реализации синтаксического контроля.
  4.  Возможность проверки управляющей части алгоритма.
  5.  Отсутствие возможности верификации информационной части.

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

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

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

В состав языка входят следующие основные символы:

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

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

Пример представления алгоритма с помощью схемы

Текст задания

Пусть необходимо определить k – количество трехзначных натуральных чисел, сумма цифр которых равна n (1 <= n <= 27 ). При этом операции деления ( /, div, mod ) не использовать.

Решение

Организуем три цикла – по одному на каждую из цифр числа. Задача – перебрать все возможные комбинации из трех цифр. Каждая цифра может принимать значение от 0 до 9 – ти, что позволяет в качестве управляющих конструкций для организации трех итерационных процессов воспользоваться циклом с параметром. Будем складывать счетчики этих циклов и сравнивать с заранее введенным n. В случае равенства, будем инкриминировать счетчик k – количества трехзначных чисел. На  изображена граф-схема алгоритма данной задачи.

Рис. . Граф-схема алгоритма.

Варианты заданий

  1.  Дан текст из 80 литер. Вывести сначала все цифры, входящие в него, а затем все остальные литеры, сохраняя при этом взаимное расположение литер в каждой из этих двух групп.
  2.  Даны две последовательности по 30 целых чисел в каждой. Найти наименьшее среди тех чисел первой последовательности, которые не входят во вторую последовательность (считая, что хотя бы одно такое число есть).
  3.  Дана непустая последовательность слов из строчных латинских букв; между соседними словами - запятая, за последним словом - точка. Вывести все буквы, которые входят в наибольшее количество слов этой последовательности.
  4.  Напечатать заданный текст из 100 литер, удалив из него повторные вхождения каждой литеры.
  5.  Определить, сколько различных литер входит в заданный текст, содержащий более 100 литер и оканчивающийся точкой (сама точка в текст не входит).
  6.  Дан текст из строчных латинских букв, за которым следует точка. Вывести в алфавитном порядке все буквы, которые входят в этот текст по одному разу.
  7.  Дан непустой текст из цифр, за которыми следует точка. Напечатать цифру, наиболее часто встречающуюся в этом тексте.
  8.  Дано 100 вещественных чисел. Распечатать их в обратном порядке по 6 чисел в строке.
  9.  Дан текст, содержащий от 1 до 70 букв, за которым следует точка. Вывести текст в обратном порядке.
  10.  Дан текст из 80 литер. Определить, симметричен ли он, т.е. читается ли он одинаково слева направо и справа налево.
  11.  Дана последовательность из 100 различных целых чисел. Найти сумму чисел этой последовательности, расположенных между максимальным и минимальным числами (в сумму включить оба этих числа).
  12.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все звонкие согласные буквы, которые входят хотя бы в одно слово.
  13.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все глухие согласные буквы, которые входят в каждое нечетное слово, и не входят хотя бы в одно четное слово.
  14.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все согласные буквы, которые входят только в одно слово.
  15.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все глухие согласные буквы, которые не входят хотя бы в одно слово.
  16.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все глухие согласные буквы, которые не входят только в одно слово.
  17.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все звонкие согласные буквы, которые входят более чем в одно слово.
  18.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все звонкие согласные буквы, которые входят в каждое нечетное слово, и не входят ни в одно четное слово.
  19.  Дана непустая последовательность слов из строчных русских букв; между соседними словами - запятая, за последним словом - точка. Напечатать в алфавитном порядке все гласные буквы, которые не входят более чем в одно слово.
  20.  Дан текст, за которым следует точка. В алфавитном порядке вывести (по разу) все строчные русские гласные буквы, входящие в этот текст.
  21.  Дан текст из строчных латинских букв, за которым следует точка. Вывести все буквы, входящие в текст не менее двух раз.
  22.  Дан текст из строчных латинских букв, за которым следует точка. Вывести все буквы, входящие в текст по одному разу.
  23.  Дан текст из цифр и строчных латинских букв, за которым следует точка. Определить, каких букв – гласных (a, e, i, o, u) или согласных – больше в этом тексте.
  24.  Описать функцию count( s ), подсчитывающую общее количество цифр, входящих в строку s.
  25.  Имеется текстовый файл, разбитый на строки. Вывести первую из самых коротких его строк.
  26.  В 1-ом текстовом файле записана последовательность целых чисел, разделенных пробелами. Записать все положительные числа из этой последовательности во 2-ой текстовый файл.
  27.  В 1-ом текстовом файле записана последовательность целых чисел, разделенных пробелами. Записать квадраты чисел этой последовательности во 2-ой текстовый файл.
  28.  Вывести картинку, изображающую умножение «столбиков» двух заданных натуральных чисел.
  29.  Дана непустая последовательность слов, содержащих от 1 до 8 букв; между соседними словами – запятая, за последним словом – точка. Вывести все слова, отличные от последнего слова.
  30.  Дана непустая последовательность слов, содержащих от 1 до 8 букв; между соседними словами – запятая, за последним словом – точка. Вывести все слова, наименьшей длины.


[

начало

конец

введите N

K

K:= 0

K:= K + 1

A1

Digit1= 1, 9

A2

Digit2= 0, 9

A3

Digit3= 0, 9

Digit1 + Digit2 + Digit3= N

A1

A2

3

да


 

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

20387. Информатика и математика. Математика для юристов 1.07 MB
  Теория множеств.1] Понятие способы задания и виды множеств [2.2] Операции над множествами [2.3] Неупорядоченные и упорядоченные множества.
20388. УГОЛОВНАЯ ОТВЕТСТВЕННОСТЬ ЮРИДИЧЕСКИХ ЛИЦ: ЗА И ПРОТИВ 381 KB
  Настоящая работа посвящена дискуссионной проблеме - проблеме уголовной ответственности юридических лиц, актуальной в научном и практическом отношении, но недостаточно освещенной в юридической литературе. Она подготовлена доктором юридических наук...
20389. ДОКАЗЫВАНИЕ В СОВЕТСКОМ УГОЛОВНОМ СУДОПРОИЗВОДСТВЕ 672 KB
  66 УПК УССР и И. 66 и 97 УПК УССР ст. 70 и 109 УПК РСФСР. Здесь были высказаны суждения как о том что их применение допустимо и по действующему за кону так как они объединяют в себе свойства соответ ственно киносъемки звукозаписи и фотоснимков так и о том что сначала нужно урегулировать в УПК возмож ность и порядок их применения.
20390. Высшая мера наказания: История, современность, будущее 962 KB
  Высшая мера наказания: История современность будущее Хотите предупредить преступление Сделайте так чтобы люди боялись законов но никого кроме законов не боялись Екатерина II Введение Вряд ли есть такая проблема в уголовном праве по которой было больше споров среди ученых политиков и практиков чем проблема смертной казни. За истекшее время смертной казни были посвящены тысячи работ авторы которых либо требовали ее немедленной отмены либо доказывали настоятельную необходимость. Законодательства разных стран мира также относятся...
20391. Конституционное (государственное) право зарубежных стран 1.32 MB
  Известен его политикоправовой комментарий к Конституции США 1985 подготовленный совместно с В. Основным источником конституционного государственного права являются конституции но они часто содержат лишь общие положения и обходят молчанием ряд важнейших вопросов государственной жизни тем самым оставляя их решение на усмотрение правительства и администрации. Наряду с этим конституции многих стран перегружены рядом мелочей и второстепенных деталей. 25бис конституции Швейцарии которая запрещает выпускать кровь у мясного скота не оглушив...
20392. Международный правопорядок 614.5 KB
  2 В книге анализируются различные подходы юристов и политиков к пониманию международного и мирового порядка дается понятие международного правового порядка исследуется процесс становления современного международного правопорядка раскрывается его сущность и значение как единого и юридически обязательного порядка для всех государств . Автор доктор юридических наук профессор возглавлял Отдел кодификации в ООН принимал участие в работе органов ООН и международных конференций по прогрессивному развитию международного права. был...
20393. Правовые основы деятельности акционерных обществ 2.27 MB
  За изданием Кодекса последовало принятие ряда федеральных законов которые развивали и детализировали положения Кодекса применительно к конкретным разновидностям юридических лиц: Об акционерных обществах О некоммерческих организациях Об обществах с ограниченной ответственностью и др. Федеральный закон Об акционерных обществах в значительной мере способствовал упорядочению деятельности акционерных обществ однако отдельные пробелы а также отсутствие детальной проработки ряда вопросов в Законе требовали дальнейшего совершенствования...
20394. Корпорации в России: Правовой статус и основы деятельности 2.91 MB
  2128 обществами Уст. Кашанина отмечала что если взять за основу характеристики форму имущественной обособленности организаций то оказывается что к числу корпораций относятся только те которые основаны на акционерном капитале и по своему правовому положению напоминают акционерные общества стран континентального права 30. Торговые корпорации Англии именуются компаниями company и подразделяются на публичные аналог открытого акционерного общества континентального права и частные аналог закрытого акционерного общества. Кашанина...
20395. Взрывчатка и наркотики: Особенности назначения экспертиз: Пособие для следователей и оперативных работников 370.5 KB
  В пособии изложены рекомендации по назначению экспертиз при расследовании фактов незаконного оборота наркотиков и взрывчатых веществ а также преступлений совершаемых путем взрыва. Наряду с этим дефицит знаний в этих областях ощущался и ощущается у работников правоохранительных органов столкнувшихся с тенденциями роста преступлений связанных с незаконным оборотом наркотиков и ВВ использованием взрыва в преступных целях. Научные работы экспертов этого института по методам экспертного исследования самодельных взрывных устройств СВУ...