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

Для данной алгоритмической структуры^[31] характерно, что в любой момент времени её реализации осуществляется обработка только по какой-либо одной из ветвей^[32].

Для описания разветвляющегося алгоритма существуют операторы:

условный

блочной структуры:

IF условие THEN^[33]

блок действий 1

ELSE

блок действий 2

ENDIF

линейной структуры:

IF условие THEN блок 1 ELSE блок 2

Обе структуры могут быть использованы как в полной форме так и в усеченной – без блока ELSE.

При работе условного оператора сначала проверяется выполнение условия. Если условие выполняется (истинное), то реализуется блок 1, в противном случае – блок 2. Условие – это логическое выражение, использующее операции сравнения (=, <, > <=, >=, <>) и логические операции^[34] (AND, OR).

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

CLS : INPUT A,B,C : D=B^2-4*A*C

IF D>0 THEN

X1=(-b+SQR(d))/(2*a) : X2=(-b-SQR(d))/(2*a) : PRINT X1,X2

ELSE

PRINT ”Решенией нет”^[35]

ENDIF

выбора (выражением может быть список через запятую 1,3,4 диапазон значений 1 TO 9; операция сравнения IS >=).

SELECT CASE выражение^[36]

CASE условие 1

блок операторов 1

CASE условие 2

блок операторов 2

CASE ELSE

блок операторов n

END SELECT

CLS : INPUT A,B,C : D=B^4*A*C

SELECT CASE D

CASE IS >0

X1=(-b+SQR(d))/(2*a) ^[37]

X2=(-b-SQR(d))/(2*a) : PRINT X1,X2

CASE ELSE

PRINT ”Решенией нет”

END SELECT

END

2.3 Циклический алгоритм. Примеры

Алгоритм называется циклическим, если содержит участок, повторяющийся один или много раз.

Циклы^[38] бывают с определённым количеством, неопределённым числом вычислений.

I = I_Н , I_K , h

тело цикла

условие

тело цикла

условие

да

нет

I – параметр цикла

I_Н – начальное значение параметра

I_K – конечное значение параметра

h – шаг изменения параметра (приращение)

Оператор цикла с параметром:

FOR I = I_Н TO I_K STEP h^[39]

тело цикла

NEXT I

Оператор цикла с предусловием:

DO WHILE^[40] условие продолжения вычислений (UNTIL условие прекращения вычислений)

тело цикла

LOOP

Оператор цикла с постусловием:

тело цикла

LOOP WHILE условие продолжения вычислений (UNTIL^[41] условие прекращения вычислений)

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

Задание

Написать программу^[42], которая создает типизированный файл и записывает в него MxN значений. Имя для файла создается по маске <login2>.dan.

Решение:

Напишем процедуру записи в файл. Так же помним, что при работе с типизированными файлами запись осуществляется в файл в DOS формате и с разделителями. Поэтому если его открыть в Блокноте будут не читаемые символы. Чтение возможно только программно^[43].

Описание структуры программы:

Для решения нам потребуются константы: M=15; N=16. Для удобства напишем процедуру:

write_to_file(); - для записи в файл. В ней будем генерировать значения массива из записывать их в файл.

Алгоритм

Рис. 3. Блок-схема 1

Рис. 4. Блок-схема 2

Код программы:

program p21;

const

M=15;

N=16;

procedure write_to_file();//запись в файл

var

i,j: integer;

k:byte;

f: file of byte;

mass: array[1..M, 1..N] of byte;//массив с данными

begin

Assign(f, 'xx162waa.dan');

Rewrite(f);

for i:=1 to M do

for j:=1 to N do

begin

k:=random(255);

mass[i][j]:=k;//наполнение массива

write(f, mass[i][j]);

end;

close(f);

writeln('Данные в файл записаны');

end;

begin

write_to_file();//сначала записываем данные в файл

end.

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

Рис. 5. Работа программы

3. Языки программирования

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

Они служит целям:

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

Поэтому существует делема, на каком языке реализовать решение задачи Язык программирования программисту^[44] дает определенный набор инструментов, если данные инструменты в данный момент не нужны, то программист их не использует.

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

интерпретаторы^[45], которые сканируют и проверяют исходный код в один шаг,
компиляторы^[46], которые сканируют исходный код для производства текста программы на машинном языке, которая затем выполняется отдельно.

3.1 Интерпретаторы и компиляторы

Одно, из основных преимуществ интерпретаторной реализации в том, что данная реализация позволяет вам сразу после ввода команды получать результат. К примеру, если написать PRINT 4*3/4 и нажать кнопку ввода, то вы сразу получите ответ = 3 (данная особенность позволяет вам использовать компьютер стоимостью от 10000 рублей как обычный калькулятор стоимостью 100 рублей)^[47]. Плюс ко всему, интерпретаторы имеют особые атрибуты, которые значительно упрощают отладку. То есть программист может перед запуском программы определить перечень переменных значения, которых он хочет отслеживать. Сформировать данный список и запустить пошагово программу, в специальной области окна он будет видеть все значения указанных переменных в данный момент времени. Есть еще одна возможность в любой момент времени нажать кнопку пауза, что позволит прервать выполнение программы и посмотреть значения необходимых переменных или же посмотреть, что программа выводит на экран^[48].

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

Компилятор^[49] - это транслятор текста на машинный язык, который считывает программу, написанную на «естественном» языке и преобразует в машинные инструкции. То есть он создает исполняемый файл и запускает его, чтобы пользователь мог увидеть результат своей работы. Но он не позволит прервать преобразование и посмотреть состояние переменных. Единственно, если произойдут критичные ошибки, которые не позволять сформировать исполняемый файл.

Компилятор сообщить об ошибки и прервет свою работу^[50]. Если вы поработаете над созданием улучшений, то вы сможете достичь значительного быстродействия. Другая сторона данного процесса состоит в том, что наша программа, используют большую часть времени на работу с файлами на дисках или ожидание ввода, что не позволить значительно повысить быстродействие.

3.2 Языки программирования

Сейчас существует множество языков программирования для решения той или иной задачи. Приведем пример одного из распространенных языков программирования и приведем его достоинства и недостатки.

С# достоинства^[51]:

Очень популярен, поэтому что имеется хорошая поддержка.
Имеет большую базу свободно доступного кода для загрузки, а также поддерживает прямую интеграцию с ASM и C.
Очень мощный и может быть использован для создания практически любой программы, включая низкоуровневые системные программы.
В каждой крупной операционной системе есть компилятор для С#. Программы на С#, специально написанные для переносимости, будут работать во многих основных операционных системах с небольшими изменениями в коде.
С# - это язык, который скомпилирован, поэтому он часто может работать быстрее, чем такие языки, как Java, Python и C ; Поскольку он не зависит от интерпретатора или «среды выполнения»^[52], которая должна быть загружена заранее.
Имеет давно установленную базу использования, которая, вероятно, гарантирует, что поддержка языка будет продолжаться в течение некоторого времени.
Многие языки основаны на C / С#, таких как Java, поэтому знание на С# облегчит понимание этих языков.
Имеет относительно небольшую связанную стандартную библиотеку С# по сравнению с такими языками, как Java Platform Standard SDK или .NET Framework^[53], что позволяет повысить гибкость и сократить отпечаток системных результирующих компиляций.
Стандартизирована Международной ассоциацией стандартов как ISO / IEC 14882 со значительными версиями стандарта, выпущенными в 1998, 2003 и 2011 годах.
Имеет значительное количество библиотек с открытым исходным кодом, включая Boost^[54], которые доступны и широко доступны.

С# недостатки:

Сам по себе это не очень безопасно, поскольку в нем отсутствуют автоматические проверки границ, неверные проверки указателей и т. д., допускается невидимые побочные эффекты (вызывающие недетерминированное поведение) и допускается неявное приведение типов. Это связано с многочисленными проблемами безопасности и утечками памяти, если не предпринимать дополнительных усилий для их предотвращения.
По умолчанию отсутствует встроенное управление памятью, требующее от разработчиков использования внешних библиотек или повторного изобретения необходимого кода.
Его система ООП^[55] довольно архаична, требуя явной виртуализации методов, среди прочего, обычно зарезервированной для старых языков.
Отсутствует возможность определения полностью настраиваемых операторов. (Не следует путать с возможностью определения пользовательских реализаций для аппаратного набора операторов, который имеет С#.)
Не предлагает полных алгебраических типов данных.
Имеет несколько более сложную систему обучения, чем некоторые другие языки.
Очень придирчиво, как форматируется код (но не столь придирчивый, как FORTRAN, RPG или Haskell^[56])
GUI^[57], Networking и Threads не стандартизированы, требуя использования нестандартных сторонних библиотек (хотя доступно множество таких библиотек, как бесплатных, так и коммерческих, а также возможность использовать библиотеки C), Boost - одна из предпочтительных библиотек. Отсутствие стандарта^[58], однако, может затруднить обучаемость и функциональную совместимость или по крайней мере потребовать некоторого расширенного расследования.

Приведем несколько примеров программ на языкы С#:

Разработать программу нахождения корней квадратного уравнения с использованием описанных инструментов языка С#:

Решение:

using Systeem;

using Systeem.Colleections.Geeneeric;

using Systeem.Linq;

using Systeem.Teext;

using Systeem.Threeading.Tasks;

nameespacee ConsoleeApplication1

{

class Program

{

static void Main(string[] args)

{

doublee a, b, c;

doublee d, x1, x2;

Consolee.WriteeLinee("a*x*x+b*x+c=0");

Consolee.Writee("Введите a="); a=Conveert.ToDoublee(Consolee.ReeadLinee());

Consolee.Writee("Введите b="); b=Conveert.ToDoublee(Consolee.ReeadLinee());

Consolee.Writee("Введите c="); c=Conveert.ToDoublee(Consolee.ReeadLinee());

if (a == 0.0){

Consolee.WriteeLinee("D=0 корней нет!");

}

eelsee{

d = b * b - 4 * a * c;

Consolee.WriteeLinee("D= {0:f3}", d);

if (d > 0){

x1 = (-b + Math.Sqrt(d)) / (2 * a);

x2 = (-b - Math.Sqrt(d)) / (2 * a);

Consolee.WriteeLinee("x1= {0:f3}", x1);

Consolee.WriteeLinee("x2= {0:f3}", x2);

}

eelsee{

if (d == 0){

x1 = (-b / (2 * a)); x2 = x1;

Consolee.WriteeLinee("x1=x2= {0:f3}", x1);

}

eelsee{

Consolee.WriteeLinee("D<0 Действительных корней нет!");

}

Consolee.ReeadLinee();

}

Разработать программу согласно задания на языке С#:

Предметная область: Вокзал. Касса вокзала имеет список тарифов на различные направления. При покупке билета регистрируются паспортные данные пассажира. Пассажир покупает билеты на различные направления.

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

Добавить комментарии к ключевым объектам и функциям.

Добавить блоки try – catch (по усмотрению)

Составить схему алгоритма в Microsoft Visio.

Добавить обработку исключительных ситуаций:

длина строки наименования тарифа больше 10 символов.
стоимость билета с учетом скидки меньше нуля.

Добавить перегруженный бинарный оператор для уменьшения стоимости тарифа.

Система должна:

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

Решение:

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