С помощью этого оператора гораздо удобнее программировать задачу 5-2 (program P5_2).

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

ü REPEAT оператор UNTIL условие

Оператор, в цикле выполняется до тех пор, пока истинно условие. В отличие от оператора WHILE здесь цикл будет выполнен хотя бы один раз. Структуру с постусловием удобно применять в случае, если цикл необходимо выполнить хотя бы раз независимо от значения условия или, если само условие формируется в цикле и не может быть оценено до входа в цикл.

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

ü BREAK

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

ü СONTINUE

Действие указанных операторов (применительно к циклу FOR) иллюстрирует рисунок выше.

Задание.Написать программу в которой вводятся два операнда Х и Y и знак операции (+,–,/,*). Вычислить результат Z в зависимости от знака. Предусмотреть реакции на возможный неверный знак операции, а также на ввод Y=0 при делении. Организовать возможность многократных вычислений без перезагрузки программа (т.е. построить цикл). В качестве символа прекращения вычислений принять ‘0’.

Функциональные ряды. При работе с компьютером возникает впечатление его огромной интеллектуальной силы. На самом деле это совсем не так. Собственно процессор умеет (правда очень быстро) выполнять только четыре арифметических действия и логические операции, т.е. располагает возможностями ученика 1-го класса. Откуда же вся его математическая мощь. Ответ простой – от программистов. Разработчики компиляторов языков (в частности Паскаля) побеспокоились о том, чтобы в нем присутствовали многие математические функции. Когда мы используем выражение exp(x) мы на самом деле вызываем подпрограмму вычисления ex, написанную для нас неизвестным автором из фирмы Borland. Однако мы можем и сами это сделать. Существует методы, позволяющие вычислять функции, используя лишь небогатые возможности процессора. Так из математики хорошо известны функциональные ряды Тейлора (здесь аргумент включен в члены ряда). Хотя такие ряды бесконечны, нам нет необходимости (и возможности) вычислять их целиком. Значения элементов ряда быстро убывают и мы можем прекратить вычисления в тот момент, когда очередной член станет меньше заданной погрешности ε.

Задача 5-7. Вычислить с заданной погрешностью функцию exдля произвольного значения Х. Ряд Тейлора для нее выглядит следующим образом.

ex≈1+x+x2/2!+ x3/3!+ x4/4!+...

Отсюда можно записать аналитические зависимости (здесь у – искомая функция, r – элемент ряда, i – номер члена разложения):

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

y=x11!/2!–x32!/3!+ x43!/4!– x54!/5!+...

Сложные циклы.Этот термин означает вложенность одного цикла в другой.

Задача 5-8. Вычислить значения функции Y=X2+Z для 0≤X≤4 и 0≤Z≤10 с шагом 1. В этой функции два аргумента, т.е. она является не плоской кривой, а криволинейной по­верхностью. Решение здесь очень простое. Строятся два цикла – внешний (по Х) и внут­ренний (по Y). Поскольку аргументы и функция целочисленные и шаг равен 1, можно ис­пользовать оператор for. В данном случае безразлично, какой параметр поместить снару­жи, а какой внутри. Здесь на одно изменение переменной Х произойдет 11 изменений z.

В следующих заданиях условия целочисленности аргумента и/или шаг=1 не соблюдаются, и для организации циклов придется использовать оператор while.

Задание. Вычислить функции Y=X2+Z для 0≤X≤4 с шагом 1 и 1≤Z≤10 с шагом 2.

Задание. Вычислить функции Y=X2+Z для 0≤X≤4 с шагом 0,5 и 1≤Z≤10 с шагом 2.

6. МАССИВЫ

Как правило, данные для вычислений задаются в упорядоченной форме – в виде последовательности ряда (вектора) чисел или в виде таблицы (матрицы) чисел. Такие совокупности данных называются массивами. Например, вектор А длиной К чисел и матрица В из N строк и M столбцов (всего из NŸM элементов) выглядят следующим (справа) образом. Построение программ, оперирующих с элементами массивов – важнейшая часть техники программирования.

Цифры при имени массива, указывающие порядковый номер элемента, называются индексами. Элементы массивов Аi и Bij обозначаются как А[I] и B[I,J]. К массиву в целом обратиться нельзя. Обработка массива означает последовательную обработку отдельных его элементов.

Оператор описания массивов. Если предполагается работа с массивами, предварительно следует “известить” об этом компьютер в разделе описаний (VAR) программы. Для одномерного массива это оператор вида

ü имя_массива: ARRAY [диапазон] OF тип_массива

Например, VAR x,z: ARRAY [1..8] OF REAL; y: ARRAY [5..10] OF INTEGER; b: ARRAY [1..4, 1..5] OF INTEGER;

Здесь первый оператор описывает массивы X и Z из 8-ти элементов (с номерами от 1 до 8) вещественного типа. Второй – массив Y из 5-ти элементов (с номерами от 5 до 10) целочисленного типа, третий – двумерный массив B из четырех строк и пяти столбцов.

VAR i,j: INTEGER;

{ввод вектора Х с подсказкой}

FOR i:=1 TO 8 DO BEGIN

WRITE(‘x[',i,']='); READLN(x[i]) END;

{ввод матрицы В с подсказкой}

FOR i:=1 TO 4 DO

FOR j:=1 TO 5 DO BEGIN

WRITE('b[',i,j,']='); READLN(b[i,j]);

END;

{построчный вывод матрицы B}

FOR i:=1 TO 4 DO BEGIN

FOR j:=1 TO 5 DO WRITE('b[',i,j,']=',b[i,j]:4:1,' ');

WRITELN {вывод пустой строки}

END;

Первоочередной задачей при работе с массивами является ввод-вывод данных. Ввод организуется с помощью циклов, как показано ниже. Сначала осуществляется ввод в вектор X. На экране мы увидим, например, подсказку вида х[2]=, после чего можно ввести значение этого элемента. Аналогичную (b[2,4]=) подсказку увидим для матрицы В размерностью 4 строки на 5 столбцов. Ввод осуществляется с помощью двух циклов, один из которых вложен в другой. В наружном цикле изменяется первый индекс I элемента матрицы В, во внутреннем – второй индекс J. Второй индекс J изменяется быстрее, чем первый (на одно изменение I индекс J изменяется 5 раз). Это означает, что ввод элементов матрицы будет производиться в следующей последовательности: B[1,1],B[1,2],...B[1,5]; B[2,1],B[2,2],...B[2,5] ;...; B[4,1],B[4,2],...B[4,5], т.е. по строкам. Аналогичным образом осуществляется и вывод, но вместо оператора READLN используется оператор WRITELN. В примере производится вывод данных из матрицы В. Если позволяет ширина экрана, удобно выводить одну строку матрицы на одной строке монитора. Оператор WRITE( 'b[',i,j,']=',b[i,j]:4:1,' ') выводит данные, например, в виде b[2,3]=25.3.Поскольку оператор WRITE не переводит строку вывода, принудительный переход на новую строку осуществляется пустым оператором WRITELN после того, как строка была полностью выведена.

Начальные значения скалярным переменным и элементам массива (в особенности при отладке) можно задать в разделе констант (начинается со слова const). Например:

CONST z:ARRAY [1..3] OF INTEGER=(4,5,2);

x: INTEGER=5;

r:ARRAY [1..3,1..2] OF INTEGER=((1,2),(3,4),(5,6));

Здесь вектору Z присваиваются значения: z[1]=4, z[2] =5, z[3]=2, переменной х: 5, а прямоугольной матрице R: r[1,1]=1, r[1,2]=2, r[2,1]=3, r[2,2]=4, r[3,1]=5, r[3,2]=6.

Задача 6-1. В векторе С предельной размерности 30 элементов найти максимальный по значению элемент и его номер в С по порядку. В программе сделана проверка для N=4 и C=[5,2,7,4] в ее обрабатывающей части. Здесь переменная М запоминает значение максимального элемента, а К – номер этого элемента в векторе С. Первоначально в качестве такого элемента берется самый первый.

Задача 6-2. Определим значения вкладов в банке на конец года. Положим, имеется N счетов вкладчиков. Для всех них известны значения остатков на счете в конце каждого квартала. Следует определить и напечатать значения всех вкладов на конец года с учетом известного процента роста вклада. Все суммы считаем целочисленными (копейки игнорируем).

Данные о вкладах хранятся в массиве Х из N строк и пяти столбцов. Первые четыре элемента каждой i-ой строки (Х[i,1], Х[i,2], Х[i,3], Х[i,4]), хранят остатки вклада на конец каждого из четырех кварталов года. В последний, пятый элемент строки X[i,5] следует занести вычисленную величину вклада на конец года, который равен остатку вклада на конец последнего квартала Х[i,4], плюс установленный процент от среднего значения вклада Y=(Х[i,1]+ Х[i,2]+ Х[i,3]+Х[i,4])/4 за год. Положим, определено, что на вклад до 5000 предусмотрен процент роста – 10%, на вклад до 10000 – 15%, на вклад свыше 10000 – 20%. Иными словами установлены коэффициенты роста 1.1, 1.15 и 1.2 соответственно. Кроме перечисленного, следует найти сумму всех вкладов в банке S и среднее значение вклада, приходящееся на одного вкладчика (S/N).

Задание. В векторе Х найти элемент, максимально близкий к некоторому Y и его номер.

Задание. В векторе Х сдвинуть по кольцу его содержимое на 1 клетку. На 2 клетки. На К клеток. Подсказка. Здесь понадобится вспомогательный массив Y, куда и будем заносить уже сдвинутые данные.

Задание. Пусть имеется таблица, содержащая сведения о работниках бригады: Имя, Отработано дней, Зарплата. Известна также сумма, которую заработала бригада S. Рассчитать зарплату для каждого работника. Усложним задачу. Пусть зарплата увеличивается на 10% тем, кто отработал больше 20-ти дней (при прежнем S). Во всех случаях сумма всех зарплат работников должна быть в точности равна S.

Задание. Запрограммировать процесс выбора в детской считалке. Пусть нужно выбрать случайным образом дежурного из группы в M человек. Дети становятся в круг и “считаются” по следующему правилу. Из круга по часовой стрелке удаляется каждый третий (шаг выбора N) участник, начиная с номера 1. В конце останется только один – дежурный. Для (см. рисунок) примера M=8, N=3. Тогда последовательно из круга выйдут номера 1,4,7,3,8,6. Наконец останутся только номера 2 и 5 и счет продолжается уже между ними 2→5→2. Таким образом, “повезло” номеру 5. Задания решить двумя способами, указанными ниже. В программе вывести номера всех выбывающих элементов и номер дежурного.

Алгоритм 1.Создается массив Х длиной в несколько раз больше чем M. Обозначим его размерность MM (в программе задайте ММ=30). Первые его M элементов заполняются последовательными числами от 1 до M. Остальные элементы от M+1 до MM остаются пока пустыми (=0). Строится FOR-цикл перебора всех элементов X. В нем, если номер элемента I минус 1 кратен N, этот номер (он подчеркнут) печатается и человек выбывает. Если нет, элемент переносится в правый конец занятой части массива Х (в первую свободную клетку). Если встретился элемент =0, значит произошла обработка всех чисел и процесс прекращается. На рисунке показана динамика изменения массива Х. Первоначально в нем заняты только клетки с 1 по 8. Цифры 1,4,7 печатаются, а остальное (2,3,5,6,8) последовательно переносится в свободную область Х, из которой печатаются цифры 3 и 8 и т.д. пока не будут выведены все цифры. После 22-ой ячейки остаются еще MM-22 пустых клеток. Их просматривать не нужно и для этого в цикле должен быть предусмотрен выход при X[i]=0.

 

Х																													дальше нули
																													выбывание
i:	1			4			7				10			13				16					19					22

Алгоритм 2. Возможен и другой алгоритм, заключающийся в том, что, как и в жизни, мы будем ходить по кругу из элементов массива Х размерности M. Каждый раз, когда человек выбывает, мы печатаем его номер и (чтобы не забыть, что он выбыл) заменяем содержимое соответствующей ячейки на 0. Здесь введем переменные: I=1 – номер каждого элемента в круге, J=1 – номер только не удаленного элемента (клетки, содержащие 0 игнорируются), L=0 число уже отобранных клеток.

1). Организуем хождение по кругу. Строим WHILE-цикл в котором переменная I меняется от 1 до M (т.е 1..M, 1..M, и т.д.). В цикле I=I+1 всегда и J=J+1 – только для непустых клеток.

2). Внутри цикла, каждый раз, когда J становится кратным K, ячейка Х(J) печатается и очищается Х[I]=0, L=L+1.

3). Вычисления прекращаются при L=M.

Сортировки в массиве.Сортировка данных является очень распространенной задачей и для нее имеется несколько методов.

Задача 6-3.В векторе X расположить элементы в порядке убывания их зна­че­ний. Алгоритм реализуется при помощи двух вложенных циклов. В наружном цикле последовательно перебираются числа x(i) массива и во внутреннем сравниваются со всеми оставшимися числами x(j) справа от данного. Если выясняется, что какое-то из x(i) меньше сравниваемого, они меняются местами – большее число становится на место меньшего. В программе для наглядности в качестве элементов массива взяты их номера i. Если вектор имеет длину четыре (N=4), будет выполнена следующая последовательность перестановок чисел:1,2,3,4:

при i=1 – 2,1,3,4; 3,1,2,4; 4,1,2,3;при i=2 – 4,2,1,3; 4,3,1,2;при i=3 – 4,3,2,1.

Здесь для обмена значений элементов x[i]↔x[j] вводится специальная “транзитная” переменная М для временного хранения данных. Действительно, если использовать только операторы x[i]:=x[j]; x[j]:=x[i] мы получим неверный результат. Хотя х[i] и примет значение х[j], оператор x[j]:=x[i]ничего не изменит, ведь х[i] теперь равен х[j]. С тем, чтобы не потерять исходное значение х[i], оно запоминается в переменной М.

Задание. Сортировка выбором.Рассмотренный алгоритм очень прост для программирования, но содержит лишние действия. Очевидно, нет необходимости делать обмен элементов всякий раз, когда встретился больший элемент. На самом деле это нужно выполнить только единожды для максимального элемента. Напишите такую программу.

Задание. Сортировка обменом.Метод заключается в анализе соседних элементов массива. Если х[i]<х[i+1] элементы меняются местами. По достижении конца массива в нижней клетке окажется самое маленькое значение. Затем процесс повторяется, но уже без последнего элемента и т.д. Такой просмотр вектора нужно выполнить N раз. Однако его можно сократить, если зафиксировать факт прекращения обменов.

Задание.Пусть имеется таблица работников цеха со столбцами: Имя, Бригада, Отработано дней, Зарплата. Отсортировать любым методом таблицу по возрастанию значений столбца “Отработано дней”.

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

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

Задача 6-4.Заполнить двумерный массив A(N,N) элементами натурального ряда (т.е. числами 1,2,3, и т.д.), начиная с нижнего правого угла в направлении, показанном пунктиром на рис. 6-4а. Чтобы выявить необходимые законы перемещения по матрице, в ее клетках показаны индексы элементов. Способов решения таких такого рода задач может быть несколько. Заметим, что в зависимости от того, с какой стороны матрицы мы находимся, нам необходимо совершать следующие движения:

j если вы находитесь у правой стороны матрицы, типовое движение это вверх на одну клетку и вниз-влево по диагонали до нижней границы;

k если у нижней границы, то влево на одну клетку и вверх-вправо по диагонали до правой границы;

l у верхней границы – влево на одну клетку и вниз-влево до левой границы;

m у левой границы – вверх на одну клетку и вверх-вправо до правой границы.

В любом случае движение прекращается при достижении клетки A(1,1). Результат заполнения массива А показан на рис. 6-4б. Программа приведена ниже. Здесь ST – номер текущей строки (первоначально N, поскольку движение начи­нается с последней ячейки массива A(N,N)), KL – номер текущей колонки (первоначально N), K – растущее значение натурального ряда (первоначально 1). Самый внешний цикл (while k<n*n) ограничивает все действия достижением растущим значением натурального ряда K значения N*N, поскольку именно столько клеток имеется в квадратной матрице размерности N. Внутри цикла организованы четыре разные группы операций в зависимости от того, какое из четырех типовых элементарных действий (см. выше) выполняется. Определяет тип действия оператор if/else if, в котором выясняется, где именно вы находитесь. Внутри каждого IF организован цикл while, в котором осуществляются необходимые перемещения в матрице в соответствии с одним из четырех алгоритмов. По завершении всех действий, т.е. после достижения последней клетки (в нашем случае A(1,1)), выполняется последовательная печать строк матрицы A с заполненными клетками.

program P6-4;

uses crt;

var n,i,j,st,kl,k:integer;

a:array [1..10,1..10] of integer;

begin;

clrscr;

write(‘укажите размерность матрицы (до 10)’); readln(n);

st:=n; kl:=n; k:=1; {текущие строка и колонка, элементы натурального ряда}

a[st,kl]:=k;{начальному элементу a(n,n) присваивается 1}

while k<n*n do begin{конец вычислений по достижении последнего элемента массива}

if (kl=n) and (st>1) then begin st:=st-1; k:=k+1; a[st,kl]:=k; {правая сторона – 1 клетка вверх}

while (st<n) and (kl>0) do begin st:=st+1; kl:=kl-1; k:=k+1; a[st,kl]:=k end; {далее вниз-влево

End

else if (kl>1) and (st=n) then begin kl:=kl-1; k:=k+1; a[st,kl]:=k;{нижняя сторона – 1 клетка влево, }

while (st>1) and (kl<n) do begin st:=st-1; kl:=kl+1; k:=k+1; a[st,kl]:=k end;{далее вверх-вправо}

End

else if (kl>1) and (st=1) then begin kl:=kl-1; k:=k+1; a[st,kl]:=k; {верхняя сторона – 1 клетка влево, }

while (st<n) and (kl>1) do begin st:=st+1; kl:=kl-1; k:=k+1; a[st,kl]:=k end;{далее вниз-влево}

End

else if(kl=1) and (st>1) then begin st:=st-1; k:=k+1; a[st,kl]:=k; {левая сторона – 1 клетка вверх, }

while (st>1) and (kl>0) do begin st:=st-1; kl:=kl+1; k:=k+1; a[st,kl]:=k end;{далее вверх-вправо}

end;

end;

writeln('вывод результата');

for i:=1 to n do begin for j:=1 to n do write(a[i,j]:4); writeln; end;

End.

Задание. Поиск в отсортированном массиве.Очевидно, что найти нужное значение Х можно сплошным перебором данных. Однако в худшем случае (если искомое значение находится внизу или его нет вовсе) нам придется просмотреть все элементы массива. Имеется гораздо более быстрый алгоритм, называемый бинарным поиском. Массив делится пополам и Х сравнивается со средним элементом. Если Х оказался больше, пополам делится нижняя часть, если нет – верхняя и т.д. Напишите программу поиска.