Материалы Роботландского университета 

Я. Н. Зайдельман

Целые числа

Значение и запись числа

А в попугаях я гораздо длиннее.

Г.Остер

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

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

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

Запись числа относительна. Число, которое по-русски называется СЕМЬ, по-английски называется SEVEN. В десятичной системе это число записывается как 7, в троичной — 21, а б двоичной — 111. В римской записи то же самое число выглядит так: VII. Но все эти записи соответствуют одному и тому же количеству. Это и означает, что запись относительна, а количество абсолютно, то есть не зависит от записи.

Рассмотрим, например, два элементарных факта: число 1999 простое, в числе 1999 три девятки. Они относятся к разным объектам: первый характеризует количество, второй — форму записи числа. Тот факт, что число 1999 простое, никак не зависит от того, каким способом мы это число записываем. Это характеристика числа как такового, характеристика количества. А три девятки в этом числе возникают благодаря десятичной записи.

Этот пример еще раз показывает абсолютность количества и относительность записи.

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

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

Целые числа и компьютер

Как представлены числа в компьютере? Что хранится в памяти — число или запись? Ответ на этот вопрос не так прост, как может показаться на первый взгляд.

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

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

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

Правильная программа должна оставаться правильной независимо от внутреннего представления чисел, а значит, она должна иметь дело с числом, а не с его записью.

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

Операции с целыми числами

Ранее (см. № 48/99) мы уже рассматривали понятие типа и в качестве примера приводили как раз тип целых чисел. Вспомним:

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

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

В список допустимых операций для целых чисел входят 5 арифметических операций, 6 сравнений и присваивание.

Включение присваивания в список операций привычно для программистов на Си, но может показаться неожиданным для программистов на Паскале и Бейсике. Сейчас мы не будем анализировать подход к присваиванию как к операции более глубоко, так как для данной темы это не столь существенно, а сам факт того, что присваивание целых чисел возможно, удивления не вызывает, б видов сравнений тоже хорошо известны. Целые числа можно сравнивать на "равно", "не равно", "меньше", "больше", "меньше или равно", "больше или равно". Синтаксис (правила записи) сравнений в разных языках может отличаться (например, "не равно" в Паскале записывается как "<>", в Си — "!=", а в Фортране — ".NE."), но суть от этого не зависит. Важно понимать, что сравнение — это операция. Как и у более привычных нам арифметических операций, у операций сравнения есть операнды (исходные целые числа) и результат, только результат в данном случае имеет не целый, а логический тип.

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

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

Во многих языках целое деление рассматривается как отдельная операция, для которой существует специальное обозначение. Например, во многих версиях Бейсика для этого используется обратная косая черта, а в Паскале — служебное слово div. В КуМире целое деление выполняется с помощью встроенной функции div. Имя этой функции совпадает с именем операции в Паскале, но синтаксис их использования различен.

Таким образом, для выполнения целого деления Х на У в указанных языках необходимо писать следующее:

Бейсик:  X\Y         Паскаль: Х div Y         КуМир:  div (X, Y)

Запись X/Y, использующая обычную операцию деления, недопустима, так как она дает вещественный результат.

Другой подход принят в Си. В этом языке нет специальной операции целого деления, но обычное деление выполняется как целое, если делимое и делитель имеют целый тип. Несмотря на внешнюю простоту и естественность такого решения, оно часто оказывается источником ошибок у начинающих программистов. Например, 1 / 3 в Си дает результат 0, так как 1 и 3 — целые и деление здесь воспринимается как деление нацело. Впрочем, это уже проблемы вещественной арифметики, которые выходят за рамки нашей темы.

Последняя арифметическая операция с целыми числами — остаток от деления. Неформальноё описание этой операции дается в начальной школе: остаток — это то, что остается после деления поровну, то есть, в наших терминах, целого деления.

Более формально деление с остатком можно определить так (запись соответствует синтаксису Паскаля):

Х mod Y = Х - (X div Y) * Y       (1)

Вот как записывается операция остаток в разных языках:

Бейсик и Паскаль: Х mod Y
Си:                          Х % Y
КуМир:                  mod(X, Y)

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

Проблема заключается в том, что единых общепринятых соглашений по этому поводу не существует. Например, в книге "Конкретная математика" (Р.Грэхем, Д.Кнут, ОЛапшшник. Конкретная математика. Основание информатики. М.: Мир, 1998. Я очень рекомендую эту книгу всем, кто не боится математики и всерьез интересуется теоретической информатикой) авторы рекомендуют при выполнении целого деления всегда выполнять округление к меньшему числу, а остаток вычислять по формуле (1), так как этот подход значительно упрощает математические преобразования с использованием этих действий. В частности, знак остатка всегда совпадает со знаком делимого. Однако авторы тут же предупреждают: "Остерегайтесь машинных языков, в которых используется другое определение".

Действительно, в различных системах программирования операции целого деления и остатка работают с отрицательными числами по-разному, причем очень часто эти особенности никак не отражены в описании. Чаще всего округление при делении производится к нулю, то есть в меньшую сторону при положительном результате и в большую при отрицательном. Остаток вычисляется по формуле (1), его знак совпадает со знаком делителя. Именно так работают многие популярные реализации Паскаля, Си, Бейсика.

Совсем необычно подошли к этому вопросу создатели КуМира. В этой системе остаток (он, как обычно, вычисляется по формуле (1))не может быть отрицательным. Поэтому округление производится в меньшую сторону, если делитель положителен, и в большую — если отрицателен. 

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

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

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

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

От числа к записи

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

Во многих системах программирования для такого преобразования существуют специальные встроенные средства. Чаще всего это некие стандартные функции, преобразующие число в строку символов и обратно. Это, например, функции 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. Переставить цифры заданного числа так, чтобы получилось:

а) наибольшее возможное число;

б) наименьшее возможное число.

Некоторые факты из теории чисел

Изучением свойств целых чисел занимается специальный раздел математики — теория чисел. В школе элементы теории чисел обычно изучают в курсе математики 6-го класса и в дальнейшем к ним не возвращаются, в результате к тому моменту, когда школьники начинают заниматься программированием, многое оказывается прочно забыто. Между тем задачи, связанные с теорией чисел, часто встречаются на олимпиадах, и не только на олимпиадах. Например, вся современная криптология (наука о шифрах) основана на теории чисел.

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

Определение 1. Число a называется делителем числа n, если существует такое число b, что
  n =а • b.

Из этого определения немедленно следует, что любое число n, большее 1, имеет как минимум два делителя: единица и само число n.

Определение 2. Число, имеющее ровно два делителя, называется простым.

Определение 3. Число, имеющее больше двух делителей, называется составным.

Заметим, что число 1, имеющее единственный делитель, оказалось особым: оно не относится ни к простым, ни к составным.

Теорема 1. Любое число, большее 1, можно единственным образом представить в виде произведения простых чисел.

Эта теорема (доказывать ее мы не будем) играет очень важную роль в теории чисел. И называется она очень торжественно — "Основная теорема арифметики".

Как опознать простое число?

Поскольку простые числа играют очень важную роль в теории чисел, естественный интерес вызывает такая задача: определить, является ли заданное число n простым или составным.

Очевидный способ решения, который вытекает непосредственно из определения простого числа, — проверить, есть ли у заданного числа делители, отличные от самого числа n и единицы. Если хотя бы один такой делитель найдется — число составное, если нет — простое.

Запишем соответствующую функцию на Турбо Паскале.

function isPrime ( n: word): boolean; {версия 1}

 {Функция проверяет, является ли заданное число простым. Возвращает true для

простого числа, false - для составного. Предполагается, что n >1}

var d: word ; { очередной делитель }

 begin  
      d:=2;  
       while n mod d <> 0 do d:= d+l;

       isPrime: = (d=n)
   end;

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

Контрольные вопросы

Как будут исполняться вызовы isPrime (1) и isPrime (0) ? Каким, на ваш взгляд, было бы разумное поведение функции в этих случаях?

Упражнение

Внесите в функцию исправления, чтобы она корректно работала при некорректных входных данных.

Написанная нами функция работает правильно, но очень медленно. Чтобы определить, что число n — простое, приходится выполнить n—1 операцию деления. Попробуем как-то уменьшить количество этих проверок.

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

function isPrime (n: word): boolean; {версия 2}

{Функция проверяет г является ли заданное число простым.
 Возвращает true для простого числа, false - для составного. Предполагается, что n>1}

 var d: word;   {очередной делитель}

begin  
   d:=2;
   while (d <= n div 2) and (n mod d <> 0) do d:=d + l ;  
   isPrime: =(d > n div 2)
   end;

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

Контрольные вопросы.

Как будут выполняться вызовы isPrime (1) и isPrime (0) для новой версии функции?

Можно ли записать последнюю проверку таким образом: isPrime := (n mod d <> 0) ?

Попробуем найти пути дальнейшего сокращения перебора. Из определения делителя вытекает, что делители существуют парами. Если n = a* b, то а и b — делители n. Пусть а — меньший из этих делителей. Тогда должно выполняться соотношение а < sqrt(n) < b.

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

Итак, каждому делителю, меньшему sqr(n), соответствует парный делитель, больший sqr(n). Отсюда следует, что поиск делителей можно вести не до n/2, а до sqr(n), так как если среди чисел, меньших sqr(n), делители не найдены, то и дальше их заведомо нет. Получаем очередной вариант функции.

function isPrime (n:word): boolean; {версия 3}

{Функция проверяет, является ли заданное число n простым. Возвращает true для простого числа, false - для составного.Предполагается, что n>1}

var d: word; {очередной делитель}                                  

begin                           

        d:=2 ;

        while (d*d <= n) and (n mod d <> 0) do d:=d+l;

        isPrime:=(d*d > n)

 end;

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

Контрольные вопросы

Почему сравнение (d*d< n) сделано нестрогим? Что изменится, если заменить его на строгое?

Итак, нам удалось сократить количество проверок в худшем случае от n—1 до sqrt(n) —1. Попробуем поискать пути дальнейшего сокращения.

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

А вот нечетные числа могут проверяться довольно долго. И половина проверок при этом оказывается бессмысленной: ведь четные числа заведомо не могут быть делителями нечетных!

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

function isPrime (n: word) : boolean; {версия 4}

{Функция проверяет, является ли заданное число простым. Возвращает true для простого числа, false - для составного. Предполагается, что n>1}

var d: word;   {очередной делитель} 
begin
    if not odd(n) then isPrime:=(n=2)
       {2 - единственное простое среди четных чисел}
    else begin
      d:=3;
      while (d*d <= n) and (n mod d <> 0)
         do d:=d+2;  
         isPrime:=(d*d > n)
 end
end;

Исключив из числа кандидатов в делители четные числа, мы сократили перебор вдвое. Но и это еще не предел. Из числа нечетных кандидатов можно исключить кратные трем числа 9, 15, 21 и т.д. Ясно, что если какое-то из них окажется делителем, то делителем будет и 3, что обнаружится намного раньше. Попробуем проверить делимость на 3 отдельно (как это только что было сделано с двойкой), а затем исключить кратные трем делители из списка проверяемых.

Тогда список кандидатов в делители будет выглядеть так: 5, 7, 11, 13, 17, 19... Разность между двумя соседними числами в этом списке непостоянна, значит, возникает проблема перехода к следующему делителю. Простой способ справиться с этой сложностью представлен в следующей версии функции.

function isPrime (n: word): boolean; {версия 5}

{Функция проверяет, является ли заданное число простым. Возвращает true для простого числа, false - для составного. Предполагается, что n>1}

var d: word; {очередной делитель}
dd: word; {шаг перехода к следующему делителю}
 begin  
    if not odd(n) then isPrime:=(n=2)
       {2 - единственное простое среди четных чисел}
    else if n mod 3=0 then isPrime := (n=3)
     else begin
         d:=5; dd:=2;  
         while (d*d <= n) and (n mod d <> 0) do begin
            d:=d+dd;  
            dd:=6-dd
            {шаг перехода поочередно равен 2 и 4}
end;  
 isPrime:=(d*d > n)
end
end;

В принципе подобную тактику можно продолжить: исключить вслед за кратными 2 и 3 делители, кратные 5, 7, следующим простым числам. Но каждое такое исключение дает все меньший эффект (из проверки исключается меньшее число кандидатов) и приводит к все более громоздкой программе. Поэтому лучше всего вовремя остановиться.

Задачи на результат

(Предисловие для учителя)

Рассмотрим такую задачу. Необходимо получить все простые числа из диапазона от 1 до как можно большего числа N. Очевидно, что для небольших N задача легко решается вручную. С помощью несложной программы можно решить эту задачу для N порядка нескольких тысяч. Для дальнейшего увеличения N необходимо применять все более изощренную технику программирования.

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

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

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

Таблица простых чисел

Попробуем построить таблицу простых чисел, то есть выписать все простые числа из диапазона от 1 до некоторого N.

(Выписать действительно ВСЕ простые числа невозможно, так как их бесконечно много. Этот факт, известный еще древнегреческим математикам, доказывается совсем несложно.

Предположим, что множество простых чисел конечно. Рассмотрим число S = р1 • р2 • ... • рk где p1 — первое простое число, р2 — второе, рk — последнее наибольшее простое число. Очевидно, что 5 делится на все простые числа.

Рассмотрим теперь число S + 1. При делении на любое простое число оно дает остаток 1. то есть не делится ни на одно из них. Но если рk — наибольшее простое число, то любое число, большее рk, должно делиться на одно из чисел p1 ,p2,...,pk.

Получили противоречие. Следовательно, наибольшего простого числа не существует.)

Простейший способ решения нашей задачи — воспользоваться уже имеющейся функцией is- Prime, перебрать все числа из заданного диапазона и выписать те, которые окажутся простыми.

procedure findPrimes (n: word); {версия 1}

 {Процедура выводит список всех простых чисел из диапазона от 1 до n}

var i: word; {очередной кандидат в простые числа}       

 begin

         for i:=2 to n do begin

        if isPrime(i) then writeln(i)

end

end;

Контрольный вопрос

Почему в комментариях к функции говорится, что она находит простые числа в диапазоне от 1, а перебор в теле функции начинается со значения i = 2?

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

procedure findPrimes (n: word); {версия 2}

{Процедура выводит список всех простых чисел из диапазона от 1 до n}

var i: word; {очередной кандидат в простые числа}        

ii: word; {шаг перехода к очередному числу}          

begin

             if n>=2 then writeln(2);{2 и 3 — заведомо простые числа}

             if n>=3 then writeln(3);

               i:=5; ii:=2;

                while i<=n do begin

                      if isPrime(i) then writeln(i);

                      i:=i+ii;

                  ii:=6-ii

         end

end;

На самом деле реальное сокращение при такой оптимизации оказывается довольно мало. Дело в том, что последняя версия функции isPrime очень быстро обрабатывает числа, кратные 2 и 3, поэтому, исключив из рассмотрения именно эти числа, мы фактически выигрываем только то время, которое уходит на вызов функции и возврат результата.

Поскольку версия 2 процедуры findPrimes никогда не вызывает функцию isPrime для чисел, кратных 2 и 3, можно упростить саму функцию, удалив из нее ненужные проверки.

function isPrime (n: word): boolean; {версия 6}

var d: word; {очередной делитель}                                   

dd: word; {шаг перехода к следующему делителю}

begin

       d:=5; dd:=2;

          while (d*d <= n) and (n mod d <> 0) do begin

          d:=d+dd;

          dd:=6-dd

       {шаг перехода поочередно равен 2 и 4}

   end;

  isPrime:=(d*d > n)

end;

Упражнения

1. Восстановите вступительный комментарий этой функции. Будьте внимательны! Он не совпадает с тем, который был в предыдущих версиях!

2. Сравните две последние (5-ю и 6-ю) версии функции isPrime. Какая из них работает быстрее? Какая универсальнее? Опишите круг задач, для решения которых подходит каждая из этих версий.

Как сократить количество проверок?

Работая над функцией isPrime, мы добились некоторого ускорения, исключив заведомо составные делители, кратные 2 и 3. В принципе можно было продолжить подобное исключение, но каждый следующий шаг на этом пути давал бы все меньший эффект (подумайте, почему) и делал бы программу все более громоздкой.

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

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

var prime: array [1..NMAX] of word;

{список простых чисел}

 np: word;

{количество реально найденных простых чисел}

procedure put (n: word);

{Процедура заносит число n в массив prime}

begin

     np:=np+l;

     prime[np]:=n

end;

function isPrime (n:word): boolean; {версия 7}

{Функция проверяет, является ли простым число п. 
Для проверки используется таблица уже найденных простых чисел}

var i: integer; {индекс очередного делителя}

begin

     i: =l;

     while (i <= np) and (sqr(prime[i]) <= n) and (n mod prime[i] <> 0) do i:=i+l;

     isPrime:=(i> np) or (sqr(prime[i]) > n)

end;

procedure findPrimes (n: word); {версия 3}

{Процедура заполняет массив prime простыми числами из диапазона от 1 до n, но не более NMAX простых чисел.}

var i: word;

{очередной кандидат в простые числа}

      ii: word;

{шаг перехода к очередному числу}

begin

nр: =0; {простых чисел еще нет}

 if n>=2 then put (2);

{2 и 3 — заведомо простые числа}

   if n>=3 then put (3) ;

   i:=5; ii:=2;

  while (i<=n) and (np < NMAX) do begin

  if isPrime(i) then put(i);

  i:=i+ii;

 ii:=6-ii

 end

 end;

Отвлечемся на время от общих вопросов и обратим внимание на некоторые детали этой программы с точки зрения языка программирования. (Здесь мы переходим с уровня П на уровень ЯП — помните разговор о трех уровнях в самом начале наших занятии?)

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

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

При программировании в стиле "классического Паскаля" put и isPrime можно было бы сделать внутренними процедурами в findPrimes. Однако личный вкус автора этого текста (основанный на традициях многих языков программирования, не допускающих подобного вложения, и некоторых общих соображениях стиля програмирования) не позволяет ему использовать эту возможность.

Упражнения

(Этот набор упражнений предназначен в первую очередь для тех, кто программирует в системе Turbo Pascal. Остальным предлагаем "перевести" последнюю программу на ваш язык программирования и исследовать ее работоспособность.)

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

2. Как известно, максимально допустимое значение для типа word равно 65 535. Однако функция findPrimes нормально работает только при n< 65 532, а дальше начинает вести себя очень странно. Разберитесь, в чем причина этого явления. Попробуйте исправить эту ошибку. Найдите подобную ошибку в ранее написанных программах.

3. Как можно увеличить диапазон поиска простых чисел в этой программе?

Решето Эратосфена

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

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

Очевидно, что первое число в этом списке — простое, так как у него заведомо нет никаких меньших его делителей, кроме 1. Итак, 2 — простое число. Тогда все числа, кратные 2, — составные, их можно вычеркнуть из списка кандидатов. Заметим, что для вычеркивания (здесь вместо вычеркивания используется подчеркивание) всех кратных не нужно производить делений и умножений: достаточно убрать каждое второе число. Список приобретает такой вид (квадратными скобками отмечены простые числа):

Наименьшее невычеркнутое число — 3. Оно не вычеркуто, следовательно, у него нет простых делителей среди меньших чисел, а значит, это число — простое. Отметим 3 как простое число и вычеркнем из списка все числа, кратные 3, то есть каждое третье число. Некоторые из них уже были вычеркнуты раньше, их можно пропустить или зачеркнуть еще раз.

После аналогичной обработки пятерки и семерки списки приобретают такой вид:

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

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

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

program sievel;

{Решето Эратосфена.Версия 1: исходное решето содержит все числа от 2 до N}

 const N==64813;

var p: array [2..N] of boolean;

    i,j: word;

begin

   for i:=2 to N do p[i]:=true;

     for i:==2 to N do begin if p[i] then begin

              write (i:8) ;

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

               j:=i;

         while (j<=N-i) do begin

        j:=j+i;

        p[j]:=false

             end

       end

end;

writein

 end.

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

Попробуем вычеркнуть четные числа заранее и не тратить на них драгоценное место в памяти. Тогда первый элемент массива будет соответствовать числу 3, второй — 5 и т.д. Элемент с номером i будет соответствовать числу k =2i + 1.

Разберемся теперь, как быть с вычеркиваниями. Если число k оказалось простым, надо вычеркнуть все числа с шагом k. Поскольку четным числам не соответствуют элементы массива, вычеркивать надо нечетные числа с шагом 2k, что соответствует вычеркиванию элементов массива с шагом k. (Чтобы лучше разобраться в этой логике, попробуйте вручную построить решето Эратосфена без четных чисел.)

program sieve2;

{Решето Эратосфена.Версия 2: исходное решето содержит только нечетные числа}

const N=64808;

var p: array [1..N] of boolean;

                i,j: word;

                k: longint;

begin

             for i:=l to N do p[i]:=true;

                write(2:8) ;

{2 — простое число, его нельзя забывать}

             for i:=l to N do begin

                   if p[i] then begin 

                   k:=2*longint (i)+l;

                      write(k:8) ;

                      j:=i;

                      while (j<==N-k) do begin

                                 j:=j+k;

                                p[j]:=false

            end

        end

     end;

writeln

end.

Итак, не запрашивая дополнительную память и почти не усложняя программу, мы вдвое увеличили диапазон поиска!

Для дальнейшего повышения эффективности нам придется перейти на уровень РЯП — реализации языка программирования — и учесть конкретные особенности Тубо Паскаля.

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

К сожалению, мы все еще очень неэффективно используем память. Дело в том, что каждый элемент типа boolean занимает 1 байт, хотя требуется всего 1 бит. Получается, что реально используется только восьмая часть памяти! (В классическом Паскале предполагалось, что массивы, описанные как packed, будут максимально экономно использовать память. Однако в системе Турбо Паскаль слово packed игнорируется.)

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

Однако базовый размер множеств в Турбо Паскале ограничен: никакое множество не может содержать больше 256 элементов. Следовательно, одним множеством обойтись не удастся, но можно использовать массив множеств. Если каждое множество содержит Size элементов, и таких множеств N, то они образуют псевдомассив из N* Size элементов.

program sieve3;                         

{Решето Эратосфена.Версия 3: представление с помощью массива множеств}

const NN=64804; {количество множеств}

 Size=8; {количество элементов в каждом множестве}

 N=NN*Size-l;

{элементы псевдомассива пронумерованы от 0 до N}

 type bits =.array[0..NN-1] of set of 0..Size-1;

procedure init (var p:bits);

{Заполнить псевдомассив значениями true}

var i:word;

begin

       for i:=0 to NN do p[i]:=[0..Size-1]

 end;

       function get (var p:bits; i:longint): boolean;

{Функция возвращает элемент псевдомассива р с индексом i}

begin

       get:=(i mod Size) in p[i div Size]

end;

procedure put (var p:bits; i:longint; value:boolean);

{Записать в элемент псевдомассива р с индексом i значение value. Параметр р описан как var, чтобы избежать переполнения стека}

 var ii:word;

begin

ii: = i div Size;

        if value then p [ii] :==p [ii] + [i mod Size] else p[ii]:=p[ii] — [i mod Size]

         end

     end;

var p: bits; {псевдомассив} i,j,k: longint;

begin

      write(2:8) ;

        init(p) ;

        for i:=0 to N do begin

                if get(p,i) then begin 

                k:=2*i+3;

                write(k:8) ;

                j:=i;

                while (j<=N-k) do begin

                        j:=j+k;

                        put (p,j,false)

            end

         end

     end;

    writeln

end.

Эта программа еще в 8 раз по сравнению с предыдущей расширила диапазон поиска. Правда, для этого нам пришлось использовать множества — довольно экзотическую возможность Паскаля. Нельзя ли обойтись без них и получить программу, пригодную для перевода на другие языки? Конечно же, можно! Ведь множества Паскаля — это не что иное, как набор битов, и все операции с множествами сводятся к манипуляции битами, а битовые операции встречаются в языках программирования чаще, чем множества. Есть они и в Турбо Паскале. Перепишем программу, заменив множества на непосредственные операции с битами.

program sieve4;

{Решето Эратосфена.Версия 4: использование битовых операций}

        const NN=64804;    {количество байт}

        Size=8;      {количество бит в байте}

        N==NN*Size-l; {элементы псевдомассива пронумерованы от 0 до N}

type bits = array[0..NN-1] of byte;

procedure init (var p:bits);

{Заполнить псевдомассив значениями true}

var i:word;

begin

for i:=0 to NN do p[i]:=255

end;

function get (var p:bits;i:longint): boolean;

{Функция возвращает элемент псевдомассива р с индексом i}

begin

      get := (p[i div Size]  and (1 shi (i mod Size))) <> 0

end;

procedure put (var p:bits; i:longint;value:boolean);

{Записать в элемент псевдомассива р с индексом i значение value. Параметр р описан как var, чтобы избежать переполнения стека}

 var ii:word;

begin

       ii:=i div Size;

          if value then p[ii]:=p[ii] or (1 shi (i mod Size)) else p[ii]:=p[ii] and not (1 shi (i mod Size))

        end

    end;

var p: bits; {псевдомассив}

   i,j,k: longint;

begin

write (2:8) ;

    init(p);

    for i:=0 to N do begin

        if-get(p,i) then begin

        k:=2* i+3;

        write(k:8);

        j:=i;

        while (j<=N-k) do begin

            j:=j+k;

            put(p,j,false)

            end

        end

    end;

writein

end.              .     .

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

Обратите внимание, что текст основной программы полностью сохранился. Изменились только описание типа bits и работающие с ним процедуры. Таким образом, основная программа получилась независимой от конкретного способа реализации псевдомассива типа bits. Такая технология лежит в основе методов объектного программирования.

Сколько существует целых чисел?

Сколько существует целых чисел? Для математика ответ на этот вопрос очевиден: множество целых чисел бесконечно. А вот с точки зрения программиста все обстоит не так просто. Программист рассматривает целые числа как один из типов данных, а любой тип характеризуется в первую очередь множеством значений, которые могут принимать эти данные. На представление целого числа отводится ограниченная память, значит, и множество возможных значений конечно.

Этого количества (больше 4 миллиардов!) оказывается достаточно для многих задач. Для многих, но не для всех. Иногда нужно обрабатывать числа, которые не входят в этот диапазон. (Программисты обычно говорят, что эти числа не помещаются в разрядную сетку.)

Такие числа мы будем называть "длинными" (не путать со стандартными типами long в Паскале и Си!), а средства работы с ними — "длинной арифметикой".

Как построить "длинное" число?

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

Попробуем применить этот метод для построения "длинных" чисел. Возьмем массив обычных целых и будем считать его позиционной записью "длинного" числа в системе счисления с некоторым основанием В. Тогда каждый элемент этого массива будет принимать значения от 0 до В — 1, а N таких элементов позволят представить числа от 0 до Bⁿ — 1 (представление отрицательных чисел мы пока не обсуждаем, о выборе конкретных значений В и N поговорим чуть позже).

Фрагменты программ для работы с "длинной арифметикой" мы будем писать на Си. (Вообще-то совсем правильно было бы делать это на Си++ с использованием объектов, но объектный подход — это уже не Буки, а какая-то другая буква, например, Веди или даже Добро программирования.) Считая, что значения В и N уже заданы (например, через # define), определим специальный тип для представления "длинных" целых:

typedef unsigned long item;

typedef item large[N];

Включив эти строки в программу, мы получаем возможность использовать новый тип item. Этот тип будут иметь элементы, составляющие "длинное" число. Сейчас мы задали его как unsigned long. Если нам захочется использовать какой-то другой тип (например, потребуются отрицательные числа), можно будет изменить определение item, но вносить изменения в функции не придется.

Вторая строка определяет тип large, соответствующий массиву из N элементов типа item.

Выделить место для записи "длинного" числа — это еще не все. Надо договориться, как мы будем записывать "длинное" число в массив: с начала или с конца массива, с начала или с конца числа. Чтобы было понятнее, что имеется в виду, все варианты показаны на рисунке для случая N = 6, В == 10, размещаемое число — 2000.

 (a1)

 (a2)

(б1)

(б2)

Еще одна проблема — заполнение неиспользуемых разрядов. На рисунках они обозначены пустыми клетками, а мы должны решить, как будут кодироваться эти пустые клетки.

Обычно в подобных ситуациях применяется одно из следующих решений:

1) Каждому " длинному" числу соответствует целая переменная — счетчик, показывающий, сколько элементов массива реально использовано.

2) Неиспользованные разряды заполняются значением, которое заведомо не может встретиться в числе, например, —1.

3) Неиспользованные разряды заполняются нулями и обрабатываются наравне с использованными. Этот вариант возможен, только если заполнение массива ведется по схеме al или 62.

Любой возможный выбор имеет свои достоинства и недостатки. Мы будем использовать заполнение массива по схеме б2 и обработку неиспользованных разрядов по варианту 3.

Упражнение

Проанализируйте возможные другие варианты, укажите, чем они лучше и чем хуже выбранного.

Методическое отступление для учителя

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

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

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

Операции с "длинными" числами

Запрограммируем основные операции с "длинными" числами. Каждую операцию .будем описывать как отдельную функцию.

1. Взаимное преобразование обычных и "длинных" чисел.

Часто бывает нужно выполнять "длинные" вычисления, в которых исходные данные представлены обычными целыми числами. Для этого нужно сначала преобразовать обычное число в "длинное".

Прототип соответствующей функции хотелось бы записать так:

large item21arge (item) ;

К сожалению, в классическом Си это невозможно. Во-первых, массив не может быть результатом функции. Во-вторых, возникают проблемы с выделением памяти для хранения результата.

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

void item21arge (item, large) ;

Обратное преобразование можно представить обычной функцией. Ее прототип:

item large2item (large);

Упражнение

Напишите функции по заданным прототипам.

Подсказка. Эта задача очень похожа на преобразование числа в строку и обратно,

2. Сложение и вычитание "длинных" чисел.

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

Как и в случае с функцией item21arge, мы вынуждены программировать функцию с фиктивным результатом, а настоящий результат передавать в качестве дополнительного параметра.

void largeadd (large a, large b/ large sum)

/* Сложение "длинных" чисел, sum == a+b */

 {int i.; /* счетчик разрядов */ 
      item carry=0;
      /* перенос в следующий разряд */

for (i=0; i<N; i++)

{   sum[i]=a[i]+b[i]+carry;
     carry=sum[i]/B;
      sum[i] %==B; }
}

Контрольные вопросы

1. Что изменилось бы в этой функции, если бы мы приняли другое решение о представлении "длинных" чисел?

2. Что произойдет, если сумма а [ i ] +b [ i ] окажется больше максимально допустимого значения типа item? Как можно избежать этой ситуации?

3. Что произойдет, если сумма окажется больше максимально допустимого значения для "длинного" числа? Можно ли избежать этой ситуации?

4. Будет ли функция корректно работать при вызове largeadd (х, у, х) ? А при вызове largeadd (х, х, х) ?

Упражнение

Разработайте функцию, выполняющую вычитание "длинных" чисел.

3. Сравнение "длинных" чисел.

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

int largecmp (large a, large b)

 /* Сравнение "длинных" чисел. Результат функции отрицателен, если а < b, положителен, если а > b, равен нулю, если а = b */

{int i;
   for (i=N-l; i>0 && a[i]==b[i]; i--) ;

return a[i]-b[i];
}

Контрольные вопросы и упражнения

1. Почему перебор производится с конца массива?

2. Почему использовано сравнение i>0,a не i>=0 ?

3. Напишите функцию largeicmp, сравнивающую "длинное" число с обычным.

4. Умножение "длинного" целого на обычное целое.

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

void largeimul (large a, int b)

 /* Умножение "длинного" целого на обычное.а*= b */

 {int i;      
 /* счетчик разрядов */
item carry=0;  
  /* перенос в следующий разряд */
  for (i=0; i<N; i++)
  { a [i] ==a [i] *b+carry;  
     carry=a[i]/B;
      a[i]%=B;
   }
}

5. Деление "длинного" целого на обычное целое.

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

item largeidiv (large a, item d)

 /* Деление "длинного" целого на обычное с остатком. a/==d. Результат функции — остаток от деления */

{ int i;item carry=0;

for (i==N-l; i>=0; i--)

 { a[i]+=B*carry;
   carry = a[i]%d;  
   a[i]/=d; } 
return carry;
}

Контрольный вопрос

В правильном "длинном" числе все элементы массива должны быть меньше основания системы счисления В. Докажите, что функция деления сохраняет это свойство.

6. Умножение "длинных" целых.

Умножение "длинных" чисел можно реализовать все по той же схеме "столбика". Попробуйте самостоятельно запрограммировать такую функцию.

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

Метод быстрого умножения основан на следующих соотношениях: Если b — четное число, то

а*b= (2а)*(b/2)     .          (1)

Если b — нечетное число, то

а*b== а+ а* (b-1)              (2)

Чтобы лучше понять работу метода, применим его сначала для умножения обычных, не "длинных" чисел, считая, что обычная операция умножения по каким-то причинам недоступна.

unsigned long mult (unsigned long a,   
                            unsigned long b)
/* Быстрое умножение a*b с помощью небольшого числа сложений */
  { unsigned long s=0;
    /* собственно произведение */
     while (b>0)
     /* Инвариант: искомое произведение р = s + a*b */
      if (b%2) { a+=a; b/=2; }
      else     { s+=a; b--; } 
     return s;  
}

На первый взгляд эта функция выполняет какие-то странные действия, трудно поверить, что результатом будет произведение чисел а и b. Однако несложный анализ позволяет убедиться, что это действительно так.

Обратите внимание на соотношение р = s + а • b. Это, — инвариант цикла, то есть условие, которое выполнено при каждом исполнении цикла. При первом исполнении инвариант, очевидно, верен: в этот момент s = 0, а и b сохраняют свои первоначальные значения. Последующие преобразования выполняются в соответствии с ранее записанными правилами (1) и (2), которые сохраняют справедливость инварианта. Когда цикл завершится (подумайте, почему это обязательно произойдет?), будет выполнено условие b = 0. В сочетании с инвариантом это дает р = s , следовательно, переменная s действительно будет содержать искомое произведение.

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

void largemult (large a, large b/ large s)
  /* Быстрое умножение "длинных" чисел
      s == а * b
   !! Внимание !!
   Исходные данные (а и b) изменяются в процессе вычислений. 
    Если нужно сохранить исходные
    значения, перед умножением следует сделать копию. */   
  { item2large (0,s);  
    while (largeicmp(b,0))  
     /* Инвариант: искомое произведение р = s + a*b */
       if (largeidiv(b,2)) largeadd(s,a,s);  
      largeadd(a,a,a);

}

 Контрольные вопросы и упражнения

1. Почему функция largemuIt "портит" значения своих аргументов, а в функции mult этого не происходит?

2. Перепишите функцию largemuIt так, чтобы аргументы не изменялись.

7. Ввод и вывод "длинных" целых.

До сих пор мы рассматривали "внутренние" операции с "длинными" числами. Их список получился неполным, но общий принцип ясен, и при необходимости набор функций можно; легко дополнить.

Однако, чтобы обеспечить действительно полный набор возможностей, одних внутренних преобразований недостаточно. Надо еще уметь вводить и выводить "длинные" числа.

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

Очевидно, что это преобразование существенно упрощается, если В — точная степень десяти. Напишем, например, функцию вывода "длинного" числа при В = 10.

void largeprinti (large a)

/* Вывод "длинного" числа, записанного по основанию В=10 */

{ int i;

/* пропускаем незначащие ведущие нули */

for (i=0; i.<N-1 && a[i]=0; i++) ;

/* выводим значащие цифры */

for (; i<N; i++) printf("%d",a[i]);

}

Контрольный вопрос

Что произойдет, если "длинное" число окажется равным нулю?

Итак, если записывать "длинные" числа в десятичной системе, их вывод программируется очень просто. Но 10 — очень маленькое основание. При В = 10 для хранения больших чисел придется брать очень большое N, что значительно увеличит время работы всех функций.

Если взять В =10^k, в каждом элементе "длинного" числа поместится k десятичных цифр. Это позволит в k раз уменьшить значение N для представления того же диапазона "длинных" чисел, что существенно ускорит время вычисление.

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

С учетом этих ограничений получаем, что при 32-разрядных элементах "длинного" числа наиболее удобное значение В =10⁵=10 000, то есть в каждом элементе "длинного" числа хранится по 4 десятичные цифры.

Казалось бы, для вывода "длинных" чисел с основанием 10 000 можно использовать уже написанную функцию largeprint1. Но для некоторых чисел результат будет получаться неправильным. (Прежде чем читать дальше, подумайте, в каких случаях это будет происходить.)

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

void largeprint5 (large a)

/* Вывод "длинного" числа, записанного по основанию В=10000 */

{ int i;

/* пропускаем незначащие ведущие нули */

for <i==0; i<N-l && a[i]==0; i++) ;

/* старшую цифру выводим без ведущих нулей */

printf("%d",a[i]);

/* выводим остальные цифры с ведущими нулями*/

for (i++; i<N; i++) printf("%04d",a[i]); }

Упражнение

Напишите функцию для ввода "длинного" числа.

Задачи для самостоятельного решения

1. Напишите функцию для возведения натурального числа в натуральную степень. Основание и показатель степени не превосходят 10 000. Постарайтесь обойтись как можно меньшим числом умножений.

(Подсказка. Алгоритм быстрого возведения в степень можно получить из алгоритма быстрого умножения, заменив сложение умножением.)                    ;

2. "Длинное" число записано в массив, по 4 десятичные цифры в каждом элементе (В = 10 000). Требуется сформировать "длинное" число, которое получится, если записать исходное десятичное число задом наперед.

3. Разработайте функции ввода и вывода "длинных" чисел для случая, когда параметр В не является степенью числа 10.