Книга является наиболее полным руководством по разработке эффективных ал

Глава 1. Введение в разработку алгоритмов 
47 
for i from n to 1 
for j from 1 to i – 1 
if (A[j]>A[j+1] 
меняем местами значения A[j] и A[j + 1] 
Математическая индукция 
Для доказательства пользуйтесь методом математической индукции. 
10.
[3] Докажите, что 
1
(
1) / 2
n
i
i n n
=
=
+
∑
для 
n
≥
0. 
11.
[3] Докажите, что 
2
1
(
1)(2
1) / 6
n
i
i
n n
n
=
=
+
+
∑
для 
n
≥
0. 
12.
[3] Докажите, что 
3
2
2
1
(
1) / 4
n
i
i
n n
=
=
+
∑
для 
n
≥
0. 
13.
[3] Докажите, что 
1
( 1)( 2)
(
1)(
2)(
3) / 4
n
i
i i
i
n n
n
n
=
+
+ =
+
+
+
∑
. 
14.
[5] Докажите, что 
1
0
1
1
n
n
i
i
a
a
a
+
=
−
=
−
∑
для 
n
≥
1, 
a
≠
1. 
15.
[3] Докажите, что 
1
1
( 1)
1
n
i
n
i i
n
=
=
+
+
∑
для 
n
≥
0. 
16.
[3] Докажите, что 
n
3
+ 2
n
делится на 3 для 
n
≥
0. 
17.
[3] Докажите, что дерево с 
n
вершинами имеет в точности 
n – 
1 ребер. 
18.
[3] Докажите, что сумма кубов первых 
n
положительных целых чисел равна квадрату 
суммы этих целых чисел, т. е., 
3
2
1
1
(
)
n
n
i
i
i
i
=
=
=
∑
∑
Приблизительные подсчеты 
19.
[3] Содержат ли все ваши книги, по крайней мере, миллион страниц? Каково общее ко-
личество страниц всех книг в вашей институтской библиотеке? 
20.
[3] Сколько слов содержит эта книга? 
21.
[3] Сколько часов составляет один миллион секунд? А сколько дней? Выполните все 
необходимые вычисления в уме. 
22.
[3] Сколько городов и поселков в Соединенных Штатах? 
23.
[3] Сколько кубических километров воды изливается из устья Миссисипи каждый день? 
Не пользуйтесь никакой справочной информацией. Опишите все предположения, сде-
ланные вами для получения ответа. 
24.
[3] В каких единицах измеряется время доступа к жесткому диску, в миллисекундах 
(тысячных долях секунды) или микросекундах (миллионных долях секунды)? Сколько 
времени занимает доступ к слову в оперативной памяти вашего компьютера, больше 
или меньше микросекунды? Сколько инструкций может выполнить центральный про-

---

48