Алгоритмы и их свойства (стр. 11 )

Program iterac_2;

uses crt;

label met;

var n, c,s: integer;

Begin

clrscr;

met: write(‘Введите натуральное число’); readln(n);

write(‘Сумма цифр числа’,N,’равна ‘);

if n<10 then goto met; {число должно быть хотя бы двузначным}

while n>=1 do

begin

c:=n mod 10; {получаем очередную цифру}

n:=n div 10; {отбрасываем последнюю цифру в числе}

s:=s+c;

end;

writeln(S);

End.

Пример 3. Вычисление квадратного корня из числа без использования функции SQR.

Значение функции можно вычислить, используя реккурентную формулу:

, т. е. значение очередного члена последовательности зависит от предыдущего.

Реализация данной формулы предполагает построение последовательности приближений к : y0, y1, y2, ..., yn, ..., например

Вычислим

. . .

Таким образом, чем больше будет вычислено членов последовательности, тем точнее будет вычислен корень. В этом случае говорят о вычислении с заданной степенью точности Е. Заданная степень точности считается достигнутой, если модуль разности между соседними членами последовательности y0, y1, y2, ..., yn, стал меньше или равен Е.

Степень точности задается достаточно малым числом (0.01, 0.001, 0.0001, …); количество цифр после десятичной точки определяет число точных цифр результата.

Обозначим предыдущий член последовательности (предыдущее приближение к У) через z, а последующий - через у. Разность между соседними приближениями обозначим delta. В качестве начального значения delta выбирается число, заведомо большее, чем возможная степень точности ответа.

Program iterac_3;

uses crt;

var x, y,e, z,delta: real;

Begin

clrscr;

write(‘Корень какого числа будем вычислять’); readln(х);

write(‘Какова степень точности’); readln(e);

z:=(x+1)/2;

delta:=100;

repeat

y:=0.5*(z+x/z);

delta:=abs(y-z);

z:=y;

until delta < e;

write(‘Квадратный корень из числа’,x:4:2);

writeln(‘равен ‘,y:7:4);

End.

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

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

Вопросы

Какой цикл называется циклом с условием? От чего зависит выполнение цикла с условием? Какие виды циклов с условием существуют? Как записывается и как работает цикл с предусловием? Как записывается и как работает цикл с постусловием? В чем отличие использования служебных слов while и until? Что может входить в тело цикла с условием? Приведите примеры реализации итерационного цикла. В каком из видов циклов с условием нет необходимости использования составного оператора? Можно ли для реализации цикла с параметром воспользоваться циклом с условием?

Задания

1. Что будет выведено на экран после выполнения фрагментов программ (составить трассировочную таблицу):

а) b:= 0; a:= 1; while a < 10 do begin b:= b + 2; a:= a + 1; end; write(b);	б) y:= 0; x:= 3; while x<=15 do begin y:= y + x; x:= x + 3; writeln(y); end;	в) n:= 0; m:= 20; repeat n:= n + m; m:= m – 2; until m = 0; write(n);	г) b:= 0; a:= 5; repeat b:= b + 10; a:= a + 1; until a=5; write(b);
д) x:=12; while x <= 4 do begin writeln(2*x, x); x:= x – 2; end;	е) p:=1; i:= 1; repeat p:= p*i; i:= i + 1; writeln(p); until i > 5;	ж) s:= 0; i:=1; while i < 25 do begin if i mod 5 = 0 then s:= s + i; i:= i + 1; end; write(s);	з) i:= 2; repeat for j = 1 to 9 writeln(i,’*’,j,’=’,i*j); i:= i + 1; until i > 3;

2. По блок-схемам составить программы

а)

б)

в)

3. По программам примеров 1 – 3 составить блок-схемы.

4. Составить план решения задач с помощью компьютера.

1) Дано натуральное число n. Среди чисел 1, 4, 9, 16, 25, …

а) найти количество четных чисел от 1 до 2n;

б) найти сумму квадратов нечетных чисел от 1 до n+15;

в) найти те, которые не превышают n;

г) найти первое число, большее n.

2) Дано число а (1 < а < 1.5). Из чисел 1+1/2, 1+1/3, …

а) найти те, которые не меньше а;

б) найти первое, меньшее а.

3) Найти количество и сумму чисел вида , которые не меньше заданного числа k.

4) Найти количество и сумму чисел вида , не превосходящих заданного натурального числа k.

5) Дано вещественное число а. Найти такое наименьшее число n, при котором

6) Дано вещественное число а. Найти количество и сумму слагаемых, при котором .

7) Дано натуральное число n. Вывести на экран все его цифры.

8) Дано натуральное число n. Определить количество четных цифр в нем.

9) Дано натуральное число n. Выяснить, является ли оно палиндромом (читается одинаково слева направо и справа налево).

10) Дано натуральное число n. Определить максимальную и минимальную цифру в нем.

11) Найти приближенное значение корня уравнения f(x)=0 на отрезке [a, b], используя метод половинного деления

л1) x4 + 2x3 – x – 1 = 0; a=0, b=1.

л2) x3 – 0.2x2 – 0.2x – 1.2 = 0; a=1, b=1.5

12) Последовательность Фибоначчи образуется так: первые два члена равны 1, каждый следующий равен сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, … Найти:

а) количество чисел последовательности, которые не превосходят данного натурального числа n (n>1000);

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

13) Дана непустая последовательность натуральных чисел, оканчивающаяся 0. Найти в ней:

а) количество нечетных чисел;

б) сумму единичных элементов;

в) количество пар соседних элементов, равных между собой;

г) самую длинную возрастающую подпоследовательность.

14) Даны два натуральных числа a и b (a < b), обозначающие числитель и знаменатель дроби. Сократить дробь, т. е. найти такие натуральные числа p и q, не имеющие общих делителей, что , например .

§8. Массивы

Решение многих задач на ЭВМ связано с обработкой большого количества числовых и символьных данных. Рассмотрим пример. «Участников спортивного соревнования оценивают 12 судей. По каждому участнику нужно:

вывести сводный лист всех оценок; вывести средний балл выступающего; определить его максимальный и минимальный балл; определить сколько судей поставили оценку выше 4; упорядочить оценки участника по возрастанию».

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

Массив – совокупность однотипных данных, объединенных одним именем, каждое из которых имеет порядковый номер.

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

Мы будем рассматривать два основных вида массивов:

одномерные (линейные таблицы) двумерные (прямоугольные таблицы)

Примеры:

Одномерный Массив Х из 10 элементов х1, х2, х3, х4 ..., х10 Массив A из 50 элементов a1, a2, a3, a4 ..., a50.	Двумерный Массив 3 х 4 Массив 4 х 4
x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34	a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44

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