86794

Разработка алгоритмов

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

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

Структуры данных и алгоритмы служат теми материалами, из которых строятся программы. Встроенные структуры данных представлены теми регистрами и словами памяти, где хранятся двоичные величины. Заложенные в конструкцию аппаратуры алгоритмы

Русский

2015-04-10

316.5 KB

9 чел.

Лабораторная работа №1 Разработка алгоритмов

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

1. Краткие теоретические сведения

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

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

Процесс создания программы для решения какой-либо практической задачи состоит из нескольких этапов:

  1.  Постановка задачи (создание технического задания на исходную задачу);
  2.  Формализация (математическая постановка задачи);
  3.  Выбор (или разработка) метода решения;
  4.  Разработка алгоритма (алгоритмизация);
  5.  Составление программы (программирование);
  6.   Тестирование и отладка программы;
  7.  Вычисление и обработка результатов и документирование программы;

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

Математическая модель

Абстрактные типы данных

Структуры данных

Неформальный алгоритм

Программа на псевдоязыке

Программа на языке Паскаль

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

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

Продолжением этого этапа является замена неформальных операторов.

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

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

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

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

  •  на естественном языке;
  •  в виде блок-схемы;
  •  на специальном языке для записи алгоритмов (алгоритмическом языке).

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

Например, алгоритм решения квадратного уравнения

ax2 + bx + c =0 в данном случае будет иметь вид:

  1.  Задаться значениями переменных a, b, c.
  2.  Вычислить D = b2 – 4ac.
  3.  Сравнить D с нулем. Если D<0, то необходимо перейти к пункту 4. В противном случае вычислить

и .

  1.  Выдать результат расчета.
  2.  Закончить вычисления.

Разработка алгоритмов в виде блок-схем

 

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

К основным структурам относятся:

1. Следование. Последовательное размещение блоков и групп блоков. В программе реализуется последовательным размещением операторов.

2. Цикл До (рис.1.1) . Применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого условия.

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

На естественном языке циклу До соответствует последовательность операторов:

  1.  Операторы начальных присваиваний.
  2.  Операторы тела циклов.
  3.  Если условие не выполняется идти к 2, иначе – идти к 4.
  4.  Выход.

3. Цикл Пока. Цикл Пока отличается от цикла До тем, что проверка условия проводится (рисунок 1.2) до выполнения тела цикла. При истинности условия выполняется оператор или группа операторов (тело цикла), в противном случае тело цикла не выполнится ни разу.

На естественном языке циклу Пока соответствует последовательность операторов:

  1.  Операторы начальных присваиваний.
  2.  Если условие выполняется идти к 3, иначе – идти к 4.
  3.  Операторы тела цикла.
  4.  Выход.

4. Разветвление. Применяется когда в зависимости от условия нужно выполнить либо одно, либо другое действие (рисунок 1.3). Действие 1 или действие 2 могут в свою очередь содержать несколько этапов.

На естественном языке разветвлению соответствует последовательность операторов:

 

1.Если условие выполняется идти к 4.

2. Выполняются операторы действия 1.

3. Идти к 5.

4. Выполняются операторы действия 2.

5. Выход.

5. Обход. Частный случай разветвления, когда одна ветвь не содержит никаких действий (рисунок 1.4).

На естественном языке обходу соответствует последовательность операторов:

1.Если условие выполняется идти к 3.

2. Выполняются операторы действия.

3. Выход.

6. Множественный выбор. Является обобщением разветвления, когда в зависимости от значения переменной (I) выполняется одно из нескольких действий. Например, при I=1 выполняется действие S1, при I=2 – S2 и т.д. (рисунок 1.5).

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

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

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

Примеры составления алгоритмов

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

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

Пример 1. Даны переменные А и В. Требуется обменять их значения, т. е. переменная А должна получить значение В, а В - значение А.

Решение. Исходные данные: А, В. Результат: А, В.

Поскольку, в ЭВМ каждая величина хранится в отдельной ячейке, то задача фактически заключается в том, чтобы поменять местами содержимое двух ячеек. Для этого введем в рассмотрение еще одну величину, например С, т. е. выделим третью ячейку (клетку), свободную; перенесем значение А в ячейку для С (С=А), затем перенесем значение В в ячейку для А, а в ячейку для В значение С (рисунок 1.6) (на рисунке ячейки изображены кругами, операции – стрелками, порядок выполнения операций - цифрами).

Решение задачи распадается на три этапа.

Соответствующие им блоки и порядок их выполнения изображены на схеме алгоритма (рисунок 1.7 а).

Пример 2. Даны величины А, В, С, D. Требуется переместить значения величин: В должно получить значение А; С - значение B; D - значение C. Блок-схема решения задачи представлена на рисунок 1.7 б. Исходные данные А, В, С, D. Результат: А, В, С, D.

Решение данной задачи должно выполняться в следующем порядке:

  1.  Ввод A, B, C, D.
  2.  D=C.
  3.  C=B.
  4.  B=A.
  5.  Вывод A, B, C, D.

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

Пример 1. Блок-схема решения задачи представлена на рисунок 1.8.

Вычислить значение Y по одной из формул:

Y=x+a, если x<10;

Y=x+b1, если 10<=x<=20;

Y=c+b2, если 20<x<30;

Y=c-b3, если x>=30, где .

 

Порядок решения задачи следующий:

  1.  Ввод a, b1, b2, b3, c.
  2.  Вычисление x.
  3.  Проверка условия x<10. Если условие выполняется, то вычислить Y=x+a и вывести результат. Если нет – перейти к 4.
  4.  Проверка условия x<=20. Если условие выполняется, то вычислить Y=x+b1 и вывести результат. Если нет – перейти к 5.
  5.  Проверка условия x<30. Если условие выполняется, то вычислить Y=c+b2 и вывести результат. Если нет – перейти к пункту 6. 
  6.  Вычислить Y=c-b3 и вывести результат.

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

Пример 1. Вычислить сумму целых чисел от n до m.

Решение. Блок-схема данного алгоритма представлена на рисунке 1.9.

Алгоритм решения на естественном языке можно представить следующим образом:

  1.  Ввести значения n, m.
  2.  Присвоить L=n.
  3.  Присвоить k=0.
  4.  Если L>m идти к 8.
  5.  Вычисление суммы k=k+L.
  6.  Вычисление нового значения L=L+1.
  7.  Идти к 4.
  8.  Вывод значений n, m, k.
  9.  Закончить вычисления.

Пример 2. В переменную x по очереди помещаются (вводятся) 10 чисел. В переменной Р получить максимальное из этих чисел. Блок-схема решения задачи 2 представлена на рисунке 1.10.

Решение. Если до входа в цикл переменной Р присвоить значение первого введенного числа х, то в цикле для очередного значения х нужно проверять условие Р>=x, и если оно не выполняется, то заменить старое значение Р на новое, равное текущему значению х.

После чего вводится следующее значение х.

Алгоритм имеет вид:

  1.  Ввод х.
  2.  Присвоение Р=х.
  3.  Присвоение I=2.
  4.  Ввод очередного значения х.
  5.  Если P>=x идти к 6.
  6.  Присвоение Р=х.
  7.  I=I+1.
  8.  Если I<=10 идти к 3.
  9.  Вывод Р.
  10.  Закончить вычисления.

2. Задание

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

1. Подсчет суммы нечетных чисел от 1 до 10.

2. Отыскание слова в орфографическом словаре.

3. Нахождение среднего арифметического трех натуральных чисел.

4. Подсчет суммы четных чисел от 1 до 10.

5. Правила пользования библиотечным каталогом.

6. Сложение столбиком двух натуральных чисел.

7. Правила перехода улицы для случаев:

а) перекресток регулируемый;

б) перекресток нерегулируемый (т.е. без светофора).

8. Вычитание столбиком двух натуральных чисел.

9. Подсчет всех чисел, входящих в интервал от 0 до 10, в последовательности из n чисел.

10. Поиск минимального числа х в последовательности из 3-х чисел a1,a2,a3.

11. Поиск максимального числа х в последовательности из 3-х чисел a1,a2,a3.

12. Правила пользования лифтом.

13. Вычисление средней (за неделю) температуры воздуха.

14. Подсчет всех чисел, меньших 0 в последовательности из 3-х чисел a1,a2,a3.

15. Подсчет всех одинаковых чисел в последовательности из 3-х чисел a1,a2,a3.

16. Правила проведения тестирования по определенной дисциплине.

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

18. Правила пересчета величины временного интервала, заданного в минутах, в величину, выраженную в часах и минутах.

19. Определение расстояния d между двумя точками на плоскости, заданными координатами х1, у1, Х2, У2.

20. Вычисление стоимости покупки с учетом скидки. Скидка в 10% предоставляется, если сумма покупки больше 10000 тенге.

21. В магазине продается костюмная ткань. Дана ее цена в тенге за кв. метр. Подсчитать стоимость куска этой ткани длиной Х м и шириной У м.

22. Нахождение суммы всех натуральных чисел от 1 до m, используя формулу суммы членов арифметической прогрессии.

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

24. Вычисление стоимости поездки на дачу на автомобиле (туда и обратно).

25. Определение стоимости междугороднего разговора по телефону с учетом 20% скидки, предоставляемой по субботам и воскресеньям.

26. Дано целое число в диапазоне 1 – 5. Вывести строку - словесное описание соответствующей оценки (1 - "плохо", 2 - "неудовлетворительно", 3 - "удовлетворительно", 4 - "хорошо", 5 - "отлично").

27. Нахождение среднего геометрического трех натуральных чисел.

28. Вычисление величины дохода по банковскому вкладу.

29. Арифметические действия над числами пронумерованы следующим образом: 1 - сложение, 2 - вычитание, 3 - умножение, 4 - деление. Дан номер действия и два числа A и B (В не равно нулю). Выполнить над числами указанное действие и вывести результат.

30. Правила снятия наличных денег по банковской карточке.

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

1. Каковы возможные подходы к определению понятия алгоритм?

2. Кто (что) может быть исполнителем алгоритма?

3. Какие существуют способы представления алгоритмов?

4. В чем особенности графического способа представления алгоритмов?

5. Как регулируются правила оформления блок-схем?

6. Каковы основные алгоритмические структуры?

7. Чем определяются свойства алгоритмов «дискретность», «определенность», «понятность», «результативность», «массовость»?

8. Что такое алгоритмический язык?

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

1.Название, цель, содержание работы.

2. Задание.

3. Краткие теоретические сведения.

4. Результаты выполнения задания.

4. Письменные ответы на контрольные вопросы.

5. Выводы по работе.


 

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

72968. АНАЛІТИЧНЕ ТА КОНСАЛТИНГОВЕ ЗАБЕЗПЕЧЕННЯ АДМІНІСТРАТИВНОГО МЕНЕДЖМЕНТУ 57.5 KB
  Вона потребує максимального концентрування на певному завданні досконалого знання предметної області оперативного вивчення ситуації розуміння конкретної проблеми і процесів її розвитку застосування різноманітних методів й прийомів аналізу певного часу тощо.
72969. Функции. Правила организации функций 85.5 KB
  При вызове функции ей при помощи аргументов (формальных параметров) могут быть переданы некоторые значения (фактические параметры), используемые во время выполнения функции. Функция может возвращать некоторое (одно!) значение.
72970. Ежелгi Римдегі құл иеленуші мемлекет және құқығы 30.94 KB
  2 кезең - рим құқығының гүлдену кезеңі. Бұл кезде цивтльдік құқықпен қатар преторлық құқық пайда болады, оның ішінен жалпы халықтық немесе халықтар құқығы бөлініп шықтығ, бұл құқық римдік азаматтармен шетелдік азаматтар арасындағы, сонымен қатар Рим мемлекетінің аумағында...
72971. Пожежна безпека виходу горючих речовин із нормально працюючого технологічного обладнання 315 KB
  Горючі гази пари і рідини виходять з апаратів і трубопроводів у виробниче приміщення або на відкриті площадки не тільки при ушкодженнях та аваріях але і при нормальній експлуатації апаратів що мають свої конструктивні особливості.
72972. Inflammation 47.5 KB
  Inflammation is defined as the local response of living mammalian tissues to injury due to any agent. It is body defense reaction in order to eliminate or limit the spread of injurious agent. The agents causing inflammation may be as under: Physical agents like heat, cold, radiation, mechanical trauma.
72973. ПЛАНУВАННЯ І ПОРЯДОК ФІНАНСУВАННЯ ВИДАТКІВ МІСЦЕВИХ БЮЖЕТІВ 169 KB
  Свої права визначати напрями використання суспільних коштів громадяни делегують своїм представникам в органах державної влади та місцевого самоврядування. З метою ефективного використання бюджетних коштів видатки необхідно здійснювати централізовано що сприятиме економії ресурсів.
72974. Урадавая палiтыка пад час падзелаў Рэчы Паспалітай (канец XVIII ст.) 133.88 KB
  Жнівень 1772 г. – першы падзел Рэчы Паспалітай. У склад Расіі былі ўключаны Інфлянцкае ваяводства, найбольшая частка Полацкага, амаль усё Віцебскае ваяводства, усё Мсціслаўскае і ўсходняя частка Рэчыцкага павету Мінскага ваяводства (з Рагачовам, Прапойскам, Чачэрскам і Гомелем).
72975. ПРОБЛЕМИ СУЧАСНОГО ЦИВІЛЬНОГО ПРОЦЕСУ ТА ШЛЯХИ ЇХ ВИРІШЕННЯ 56.28 KB
  Проблеми цивільного процесу умовно поділяються на теоретичні та практичні проблеми Найголовнішими сучасними проблемами цивільного процесу є такі: Невідповідність нового ЦПК конституційним принципам здійснення правосуддя гласность состязательность введення інституту присяжних.
72976. Культура речи 898.5 KB
  Высокая культура разговорной и письменной речи хорошее знание и чутье родного языка умение пользоваться выразительными средствами его стилистическим многообразием самая лучшая опора самое верное подспорье и самая надежная рекомендация для каждого человека в его общественной жизни...