Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Основные алгоритмические структуры).pdf

В данном варианте происходит увеличение значения счетчика на 1 в каждой итерации. Язык имеет также реализацию с уменьшением значения параметра счетчик1 на единицу.

for<счетчик2> = <значение2>downto<конечное_значение>do<оператор1>;

Отметим, что в реализации цикла со счетчиком на Pascal нет возможности указать шаг не равный единице [11].

Язык Python имеет другие особенности. Во-первых, в этом языке используется интерпретатор, а не компилятор, как в случае с Pascal.

Интерпретатор — это программа или техническое средство, выполняющее интерпретацию, а также вид транслятора, осуществляющего пооперационную (покомандную) обработку и выполнение исходной программы или запроса. В отличие от компилятора, который осуществляет трансляцию всей программы высокого уровня в машинные коды один раз без ее выполнения (создает объектную программу), интерпретатор транслирует исходную программу команда за командой каждый раз при выполнении и не создает объектного модуля. За счет такого режима выполнение программы происходит медленнее, чем в случае ее обработки транслятором, однако при обработке интерпретатором программы выполняются сразу, без промежуточной стадии трансляции[14].

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

Цикл while в Python записывается следующим образом:

while условие:

выражение 1

выражение 2

выражение 3

Цикл for в Python обладает способностью переберать элементы любого комплексного типа данных (например, строки или списка). В Python цикл for обладает следующим синтаксисом:

for item in sequence:

<выражения>

Cинтаксис оператора if выглядит так.

if выражение:

инструкция_1

инструкция_2

инструкция_n

После оператора if записывается выражение[12]. Если это выражение истинно, то выполняются инструкции, определяемые данным оператором. Выражение является истинным, если его результатом является число не равное нулю, непустой объект, либо логическое True. После выражения нужно поставить двоеточие/

Бывают случаи, когда необходимо предусмотреть альтернативный вариант выполнения программы. Т.е. при истинном условии нужно выполнить один набор инструкций, при ложном – другой. Для этого используется конструкция if – else[13].

if выражение:

инструкция_1

инструкция_2

...

инструкция_n

else:

инструкция_a

инструкция_b

инструкция_x

if выражение_1:

инструкции_(блок_1)

elif выражение_2:

инструкции_(блок_2)

elif выражение_3:

инструкции_(блок_3)

else:

инструкции_(блок_4)

Пример.

a = int(input("введите число:"))

if a < 0:

print("Neg")

elif a == 0:

print("Zero")

else:

print("Pos")

Если пользователь введет число меньше нуля, то будет напечатано “Neg“, равное нулю – “Zero“, большее нуля – “Pos“[12,13].

Глава 3. Примеры использования программ

3.1. Линейные программы

Рассмотрим примеры использования различных алгоритмических структур в языках Python и Pascal.

Python представляет собой интерпретируемый язык, синтаксис которого устроен так, чтобы создание программ требовало от программиста как можно меньше усилий. Код на данном языке выглядит компактно и понятно[14].

Рассмотрим решение одной и той же задачи, вычисление значения функции

на этих языках программирования.

Это простая линейная программа. С помощью Python данная программа может быть представлена в следующем виде[12,13]:

import math

x=float(input("Введите число "))

print(“y =", math.sqrt(x)/math.cos(x))

Для сравнения запишем данный алгоритм на языке Pascal.

var a:real;

begin

write('Введите число ');

readln(a);

write('y = ',sqrt(a+5)/cos(a));

end.

Как видно из приведенного примера, код программы на языке Python состоит из трех строк, а код на языке Pascal из 5.

Таким образом, во многих случаях, код программы на Python содержит меньше строк, чем код на Pascal.

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

Рассмотрим решение следующей задачи на языке Pascal.

Пускай необходимо вычислить

при

Блок-cхема

Начало алгоритма

y=2.25;

c=4*sqrt(0.8/y);

b=sin(c)/cos(y);

gamma:=sin(y/b)/cos(y/b)+sin(b/c)/cos(b/c)+sin(c/y)/cos(c/y)

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

Вывод gamma

Рисунок 7 - Блок-схема линейной программы на Pascal

Текст программы на языке Паскаль:

var y,b,c,gamma:real;

begin

y:=2.25;

c:=4*sqrt(0.8/y);

b:=sin(c)/cos(y);

gamma:=sin(y/b)/cos(y/b)+sin(b/c)/cos(b/c)+sin(c/y)/cos(c/y);

writeln(gamma:0:4);

end.

Результат выполнения программы: 3.1732

3.2. Программы с использованием ветвлений

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

Утверждается, что НОД двух таких чисел равен числу Фибоначчи номера их наибольшего делителя. Другими словами, если мы обозначим, n-число Фибоначчи F(n), то есть:

НОД(Fn, Fm) = F(НОД(n,m))

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

var m,n,l,i,z:integer;

function fib(m:integer):integer;

begin

var i,k,a,b,c:longint;

k:=m;

a:=0;

b:=1;

if m=1 then fib:=1 else begin

for i:=2 to k do begin

c:=a+b;a:=b; b:=c;

fib:=c;end;end;end;

begin

writeln('Введите m>=1 ');

readln(m);

write(m,'-е число Фибоначчи= ');

writeln(fib(m),' ');

writeln('Введите n>=1 ');

readln(n);

write(n,'-е число Фибоначчи= ');

writeln(fib(n),' ');

if m<n then l:=m else l:=n;

for i:=1 to l do

if (m mod i = 0) and (n mod i = 0) then z:=i;

writeln('НОД =',fib(z));

end.

3.3. Программы с использования циклов

Рассмотрим нахождение факториала числа на языке Python c помощью функции while[10]:

Листинг программы:

number = int(input("Введите число: "))

i = 1

factorial = 1

while i <= number:

factorial *= i

i += 1

print("Факториал числа", number, "равен", factorial)

Результат работы программы:

Если вводим 5, программа выдает 120.

Одним из наиболее популярных приложений циклов являются суммы рядов и интегралы[15,16].

Например, рассмотрим задачу, в которой необходимо вычислить

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

Начало

j<=15

j=1

S=0

s:=s+b*cos(j+1)/sin(j+1)

b:=ln(j+1)/ln(10);

Вывод s

Конец

j=j+1

да

Рисунок 8 - Блок-схема решения задачи вычисления суммы

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

varj:integer; b,s:real;

begin

forj:=1 to 15 do begin

b:=ln(j+1)/ln(10); {b=lg(j+1)}

s:=s+b*cos(j+1)/sin(j+1);

end;

writeln(s:0:4);

end.

Результат.

-2.0825

В данной задаче используется цикл со счетчиком, так как известно число повторений[14].

Или, например, вычисление двойной суммы

с точностью 10^-4

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

Рисунок 9 — Блок-схема алгоритма вычисления двойной суммы

var a,s,e,sum: real; i,j:integer;

begin

e:=1E-4; {e=0.0001}

j:=1;

fori:=1 to 10 do begin

repeat

a:=exp(i/j)/(sqr(i)+sqr(j));

j:=j+1;

s:=s+a;

until a<=e;

sum:=sum+s/(i+1);;

end;

writeln((sum*6.4):0:4);

end.

Результат.

27.6367

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

Заключение

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

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

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

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

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

Ветвление позволяет реализовывать нелинейную логику выполнения программ[1-3]. При использовании полного ветвления необходимо учитывать, что оператор, стоящий сразу после выхода из ветвления будет выполнен в любом случае. При использовании неполного ветвления необходимо учитывать, что в ветвлении явно не указывается, что будет сделано в случае, если условие не выполняется (ложно). Цикл с предусловием стоит использовать в случае, если неизвестно точное количество повторений. Цикл с постусловием стоит использовать в случае, если необходимо, чтобы цикл был выполнен хотя бы один раз. Цикл с параметром является самым компактным способом записи циклической структуры.

Далее была описана реализации основных конструкций в языках программирования Pascal и Python. Отметим, что конструкции Python значительно более компактные. Кроме того, в этом языке реализована возможность использования различных конструкций выбора. Язык Pascal характеризуется четкой структурой составных частей программы. Язык Python характеризуется динамической типизацией данных, то есть тип переменной определяется только во время ее выполнения. Это обеспечивает гибкость в использовании данных различных типов.

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

В курсовой работе были достигнута поставленная цель и решены все определенные во введении задачи.

Список использованной литературы

Абрамов, В.Г.; Трифонов, Н.П. и др. Введение в язык Паскаль; Наука, 2011. - 320 c.
Агальцов, В. П. Математические методы в программировании / В.П. Агальцов. - М.: Форум, 2012. - 240 c
Акулов О.А. Информатика: учебник / О.А. Акулов, Н.В. Медведев. – М.: Омега-П, 2013. – 270 с.
Алексеев А.П. Информатика 2008 / А.П. Алексеев. – М.: СОЛОН-ПРЕСС, 2008. – 608 с.
Баженова, И.Ю. Языки программирования: Учебник для студентов учреждений высш. проф. образования / И.Ю. Баженова; Под ред. В.А. Сухомлин. — М.: ИЦ Академия, 2012. — 368
Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. - М., 2012. - 496 c.
Дж. Макконелл, Основы современных алгоритмов, М.: «Техносфера», 2009, С. 10-11
Доусон М. Программируем на Python / М.Доусон,. – СПб.: Питер, 2014. – 416 с.
Епанешников А. М., Епанешников В. А. Программирование в среде Turbo Pascal 7.0.- 2012.
Епанешников, А.М.; Епанешников, В.А. Программирование в среде Turbo Pascal 7.0; М.: ДИАЛОГ-МИФИ; Издание 4-е, испр., 2013. - 367 c.
Информатика: Учебник для вузов. Стандарт третьего поколения / Макарова Н.В, Волков В.Б.-СПб.:Питер, 2015.
КуМир [Электронный ресурс]. URL: https://www.niisi.ru/kumir/(Дата обращения 15.02.2019)
Лукин С.М., Турбо-Паскаль 7.0. Самоучитель для начинающих // ¶М:Диалог-МИФИ, 2015.
Лутц М. Программирование на Python/М. Лутц- том II, 4-е издание. Пер. с англ. – СПб.: Символ-Плюс, 2011. – 992 с.
Макарова Н.В. Информатика /под ред. Проф. Н.В. Макаровой. -М.: Финансы и статистика, 2013.
Малышев Р.А. Локальные вычислительные сети: Учебное пособие/ РГАТА. – Рыбинск, 2012.
Семакин И.А., Информатика: Базовый курс /Семакин И.А., Залогова Л., Русаков С., Шестакова Л. – Москва: БИНОМ.,2009.
Симонович С.В.Информатика. Базовый курс/Симонович С.В. и др. - СПб.: издательство "Питер", 2014.
Стариченко, Б.Е. Теоретические основы информатики : учебник для вузов / Б.Е. Стариченко .— 3-е изд., перераб. и доп. — М. : Горячая линия – Телеком, 2016 .— 401 с. — ISBN 978-5-9912-0462-0
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание — М.: Вильямс, 2013.
Учебник по паскалю [Электронный ресурс]. URL: http://pcfu.ru/stati/programmirovanie/uchebnik-po-paskalyu-oglavlenie//(Дата обращения 15.02.2019)