Вы - -й посетитель этой странички
Основы программирования
С.М. Окулов,
г. Киров
Продолжение. См. № 42, 43, 44, 45, 46, 47, 48/2000; 6, 7, 8/2001
Занятие 11. Процедуры
План занятия
· структура
программы;
· вызов
процедур, передача данных;
· глобальные
и локальные переменные, формальные и фактические параметры процедур;
· экспериментальная
работа с программами перестановки значений переменных
a, b, c в
порядке возрастания; вычисления значения
выражения
y = an • xn + an—1
• xn—1 + … + a2 • x2
+ a1 • x1 + a0 ; формирования значений элементов
одномерного массива с помощью датчика случайных чисел; поиска
элементов, принадлежащих двум массивам одновременно; перестановки
частей массива;
· выполнение
самостоятельной работы.
Структура программы
Программа на языке Турбо Паскаль состоит из заголовка, раздела описаний и тела программы. Раздел описаний может включать разделы описания меток, констант, типов, переменных, процедур и функций. Последовательность упомянутых разделов описаний может быть произвольной, но естественно, что если вводится переменная нового типа, заданного в разделе описания типов Type, то данный раздел Type должен предшествовать разделу описания переменных Var. Принцип то, что используется, должно быть описано справедлив и для раздела описаний.
Program имя
программы;
Label <метки>;
Const <описание
констант>;
Type <описание
типов данных>;
Var <описание
переменных>;
<процедуры и функции>;
Begin
<тело программы>
End.
Примечание. В наших программах мы постараемся метки не использовать.
На предыдущих занятиях мы познакомились с тем, как описываются переменные и типы. На этом занятии мы начнем изучать процедуры. Структура процедуры похожа на структуру программы. Отличия выделены жирным шрифтом.
Procedure имя
процедуры (<параметры>);
Label <метки>;
Const <описание констант>;
Type <описание
типов данных>;
Var <описание
переменных>;
<вложенные
процедуры и функции>;
Begin
<основное
тело процедуры>
End;
Вызов процедур
Чтобы объяснение было наглядным, обратимся к примеру, приведенному на рисунке.
Приведен фрагмент текста программы, в
котором вызывается процедура вычисления суммы
двух целых чисел. Процедура вызывается по имени. При
вызове процедуры управление передается на
соответствующий участок программного кода. После
выполнения процедуры осуществляется возврат на оператор
основной программы, следующий за вызовом процедуры. Мы
не рассматриваем вопрос, как это осуществляется.
Например,
как происходит возврат на оператор WriteLn(c).
При вызове процедуры в нее могут передаваться
данные. В нашем примере в процедуру
Sum передаются
переменные a, b, c.
Процедура имеет три параметра
x, y и z.
Причем x, y описаны
без идентификатора
Var, а z — с
идентификатором Var.
Поясним разницу следующей схемой.
a ®
x
b ®
y
c «
z
При вызове процедуры Sum(a,b,c) из основной
программы значение переменной
a присваивается
переменной x процедуры Sum,
а значение переменной b — переменной
y.
Иначе обстоит дело с переменными c и z. Не поясняя пока “кухни” взаимодействия
этих переменных, будем считать, что процедура
Sum “знает” о том, где в памяти компьютера находится
переменная c
и что при изменении переменной z необходимо
произвести соответствующее изменение
переменной c.
На это указывает идентификатор Var в описании
параметра z.
Дадим ряд стандартных определений. В
любой программе все переменные делятся на
глобальные и локальные. Глобальные
переменные описываются
в разделе описаний основной части программы, а
локальные
— в разделах описаний процедур и функций. Но,
конечно, дело не только в том, где описываются
переменные. Локальные переменные существуют только в
течение времени работы процедуры, определяются (создаются) при ее вызове и “исчезают” после
завершения работы процедуры (после выполнения оператора
End).
Параметры. При
описании процедуры указывается список
формальных параметров.
Каждый параметр является локальным, к нему можно
обращаться только в пределах данной процедуры (в нашем
примере
x, y, z —
формальные параметры). Фактические
параметры — это
параметры, которые передаются процедуре при обращении к ней (a,
b, c —
фактические параметры). Количество
и типы формальных и фактических параметров должны совпадать.
Параметры-значения. В
нашем примере фактические параметры a и b передавались
“по значению”. При таком способе передачи параметров
значение фактического параметра становится значением
соответствующего формального параметра. Внутри
процедуры можно производить любые действия с данным
формальным параметром (допустимые для его типа),
но эти изменения никак не отражаются на значении
фактического параметра, то есть каким он был до
вызова процедуры, таким же и останется после
завершения ее работы (x, y —
формальные параметры-значения).
Параметры-переменные. Это
те формальные параметры, перед которыми стоит идентификатор
Var.
При таком способе передачи параметров в
процедуру передается не значение, а адрес фактического
параметра (обязательно переменной). Любые операции с
формальным параметром выполняются
непосредственно над фактическим параметром
Договоримся о том, как мы будем стараться
использовать процедуры, может быть, в ущерб
эффективности программ, например, с точки зрения
количества переменных и т.д. Каждая процедура должна
иметь одну точку входа и одну точку выхода,
использование глобальных переменных в процедуре должно
быть минимальным, передавать данные в процедуры
мы будем лишь посредством параметров. Почему? Мы
осваиваем структурную технологию разработки
программ, при этом на каждом этапе задача разбивается
на ряд подзадач, определяя тем самым некоторое
количество отдельных подпрограмм (подпрограмма
— это
повторяющаяся группа операторов, оформленная в
виде самостоятельной программной единицы). При
этом мы стараемся структурировать задачу не только
по управлению, но и по данным, используя при этом
весьма ограниченный набор инструментов (параметры-значения,
параметры-переменные). Концепция процедур
и функций — один из механизмов второго витка
развития технологий программирования, а именно,
структурного проектирования.
Экспериментальный раздел занятия
1. Составить программу перестановки значений переменных a, b, c в порядке возрастания, т.е. так, чтобы a £ b £ c.
Program My11_1;
Var a,b,c:Integer;
Procedure Swap (Var x,y:Integer);
Var t:Integer;
Begin
t:=x;x:=y;y:=t
End;
Begin
WriteLn ('Введите три числа ');
ReadLn (a,b,c);
If a>b Then Swap (a,b);
If b>c Then Swap (b,c);
If a>c Then Swap (a,c);
WriteLn (a:5,b:5,c:5);
ReadLn
End.
Найдите ошибку в этом решении. Требуется
исправить имя одной переменной в одной строке
программы. Составьте для поиска ошибки полную
систему тестов. Измените программу так, чтобы
аналогичная задача решалась для четырех переменных.
2.
Составить
программу вычисления выражения
y = an • xn + an—1
• xn—1 + … + a2 • x2
+ a1 • x1 + a0 , где все данные — целые числа. Коэффициенты
an , an—1
, …, a1
, a0
являются
первыми членами арифметической прогрессии, определяемой первым элементом
(q)
и разностью между соседними элементами
(d).
Значения q, d, n, x вводятся
с клавиатуры. Например, q = 2, d = 3, n = 5 и
x = 4. Нам
необходимо вычислить выражение 2•45
+
5•44 +
8•43 +
11•42 +
14•41 +
17•40.
Program My11_2;
Var q,d,n,x,t,w,s: Integer;
Procedure Degree (x,y: Integer;
Var st: Integer);
Var i:Integer;
Begin
st:=1;
For i:=1 To y Do st:=st*x
End;
Begin
Writeln ('Введите исходные данные – четыре не очень больших числа');
Readln (q,d,n,x);
s:=0;t:=n;
For i:=1 To n+1 Do Begin
Degree (x,t,w); s:=s+q*w;
Dec (t); Inc (q,d)
End;
Writeln ('Результат ',s);
Readln
End.
Использование процедуры для решения этой задачи несколько искусственно, но наша цель — отработать механизм использования процедур. Составьте таблицу изменения значений переменных q, t, w при работе программы. Проверьте правильность заполнения таблицы, используя отладчик и режим пошагового исполнения программы. Зафиксируйте значения q, d, x и найдите экспериментальным путем (или модифицируя программу) то значение n, при котором диапазона типа Integer уже не хватает для хранения результата.
Примечание. Переменные с именем x в основной программе и в процедуре Degree — это разные переменные!
Запишем приведенное выше выражение по-другому: 17 + 4•(14 + 4•(11 + 4•(8 + 4•(5 + 4•2)))).
Результат вычислений, естественно, тот же
самый.
В общем виде запись выглядит следующим
образом: a0 + x•(a1 + x•(a2
+ x•(…
+ x•(an—1 + x•an )))).
Приведенная запись называется схемой
Горнера. Измените программу так, чтобы вычисление
выражения осуществлялось по схеме Горнера.
А что означает запись 4 2•5 + 4•8 + 4•11 + 4•14 + 4•17 + ?
Можно ли вычислить это выражение?
Оказывается, да. Берем два числа — 4 и 2 — и выполняем с ними
операцию, записанную после них, т.е. умножение.
Сохраняем результат и продолжаем вычисление.
Берем 8 и 5 и выполняем сложение. Потренируйтесь.
Напишите несколько примеров и преобразуйте их запись
к такому виду. Она называется обратной польской
записью, в честь польского математика Яна
Лукашевича. Для общего случая в нашей задаче обратная
польская запись имеет вид: an x •an—1
+ … a2 x•a1 + x•a0 +.
Пусть у нас есть процедура Part,
выполняющая одно арифметическое действие (умножение или сложение)
над двумя числами. Напишите программу для
решения нашей задачи с использованием процедуры
Part.
Procedure Part (x,y:Integer; t:Byte;
Var z:Integer);
Begin
If t=1 Then z:=x+y Else z:=x*y
End;
У нас есть три способа вычисления
значения одного и того же выражения. Сравните количество
операций умножения и сложения, необходимых для
получения результата в каждом из случаев. Какой
вывод вы можете сделать?
3.
Задание
значений элементам одномерного массива (с помощью генератора случайных чисел)
и вывод результата на экран мы рассмотрели на
предыдущем занятии. Оформим эти действия как
процедуры.
Program My11_3;
Const n=8; l=-10; h=21;
Type MyArray=Array[1..n] Of Integer;
Var A:MyArray;
Procedure Init (t,v,w:Integer;
Var X:MyArray);
Var i:Integer;
Begin
Randomize;
For i:=1 To t Do X[i]:=v+Integer (Random(w))
End;
Procedure Print (t:Integer; X:MyArray);
Var i:Integer;
Begin
For i:=1 To t Do Write (X[i]:5);
WriteLn;
End;
Begin
WriteLn ('Формирование значений элементов массива
A');
Init (n,l,h,A);
{Значения n элементов массива А
формируются из интервала целых чисел от l до
h.}
WriteLn ('Вывод');
Print (n,A)
{n первых элементов массива А выводятся на экран (в данном случае).}
End.
Зачем нам понадобилось оформлять такие
простые действия в виде процедур? Было несколько
строк программного кода, а сейчас… Пожертвуем кажущейся
простотой предыдущей версии программы. С этого
момента будем стараться создавать программы так, чтобы
основная программа состояла из вызовов процедур и
функций. Нарисуйте схему (по подобию тех, что приведены
в начале занятия), отражающую взаимосвязь основной
программы и процедур как по управлению, так и по
данным.
Изменим заголовок процедуры Print на
Procedure Print (n:Integer;X:Array[1..n] Of Integer)
и запустим программу. Результат не
заставит себя ждать:
Error 54: OF expected.
Курсор находится на квадратной скобке, т.е. после слова
Array ожидается Of. Пойдем на поводу у системы
программирования, изменим описание на
Procedure Print (n:Integer; X:Array Of Integer).
Результат чуть-чуть изменился, уже
знакомая ошибка — Error 201:
Range check error.
Отключим контроль на выход за пределы диапазона —
{$R-}. Программа заработала, точнее, она выдает
результат.
Итак, сплошные загадки. Попробуйте дать им
разумное объяснение.
4.
Даны два
одномерных массива. Найти элементы, принадлежащие и тому и другому массивам. Наша технология написания программ (использование процедур и функций) начинает
приносить дивиденды. Процедуру
Init при решении
задачи требуется использовать два раза с различными
параметрами, процедуру Print —
три раза. Сделаем “костяк” программы. Процедуры
Init и Print,
естественно, не приводятся, они у нас почти универсальны и
берутся из предыдущего задания. Программа (ее “костяк”)
должна компилироваться. Сохраните ее. Набирать
весь текст программы, а затем приступать к отладке — это
дурной тон в программировании. Возьмите за правило и
всегда его придерживайтесь — “в любой момент
времени у нас должна быть компилируемая программа,
сохраненная на внешнем носителе”. Кроме того, текст
любой процедуры и, естественно, основной программы
должен помещаться на экране и, конечно, быть
читаемым.
{$R+}
Program My11_4;
Const n=10; la=-10; ha=21;
m=8; lb=-15; hb=31;
Type MyArray=Array[1..n] Of
Integer;
Var A,B,C:MyArray;
k:Integer;
Procedure Solve (qx, qy:Integer; Var qz:Integer; X,Y:MyArray; Var Z: MyArray);
Begin
End;
Begin
Init
(n,la,ha,A);
WriteLn ('Вывод значений элементов массива A');
Print
(n,A);
Init
(m,lb,hb,B);
WriteLn
('Вывод значений элементов массива B');
Print
(m,B);
Solve (n,m,k,A,B,C);
WriteLn
('Вывод тех целых чисел, которые
есть и в А, и в B');
Print
(k,C);
ReadLn
End.
Начнем уточнять наше решение, а именно, процедуру Solve.
Procedure Solve(qx,qy:Integer;
Var qz:Integer; X,Y:MyArray; Var Z: MyArray);
Var i,j:Integer;
Begin
qz:=0;
For i:=1 To qx Do
For j:=1 To qy Do
If X[i]=Y[j] Then Begin
Inc(qz);
Z[qz]:=X[i]
{j:=qy}
End
End;
После запуска программы окажется, что при некоторых исходных данных она выдает неправильный результат. Пусть, например, в первом массиве имеется один элемент со значением 10, а во втором — пять таких элементов. Согласно формулировке задачи в ответе 10 должна присутствовать один раз, а она выводится пять раз. Уберем фигурные скобки у оператора j:=qy. Мы “насильно” изменяем управляющую переменную цикла For j:=1 … Выводится правильный результат. Однако этот прием мы считаем признаком плохого стиля программирования. Изменим внутренний цикл.
Procedure Solve(qx,qy:Integer;
Var qz:Integer; X,Y:MyArray; Var Z: MyArray);
Var i,j:Integer;
Begin
qz:=0;
For i:=1 To qx Do Begin
j:=1;
While (j<=qy) And (X[i]<>Y[j]) Do Inc(j);
If j<=qy Then Begin
Inc(qz);
Z[qz]:=X[i]
End
End
End;
5. Даны
массив A из n элементов
и число m,
где 1 < m < n.
Не используя дополнительных массивов, переставить первые m элементов в
конец массива, а элементы с (m + 1)-го по n-й
— в начало, сохраняя порядок элементов.
Подскажем идею решения. Переворачиваем
первые m элементов,
затем переворачиваем элементы, начиная с (m +
1)-го. Затем переворачиваем все элементы массива. Приведем пример.
Пусть n =
10, m =
6,
массив A:
5 1 —4 3 7 2
—1 9 8 6
2 7 3 —4 1 5
—1 9 8 6
первое переворачивание m элементов
2 7 3 —4 1 5
6 8 9 —1
второе переворачивание элементов с
m + 1 по n
—1 9 8 6 5 1
—4 3 7 2
третье переворачивание элементов с 1 по
n
В тексте решения не приводится реализация процедур Init и Print. Для процедуры Rev рекомендуется выполнить “ручную” трассировку при различных значениях t и l.
{$R+}
Program My11_5;
Const n=10;m=6;
Type MyArray=Array[1..n] Of Integer;
Var A:MyArray;
Procedure Init (Var X:MyArray);
Procedure Print (X:MyArray);
Procedure Swap (Var a,b:Integer);
{Из первого задания.}
Procedure Rev (t,l:Integer; Var X:MyArray);
Var i:Integer;
Begin
For i:=t To t+(l-t) Div 2 Do Swap (X[i],X[l-i+t])
End;
Begin
Init (A); Print (A);
Rev (1,m,A); Rev (m+1,n,A); Rev (1,n,A);
Print (A);
ReadLn
End.
Задания для самостоятельной работы
1. Даны два
различных выражения вида:
y = an •xn + an—1
•xn—1 + … + a2 •x2
+ a1 •x1 + a0 ,
z = bn •xn + bn—1
•xn—1 + … + b2 •x2
+ b1 •x1 + b0 ,
— где все коэффициенты — целые числа.
Коэффициенты хранятся в массивах A и B.
При заданном значении
x найти
максимальное значение из y и z.
2. Даны два
одномерных массива из целых чисел. Найти элементы, которые есть в первом
массиве и которых нет во втором.
3. Даны два
одномерных массива из целых чисел. Найти элементы, которые входят только в
один из массивов.
4.
Решить
задачу 4 из раздела экспериментальной работы для трех массивов.
5.
Даны 3
одномерных массива из целых чисел. Найти элементы, которые есть в первом массиве
и которых нет во втором и третьем массивах.
6. Решить
задачу 3 для трех одномерных массивов.
7.
Даны два
одномерных массива из целых чисел разной размерности. Найти среднее
арифметическое элементов каждого массива и их сумму.
Решить задачу для трех массивов.
8.
Даны три
одномерных массива из целых чисел одинаковой размерности. Сформировать
четвертый массив, каждый элемент которого равен
максимальному из соответствующих элементов первых трех
массивов.
9. Даны два
одномерных массива (A, B)
одинаковой размерности n и число m.
Поменять местами первые элементы массивов и выполнить
перестановку элементов массивов в обратном порядке (задание
№ 5 раздела экспериментальной работы).
10. Дано
четное число n.
Проверить для этого числа гипотезу Кристиана Гольдбаха (1742 год). Эта
гипотеза (по сегодняшний день не опровергнутая и
полностью не доказанная) заключается в том, что
каждое четное n,
большее двух, представляется в виде суммы
двух простых чисел. Ограничим диапазон
проверяемых чисел интервалом 2 £
n £
999. Фрагмент
проверки числа на простоту оформить в виде процедуры.
Примеры:
6 = 3 + 3
12 = 5 + 7
30 = 7 + 23
308 = 31 + 277
992 = 73 + 919
Исследовать гипотезу К.Гольдбаха для
больших значений n.
11. Известны
следующие признаки делимости числа n:
· для
делимости на 2 необходимо, чтобы последняя цифра числа делилась на 2;
· для
делимости на 3 требуется, чтобы сумма цифр числа делилась на 3;
· для
делимости на 4 необходимо, чтобы число из последних двух цифр делилось на 4;
· для
делимости на 5 необходимо, чтобы последняя цифра числа была 0 или 5;
· для
делимости на 8 необходимо, чтобы число из 4 последних цифр делилось на 8;
· для
делимости на 9 необходимо, чтобы сумма цифр числа делилась на 9;
· для
делимости на 11 необходимо, чтобы разность между суммой цифр, стоящих на четных
местах, и суммой цифр, стоящих на нечетных местах,
делилась на 11.
Написать процедуры проверки признаков
делимости. Проверить их для различных значений
n.
Материал для чтения
1. Некоторые
факты из элементарной теории вероятностей.
Всем
нам достаточно часто приходится сталкиваться с ситуациями, когда, зная
возможные исходы некоторого события (опыта), мы не
можем точно предсказать его результат. Например,
при бросании монеты — какой стороной она упадет вверх;
при бросании игральной кости — какая из шести
сторон окажется сверху; при вытаскивании карты из
игральной колоды — какая карта будет вытянута и т.д.
Главное, что присуще всем этим ситуациям, то, что
исходы равноправны. Выпадет орел или решка; выпадет
сторона игральной кости с числом от 1 до 6; вытянута
одна из 52 карт. Как оценивать исходы, какую меру
взять для оценки того, что произойдет то или иное
событие. Пусть, например, событие — это выпадение четного
числа при бросании игральной кости. Общее
количество исходов — 6, число благоприятных исходов — 3.
Вытянута карта пиковой масти, общее количество исходов —
52, благоприятных — 13. Понятие меры в теории
вероятности вводится следующим образом. Определяется
множество элементарных событий S,
его элементы считаются равноправными, равновероятными. Любое
событие A — подмножество S также
состоит из элементарных событий. Отношение
|A| / |S|,
где через | | обозначено количество элементов в множестве,
называется вероятностью события A и
обозначается P(A).
Вероятность любого события А заключена
между нулем и единицей: 0 £
P(A) £
1.
Приведем примеры:
·
При
бросании двух игральных костей вероятность
получения 10 и более очков равна 4/36 = 1/9, так как всего имеется 36 равновероятных
исходов и четыре из них благоприятны — (5, 5), (5, 6), (6, 5)
и (6, 6).
·
Вероятность
того, что на первой кости выпадет меньше очков, чем на второй, равна 15/36.
·
Стрелок
попадает в цель в среднем 92 раза из 100 выстрелов. Вероятность попадания равна
92/100 (0,92).
· На каждую
1000 готовых деталей некоторого предприятия приходится в среднем 16
бракованных. Вероятность изготовления брака для
данного производства равна 0,016.
·
Первый
стрелок попадает в цель с вероятностью 0,8, второй — 0,7. Найти вероятность
поражения цели, если оба стрелка стреляют
одновременно. Цель считается пораженной при попадании в
нее хотя бы одной из двух пуль. Пусть
производится 100 двойных выстрелов. Примерно в 80 из них
цель будет поражена первым стрелком, а в 20
случаях он промахнется. Второй стрелок из 10
выстрелов примерно 7 раз поражает цель, в 20
выстрелах — 14 раз. Таким образом, при 100
выстрелах цель окажется пораженной примерно 94 раза.
Вероятность поражения — 0,94.
·
Событие,
вероятность которого равна 1, называется достоверным — оно наступает всегда.
Монета упадет гербом или решкой, считаем, что на
ребро
она встать не может. Событие, вероятность
которого равна 0, называется невозможным — оно
не
наступает никогда. В нашем примере
бросания
игральной кости (и других) есть то, что
называют
элементарным событием — выпадение
стороны
кости с определенным числом. Остальные
события
составляются из элементарных событий,
например,
выпадение стороны кости с четным числом.
События A и B называют несовместимыми,
если появление одного из них исключает появление
другого. При бросании монеты орел и решка не могут
выпасть одновременно. Если A и B —
несовместимые события, то P(A + B)
= P(A)
+ P(B).
Утверждение обобщается на n несовместимых
событий. Говорят, что несколько событий A1
, A2 , …, An образуют полную
группу, если
вероятность того, что произойдет одно из них, является достоверным
событием. Примеры:
·
Опыт —
бросание двух монет. События “два орла”, “две решки” и “один герб, одна
решка” образуют полную группу и являются
несовместимыми.
·
Опыт —
бросание игральной кости. События “1 или 2 очка”, “2 или 3 очка”, “3 или 4 очка”,
“4 или 5 очков” и “5 или 6 очков” образуют
полную группу, но не являются несовместимыми.
·
Опыт —
вынимание одной карты из колоды в 36 карт. События — вынимание туза, короля,
дамы, валета, десятки, девятки, восьмерки,
семерки и шестерки — образуют полную группу
и являются несовместимыми.
·
Опыт —
передача в одинаковых условиях трех сообщений равной длины. События “искажено
первое сообщение”, “искажено второе
сообщение” и “искажено третье сообщение” не
образуют полную группу и не являются
несовместимыми.
2. Информация. Итак, об
информатике говорят как о науке, изучающей обработку информации с
помощью ЭВМ. Мы называем ЭВМ универсальной
машиной по обработке информации. Обсудим кратко
термин информация,
понимая при этом, что строгого определения нам не дать, ибо понятие информации
является первичным, неопределяемым. Слово
информация используется в двух значениях —
качественном и количественном. С одной стороны, мы понимаем под
информацией конкретные сведения о чем-либо,
представленные в виде речи, текста, изображения,
цифровых данных, графиков, таблиц и т.п. С другой
стороны — ее численную меру, то есть выраженное в битах
количество абстрактной информации. Остановимся
на втором аспекте. Одним из параметров
измерения информации является ее объем: количество бит,
байт и т.д. Есть последовательность из единиц и нулей.
Длину этой последовательности в одних книгах
называют количеством информации, в других — объемом
информации. Другой способ оценки количества
информации основан на вероятностном подходе. Вводится
мера неопределенности, мера нашего незнания чего-либо.
Устранение неопределенности достигается за счет
получения информации. Если есть “лапоть” для
измерения неопределенности, то он может быть
использован для наших целей — определения количества
информации. Приведем традиционное рассмотрение этой
схемы на примере игры “Бар — Кохба”.
Игра “Бар — Кохба”. Один из игроков что-то
загадывает, а второй должен отгадать
загаданное, задавая вопросы, которые предполагали бы только
ответы типа “да”, “нет”. Предположим, что в классе 16
учеников и учитель загадал номер по журналу одного
из учеников, они по какой-то причине пронумерованы
числами от 0 до 15. В начальный момент времени у нас
полное незнание того, какой номер загадан.
Первая серия наших вопросов.
1-й вопрос. Находится
ли загаданный номер в интервале от 8 до 15? Ответ — да (1).
2-й вопрос. Находится
ли загаданный номер в интервале от 12 до 15? Ответ — нет (0).
3-й вопрос. Находится
ли загаданный номер в интервале от 11 до 12? Ответ — да (1).
4-й вопрос. Загадан
номер 11? Ответ — нет (0).
Вторая схема формулировок вопросов.
1-й вопрос. Находится
ли загаданный номер в интервале от 0 до 3? Ответ — нет.
2-й вопрос. Находится
ли загаданный номер в интервале от 12 до 15? Ответ — нет.
3-й вопрос. Находится
ли загаданный номер в интервале от 4 до 7? Ответ — нет.
4-й вопрос. Находится
ли загаданный номер в интервале от 8 до 11? Ответ — да.
5-й вопрос. Находится
ли загаданный номер в интервале от 10 до 11? Ответ — да.
6-й вопрос. Загадан
номер 11? Ответ — нет.
Чем отличаются серии вопросов? Мера
нашего незнания в том и в другом случаях одинакова,
то есть получено одно и то же количество
информации. Примем за единицу измерения информации (1 бит)
количество информации, содержащееся в
ответе, при условии, что ответы равновероятны.
В первом случае каждый ответ содержит один бит информации,
ибо ответы “да” и “нет” были равновероятны.
Во втором случае — нет, в среднем один ответ
содержал 4/6 бита информации. Всего получено 4 бита
информации. Неопределенность полностью устранена, мы
знаем загаданный номер. Пусть есть N равновероятных
событий и выделено одно из событий (t).
Для того чтобы определить t,
необходимо получить количество информации I,
равное log2N.
Эта формула для вычисления количества информации предложена американским
инженером Р.Хартли в 1928 году. Если события не
равновероятные, то количество информации вычисляется по
формуле американского математика К.Шеннона:
I = —(p1 log2
p1 +
p2 log2 p2 +
… + pN log2 pN ),
— где pi —
вероятности событий. Из формулы К.Шеннона получается формула Р.Хартли при
pi = 1/N для всех значений
i.
Действительно,
I = —(1/N•log2
(1/N)+
… +1/N•log2 (1/N))
= log2 N.
В скобках первой серии вопросов указаны
цифры 0 или 1. Если выписать ответы в виде
двоичного числа 10102 и
перевести его в десятичную систему счисления, то получим число 10 — номер
загаданного ученика! Итак, каждая двоичная цифра несет в
себе один бит информации, отсюда и название единицы
измерения — бит (binary
digit —
двоичная цифра). В игре “Бар — Кохба” вопросы задаются
последовательно, на основании ответов учителя. А можно ли
задать сразу четыре вопроса, а затем получить четыре
ответа учителя и определить номер загаданного ученика?
Оказывается, да. Вопросы формулируются так: “Вы
загадали номер, двоичная запись которого содержит
единицу в первом разряде?” Обратите внимание на то,
что и в этом случае ответы “да” и “нет”
равновероятны. Предположим, что учитель одновременно
загадал номера двух учеников (t1 и t2
) в разных
классах. Количество учеников в классах — N1
и N2 . Необходимо
отгадать пару (x1, x2 ),
принадлежащую множеству всех пар — (N 1
´
N 2 ).
Согласно формуле Хартли, необходимо задать log2(N1•N 2 )
вопросов, или получить log 2 (N 1 • N 2 )
бит информации. С другой стороны, номера учеников можно отгадывать
независимо, для отгадывания t1 требуется
задать log2N1 вопросов,
для отгадывания t2 — log2N2
вопросов.
Следовательно, общее число вопросов равно
log2N1 + log2N2 . Итак, мы
получили log 2 (N 1 • N 2 )
= log 2N1 + log 2N2 ,
что совпадает с хорошо известным свойством
логарифмической функции. Это закон аддитивности информации.
Примеры
Имеется 27 монет: 26 настоящих и одна
фальшивая, она легче настоящих. Сколько
взвешиваний необходимо произвести, чтобы
определить
фальшивую монету?
Фальшивой может оказаться любая из 27 монет, следовательно, по формуле Хартли
количество недостающей информации равно log227 битов. Любое взвешивание имеет три исхода и
может дать нам только log23 битов
информации. Если мы производим X взвешиваний,
то они дадут X•log23
битов информации.
Итак, X•log2
³
log227
= log233 = 3•log23.
Следовательно, X ³
3.
На самом деле достаточно ровно 3 взвешиваний: первое по 9
монет, второе по 3 монеты из найденной группы и,
наконец, по одной монете из найденной группы по 3 монеты.
Чтобы найти элемент множества, состоящего из 7 элементов, необходимо задать три
вопроса, а чтобы найти элемент множества,
состоящего из 9 элементов, — 4 вопроса, то есть
по формуле Хартли получить log27 + log29 битов
информации. Но если необходимо отгадать
пару элементов из этих множеств, то требуется
получить log2(7•9)
битов информации, а это меньше 6 вопросов. Противоречия нет —
log 2 (7•9) = log 2 7 + log
2 9 = 5,97728 < 6.
Как понимать формулу Хартли, если log2N
не является целым числом? Предположим, что
мы выполняем отгадывание не один, а k раз, то есть строим последовательность из
k неизвестных элементов — (x1 , x2 , …, xk
).
Таких последовательностей Nk .
Очевидно, что для числа вопросов (sk ) в этом
случае выполняются следующие неравенства:
log
2Nk < s k < log
2 N k + 1
или
log
2 N < sk
/ k < log
2 N +
1/k.
Число
s k / k
показывает,
сколько вопросов в среднем необходимо для того, чтобы
отгадать один элемент множества, содержащего
N элементов. Выбирая значение k достаточно
большим, величину 1/k можно
сделать сколь угодно малой. Итак, в том случае, когда
N не совпадает
со степенью двойки, число вопросов, которое в
среднем необходимо задать для отгадывания
одного элемента множества мощности N,
будет отличаться от log
2 N на
сколь угодно малую величину.
Продолжение следует