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


 

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

53384. Учет реконструкции и модернизации основных средств 26.18 KB
  Порядок формирования и использования резерва сводится к следующему: отчисления в резерв списываются на расходы равными долями на последний день соответствующего периода. Затем сумма фактически осуществленных затрат на проведение ремонта списывается за счет средств резерва.
53385. Понятие дебиторской и кредиторской задолженности и порядок их списания 24.2 KB
  В своей хозяйственной деятельности предприятие вступает в отношение с другими организациями, несет обязательства по уплате налогов, сборов, а также выступает в качестве субъекта трудовых отношений. При этом возникают кредиторская и дебиторская задолженность.
53387. Класичне, статистичне означення імовірності 1.82 MB
  Узагальнити і систематизувати знання, вміння та навички учнів; навчити застосовувати їх при розвязуванні прикладних задач з біології; ознайомити з історичним матеріалом. Розвивати творчі здібності учнів. Організація робочих місць учителя та учнів. Заповнює кросворд один з учнів класу працюючи за компютером.
53388. Імпресіонізм у світовому красному письменстві («Intermezzo» М.Коцюбинського та лірика П.Верлена) 587 KB
  Світ природи і духовний стан ліричного героя у верленівських пейзажах душі Осіння пісня В серці і сльози і біль. Аналіз поезії Осіння пісня 1866 Що вчувається ліричному героєві в музиці осені Які спогади викликає в ньому бій годинника Як впливають на ліричного героя вітер поле жовте листя Схарактеризуйте емоційний стан ліричного героя. Ця мелодія відображає стан осінньої природи й водночас внутрішній стан ліричного героя. Водночас і нам дає зрозуміти що керує діями письменника його почуття помисли що робиться в його...
53389. Порушення роботи імунної системи 71.5 KB
  МЕТА: Сформувати в учнів поняття про імунні системи імунні реакції організму алергію алергени СНІД; розглянути засоби профілактики від інфекційних хвороб; показати згубний вплив радіації отрутохімікатів на імунну систему; розвивати вміння надавати собі допомогу при різних видах захворювань; продовжувати екологічне виховання і виховання здорового способу життя. Давайте згадаємо які системи органів є у тварин А які системи органів людини ви вже вивчили Зараз на уроці ми розглянемо імунну систему. Центральне місце серед клітин імунної...
53391. Древняя Индия 41 KB
  Развивающая: Развивать умение пользоваться историко-географической картой, извлекать из неё знания, закрепить их с помощью работы по контурной карте. Умение переходить от одной формы работы к другой. Воспитательная: Закрепление представлений о том, что общечеловеческие достижения в культуре имеют конкретное происхождение. Представить культуру Индии как часть общемировой.
53392. США. Індіанці: пошуки вирішення проблеми. Контроль навичок - аудіювання 95.06 KB
  By the end of the lesson you should be able to reply and react appropriately to various statements. Beside, you will listen to some new information about the first Americans who came to Alaska from Asia crossing the Bering land bridge, which later became the Bering Strait. You will hear the text about American Indians and their problems.