От числа к записи
При решении задач часто приходится выполнять взаимное преобразование значения и записи числа: получать по известному значению внешний вид числа (например, набор десятичных цифр) и, наоборот, определять число, зная, какими цифрами оно записывается.
Во многих системах программирования для такого преобразования существуют специальные встроенные средства. Чаще всего это некие стандартные функции, преобразующие число в строку символов и обратно. Это, например, функции STR$ и VAL в системе QBasic, функции Str и Val в системе Turbo Pascal, функции sprinf ; и ssсanf в стандартной библиотеке Си. А в таких языках, как Perl или JavaScript, разница между значением и записью вообще как бы стерта: система по контексту определяет, что подразумевается в каждом конкретном случае.
Кроме того, неявное преобразование происходит всякий раз, когда мы используем стандартные средства ввода/вывода. Простая паскалевская, конструкция write (х) означает, что числовое значение переменной х необходимо преобразовать в последовательность символов и затем передать на выходное устройство.
А теперь давайте на время откажемся от всех перечисленных возможностей и посмотрим, как можно выполнить преобразование значения и записи числа, не пользуясь никакими дополнительными средствами, кроме стандартных целочисленных операций.
Сначала научимся разбивать число на отдельные цифры, составляющие его десятичную запись. Это нетрудно сделать, поняв суть позиционной записи: в десятичной записи любого числа последняя цифра показывает количество единиц, а все остальные — десятков. Например, запись 2138 означает число, состоящее из 213 десятков и 8 единиц. Иными словами, 2138== 213 * 10+8. Сравните это с уравнением (1) — перед нами типичная запись результата деления с остатком. Итак, разделив число на 10, мы получим в остатке его последнюю цифру, а в частном — число, которое получается из исходного вычеркиванием последней цифры. Повторив эту операцию несколько раз, можно по очереди отделить от числа все цифры.
Задача 1
Определить сумму цифр десятичной записи натурального числа.
Решение. Пользуясь описанным выше методом, будем отделять от числа цифры и считать их сумму. Запишем соответствующие функции на Паскале (использована версия Турбо Паскаль, в которой есть тип word, гарантирующий неотрицательность) и Си.
function DigitSum (n: word) : word;
{Подсчет суммы цифр натурального числа.}
var sum: word;
begin
sum: = 0;
while n>0 do
begin
sum: =sum + n mod 10;
n: =n div 10
end;
DigitSum: ==sum
end;
unsigned DigitSum (unsigned n)
/* Подсчет суммы цифр натурального числа.*/
{ unsigned sum=0;
for (; n; n/ = l0) sum + =n %10
return sum;
}
Рассмотрим теперь преобразование числа в строку символов. Начнем с одной цифры, а затем перейдем к произвольным целым числам.
Задача 2
Преобразовать одну десятичную цифру (от 0 до 9) в соответствующий символ.
Решение 1. Поскольку возможных цифр всего 10, их можно просто перечислить, указав для каждой соответствующий символ. На Паскале это можно записать в виде такой функции:
function digit2char (digit: integer) : char;
{Функция преобразует одну десятичную цифру в символ.
Предполагается, что 0<=digit<==9. Другие значения digit считаются ошибочными, результатом функции для них будет пробел.} largemuIt
begin
case digit of
0: digit2char:= "0";
1: digit2char:= "0";
2: digit2char:= "0";
3: digit2char:= "0";
4: digit2char:= "0";
5: digit2char:= "0";
6: digit2char:= "0";
7: digit2char:= "0";
8: digit2char:= "0";
9: digit2char:= "0";
0: digit2char:= "0";
else digit2char:=" ";
end
end;
Недостаток этой функции очевиден: выписывание однообразных частных случаев смотрится весьма нудно и эстетически непривлекательно. Менее заметно достоинство выбранного подхода: независимость от кодировки. Каковы бы ни были коды символов-цифр, наша функция будет работать правильно.
Решение 2. Как известна, в стандартной кодировке ASCII коды цифр расположены подряд. Более того, в каноническом описании языка Паскаль г говорится, что это обязательное свойство для всех возможных реализации Паскаля. В таком случае можно пожертвовать независимостью от кодировки и сделать функцию менее громоздкой.
function digit2char (digit: integer) : char;
{Функция преобразует одну десятичную цифру в символ. Предполагается, что 0<==digit<=9. Другие значения digit считаются ошибочными, результатом функции для них будет пробел.}
begin
if digit in [0..9]
then digit2char:=chr(ord('0')+digit)
else digit2char:=' '
end;
Рассмотрим подробнее конструкцию chr(ord('0')+digit).
Здесь используются стандартные функции ord и chr, преобразующие символ в его код и обратно. Обратите внимание: функция ord возвращает код символа в кодовой таблице, а не числовое значение цифры. Например, для таблицы ASCII ord ('0') оказывается равным 48. Прибавив к этому числу значение цифры digit, получаем табличный код этой цифры. Здесь используется тот факт, что все цифры расположены в кодовой таблице подряд. Наконец, применив к результату функцию преобразования chr, получаем символ соответствующей цифры.
Конструкция с вложенными вызовами взаимно обратных функций оказалась необходима, потому что в Паскале нет неявного преобразования чисел и символов. Очень похоже выполняется подобное преобразование в Бейсике и КуМире. В Си символы считаются тождественными своим кодам, и выражение получается несколько проще. Приведем для сравнения полную запись аналогичной функции на Си.
char digit2char (int digit)
/* Функция преобразует одну десятичную цифру в символ. Предполагается, что 0<=digit<=9. Другие значения digit считаются ошибочными, результатом функции для них будет пробел. */ { -
if (0<=digit && digit<=9) return '0'+digit;
else return ' ';
}
Упражнение 1. Решите обратную задачу: напишите функцию char2digit, преобразующую символ десятичной цифры в числовое значение. Рассмотрите два способа решения, аналогичные двум решениям задачи 2.
Задача 3
Преобразовать натуральное число в последовательность символов.
Решение 1. В двух предыдущих задачах мы научились разбивать число на цифры и преобразовывать цифры в символы. Теперь надо совместить эти действия. Поскольку цифры отделяются с конца числа, очередную цифру надо приписывать в начало уже построенной последовательности. Для этого можно использовать операцию конкатенации (соединения) строк. Такая операция, как правило, присутствует в системах программирования, которые допускают использование строк как самостоятельного типа данных. Вот как выглядит функция преобразования в системе КуМир:
алг лит int2str (apг цел n)
дано n>0 | преобразуем только натуральнее числа
надо | знач содержит строковую запись числа n
нач цел nn :
nn: =n | КуМир не разрешает изменять
| аргумент, поэтому создаем копию
знач:=""
нц пока nn>0
знач := digit2char(mod(пп,10)) + знач
nn := div(nn,10)
кц
кон
Решение 2, К сожалению, операция конкатенации есть не во всех системах. В Си, например, нет типа данных, аналогичного лит в КуМире или string в Турбо Паскале, нет и конкатенации. Правда, в стандартной библиотеке Си есть функция strcat, но она позволяет выполнять только правое присоединение (вызов strcat;(a,b) в КуМире соответствует присваиванию а: ==а+b), а нам нужно левое.
Получается противоречие: цифры числа поступают на обработку справа налево, а записывать их мы можем только слева направо. Значит, сначала надо где-то сохранить все цифры, а потом преобразовать их в символы и объединить в строку. Такая отложенная обработка легко реализуется с помощью рекурсии.
char * int2str (int n, char *s)
/* Функция преобразует целое п в строку символов, записывает в строку s и возвращает
в качестве результата. */
{
char dig[2];
/* строка для хранения очередной цифры */
if (n==0) strcpy(s,"");
else
int2sfcr (n/10, s) ;
{/* рекурсивный вызов;
в s записывается число n без последней цифры */
dig[0] == digit2char(n%10);
dig[l] == '\0'; /* концевой ноль */
strcat(s,dig);
}
return s;
}
Логику рекурсивного вызова можно в данном случае объяснить так: чтобы записать число, надо записать это число без последней цифры, а потом добавить последнюю цифру.
Упражнение 2. Доработайте функцию int2str, чтобы она могла преобразовывать в строку отрицательные числа и ноль. Обратите особое внимание на преобразование нуля: не допускайте появления ведущего нуля при обработке положительных чисел. Сделайте два варианта преобразования: с использованием конкатенации и рекурсии.
От волшебного числа 10 к недесятичным системам счисления
Разбивая число на цифры, мы постоянно выполняли деление на 10; Это вполне естественно -- ведь мы анализировали запись числа в десятичной системе счисления. Но давайте вспомним одну из заповедей хорошего стиля программирования: в программе не должно быть волшебных чисел, их надо заменять именованными константами. Следуя этому правилу, надо включить в программу описание константы (или ввести специальную переменную, если в языке нет понятия константы) base со значением 10 (имя base означает основание, имеется в виду основание системы счисления) и заменить число 10 на base.
Оказывается, такая замена не просто улучшает вид программы, она имеет еще и глубокий содержательный смысл. Давайте подумаем, что будет, если указать для base вместо 10 какое-нибудь другое значение? Прежде чем читать дальше, попробуйте сами ответить на этот вопрос.
Последовательно деля число на 10, мы тем самым выделяем в нем единицы, десятки, сотни и т.д., то есть формируем запись этого числа в десятичной системе счисления. Подставив вместо 10 другое значение base, мы получим запись в другой системе счисления, основанием которой будет выбранное значение base.
При base<10 наша функция будет правильно преобразовывать число в запись в соответствующей системе счисления. При base>10 необходимо внести коррективы в функцию digit2char, чтобы обрабатывать цифры (именно цифры!), большие 9. Обычно в качестве таких цифр используют латинские буквы: цифра А соответствует 10, В — 11 и т.д. В шестнадцатеричной системе, где традиционно используется такая запись, самой старшей цифрой оказывается F — 15, В принципе этот ряд можно продолжить до конца латинского алфавита. Значением цифры Z будет 35, что дает возможность использовать все системы счисления вплоть до Зб-ичной.
Упражнение 3. Доработайте функцию digit2str так, чтобы она обрабатывала цифры от 0 до 35. Цифрам от 0 до 9 должны ставиться в соответствие символы десятичных цифр, а цифрам от 10 до 35 — заглавные латинские буквы. Можно считать, что используется кодировка ASCII, то есть все символы заглавных латинских букв расположены в кодовой таблице подряд.
Упражнение 4. Переделайте функцию char2str так, чтобы она могла записывать число в любой системе счисления с основаниями от 2 до 36. Желательную систему счисления можно указывать в качестве дополнительного параметра.
От записи к числу
Мы научились с помощью стандартных целочисленных операций получать запись числа в произвольной системе счисления. Займемся теперь обратной задачей — восстановлением числа по его записи.
Задача 4
В строке s содержится запись натурального числа в системе счисления с основанием base. Получить значение этого числа.
Решение. Главное в этой задаче — понять, как изменяется значение числа при добавлении к его записи одной цифры. Вспомним уже рассмотренный пример:
2138 := 213* 10 + 8. Если рассмотреть его как переход от правой части к левой, мы как раз и получим нужное преобразование. В самом деле, известно, что, приписав к числу ноль, мы увеличиваем это число в 10 раз. А чтобы приписать ненулевую цифру, можно приписать ноль (то есть умножить число на 10), а затем прибавить к результату нужную цифру.
Естественно, в общем случае умножать надо не на 10, а на основание системы счисления. Заметим, что в любой позиционной системе ее основание записывается как 10, а приписывание нуля к числу означает умножение на 10, то есть на основание системы счисления.
Запишем решение задачи в виде функции на Турбо Паскале.
function str2int(s:string; .
base'.integer) :, word;
{ Преобразование числа, записанного в строке s, в целое base задает основание системы счисления, 2<=base<=36. Если s содержит недопустимые символы, преобразуется начало строки, состоящее из цифр base-системы. Если допустимых символов нет или неверно значение base, возвращается ноль}
var
n: word; {преобразованное число}
i: integer; {счетчик символов}
digit: integer; {очередная цифра}
begin
n:=0;
if base in [2..36] then
begin
i: =l;
while i<length(s) do begin
digit: char2digit(s[i]);
if digit in [0..base-1]
then begin
n: =base*n + digit;
i:-i+l
end
else it lengthts +l (обнаружен неверный символ -досрочное прекращение обработки}
end
end;
str2int: =n
end;
function char2digit (c:char): integer;
{Преобразование одного символа-цифры в числовое значение. Допустимые символы - цифры от 0 до 9 и латинские буквы (заглавные и строчные), которым приписываются значения от 10 до 35. При недопустимом символе функция возвращает минус единицу.}
begin
case с of
О'..'9': char2digit:=ord(c)-ord('0') ;
'А'..'Z': char2digit:=10+ord(c)-ord('A') ;
'а' .. 'z': char2digit: =l0+ord(c)-ord('a');
else char2digiti: = - l
end
end;
Контрольный вопрос. При обращении к функции char2digit с неверным значением параметра возвращается значение —1. Почему при вызове char2digit из функции str2int не производится сравнения результата с этим значением?
Не могу удержаться и не привести функцию str2int на Си. Цель этой демонстрации — показать свойственный этому языку стиль программирования, типичные приемы Си, делающие программы очень компактными и эффективными (хотя отчасти менее понятными, особенно для тех, кто еще не имеет опыта написания и чтения Си-программ). В общем, если уж писать на Си, то не стоит делать это, как на Паскале.
unsigned str2int (char s[], int base)
/* Преобразование числа, записанного в строке s, в целое base задает основание системы счисления, 2<=base<=36. Если s содержит недопустимые символы, преобразуется начало строки, состоящее из цифр base-системы. Если допустимых символов нет или неверно значение base, возвращается ноль */ { unsigned n=0; /* преобразованное число */
char *р; /* указатель на очередной символ */
int digit; /* очередная цифра */
if (!(2<=base && base<=36)) return 0;
for (p=s; *p && (digit=char2digit(*p))>=0
&& digit<base; p++)
n=base*n + digit;
return n;
}
Упражнение 5. Доработайте функцию str2int, чтобы она могла правильно обрабатывать отрицательные числа.
Заканчивая разговор о преобразованиях (но не о целых числах!), разберем несколько задач.
Задача 5
Развернуть натуральное число задом наперед. Например, 1999 должно превратиться в 9991.
Решение. Мы уже умеем разбивать число на отдельные цифры и собирать из отдельных цифр число. Осталось только вспомнить, что при разборке цифры "отваливаются" с конца числа, а при сборке удобнее брать их с начала, и сообразить, что конец исходного числа соответствует началу того, которое требуется получить.
Для разнообразия напишем функцию на КуМире.
алг цел развернуть число (цел число)
дано число > 0
надо | знач= число "задом наперед" нач цел копия
|КуМир не разрешает изменять
| значения аргументов
знач : = 0
копия := число
нц пока копия > 0
|знач := 10*знач + mod(копия, 10)
копия: = div(копия,10)
кц
кон
Контрольный вопрос. Какой результат выдаст эта функция, если вызвать ее с аргументом, равным 2000 ? Как вы считаете, можно ли считать, что в этом случае разворот выполняется корректно?
Задача 6
Вычеркнуть из натурального числа все вхождения цифры, которая встречается в этом числе чаще других. Если несколько цифр встречаются одинаково часто, вычеркнуть наибольшую из них. Если вычеркнутыми окажутся все цифры, считать результат равным нулю.
Решение. Перед нами типичная задача-многоходовка. Надо составить план решения, разбить задачу на части, а потом разбираться с каждой частью отдельно.
Очевидных этапов решения три:
— подсчитать, сколько раз встречается в исходном числе каждая цифра;
— определить самую популярную цифру;
— преобразовать число, вычеркивая нужную цифру.
Для выполнения первого этапа (подсчет количества каждой цифры) можно завести массив из 10 элементов, которые будут соответствовать цифрам от 0 до 9, и разобрать число по цифрам, каждый раз увеличивая соответствующий очередной цифре элемент массива.
На втором этапе (определение самой популярной цифры) задача сводится к стандартному поиску максимального элемента в массиве.
Самый трудный — третий этап. Нужно разобрать число и собрать его снова, удалив при этом "лишние детали". Причем собрать нужно не в обратном, а в исходном порядке. Это значит, что нужно либо научиться собирать число с конца, либо где-то хранить полученные при разборке цифры до того момента, пока они понадобятся.
Попробуем реализовать оба варианта. Для сборки числа с конца можно применить такой прием. Будем учитывать позиционный множитель, который равен 1 для последней цифры и в 10 раз больше для каждой следующей. Умножая цифры на этот множитель, мы получим нужное число.
Можно реализовать и временное хранение. Вполне подходящим местом для него может стать рекурсивный стек.
Теперь попробуем воплотить все сказанное в программе.
алг удалить популярную цифру (арг цел X, рез цел Y)
дано Х>0
надо | Y получен из Х вычеркиванием самой
| популярной цифры
нач цел сколько[0:9]
| сколько раз встречается каждая
| цифра
цел цифра | самая частая цифра в Х
анализ количества цифр (X, сколько)
цифра := imax (0, 9, сколько)
Y := удалить цифру (X, цифра)
кон
алг анализ количества цифр (арг цел число,
рез цел таб ц[0:9])
дано число > 0
надо | элементы ц[i] показывают, сколько
| раз встречается цифра i в записи
| числа
нач цел i | счетчик для перебора
цел копия, цифра
нц для i<от 0 до 9
| сколько[i] := 0
кц
копия := число
нц пока копия > О
цифра := mod(копия,10)
ц[цифра] :== ц[цифра]+1
копия :== div(копия,10)
кц
кон
алг цел imax (арг цел низ, верх,
цел таб а[низ:верх])
дано
надо | знач = индекс наибольшего элемента
| в таблице а. Если наибольших
| элементов несколько, берется последний
нач цел i
знач :=низ
нц для i от низ+1 до верх
если a[i] >= а[знач]
| то знач := i все
кц
кон
алг цел удалить цифру {арг цел число, цифра)
| вариант 1
дано число > О
надо | знач = число, из которого вычеркнуты
| заданные цифры
нач цел копия, множитель, ц
копия := число
знач := 0
множитель := 1
нц пока копия > 0
ц : = mod(копия,10)
если ц <> цифра
то знач := знач + множитель*ц
множитель := множитель*10
все
копия :== div(копия,10)
кц
кон
алг цел удалить цифру (арг цел число, цифра)
| вариант 2
дано число >= 0
надо | знач = число, из которого вычеркнуты
| заданные цифры
нач цел ц
если число = 0 то знач := 0 иначе
ц :== mod(число,10)
если ц = цифра
то знач := удалить цифру
(div(число,10),цифра)
иначе знач :== удалить цифру
(div(число,10), цифра)*10 + ц
все
все
кон
Контрольные вопросы
Почему в функции imax в сравнении использован знак >= ? Что будет, если заменить ею на > ?
За счет чего в рекурсивном варианте функции "удалить цифру" удалось о6ойтись без множителя и копии? Что их заменяет?
Задачи для самостоятельного решения
1. В заданном натуральном числе поменять местами первую и последнюю цифры.
2. Вывести целое число в столбик, по одной цифре в каждой строке.
3. Переставить цифры заданного числа так, чтобы получилось:
а) наибольшее возможное число;
б) наименьшее возможное число.