86794

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

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

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

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

Русский

2015-04-10

316.5 KB

5 чел.

Лабораторная работа №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. Выводы по работе.


 

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

3479. Определение коээфициента поверхностного натяжения жидкости по способу отрыва капли 185 KB
  Определение коээфициента поверхностного натяжения жидкости по способу отрыва капли Приборы и принадлежности: Бюретка с краном на штативе, два стакана, воронка, вода, исследуемая жидкость (спирт). Теория работы и описания приборов Жидкость состоит из...
3480. Физика среды и ограждающих конструкций, Строительная теплофизика 206 KB
  Физика среды и ограждающих конструкций. Среда и ее воздействие на объекты строительства. Воздушная среда и ее параметры. Водная среда и ее параметры. Климатические факторы. Влияние среды на долговечность строительных конструкций...
3483. Медична генетика 638 KB
  Залежність прояву ознак від впливу зовнішніх умов відзначав ще Ж.-Б.Ламарк, який розглядав це як один із еволюційних факторів. Учені давно помітили, що однояйцеві близнята, тобто організми з однаковим генотипом, відрізняються фенотипно, якщо розвива...
3484. Лекційний курс з основ фізики 2.71 MB
  Тема 1. Фізичні основи механіки. Кінематика Лекція 1. Основи кінематики поступального та обертального рухів Основні визначення В механіці розглядають механічний рух. Під механічним рухом розуміють зміну з часом положення тіла відносно інших тіл в пр...
3485. Измерение скорости пули с помощью физического маятника 55.8 KB
  Измерение скорости пули с помощью физического маятника Цель работы: с помощью физического маятника определить скорость пули. Рабочую формулу для экспериментального определения скорости пули получить исходя из законов сохранения момента импульса и эн...
3486. Определение ускорения свободного падения при помощи оборотного и математического маятников 443.96 KB
  Определение ускорения свободного падения при помощи оборотного и математического маятников, изучение законов колебания маятника, ознакомление с косвенными методами измерения ускорения свободного падения при помощи математического и оборотного...
3487. Бухгалтерский учёт хозяйственных процессов 391 KB
  Бухгалтерский учёт хозяйственных процессов Введение Бухгалтерский учёт представляет собой упорядоченную систему сбора и обобщения информации в денежном выражении об имущес...