“В МИР ИНФОРМАТИКИ” № 74

У компьютера своя информатика

Е.А. Еремин,
г. Пермь

Мы знаем тысячи разрозненных фактов, но часто рассматриваем их изолированно друг от друга, не задумываясь о том, что все они должны быть как-то связаны, поскольку мир вокруг нас един. Например, любому ребенку известно, что летом тепло, а зимой холодно (факт А). Кроме того, не менее очевидно, что чем ближе к Солнцу, тем теплее (факт Б). Каждый из тезисов очевиден и неоспорим, оба вроде бы об одном и том же, но при попытке объединить А и Б вместе вдруг возникают трудности: а почему же тогда сейчас, когда в северном полушарии зима, в Австралии лето?

По данным статьи [1], которая представляет собой стенограмму выступления А.Кэя¹ в Конгрессе США, почти 95% старшекурсников этой страны в ходе проведенного опроса уверенно утверждали, что “Земля летом ближе к Солнцу, чем зимой”. А на последующий вопрос: “Знаете ли вы, какое время года настает в Южной Америке и Австралии, когда у нас в Штатах приходит лето?” — давали не менее уверенный ответ: “Зима, разумеется”. Причем противоречие нового названного факта предыдущим двум мало кто замечал… А.Кэй пишет, что “мы столкнулись с отсутствием у этих ребят самых элементарных навыков критического мышления. Ведь и им, и их наставникам, не выдержавшим испытания, были известны факты, противоречащие невразумительным догадкам. Почему же никто из них не спохватился: “Эй, послушайте, как же так?..” Все, что нужно для правильного ответа, было им известно! Однако сопоставить факты, сложить из них мозаику, которая станет правильным ответом, большинству участников испытания не удалось”.

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

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

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

Что касается факта Б, то он, видимо, менее известен широкой аудитории, но для меня он не менее очевиден, чем факт А. Речь идет о том, по какому алгоритму в компьютере на практике осуществляется перевод. О деталях поговорим чуть позднее, а сейчас подумаем, как должны быть связаны факты А и Б? Иначе говоря, использует ли компьютер те же самые алгоритмы, которые мы так старательно изучали на уроках?

Увы, ответ если и не отрицательный, то весьма далекий от положительного. Словом, компьютер осуществляет перевод не совсем так, как это делаем мы с вами!

Причин тому несколько. Во-первых, компьютер приводит к двоичному виду не десятичное число, а его введенное с клавиатуры текстовое отображение². Причем это происходит и в программе “Калькулятор”, и в электронных таблицах, и при выполнении программ на языках программирования высокого уровня, и т.д. Во-вторых, при проведении расчетов мы пользуемся десятичной системой, а компьютер — двоичной (чуть позднее мы увидим, что это приводит к весьма существенным последствиям при выборе алгоритма). Наконец, в-третьих, мы проводим перевод чисел редко, поэтому не заботимся об оптимальности вычислительного процесса, а для компьютера ситуация другая. Таким образом, задачи “10 в 2” и “2 в 10” для человека и для компьютера выглядят по-разному.

Рассмотрим теперь реализацию процесса перевода в компьютере подробнее.

В основе перевода из одной системы счисления в другую лежит следующая общая теорема (см., например, [2]):

Для перевода целого числа Ap из p-ичной системы счисления в систему счисления с основанием d необходимо Ap последовательно делить с остатком на число d, записанное в той же
p-ичной системе, до тех пор, пока полученное частное не станет равным нулю. Остатки от деления при этом будут являться d-ичными цифрами числа Ad, начиная от младшего разряда к старшему. Все действия необходимо проводить в p-ичной системе счисления.

Если формулировка кажется вам запутанной и устрашающей, положите везде p = 10 и d = 2 (слова “записанное в той же p-ичной системе” в данном случае становятся излишними), в результате чего получится известное всем правило перевода “10 в 2”. Необычайно важно понять, что данный алгоритм в принципе пригоден для перевода между абсолютно произвольными системами счисления. Проблема заключается в последней фразе — действия необходимо производить в той же системе, в которой представлено исходное число. Отсюда следует важный для нас сейчас вывод, что для человека данное правило удобно лишь при p = 10, т.е. при переводе из десятичной системы. Поэтому, хотя теорему можно применять и для “2 в 10”, осуществляя все расчеты в двоичной системе, делать это гораздо проще, используя другой (известный из школы) алгоритм.

Что касается компьютера, то ему, напротив, “удобнее” производить вычисления в двоичной системе. Поэтому для перевода “2 в 10” используется последовательное деление на десять в двоичной системе, а “10 в 2” — сложение степеней десятки. Таким образом, в компьютере уже известные нам методы применяются, так сказать, “зеркальным” образом по сравнению с тем, как их использует человек.

И еще об одной особенности перевода “10 в 2” в компьютерной реализации. Рассмотрим ее на примере конкретного числа — 1234.

1234 = 1 · 10³ + 2 · 10² + 3 · 10¹ + 4 · 10⁰ (1).

Для упрощения вычислений данное выражение удобно преобразовать путем вынесения множителя 10 за скобки. Получим:

1234 = (1 · 10² + 2 · 10¹ + 3) · 10 + 4.

Повторим процедуру еще раз.

1234 = ((1 · 10 + 2) · 10 + 3) · 10 + 4.

Присмотревшись повнимательнее, увидим, что получившаяся формула описывает последовательное умножение предыдущего результата R_k – 1 на 10 и прибавление очередной цифры c_k:

R_k = 10R_k – 1 + c_k (2).

Заметим, что в качестве начального условия удобно принять R₀ = 0.

Формула (2) по сравнению с исходным выражением (1) имеет существенные преимущества. Во-первых, она не требует запоминания промежуточного результата, а сразу использует его для дальнейших вычислений. Во-вторых, как доказали математики, такая схема вычислений, называемая “схемой Горнера”, содержит минимально возможное число арифметических операций. Наконец, в-третьих, формула (2) корректно обрабатывает число по мере ввода цифр, тогда как (1) требует, чтобы все цифры числа были уже известны (иначе нельзя расставить степени!); в некоторых программах такое свойство оказывается полезным.

Так вот, при “машинном” переводе “10 в 2” используется именно схема Горнера.

Примечание. Схема Горнера оказывается удобной и при традиционном, “ручном”, переводе “2 в 10”. Более того, из ее записи видно, почему последовательное деление на 2 при обратной процедуре “10 в 2” дает именно двоичные цифры (подробнее см. главу 6 в [3]).

Напомнив читателям еще раз о том, что процедура “10 в 2” переводит текстовую строку с десятичным представлением числа в двоичное число, а “2 в 10” — наоборот, приведем текст программ, подтверждающих приведенные выше положения, связанные с переводом целых чисел из одной системы счисления в другую. Они снабжены подробными комментариями и, надеюсь, будут понятны читателям.

Язык Паскаль

{10 в 2}

Const baza = ord('0'); {Код символа '0'}

Var s: string; z, r, i: integer;

BEGIN

{Ввод строки с десятичным числом

(без ошибок!)}

write('Введите целое число в виде

последовательности цифр

(без пробелов) ');

readln(s);

i := 1; {Номер символа}

r := 0; {'Очистка' будущего результата}

while i <= Length(s) {до конца строки} do

begin

{Преобразуем цифру-символ в число}

z := Ord(s[i]) — baza;

{Получено двоичное представление цифры}

{Добавляем цифру к ранее полученному

результату}

r := 10 * r + z;

{Ясно, что в компьютере все это

происходит в двоичном виде}

i := i + 1

{Номер следующего символа-цифры}

end;

{Вывод результата}

writeln('Вы ввели число: ', r)

{Он должен совпасть с введенным числом,

что означает тот факт, что заданное в виде

строки десятичное число правильно

переведено компьютером в двоичный вид

(без многократного деления числа на 2)}

END.

Язык Бейсик3

'10 в 2

DIM s AS STRING, r, baza, z, i AS INTEGER

baza = ASC("0") 'Код символа '0'

'Ввод строки с десятичным числом

'(без ошибок!)

INPUT "Введите целое число в виде

последовательности цифр

(без пробелов)"; s

i = 1 'Номер символа

r = 0 'Очистка' будущего результата

WHILE i <= LEN(s) 'до конца строки

'Преобразуем цифру-символ в число

z = ASC(MID$(s, i, 1)) — baza

'Получено двоичное представление цифры

'Добавляем цифру к ранее полученному

'результату

r = 10 * r + z

'Ясно, что в компьютере все это

'происходит в двоичном виде

i = i + 1 'Номер следующего символа-цифры

WEND

'Вывод результата

PRINT "Вы ввели число: "; r

'Он должен совпасть с введенным числом,

'что означает тот факт, что заданное в виде

'строки десятичное число правильно

'переведено компьютером в двоичный вид

'(без многократного деления числа на 2)

Язык Паскаль

{2 в 10}

Const baza = ord('0'); {Код символа '0'}

Var s: string; n, z: integer;

BEGIN

write('Введите число ');

readln(n);

{В этот момент в переменной n

хранится двоичное число, равное

введенному десятичному.

Это произошло в результате работы

компьютера по программе,

аналогичной программе 1}

s := ''; {Будущий результат пока 'пуст'}

while n > 0 do

begin

{Выделяем последнюю цифру числа n}

z := n mod 10;

{и приписываем ее в виде символа

к началу ранее полученного результата}

s := Chr(z + baza) + s;

{Ясно, что в компьютере все это

происходит в двоичном виде}

n := n div 10 {оставшееся число}

end;

{Вывод результата в виде строки}

writeln('Вы ввели число: ', s)

{Он должен совпасть с введенным числом,

что означает тот факт, что

двоичный аналог заданного

десятичного числа правильно

переведен компьютером в строковое

представление этого числа}

DIM s AS STRING, n, baza, i AS INTEGER

baza = ASC("0") 'Код символа "0"

INPUT "Введите целое число ", n

'В этот момент в переменной n

'хранится двоичное число, равное

'введенному десятичному.

'Это произошло в результате работы

'компьютера по программе,

'аналогичной программе 1

s = "" 'Будущий результат пока "пуст"

WHILE n > 0

'Выделяем последнюю цифру числа n

i = n MOD 10

'и приписываем ее в виде символа

'к началу ранее полученного результата

s = CHR$(i + baza) + s

'Ясно, что в компьютере все это

'происходит в двоичном виде

n = n \ 10 'Оставшееся число

WEND

'Вывод результата в виде строки

PRINT "Вы ввели число: "; s

'Он должен совпасть с введенным числом,

'что означает тот факт, что

'двоичный аналог заданного

'десятичного числа правильно

'переведен компьютером в строковое

'представление этого числа

END

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

Как оказалось, алгоритмы перевода “10 в 2” и “2 в 10” в компьютере реализуются на практике не так (или, точнее, не совсем так), как нас учат в книгах. Но это имеет под собой вполне логичное объяснение: нас учат, как удобнее выполнять действия человеку. Что же касается компьютера, то у него “своя” информатика — двоичная, и “человеческие” десятичные алгоритмы ему не всегда подходят. С моей точки зрения, это один из примеров, который наглядно демонстрирует тот факт, что попытки “умозрительно” описывать поведение компьютера на основе повседневного (десятичного и неформального) человеческого опыта без знания фундаментальных технических подробностей могут приводить к абсолютно неправильным представлениям.

В заключение сформулируем выводы.

1. Компьютер реализует не перевод из одного числа в другое, а перевод строки с десятичным представлением числа в двоичное число и наоборот.

2. Компьютер, в основе которого лежит двоичная арифметика, использует для перевода “10 в 2” разложение по степеням числа 10, а для “2 в 10” — последовательное деление на 10. Человек поступает по-другому: для “10 в 2” пользуется делением на основание системы счисления 2, а для “2 в 10” — суммированием разложения по степеням двойки.

3. Для оптимизации вычислений процедуры “10 в 2” компьютер использует экономную вычислительную схему Горнера.

4. (Для учителей) Всякая абстрактная теория, будучи приложенной к практике, оказывается богаче и интереснее. При этом автоматически исчезает вопрос “Зачем все это нужно?”. Гармоничное единство фундаментальной теории и ее практического применения⁴ — не в этом ли правильный путь к построению хорошего курса информатики?

Литература

1. Кэй А. Идеям тоже нужна любовь. / Компьютер в школе, 1998, № 1.

2. Акулов О.А., Медведев Н.В. Информатика: базовый курс. М.: Омега-Л, 2005.

3. Гейн А.Г. Информатика: Книга для учителя: Методические рекомендации к учебнику для 10–11-х классов / А.Г. Гейн, Н.А. Юнерман. М.: Просвещение, 2001.

4. Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992.

⁴ Современный курс информатики в школе чаще всего строится по принципу: фундаментальная теория (информация, системы счисления и т.д.) — отдельно, практика (Microsoft Office) — отдельно; в то же время на принципы работы компьютера, которые во многом являются связующим звеном того и другого, отводится всего 16 часов (с 7-го по 11-й класс), причем сюда входит время на изучение правил техники безопасности, операционных систем и других вопросов.