БОЛЬШИЕ и длинные целые числа Поздняков Сергей Николаевич, профессор СПбГЭТУ (ЛЭТИ) - презентация

1 БОЛЬШИЕ и длинные целые числа Поздняков Сергей Николаевич, профессор СПбГЭТУ (ЛЭТИ)

2 Сколько символов нужно, чтобы представить большое число? Древние Египет и Вавилон

3 Древний пастух и единичная система счисления

4 Арифметика единичной системы Умножать тоже нетрудно, Умножать тоже нетрудно, например, так можно три умножить на четыре х Но! Чтобы записать число атомов во Вселенной понадобилось бы использовать сами эти атомы для записи их числа! Но! Чтобы записать число атомов во Вселенной понадобилось бы использовать сами эти атомы для записи их числа! Складывать легко: = Складывать легко: =

5 РИМСКАЯ СИСТЕМА СЧИСЛЕНИЯ В Римской системе счисления дела уже лучше. В ней числам пять, десять, пятьдесят, сто, пятьсот, тысяча уже сопоставляются отдельные символы, которые дополняются справа или слева, обозначая добавление или вычитание. В Римской системе счисления дела уже лучше. В ней числам пять, десять, пятьдесят, сто, пятьсот, тысяча уже сопоставляются отдельные символы, которые дополняются справа или слева, обозначая добавление или вычитание. Однако, вообще говоря, требуется неограниченное число цифр. Сколько символов нужно для записи 444? (CDXLIV) Сколько символов нужно для записи 444? (CDXLIV) Сколько символов нужно для записи 555? (DLV) Сколько символов нужно для записи 555? (DLV) Сколько символов нужно для записи 666? (DCLXVI) Сколько символов нужно для записи 666? (DCLXVI) Сколько символов нужно для записи 777? (DCCLXXVII) Сколько символов нужно для записи 777? (DCCLXXVII) Сколько символов нужно для записи 888? (DCCCLXXXVIII) Сколько символов нужно для записи 888? (DCCCLXXXVIII) Сколько символов нужно для записи 999? (CMXCIX) Сколько символов нужно для записи 999? (CMXCIX) Сколько символов нужно для записи 1000? (M) Сколько символов нужно для записи 1000? (M) Сколько символов нужно для записи 10000? (MMMMMMMMMM) Сколько символов нужно для записи 10000? (MMMMMMMMMM) (скрипт для перевода в Римскую систему счисления и обратно)

6 ПОПРОБУЕМ УМЕНЬШИТЬ ЧИСЛО ЦИФР ЗА СЧЁТ УЧЁТА ИХ ПОЛОЖЕНИЯ В ЗАПИСИ ЧИСЛА CD XL IV ab ab ab D L V b b b DC LX VI ba ba ba DCC LXX VII baa baa baa DCCC LXXX VIII baaa baaa baaa CM XC IX ac ac ac 1 – a 2 – aa 3 – aaa 4 – ab 5 – b 6 – ba 7 – baa 8 – baaa 9 – ac 10 – c Закодируем группы символов

7 Позиционная система счисления Что означает запись ? Что означает запись ? Это число: Это число: 2* * * * * Что означает десятичная запись Что означает десятичная запись N= a n a n-1 …a 1 a 0 ? Это число: Это число: a n *10 n + a n-1 *10 n-1 + …+a 1 * a 0 *10 0 a n 0; 0 a i

8 p-ичная система счисления p-ичная запись p-ичная запись N= a n a n-1 …a 1 a 0 ? Это число: Это число: a n *p n + a n-1 *p n-1 + …+a 1 *p 1 + a 0 *p 0 a n 0; 0 a i < p

9 ТАБЛИЦЫ СЛОЖЕНИЯ И УМНОЖЕНИЯ Мы владеем алгоритмами работы с записями чисел в десятичной системе счисления на уровне навыков, то есть, выполняем их, не думая Мы владеем алгоритмами работы с записями чисел в десятичной системе счисления на уровне навыков, то есть, выполняем их, не думая Выделим эти алгоритмы. Выделим эти алгоритмы. Но сначала надо заново выучить таблицу умножения. *4*4*4*

10 Алгоритм сложения __297 __ __232 __ В десятичной системе В четверичной системе s:=0 (перенос разряда) ЦИКЛ ПО i от 0 до n c i :=a i +b i +s mod p c i :=a i +b i +s mod p s:=a i +b i +s div p s:=a i +b i +s div pКЦ ЕСЛИ s 0 ТО c n+1 :=s

11 Алгоритм умножения на цифру * * ____ 7 ____ * ____2 ____ В десятичной системе В четверичной системе s:=0 (перенос разряда) ЦИКЛ ПО i от 0 до n c i :=a i *b k +s mod p c i :=a i *b k +s mod p s:=a i *b k +s div p s:=a i *b k +s div pКЦ ЕСЛИ s 0 ТО c n+1 :=s

12 Умножение на p k * * __100 __ * __ 100 __ В десятичной системе В четверичной системе ЦИКЛ ПО i от 0 до n c i+k :=a i c i+k :=a iКЦ ЦИКЛ ПО i от 0 до k-1 c i :=0 c i :=0КЦ

13 Умножение длинных чисел Сводится к трём описанным алгоритмам: Сводится к трём описанным алгоритмам: c:=0 ЦИКЛ ПО k от 0 до n c:=c+a*b k *p k c:=c+a*b k *p kКЦ

14 Первый алгоритм перехода к новому основанию – схема Горнера N p =a n *p n + a n-1 *p n-1 + …+a 1 *p 1 + a 0 *p 0 = =(…(a n *p+ a n-1 )*p+ …+a 1 )*p+ a 0 = =(…(a n *p+ a n-1 )*p+ …+a 1 )*p+ a 0 = умножения и сложения делаем в q-ичной системе =b m *q m + b m-1 *q m-1 + …+b 1 *q 1 + b 0 *q 0 =N q =b m *q m + b m-1 *q m-1 + …+b 1 *q 1 + b 0 *q 0 =N q Np:Np:Np:Np: anananan a n-1 … a K-1 aKaKaKaK… a0a0a0a0 anananan a n *p+ a n-1 …S S*p+ a k … NqNqNqNq N 3 =(12102) N 4 =(2102) 4 Пример: умножаем и складываем в четверичной системе

15 Второй алгоритм перехода к новому основанию – делением N p =a n *p n + a n-1 *p n-1 + …+a 1 *p 1 + a 0 *p 0 = =(…(a n *p+ a n-1 )*p+ …+a 1 )*p+ a 0 = =(…(a n *p+ a n-1 )*p+ …+a 1 )*p+ a 0 = =b m *q m + b m-1 *q m-1 + …+b 1 *q 1 + b 0 *q 0 =N q =b m *q m + b m-1 *q m-1 + …+b 1 *q 1 + b 0 *q 0 =N q ЦИКЛ ПОКА N 0 очередная цифра с конца := N mod q очередная цифра с конца := N mod q N := N div q N := N div qКЦ деления делаем в p-ичной системе

16 Пример решения той же задачи другим алгоритмом |11__ | | |11 11__ |11 11__ |

17 Смешанная система счисления Шел Кондрат В Ленинград, А навстречу двенадцать ребят. У каждого по три лукошка, В каждом лукошке кошка, У каждой кошки двенадцать котят. У каждого котенка В зубах по четыре мышонка. И задумался Кондрат: "Сколько мышат и котят Ребята несут в Ленинград?" (Глупый, глупый Кондрат! Он один и шагал в Ленинград. А ребята с лукошками, С мышами и кошками Шли навстречу ему Шли навстречу ему В Кострому.) "Шел Кондрат в Ленинград..." Загадка

18

19 В котором лукошке какого ребёнка и в зубах какого котёнка находится 137 мышонок? 137=R *3*12*4+L*12*4+K*4+ M 137=R *3*12*4+L*12*4+K*4+ M 137=(R *3*12+L*12+K)*4+ M откуда 137=(R *3*12+L*12+K)*4+ M откуда M=137 mod 4=1; R *3*12+L*12+K = 137 div 4 =34 M=137 mod 4=1; R *3*12+L*12+K = 137 div 4 =34 34=(R *3+L)*12+K откуда 34=(R *3+L)*12+K откуда K= 34 mod 12=10; R *3+L = 34 div 12 =2 K= 34 mod 12=10; R *3+L = 34 div 12 =2 2= R *3+L откуда L=2 и R=0 2= R *3+L откуда L=2 и R=0 Это означает, что это первый (M) мышонок в зубах одиннадцатого котёнка (K+1), сидящего в третьем лукошке (L+1) первого (R+1) ребенка.

20 Перечисление перестановок Как пронумеровать перестановки, идущие в лексикографическом порядке? Как пронумеровать перестановки, идущие в лексикографическом порядке? … Каков алгоритм построения следующей перестановки? Каков алгоритм построения следующей перестановки? Найти самый длинный «хвост» перестановки, цифры которого идут в порядке убывания. Найти самый длинный «хвост» перестановки, цифры которого идут в порядке убывания. Поменять цифру, стоящую непосредственно перед «хвостом» с последней цифрой «хвоста». Поменять цифру, стоящую непосредственно перед «хвостом» с последней цифрой «хвоста». Переписать цифры «хвоста» в порядке возрастания. Переписать цифры «хвоста» в порядке возрастания.

21 Факториальная система счисления Найдем, какой по счёту идёт перестановка Найдем, какой по счёту идёт перестановка До неё стоят все перестановки, начинающиеся с 1, 2, 3, 4: их 4*7! (факториал). До неё стоят все перестановки, начинающиеся с 1, 2, 3, 4: их 4*7! (факториал). Далее идут перестановки, начинающиеся с 5, на втором месте которых стоят цифры 1, 2 или 3 – их 3*6!, затем перестановки, которые начинаются с цифр 54, а за ними одна из цифр 1, 2, 3 (4 и 5 уже не могут использоваться) и т.д. (последняя цифра определяется автоматически). Далее идут перестановки, начинающиеся с 5, на втором месте которых стоят цифры 1, 2 или 3 – их 3*6!, затем перестановки, которые начинаются с цифр 54, а за ними одна из цифр 1, 2, 3 (4 и 5 уже не могут использоваться) и т.д. (последняя цифра определяется автоматически). Теперь можно сказать, что до данной перестановки стоят Теперь можно сказать, что до данной перестановки стоят 4*7!+ 3*6!+3*5!+2*4!+3*3!+0*2!+1*1! перестановок. 4*7!+ 3*6!+3*5!+2*4!+3*3!+0*2!+1*1! перестановок. Значит номер данной перестановки на 1 больше, либо равен этому числу, если нумеровать с нуля. Значит номер данной перестановки на 1 больше, либо равен этому числу, если нумеровать с нуля. Эта запись подсказывает идею факториальной системы счисления. Эта запись подсказывает идею факториальной системы счисления.