Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


Ћекци€ 7. Ѕазовые алгоритмические структуры




–ассматриваютс€ основные пон€ти€ об алгоритме в программах и алгоритмизации решени€ задач.

јлгоритм Ц это упор€доченна€ совокупность формализованных и полных команд исполнителю алгоритма (человек, Ё¬ћ), задающих пор€док и содержание действий, которые он должен выполнить дл€ нахождени€ решени€ любой задачи из рассматриваемого класса задач.

јлгоритм удовлетвор€ет следующим основным свойствам:

  1.  онечность (дискретность) команд и выполн€емых по ним действий алгоритма.
  2. ¬ыполнимость в определенной операционной среде (в определенном классе исполнителей).
  3. –езультативность отдельных команд и всего алгоритма.
  4. ѕрименимость алгоритма ко всем возможным входным данным конкретного класса задач.
  5. ќпределенность (детерминированность) команд и всего алгоритма дл€ всех входных данных.
  6. ‘ормализованное, конструктивное описание (представление) команд алгоритма.
  7. ћинимальна€ полнота системы команд алгоритма.
  8. Ќепротиворечивость любых команд алгоритма на любом наборе входных данных.

Ќа алгоритмическом €зыке ѕаскаль любой алгоритм простой (не модульной, не составной) структуры имеет следующий стандартный вид:

Program <им€ (заголовок) алгоритма>; Uses <список подключаемых библиотек, если они нужны>; { комментарии, если нужны } Label <список меток (имен участков программ), если они нужны>; { комментарии } Const <список констант (не измен€емых величин), если они нужны>; { комментарии } Type <список имен и типов структур данных, если они нужны>; { комментарии } Var <список имен и типов переменных, если они нужны>; { комментарии } { < услови€ задачи и применимости алгоритма > } { < цель составлени€ и выполнени€ алгоритма > }Begin <команды ввода входных данных, если они нужны>; { комментарии } <тело алгоритма (команды управлени€ и преобразовани€ алгоритма)>; { комментарии } <команды вывода результатов (выходных данных), если они нужны>; { комментарии }End.

ѕример. ѕрограмма вычислени€ объема v правильного цилиндра с радиусом основани€ r и высотой h.

Program V—il;Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете" }Const pi = 3.14;Var r, h, v: real; { дл€ правильного цилиндра с радиусом основани€ r и высотой h } { вычислить и выдать на экран значение его объема v }Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (r, h); { ввод входных параметров } v:=pi*r*r*h; { вычисление объема по формуле дл€ цилиндра } WriteLn (С¬ычисленный объем цилиндра равен Т, v) { вывод результата }End.

ѕриведем таблицу наиболее часто используемых в €зыке ѕаскаль функций и процедур.

ќбычна€ запись ѕаскаль
 вадрат числа х sqr(x)
 орень квадратный из x sqrt (x)
ћодуль |х| abs (x)
sin x sin(x)
cos x cos(x)
tg x tg(x)
ctg x ctg(x)
arcsin x arcsin (x)
arccos x arccos(x)
arctg x arctg(x)
Ќатуральный логарифм ln x ln(x)
—тепень числа е = 2, 7... или еx exp(x)
ќстаток от делени€ целого х на целое у x mod y
„астное от делени€ целого х на целое y x div y
÷ела€ часть числа х (вещественного) int(x)
—лучайное число от 0 до х rnd(x)
ƒлина текста х в символах length (x)

ѕример. –езультаты применени€ этих функций: sqrt(9) = 3, abs(Ц5) = 5, sin(0) = 0, cos(0) = 1, ln(1) = 0, exp(1) =e, 23 mod 5 = 3, 20 mod 5 = 0, 23 div 5 = 4, 20 div 5 = 4, int(2.7) = 2, int(2) = 2, rnd(0) = 0.231356, length(СинформТ) = 6.

ѕор€док выполнени€ операций (старшинство операций Ц по убыванию) в €зыке ѕаскаль:

  1. вычисление выражений в скобках;
  2. вычисление стандартных функций;
  3. умножение и деление (обозначаютс€ "*" и "/");
  4. сложение и вычитание (обозначаютс€ "+" и "Ц").

ѕример. ¬ыражение b*c + (d/t*(v/n/m))*sin(x) вычисл€етс€ в следующем пор€дке (слева направо): v/n, (v/n)/m, d/t, (d/t)*(v/n/m), sin(x), b*c, (d/t*(v/n/m))*sin(x), b*c+(d/t*(v/n/m))*sin(x) и эквивалентно математическому выражению: .

–ассмотрим базовые простые команды €зыка ѕаскаль.

1.  оманда описани€ (заголовка) алгоритма (программы):

Program <им€ алгоритма>;,

где <им€ алгоритма> Ц им€, задаваемое составителем программы (краткое, полное, грамотное отражение сути алгоритма).

2. ¬вод Ц команда ввода в рассмотрение (в тело алгоритма) тех или иных входных параметров:

Read (<список вводимых параметров>);

или

ReadLn (<список вводимых параметров>);.

ѕерва€ команда вводит данные с текущей позиции экрана (где стоит курсор), втора€ Ц с новой строки экрана.

3. ¬ывод Ц команда вывода на экран тех или иных входных или выходных параметров алгоритма:

Write (<список выводимых параметров>);

или

WriteLn (<список выводимых параметров>);.

ѕерва€ команда выводит данные с текущей позиции экрана (где стоит курсор), втора€ Ц с новой строки экрана.

4. ѕрисваивание Ц команда изменени€ текущего значени€ переменной вида:

<идентификатор>:= <выражение>;,

где <идентификатор> соответствует имени переменной, <выражение> Ц корректно записанное выражение. «нак ":=" означает последовательное выполнение двух действий: определение текущего значени€ <выражени€> и замена текущего значени€ переменной, им€ которой задано <идентификатором>, на новое значение, равное значению <выражени€>.

  1.  оманда начала алгоритма (блока) Ц команда Begin.
  2.  оманда завершени€ алгоритма (блока) Ц команда End.

7.  оманда вставки комментариев в текст алгоритма имеет вид:

<комментируемое в программе> <текст комментари€>.

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

 

–азличают три базовые алгоритмические структуры: следование, ветвление, повторение.

1. —труктура следование состоит из двух команд с указанной очередностью их выполнени€ и имеет вид:

<команда Ц предшественник>;<команда Ц преемник>.

2. —труктура типа ветвлени€ в полной форме состоит из некоторого услови€, провер€емого на истинность при выполнении структуры, команды, выполн€емой при выполнении провер€емого услови€, и команды, выполн€емой при невыполнении услови€. —труктура имеет вид

if <условие> then <команда, выполн€ема€ при выполнении услови€> else <команда, выполн€ема€ при невыполнении услови€>;.

 лючевые (служебные) слова ѕаскал€ Ц if (если), then (то), else (иначе).  лючевые слова нельз€ измен€ть, замен€ть, так как их эталоны закреплены в переводчике с €зыка ѕаскаль (о нем подробнее Ц ниже).

ѕример.  оманда вида

if (х>y) { если текущее значение х больше текущего значени€ y, } then у:= х { то текущее значение у полагаем равным текущему значению х, } else x:= y; { иначе (при х <= y) текущее значение x замен€ем на текущее значение y }.

—труктура типа ветвлени€ в неполной форме Ц частный случай ветвлени€ в полной форме, в которой, при невыполнении услови€, управление просто передаетс€ следующей команде и больше никаких действий команда ветвлени€ не осуществл€ет. Ёта структура имеет вид

if <условие> then <команда, выполн€ема€ при исполнении услови€>;.

3. —труктура повторени€ (цикл) служит дл€ компактной записи одного и того же набора команд, повтор€емых дл€ различных значений параметров команд.

—труктура повторени€ типа "пока (while)" записываетс€ в виде:

while <условие продолжени€ повторени€> do <повтор€ема€ команда>;

или

while <условие продолжени€ повторени€> do begin <повтор€ема€ команда номер 1>; <повтор€ема€ команда номер 2>;... <повтор€ема€ команда номер N> end;.

ƒошел до сюда 01.11.14 —делал примеры по каждой структуре

 лючевые слова ѕаскал€ Ц while (пока), do (выполн€ть), begin (начало), end (конец).

“елом цикла называетс€ последовательность повтор€емых команд, котора€ может быть и пустой (редко встречаемый случай).

„асть команды цикла " while <условие продолжени€ повторени€>" Ц заголовок цикла.

ƒанный цикл выполн€етс€ по правилу: если условие повторени€ дл€ текущих его параметров не выполнено, то повторение команд (тела) цикла на этом завершаетс€; если же оно выполнено, то выполн€етс€ тело цикла и оп€ть провер€етс€ условие повторени€ команд тела цикла.

ѕример. ѕусть необходимо находить сумму всех нечетных элементов натурального р€да чисел до тех пор, пока эта сумма не превысит значение n. —лагаемое, при котором эта сумма превысит n Ц включать в сумму.

"«абудем" временно чисто математическое решение этой задачи Ц с использованием суммы арифметической прогрессии с шагом 2. јлгоритм программа) имеет вид

Program Summa;Uses Crt; { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}Var i, n, s: real; { дл€ р€да чисел 1, 3, 5, Е, } { найти и выдать сумму s всех первых чисел р€да, дл€ которых впервые s > n }Begin ClrScr; { команда очистки экрана (от данных предыдущей задачи) } ReadLn (n); { ввод входного параметра } s:=1; { начальное значение суммы до входа в цикл } i:=1; { количество просуммированных чисел в начале } while (s<=n) do { заголовок цикла (проверка услови€ выхода из цикла) } begin i:=i+2; { находим новое слагаемое } s:=s+i { добавили к предыдущему значению суммы новое слагаемое } end; WriteLn ('¬ычисленна€ сумма равна ', s); { вывод результата }End.

¬тора€ форма повторени€ Ц цикл типа "до" (for), котора€ имеет вид

for <переменна€>:= <начальное значение переменной> to <конечное ее значение> do <команда>;

или

for <переменна€>:= <начальное значение переменной> to <конечное ее значение> do begin <повтор€ема€ команда номер 1>; <повтор€ема€ команда номер 2>;... <повтор€ема€ команда номер N> end;.

«десь <переменна€> Ц им€, идентификатор пересчитываемой переменной.

 лючевые слова ѕаскал€ Ц for (дл€), to (к).

Ётот цикл выполн€етс€ по правилу: дл€ начального значени€ переменной выполн€ютс€ команды тела цикла по пор€дку и затем провер€етс€, превысило ли текущее значение переменной ее заданного конечного значени€; если превысило Ц цикл заканчиваетс€, иначе значение переменной увеличиваетс€ на единицу и снова повтор€етс€ тело цикла и т.д.

ѕример. Ќеобходимо вычислить среднюю стоимость единицы всех n видов товаров (единица измерени€ Ц одна и та же, например, тонна), если стоимость единицы каждого товара увеличиваетс€ на 10, а наименьша€ стоимость единицы товара равна 2. ≈сли "забыть" временно лучшее, "чисто математическое" решение этой задачи, то алгоритм будет иметь вид

Program ST;Uses Crt { подключение библиотеки ввода/вывода на экран "в звуке и цвете"}Var i, n, s, x: integer; { стоимость единицы товара даетс€ р€дом n чисел вида: 2, 12, 22, 32, Е } { найти и выдать среднюю стоимость s всех n товаров s }Begin ClrScr { команда очистки экрана (от данных предыдущей задачи) } ReadLn (n); { ввод входного параметра } s:=0; { начальное значение суммы до входа в цикл } x:=2; { начальное значение стоимости товара Ц стоимость первого товара } for i:=1 to n do { заголовок цикла (проверка услови€ выхода из цикла) } begin s:=s+x; { находим новую сумму товаров } x:=x+10 { находим стоимость следующего товара } end; WriteLn ('¬ычисленна€ средн€€ стоимость товаров равна ', s/n: 5:5); { вывод результата }End.

–ассмотрим примеры алгоритмизации (программировани€) задач на €зыке ѕаскаль.

ѕример. —оставим алгоритм вычислени€ факториала заданного натурального числа n, то есть произведени€ n! = 1 * 2 * 3 *... * (n Ц 1) * n c использованием рекуррентной формулы n! = (n Ц 1)! * n. ќпишем метод решени€. ƒл€ этого заметим цепочку справедливых равенств:

1! = 1, 2! = 1 * 2 = 1! * 2, 3! = 1 * 2 * 3 = 2! * 3,..., m! =1 * 2 * 3 *... * (m Ц 1) * m = (m Ц 1)! * m.

—ледовательно, дл€ вычислени€ факториала m! необходимо факториал (m Ц 1)! домножить на m, где m = 1, 2,..., n. ѕрограмма на ѕаскале имеет вид

Program Factorial;Uses Crt;Var n, f, i: integer; { дано натуральное число n } { найти и выдать произведение всех натуральных чисел до n включительно }Begin ClrScr; WriteLn('¬ведите число n: '); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } f:=1; { начальному значению f присваиваетс€ 1, то есть 1!=1 } for i:=1 to n do { цикл умножени€ текущего произведени€ f на текущее i } f:=f*i; { предыдущее значение факториала умножаем на текущее значение i } WriteLn('ѕолученный результат f: ',f); { вывод результата }End.

ѕример. —оставим алгоритм перевода заданного дес€тичного натурального числа n в двоичную систему. ћетод решени€ определ€етс€ процедурой перевода Ц последовательными делени€ми числа n на 2 и последующим сбором остатков от делени€. ≈сли последовательно выдавались с равные 1,0,1,0,0,1, то двоичное изображение c равно 100101. јлгоритм имеет вид

Program S10-S2;Uses Crt;Var n, a, i, c: integer; { дано дес€тичное натуральное число } { выдать последовательно цифры его двоичного изображени€ }Begin ClrScr; WriteLn('¬ведите переводимое число: '); { приглашение к вводу входного параметра } ReadLn(n); { ввод входного параметра } WriteLn('ѕолученное двоичное число от конца:'); { выдача "шапки" к результату } i:=0; { начинаем с младшего, нулевого разр€да } while (n>0) do { цикл делени€ числа и получаемых частных (пока делитс€) } begin i:=i+1; { переход к следующему делению } c:=n mod 2; { находим очередной остаток от делени€ на 2} n:=n div 2; { находим очередное частное от целочисленного делени€ } write(c) { выдаем новую двоичную цифру } end;End.




ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2016-12-05; ћы поможем в написании ваших работ!; просмотров: 661 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—тудент всегда отча€нный романтик! ’оть может сдать на двойку романтизм. © Ёдуард ј. јсадов
==> читать все изречени€...

742 - | 563 -


© 2015-2023 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.022 с.