Гладков_Кулютникова Информатика

53 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

Процесс последовательного вычисления значений xk (k = 1, 2, ...) по указанным формулам называется итерационным процессом (процессом последовательных приближений).

Задача. Решить уравнение 3sin x - 0,35x - 3,8 = 0 ; отрезок, на котором существует корень, [2; 3].

Преобразуем уравнение x = 3sin x - 3,8 . 0,35

Var x0, x1, eps: real; begin

write (‘введите начальное приближение’); readln (x0);

write (‘введите абсолютную погрешность’); readln (eps);

x1 := (3*sin(sqrt(x0)) - 3.8)/0.35; while abs(x0 - x1) > eps do begin

x0 := x1;

x1 := 3*sin(sqrt(x0) - 3.8)/0.35

end;

writeln (‘решение уравнения х =’, x0) end.

Метод половинного деления

Пусть дано уравнение f(x) = 0, где функция f непрерывна на отрезке [a, b] и на концах отрезка имеет разные знаки, т.е. f(a)*f(b)<0. Если непрерывная функция на отрезке меняет знак, то она на этом отрезке имеет, по крайней мере, один корень. Пусть [a, b] выделен так, что на нем имеется только один корень уравнения. Найдем этот корень методом половинного деления.

Для этого разделим отрезок [a, b] пополам и присвоим x1 = (a+b)/2. Если f(x) = 0, то х1 - корень уравнения. Если f(x) ¹ 0, то выбираем тот из отрезков [a, x1] или [x1, b], на концах которого f(x) имеет противоположные знаки. Полученный отрезок снова делим пополам и проводим те же рассуждения. Процесс продолжаем до тех пор, пока длина отрезка, на концах которого функция имеет противоположные знаки, не станет меньше заданной точности e. Как только длина отрезка станет меньше e, любую точку отрезка можно с точностью e принять за корень уравнения f(x) = 0.

В программе используется цикл с условием, поскольку есть две причины выхода из цикла: 1). когда f(x) = 0 или f(x) £ e;

2). |x1 - x2| < e.

begin

x1 := a; x2 := b; f := true;

54 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

while f do

if abs (x1 - x2) > eps then begin

y1 := cos(2/x1) - 2*sin(1/x1) + 1/x1; x := (x1 + x2)/2;

y2 := cos(2/x) - 2*sin(1/x) + 1/x; if abs(y2) > eps then

if y1*y2 > 0 then x1 := x else x2 := x

else f := false

end else f := false;

writeln (‘корень уравнения ’,x) end.

Вычисление определенного интеграла методом трапеций

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

b

∫ f (x)dx .

a

Согласно методу трапеций отрезок интегрирования [a, b] разбивается на n равных частей длины h = (b - a)/n. Обозначим точки разбиения x0 = a, x1 = x0 + h, ..., xi = x0 + ih, ... ,

xn = b.

Значения функции f в точках xi обозначим yi, т.е. yi = f(xi). Тогда согласно методу трапеций

x

интервале [1; 4], количество разбиений n = 52.

begin

h := (b-a)/n;

y0 := sqr(ln(a))/a; yn := sqr(ln(b))/b; S := (y0 + yn)/2; for i:= 1 to n-1 do begin

x := a + i*h;

S := S + sqr(ln(x))/x

end; S := S*h;

55 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

writeln (‘интеграл равен ’, S) end.

СЛУЧАЙНЫЕ ЧИСЛА

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

Случайные числа широко используются в задачах, моделирующих жизненные ситуации (игры, эпидемии заболеваний и др.). В Паскале реализован датчик или генератор псевдослучайных чисел. Числа, вырабатываемые при помощи приведенных ниже функций, называют псевдослучайными (“ похожими” на случайные), поскольку это модель случайных чисел, иногда весьма приближенная.

Randomize - инициирует датчик

Random - генерирует случайные действительные числа из диапазона [0; 1) Random (x) - генерирует случайные целые числа из диапазона [0; х).

Метод Монте-Карло (метод статистических испытаний)

Случайные числа широко используются для приближенного вычисления площади с помощью метода Монте-Карло. Суть метода очень проста. Пусть есть некоторая фигура, площадь которой необходимо вычислить. Размещаем эту фигуру внутри стандартного квадрата со сторонами, параллельными осям. Пусть про любую точку квадрата можно узнать попадает ли эта точка внутрь фигуры или нет. Тогда площадь может быть вычислена следующим образом: поделив количество точек, попавших внутрь фигуры, на количество всех точек, попавших в квадрат, можно узнать, какую часть площади квадрата занимает фигура, умножив это отношение на площадь квадрата, получим площадь фигуры. Ясно, что число точек, попавших внутрь фигуры, тем больше, чем больше фигура, а точность решения будет пропорциональна количеству точек в квадрате. Пара случайных чисел в этом методе может быть рассмотрена как координаты точки на плоскости.

Задача. Определите площадь круга с радиусом R=1.

Решение. Поместим этот круг в квадрат со стороной а = 2. Точка принадлежит квадрату, если - 1 ≤ х ≤ 1 и -1 ≤ y ≤ 1. Ecли x2 + y2 ≤ 1, то точка попадает внутрь круга.

writeln (‘Задайте количество точек’); readln (n);

56 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

Randomize; m := 0;

for i := 1 to n do begin

x := 2 * random - 1; y := 2 * random - 1; if sqr (x) + sqr (y) <= 1 then m := m + 1; end;

writeln (‘Площадь круга равна ’, 4 * m/n); end.

Упражнения.

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

2.Напишите программу, моделирующую розыгрыш тиража “ Спортлото”. Из 49 различных шаров должно выбираться случайным образом 6 шаров. Каждый номер в тираже встречается один раз, т.к. вынутый шар обратно не возвращается, т.е. программа должна генерировать 6 различных случайных чисел из диапазона от 1 до 49 и выводить их на экран.

3.Внесите изменения в программу из упражнения 2, чтобы программа моделировала розыгрыш тиража “ Спортлото” 6 из 45 или 5 из 36.

4.Напишите программу моделирования гадания на ромашке.

МАССИВЫ

Одномерные массивы

Если необходимо при решении задачи использовать большое количество данных одного типа, то обозначать их различными именами и обрабатывать становится затруднительно. В предыдущем разделе был показан прием, позволяющий вводить большое количество однородных данных, используя одну переменную. К сожалению, этот способ имеет существенный недостаток: сохраняется только последнее введенное значение, что не позволяет повторно обратиться к введенным данным. Например, задача нахождения количества элементов в заданной последовательности чисел, равных последнему элементу, предполагает просмотр элементов последовательности два раза: первый - при вводе элементов и получении значения последнего элемента и второй - при поиске количества элементов, совпадающих с последним. Логично ввести для всей последовательности одно обобщающее имя, а индексом (или номером) отметить то число, которое нас интересует. Этот прием часто используется и в обыденной жизни. Например, книги на книжной полке. Можно попросить ребенка, не умеющего читать, принести третью книгу с полки. И однозначно получим то, что хотели. Таким образом, в данном случае обобщающим именем служит “ полка”, а индексом - порядковый номер книги на полке. Другой пример: можно не знать имени зрителя в концертном зале, но однозначно его определить, указав номер ряда и место в ряду, которое занимает зритель.

Такие данные описываются при помощи структурированного типа данных, который называется массивом.

Массив - упорядоченная совокупность данных, имеющая одно имя. Каждому элементу массива соответствует выражение порядкового типа (чаще целое число), определяющее место этого элемента в массиве, которое называется индексом. Если для определения места элемента используется один индекс, такой массив называют

59 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

for i:=1 to n div 2 do {используется формула четного числа. Поскольку} {обработка a[2*i]}; {элементов с четным индексом - половина от }

{количества, то переменная цикла i изменяется до}

{ n div 2 }

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

а) нечетные элементы массива, двигаясь от начала массива; б) нечетные элементы, двигаясь от конца массива к его началу;

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

шагом) схемы перебора элементов массива.

Пример. Организуйте перебор элементов массива, индексы которого являются степенями двойки, т.е. 1, 2, 4, 8, 16 и т.д. Предлагается следующее решение этой задачи:

i:=1;

while i<=n do

begin {обработка a[i]}; i:=i*2

end;

Упражнение. Организуйте перебор элементов массива, индексы которого являются:

*полными квадратами, т.е. 1, 4, 9, 16, 25,...;

*числами Фибоначчи, т.е. 1, 2, 3, 5, 8, 13,...

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

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

Решение. Необходимо вспомнить, что простыми называются числа, которые делятся на 1 и на само себя. Организуем внешний цикл, который будет перебирать все индексы массива, а внутренний цикл будет определять, является ли этот индекс простым числом. Для этого будем рассматривать все возможные делители для индекса i из интервала [2; i] (поскольку на 1 делятся все числа) до тех пор, пока индекс не разделится нацело на очередной делитель. Если при этом делитель и i совпадут, следовательно, i - простое число, иначе - нет.

for i := 1 to n do begin

j := 1; {j - делитель} repeat

j := j + 1;

until i mod j = 0;

if i = j then {обработка a[i]}; end;

Перебор подмассивов

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

60 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

необходимости вводить такое количество индексов, каково количество обрабатываемых подмассивов. Рассмотрим примеры.

Пример 1. Для каждого элемента массива просмотрите все его последующие элементы. Здесь возможно несколько вариантов.

Вариант 1. Массив просматривается по одному элементу слева направо. Подмассив просматриваем по одному тоже слева направо.

Обозначим i - индекс массива, а j - индекс подмассива, тогда схема может быть такой:

Вариант 2. Подмассив просматриваем справа налево. for i:=1 to n-1 do

begin j:=n; while j>i do

begin {обработка a[j]}; j:=j-1

end;

end;

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

Пример 2. Для каждого элемента просмотрите все ему предшествующие. Пусть также i - индекс массива, а j - индекс подмассива.

Вариант 1. Основной массив просматривается слева направо, подмассив просматривается также слева направо.

Вариант 2. Основной массив просматривается слева направо, а подмассив - справа налево.

for i:=2 to n do begin j:=i-1;

while j>0 do

begin {обработка a[j]}; j:=j-1

end;

end;

Вариант 3. Основной массив просматривается справа налево, а подмассив - слева направо.

i:=n;

while i>1 do

begin for j:=1 to i-1 do {обработка a[j]}; i:=i-1

end;

Вариант 4. Основной массив просматривается справа налево и подмассив - справа налево.

i:=n;

while i>1 do begin j:=i-1;

while j>0 do

begin {обработка a[j]};

61 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

j:=j-1 end; i:=i-1

end;

КЛАССЫ ЗАДАЧ ПО ОБРАБОТКЕ МАССИВОВ

Перечисленные ниже классы задач относятся как к одномерным, так и к двумерным массивам.

Классы задач:

1)однотипная обработка всех или указанных элементов массива;

2)задачи, в результате решений которых изменяется структура (порядок следования элементов) массива;

3)обработка нескольких массивов одновременно. Сюда же относятся задачи, когда по-разному обрабатываются подмассивы одного и того же массива;

4)поисковые задачи для массивов.

Задачи первого класса

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

Пример 1. Найдите среднее арифметическое элементов массива.

Решение. Задача сводится к отысканию суммы, для чего вводится дополнительная переменная S, в которой накапливается сумма путем прибавления очередного элемента массива, т.е. S := S + a[i]. При этом можно использовать любую линейную схему перебора с единичным шагом. После нахождения суммы необходимо ее поделить на количество элементов, получим среднее арифметическое.

const nn = 30;

var a: array [1..nn] of integer; i, n, S: integer;

begin

write (‘задайте количество элементов массива’); readln (n);

for i := 1 to n do read (a[i]);

S := 0;

for i := 1 to n do S := S + a[i];

write (‘среднее арифметическое равно ’, S/n)

end.

Пример 2. Определите количество четных элементов массива с нечетными порядковыми номерами.

Решение. Сначала надо определить условие, по которому будут отбираться элементы массива. Это должны быть четные элементы (делятся на 2 без остатка) a[i] mod 2 = 0 и имеющие нечетные порядковые номера (номер элемента совпадает с его индексом) i mod 2<>0. Поскольку нас интересуют элементы, удовлетворяющие обоим условиям, соединены эти условия будут оператором and. Выполнение этого условия должно проверяться для всех элементов массива, т.е. используется любая из схем перебора по одному, и в случае выполнения условия счетчик элементов должен увеличиваться на 1.

const nn = 30;

62 Гладков В.П., Кулютникова Е.А. Пособие по информатике для самообразования.

var a: array [1..nn] of integer;

i, n, S: integer; {S - счетчик элементов} begin

write (‘задайте количество элементов массива’); readln (n);

for i := 1 to n do read (a[i]);

S := 0;

for i := 1 to n do

if (a[i] mod 2 = 0) and (i mod 2 <> 0) then S := S +1; writeln (‘S= ‘, S)

end.

Пример 3. Найдите максимальный (минимальный) элемент массива.

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

const n = 30;

var a: array [1..n] of integer; i, max: integer;

begin

for i := 1 to n do read (a[i]);

max := a[1];

for i := 2 to n do

if a[i] > max then max := a[i];

writeln (‘максимальный элемент массива равен ’, max)

end.

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

const n = 30;

var a: array [1..n] of integer; i, imax: integer;

begin

for i := 1 to n do read (a[i]); imax := 1;

for i := 2 to n do

if a[i] > a[imax] then imax := i;

writeln (i:2,‘ыйэлемент массива - максимальный, его величина равна ’, a[imax]);

end.

Упражнения.

1. Установите, какую задачу решает приведенный ниже фрагмент программы. Перепишите его с использованием оператора while.

s := 1; max := a[1]; for i := n downto 2 do

if max < a[i]