Как опознать простое число?
Поскольку простые числа играют очень важную роль в теории чисел, естественный интерес вызывает такая задача: определить, является ли заданное число 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, — составные, их можно вычеркнуть из списка кандидатов. Заметим, что для вычеркивания (здесь вместо вычеркивания используется подчеркивание) всех кратных не нужно производить делений и умножений: достаточно убрать каждое второе число. Список приобретает такой вид (квадратными скобками отмечены простые числа):
[2]
Наименьшее невычеркнутое число — 3. Оно не вычеркуто, следовательно, у него нет простых делителей среди меньших чисел, а значит, это число — простое. Отметим 3 как простое число и вычеркнем из списка все числа, кратные 3, то есть каждое третье число. Некоторые из них уже были вычеркнуты раньше, их можно пропустить или зачеркнуть еще раз.
[2] [3]
После аналогичной обработки пятерки и семерки списки приобретают такой вид:
[2] [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. Такая технология лежит в основе методов объектного программирования.
Сколько существует целых чисел?
Сколько существует целых чисел? Для математика ответ на этот вопрос очевиден: множество целых чисел бесконечно. А вот с точки зрения программиста все обстоит не так просто. Программист рассматривает целые числа как один из типов данных, а любой тип характеризуется в первую очередь множеством значений, которые могут принимать эти данные. На представление целого числа отводится ограниченная память, значит, и множество возможных значений конечно.
В распространенных системах программирования для хранения целых чисел обычно отводится два или четыре байта, то есть 16 или 32 бита. В первом случае можно представить 216 = 65 536 различных чисел, во втором — 232= 4 294 967 296. Таким образом, используя для целого числа 4 байта (что соответствует типу цел в КуМире, longint в Турбо Паскале, long int в Борланд Си), мы можем представить числа от —2 147 483 648 до 2 147 483 647 или, если отказаться от отрицательных чисел, от 0 до 4 294 967 295.
Этого количества (больше 4 миллиардов!) оказывается достаточно для многих задач. Для многих, но не для всех. Иногда нужно обрабатывать числа, которые не входят в этот диапазон. (Программисты обычно говорят, что эти числа не помещаются в разрядную сетку.)
Такие числа мы будем называть "длинными" (не путать со стандартными типами long в Паскале и Си!), а средства работы с ними — "длинной арифметикой".
Как построить "длинное" число?
Вспомним, как в десятичной и других позиционных системах счисления несколько записанных рядом цифр образуют число. Множество возможных значений каждой цифры Ограничено, но за счет позиционного "веса", который зависит от положения цифры, удается с помощью короткой записи представить довольно большие числа.
Попробуем применить этот метод для построения "длинных" чисел. Возьмем массив обычных целых и будем считать его позиционной записью "длинного" числа в системе счисления с некоторым основанием В. Тогда каждый элемент этого массива будет принимать значения от 0 до В — 1, а N таких элементов позволят представить числа от 0 до Bn — 1 (представление отрицательных чисел мы пока не обсуждаем, о выборе конкретных значений В и N поговорим чуть позже).
Фрагменты программ для работы с "длинной арифметикой" мы будем писать на Си. (Вообще-то совсем правильно было бы делать это на Си++ с использованием объектов, но объектный подход — это уже не Буки, а какая-то другая буква, например, Веди или даже Добро программирования.) Считая, что значения В и N уже заданы (например, через # define), определим специальный тип для представления "длинных" целых:
typedef unsigned long item;
typedef item large[N];
Включив эти строки в программу, мы получаем возможность использовать новый тип item. Этот тип будут иметь элементы, составляющие "длинное" число. Сейчас мы задали его как unsigned long. Если нам захочется использовать какой-то другой тип (например, потребуются отрицательные числа), можно будет изменить определение item, но вносить изменения в функции не придется.
Вторая строка определяет тип large, соответствующий массиву из N элементов типа item.
Выделить место для записи "длинного" числа — это еще не все. Надо договориться, как мы будем записывать "длинное" число в массив: с начала или с конца массива, с начала или с конца числа. Чтобы было понятнее, что имеется в виду, все варианты показаны на рисунке для случая N = 6, В == 10, размещаемое число — 2000.
2 0 0 0
(a1) 0 0 0 2
(a2)2 0 0 0
(б1)0 0 0 2
(б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. Сравнение "длинных" чисел.
Приведем соответ
|
