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

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

Нахождение суммы

Задача 1. Пусть требуется вычислить сумму первых n натуральных чисел, т.е.

n

S = ∑i . Задача сводится к организации арифметического цикла по i. Переменная цикла i

i =1

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

Исходные данные: n - количество слагаемых (или значение последнего слагаемого). В цикле будет повторяться одно и то же действие: к предыдущему значению суммы прибавить очередное значение i (очередное слагаемое). Перед началом цикла необходимо обнулять значение переменной, в которой будет накапливаться сумма.

var S, i, n: integer;	{S - сумма, i - слагаемое ,
	n - количество слагаемых}

begin

writeln (‘задайте количество слагаемых’); readln (n);

S := 0;

for i := 1 to n do S := S + i;

writeln (‘cумма равна ‘, S)

end.

Эту же программу можно написать, используя операторы while и repeat.

var S, i, n: integer; begin

readln (n); S := 0;

i := 1;

while i <= n do begin S := S + i;

i := i + 1 end;

writeln (‘сумма равна’, S) end.

var S, i, n: integer; begin

readln (n); S := 0;

i := 1; repeat

S := S + i; i := i + 1 until i > n;

writeln (‘сумма равна’, S) end.

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

Контрольный вопрос. Можно ли задачу, написанную с использованием операторов while или repeat, представить оператором for?

Задача 2. Найдите сумму n произвольных действительных чисел.

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

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

var i, n: integer; {n - количество слагаемых, i - номер очередного слагаемого}

S, a: real; {S - сумма, a - значение очередного слагаемого} begin

writeln (‘задайте количество слагаемых’); readln (n); S := 0;

for i := 1 to n do

begin write (‘введите очередное слагаемое’); readln (a);

S := S + a

end;

writeln (‘сумма =’, S)

end.

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

var S, a: real; i: integer;

begin

S := 0; i := 1;

writeln (‘введите первое слагаемое’); readln (a);

while a <> 0 do begin S := S + a;

i := i + 1;

write (‘введите’, i:2, ’-ое слагаемое’); readln (a)

end;

writeln (‘сумма равна’, S)

end.

Циклическую часть можно оформить с помощью оператора repeat следующим образом:

i := 0; repeat

i := i + 1;

write (‘введите’, i:2, ’-ое слагаемое’); readln (a);

S := S + a;

until a = 0;

Задача 4. Напишите программу вычисления суммы при заданном x:

y = x + x		2	+ x		3	+... = ∑ x		i
								.
						n
2			3			i =1 i

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

Для данной суммы найдем рекуррентную зависимость i-го элемента от (i-1)-го.

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

	ai	= ai −1	× r r =				ai	=		xi × (i - 1)
							ai −1			i × xi −1
			ai	= ai −1	×	x × (i - 1)			.
							i

var y, x, ai: real; n, i : integer;

begin

read (x, n); ai := x; y := 0;

for i := 2 to n+1 do begin y := y + ai;

ai := ai * x * (i-1)/i

end;

writeln (‘y =‘, y);

end.

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

const eps = 0.001; var y, x, ai: real;

n, i: integer;

begin

read (x, n);

ai := x; y := 0; i := 1; while abs (ai) >= eps do begin y := y + ai;

i := i + 1;

ai := ai * x * (i-1)/i

end;

writeln (‘y =‘, y); end.

Задача 5. Найдите знакочередующуюся сумму: S =1 −2 + 3 −4 +...+ n . Всего в

этой сумме n слагаемых.

Нетрудно заметить, что нечетные элементы прибавляются, а четные - вычитаются. Вариант 1. Будем отдельно вычислять сумму нечетных элементов и сумму четных

элементов, а затем найдем их разность.

var i, n: integer;	{i - значение очередного слагаемого:
	n - количество слагаемых}
S1, S2: integer;	{S1 - сумма нечетных элементов;
	S2 - сумма четных элементов}

begin

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

S1 := 0; S2 := 0; i := 1;

while i <= n do

begin S1 := S1 + i; i := i +2

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

end; i := 2;

while i <= n do

begin S2 := S2 + i; i := i +2

end;

writeln (‘сумма равна’, S1 - S2)

end.

Вариант 2. При вычислении суммы проверять: если элемент четный, то вычитать его из суммы, иначе - прибавлять.

var	i, n: integer;	{i - значение очередного слагаемого:
		n - количество слагаемых}
begin	S: integer;	{S - сумма}
write (‘задайте количество слагаемых’);
readln (n);
S := 0;
for i := 1 to n do
if i mod 2 = 0 then S := S - i
else S := S + i;
writeln (‘сумма равна ’, S)
end.		следующей суммы S =1 −2 + 3 +4 −5 + 6 + 7 −
При	вычислении		можно

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

S := 0;

for i := 1 to n do

if i mod 3 = 2 then S := S - i

else S := S + i;

Таким образом, можно сделать вывод, что j-ый элемент в группе из k элементов может быть определен следующим образом: i mod k = j.

Упражнения.

1.Найдите сумму: S =15 +17 −19 + 21 + 23 − 25 + 27+... , где всего n слагаемых.

2.Вычислите:

а).

y = sin(1) − cos(sin(22 ))+ sin(cos(sin(33 )))+ cos(sin(cos(sin(44 ))))− sin(cos(sin(cos(sin(55 )))))+L

Всего n слагаемых.

б). y = sin(1 + cos(2 − sin(3 +cos(4 + sin(5 − cos(6+...)...))))). Всего n вложений

функций.

3. Восстановите формулу, которая вычисляется программой:

а). S := 1;	б). S := 2;
for i := 1 to n do	for i := 1 to n do
if i mod 2 = 0 then S := S/sin(S)	if i mod 3 <> 0 then S := i/sin(S)
else S := S/cos(S);	else S := cos(S)/i;

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

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

Задача 6. Определите количество элементов в заданной последовательности вещественных чисел, которые являются четными, но имеют нечетные порядковые номера.

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

var x : real;	{значение очередного элемента}
i, n, k: integer;	{i - номер очередного числа,
	n - количество элементов,
	k - счетчик}

begin

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

k := 0;

for i := 1 to n do

begin write (‘введите очередное число’); readln (x);

if (x mod 2 = 0) and (i mod 2 <> 0) then k := k + 1

end;

writeln (‘количество элементов ’, k)

end.

Задача 7. Найдите максимальный элемент в заданной последовательности целых чисел.

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

var x : integer; {значение очередного элемента} i, n, max: integer; {i - номер очередного числа,

n - количество элементов, max - кандидат на максимум}

begin

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

writeln (‘введите первое целое число’);

readln (max); {первое число - кандидат на максимум} for i := 2 to n do

begin write (‘введите’, i:2, ‘число’); readln (x);

if x > max then max := x;

end;

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

end.

Задача 8. Найдите номер максимального элемента в данной последовательности. Необходимо ввести дополнительную переменную, которая будет хранить

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

var x :	integer;		{значение очередного элемента}
i, n, max, imax:		integer;		{i - номер очередного числа,
				n - количество элементов,

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

	max - кандидат на максимум
	imax - номер кандидата}
begin
writeln (‘Задайте количество элементов’);
writeln (n);
writeln (‘введите первое целое число’);
readln (max);	{первое число - кандидат на максимум}
imax := 1;
for i := 2 to n do
begin write (‘введите’, i:2, ‘число’);
readln (x);
if x > max then	begin max := x; imax := i end;

end;

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

end.

Задача 9. Дана последовательность чисел, в которой есть одинаковые числа. Найдите количество максимальных элементов.

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

var x :	integer;	{значение очередного элемента}
i, n, max, Smax:	integer;	{i - номер очередного числа,
		n - количество элементов,
		max - кандидат на максимум
		Smax - количество максимальных
		элементов}
begin
writeln (‘Задайте количество элементов’);
writeln (n);
writeln (‘введите первое целое число’);
readln (max);	{первое число - кандидат на максимум}
Smax := 1;
for i := 2 to n do
begin write (‘введите’, i:2, ‘число’);
readln (x);
if x > max then	begin max := x; Smax := 1 end;

if x = max then Smax := Smax +1

end;

writeln (‘количество максимальных элементов равно ‘, Smax)

end.

Задача 10. В 1228 году итальнский математик Фибоначчи сформулировал интересную задачу: “ Некто поместил пару кроликов в некоем месте, огороженном со всех сторон стеной, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова, что через месяц пара кроликов производит на свет другую пару, а рождают кролики со второго месяца после своего рождения”.

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

a := 1; b := 1; for i := 3 to n do begin

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

иметь 2 и 3, а для определения 8 – уже 3 и 5, т.е. ноебходимо осуществлять сдвиг по вычисленным значениям.

{программа определяет n-ое число Фибоначчи}

var a, b, c: integer; {a - предпредыдущее, b - предыдущее, c - текущее} i, n: integer;

begin

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

if (n = 1) or (n = 2) then writeln (n:2, ‘оечисло Фибоначчи равно 1’) else

begin

c := a + b;

a := b; b := c

end;

writeln (n:2, ‘оечисло Фибоначчи равно ’, c)

end;

end.

Упражнение. Измените программу таким образом, чтобы она определяла сумму всех чисел Фибоначчи, не превосходящих заданного N.

Особый интерес представляют поисковые задачи. Такая задача может быть сформулирована следующим образом.

Задача 11. Найдите первый элемент в заданной последовательности, совпадающий с заданным.

Особенностью задач такого типа являются две причины выхода из цикла: 1) найден заданный элемент, необходимо прекратить поиск, 2) элемент не найден, но закончилась заданная последовательность чисел. Реализуются такие задачи с использованием логической переменной, которая меняет свое значение, если найден искомый элемент.

var a, x: integer; {a - очередное число, x - искомый элемент} i, n: integer;

t: boolean;

begin

write (‘Задайте количество чисел в последовательности’);

readln (n);
write (‘искомый элемент’);
readln (x);
t := false;		{искомый элемент не найден}
i := 1;
while (i <= n) and not t do		{пока есть элементы и не найдено}
begin	write (‘введите число из последовательности’);
	readln (a);
	if a = x then t := true		{нашли элемент}
	else i := i +1;		{переход к следующему}
end;

if t then writeln (‘Нашли элемент с номером’, i) else writeln (‘Такого элемента нет’);

end.

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

Упражнения.

1.Напишите программу, проверяющую является ли заданная последовательность вещественных чисел неубывающей. Примечание. Две причины выхода из цикла: 1) - нарушение условия не убывания и 2) просмотрены все элементы. Необходимо использовать логическую переменную. Кроме того, обработка идет по два элемента, а ввод - поэлементно, поэтому необходима дополнительная переменная, хранящая предыдущее число.

2.Найдите первую пару элементов в заданной последовательности вещественных чисел, которые принадлежат интервалу [a, b] и первые две цифры дробной части которых равны.

Вложенные циклы

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

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

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

Задача 12. Даны натуральные числа a и b (a < b). Получите все простые числа p, удовлетворяющие неравенству a ≤ p ≤ b.

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

var a, b, p, i: integer;	{a, b - границы диапазона
	p - проверяемое число}
begin
write (‘задайте границы диапазона’);
readln (a, b);
for p := a to b do	{перебор целых чисел из указанного диапазона}
begin i := 1;
repeat
i := i +1;	{перебор делителей}
until p mod i = 0;
if i = p then writeln (p, ‘ ’); проверяется{		, является ли число простым}
end;
end.

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

Упражнение. Даны вещественные числа a и b (a < b). Получите все целые числа р, удовлетворяющие неравенству a ≤ p ≤ b, сумма цифр которых является четным числом.

Переборный метод решения задач

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

Задача 13. Эта задача была сформулирована поэтом Антанасом Баранаускасом, который интересовался теорией чисел. Это любимая задача его детства, над которой он бился две недели: сколько можно купить быков, коров и телят, платя за быка 10 руб., за корову - 5 руб., а за теленка - полтинник, если на 100 рублей надо купить 100 голов скота?

Решение. Условие этой задачи можно представить в виде системы:

10b + 5k + 0.5t = 100	20b +10k + t = 200
	или после преобразования	,
b + k + t = 100	b + k + t	= 100

где b - количество быков, k - количество коров, t - количество телят. Необходимо организовать три цикла для перебора всех возможных значений количества быков, коров и телят. Причем, можно заметить, что на 100 рублей можно купить не более 10 быков, 20 коров и 200 телят.

var a, b, c: integer; begin

for b := 0 to 10 do for k := 0 to 20 do

for t := 0 to 200 do

if (20*b + 10*k + t = 200) and (b + k + t = 100)

then writeln (‘на 100 рублей можно купить’,b,‘быков’,k,‘коров’,t, ‘телят’);

end.

Попытайтесь уменьшить количество циклов для решения данной задачи. Задача 14. Найдите все трехзначные числа, сумма цифр которых кратна 3.

Решение. Задача решается путем перебора всех трехзначных чисел. Причем перебор чисел можно организовать по-разному: 1) перебирать трехзначные числа, выделять цифры из числа и находить сумму цифр ; 2) организовать три цикла для перебора цифр сотен, десятков и единиц и находить сумму этих цифр.

Вариант 1.

var i : integer; begin

for i := 100 to 999 do {перебор всех трехзначных чисел} if (i div 100 + i div 10 mod 10 + i mod 10) mod 3 = 0

then write (i, ‘ ’);

end.
Вариант 2.
var i, j, k : integer;
begin	{перебор цифр сотен}
for i := 1 to 9 do

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

for j := 0 to 9 do	{перебор цифр десятков}
for k := 0 to 9 do	{перебор единиц}

if (i + j + k) mod 3 = 0 then write (i*100 + j*10 + k, ‘ ‘);

end.

Упражнения.

Напишите программу для решения следующих задач.

1.Сегодня утром я видел в парке людей, собак и кошек. Собак было больше, чем людей. У собак и людей вместе было 100 голов и ног. А собак и людей вместе было втрое больше, чем кошек. Сколько я видел кошек? (Ответ - 8 кошек).

2.Джон Смит сообщил своей семье, что отныне каждый месяц им следует экономить вдвое больше, чем в предыдущем месяце. Они сэкономят 1 доллар в первый месяц, 2 доллара во второй месяц, 4 доллара в третий месяц и т.д. Сколько они сэкономят за год? Через сколько месяцев сумма сэкономленных долларов превысит 10000 долларов?

3.Преподаватели Калифорнийского университета удивлялись на своего нового коллегу. Когда ему сказали, что его месячный оклад составит сумму **** и через 6 месяцев будет повышен до 3 тысяч долларов, он ответил: “ Какое чудесное число! Если разделить его на 10, то остаток будет равен 9, если разделить на 9, то остаток будет 8 и т.д.

Вконце концов остаток будет 1, когда мы разделим эту сумму на 2. Каков был первоначальный оклад нового преподавателя? (Ответ - 2519 долларов).

4.Найдите все натуральные пятизначные числа вида 67m1n (m и n-цифры), которые делятся на 36. Для представления натуральных чисел разрешается использовать короткие целые, меньшие или равные 32767. (Ответ - 67212 и 67716).

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

ЧИСЛЕННЫЕ МЕТОДЫ

Решение конкретных задач часто сводится к нахождению корней уравнения вида

f(x) = 0,

где функция f(x) определена и непрерывна на некотором интервале.

Если f(x) - многочлен, то уравнение называют алгебраическим, если же в f(x) входят тригонометрические, логарифмические, показательные функции, то такое уравнение называют трансцендентное.

Всякое значение х* такое, что f(x*) = 0 называется корнем уравнения, а нахождение этого значения - решение уравнения.

Решение уравнения разбивается на два этапа:

1.отделение корней, т.е. отыскание достаточно малых областей, в каждой из которых заключен один и только один корень уравнения;

2.вычисление выделенного корня с заданной точностью.

Для вычисления выделенного корня существует множество методов. В этом пособии будут рассмотрены методы итераций и половинного деления.

Метод итераций

Уравнение f(x) необходимо представить в виде x = ϕ (x). Выберем теперь на участке [a, b] (участок, в котором находится корень уравнения) произвольную точку x0 и последовательно будем вычислять:

x1 =ϕ (x0), x2 = ϕ (x1), ... , xk = ϕ (xk-1).

Обычно в качестве x0 выбирают левую границу интервала [a, b].