Задачи Операции со сверхбольшими числами

Разбить на страницы

Показывать лекцию целиком

Архитектура 32-х разрядных систем позволяет обрабатывать числа в максимальном диапазоне 0..4294967295. Но это слишком узкий диапазон натуральных чисел для решения многих прикладных задач (см. табл. 3.1).

Справочные сведения:

Форматы целых чисел
Описатель типа	Длина(байт)	Минимальное число	Максимальное число
`Integer`	2 (со знаком)	-32768	+32767
`Shortint`	1 (со знаком)	-128	+127
`Longint`	4 (со знаком)	-2147483648	+2147483647
`Byte`	1 (без знака)	0	255
`Word`	2 (без знака)	0	65535

Учиться производить операции со "сверхбольшими" числами будем на практике.

Задача: Найти произведение сверхбольшого числа на цифру.

Идею решения рассмотрим на примере, в котором нужно найти произведение "сверхбольшого" числа 4510905723598 на цифру 3:

Вводим число в СТРОКОВУЮ переменную.

"РАЗБИРАЕМ" ЧИСЛО НА ЦИФРЫ, помещая каждую цифру в элемент массива:


4	5	1	0	9	5	7	2	3	5	9	8

Умножаем каждый элемент на "3":


12	15	3	0	27	0	15	21	6	9	15	27	24

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

(рис 3.1)

Программа на Бейсике:

input  "введите длинное число"; a$
n = len(a$)
dim a(n), rez(n)
input  "второй сомножитель"; x
for i=1 to n
  a(i)=val(mid$(a$, i, 1))
next
rem=========================
for i=1 to n
  rez(i)=a(i) * x
next
for i=n to 2 step -1
  rem==перенос в старший разряд==
  rez(i - 1) = rez(i - 1) + (rez(i) \ 10)
  rem==остаток в младшем разряде=
  rez(i) = rez(i) mod 10
next
rem====вывод результата==========
for i = 1 to n
  print rez(i);
next

Программа на Паскале:

const 	m=100;
var a, rez: array [1..m] of byte;
  i, n, x, k: integer;
  stroka: string;
begin
  writeln  ('введите длинное число'); readln (stroka);
  n:= length (stroka);
  writeln ('второй сомножитель'); readln (x);
  for i:=1 to n do
    val (copy(stroka, i, 1), a[i], k);
  {==========================}
  for i:=1 to n do
    rez[i]:= a[i] * x;
  for i:=n downto 2 do
    begin
    rez[i - 1]:= rez[i - 1] + rez[i] div 10;
	rez[i]:= rez[i] mod 10;
	end
  {====вывод результата===========}
  for i:=1 to n do
  	write (rez[i]);
end.

Тест:


Дано:	32859305092145 5
Результат:	164296525460725

Задача: Найти сумму двух "сверхбольших" чисел.

Идею решения рассмотрим на примере вычисления суммы двух "сверхбольших" чисел 4510905723569 и 361295487.

Вводим числа в строковые переменные. "РАЗБИРАЕМ" каждое ЧИСЛО НА ЦИФРЫ, помещая цифры в элементы массивов. Массив, в котором будет храниться меньшее число (в примере это массив b) будем заполнять с 5-ой ячейки.

(рис 3.2)

Массив Sum заполняется суммой соответствующих ячеек массивов А и В. Затем организуем перенос: в каждой ячейке оставляем младшую цифру хранящегося там числа, а старшую цифру суммируем с числом, находящимся в левой ячейке.

Программа на Бейсике:

input "первое слагаемое"; a$
input "второе слагаемое"; b$
n = len(a$)
m = len(b$)
if n > m then max = n else max = m
dim a(max), b(max), sum(max)
rem=========================
for i = 1 to n
  a(i + (max - n)) = val(mid$(a$, i, 1))
next
for i = 1 to m
  b(i + (max - m)) = val(mid$(b$, i, 1))
next
rem=========================
for i = 1 to max
  sum(i) = a(i) + b(i)
next
for i = max to 2 step -1
  sum(i - 1) = sum(i - 1) + sum(i) \ 10
  sum(i) = sum(i) mod 10
next
rem=========================
for i = 1 to max
  print (sum(i));
next

Программа на Паскале:

const 	mm=100;
var a,b, sum: array [1..mm] of byte;
  i, n, m,max, x, k: integer;
  strokaA, strokaB: string;
begin
  writeln ('первое слагаемое'); readln  (strokaA);
  writeln ('второе слагаемое'); readln (strokaB);
  n:= length (strokaA);
  m:= length (strokaB);
  if n>m then max:=n
    else max:=m;
  for i:=1 to n do
    begin
    val(copy(strokaA, i, 1),x,k);
	a[i+(max-n)]:=x;
	end;
  for i:=1 to m do
    begin
	val(copy(strokaB, i, 1),x,k);
	b[i+(max-m)]:=x;
	end;
  {======суммирование===========}
  for i:=1 to max do
    sum[i]:= a[i]+b[i];
  for i:=max downto 2 do
    begin
	sum[i-1]:=sum[i-1] + sum[i] div 10;
	sum[i]:= sum[i] mod 10;
	end;
  {====вывод результата===========}
  for i:=1 to max do
    write (sum[i]);
end.

Тест:


Дано:	236754569081 937501
Результат:	236755506582

Задача Найти произведение двух сверхбольших чисел.

Идею решения иллюстрирует схема (рис. 3.3):

(рис 3.3)

возьмем последний элемент массива В; умножаем его на все элементы массива А. Результат храним в массиве Rez;

суммируем два массива - Sum и сдвинутые на 1 позицию влево элементы массива Rez; Результат заносим в Sum;

берем следующий элемент массива В (находящийся левее); повторяем с шага 2;

выводим на экран содержимое массива Sum.

Программа на Бейсике:

input "первое слагаемое"; a$
input "второе слагаемое"; b$
n = len(a$)
m = len(b$)
dim a(n), b(m), rez(n), sum(n + m)
rem======разбор на цифры============
for i = 1 to n
  a(i) = val(mid$(a$, i, 1))
next
for i = 1 to m
  b(i) = val(mid$(b$, i, 1))
next
rem==произведение на j-ую цифру=========
for j = m to 1 step -1
  for i = 1 to n
    rez(i) = a(i) * b(j)
  next
  for i = n to 2 step -1
    rez(i - 1) = rez(i - 1) + rez(i) \ 10
	rez(i) = rez(i) mod 10
  next
  rem====сумма со сдвигом==========
  for i = 1 to n
    sum(i + j - 1) = sum(i + j - 1) + rez(i)
  next
  for i = n to 2 step -1
    sum(i - 1) = sum(i - 1) + sum(i) \ 10
	sum(i) = sum(i) mod 10
  next
next
rem====вывод результата==============
for i = 1 to n + m - 1
  print sum(i);
next

Программа на Паскале:

const mm=100;
var a,b, rez,sum: array [1..mm] of byte;
  i, j, n, m, max, x, k: integer;
  strokaA, strokaB: string;
begin
  writeln ( 'первый сомножитель'); readln (strokaA);
  writeln ( 'второй сомножитель'); readln (strokaB);
  n:= length(strokaA);
  m:= length(strokaB);
  {======разбор на цифры===============}
  for i:= 1 to n do
    begin
	val(copy(strokaA, i, 1),x,k);
	a[i]:= x;
	end;
  for i:= 1 to m do
    begin
	val(copy(strokaB, i, 1),x,k);
	b[i]:= x;
	end;
  {==произведение на j-ую цифру============}
  for j:= m downto 1 do 
    begin
	for i:= 1 to n do
	  rez[i]:= a[i] * b[j];
	for i:= n downto 2 do 
	  begin
	  rez[i - 1]:= rez[i - 1] + rez[i] div 10;
	  rez[i]:= rez[i] mod 10;
	  end;
	{====сумма со сдвигом==============}
	for i:= 1 to n do
	  sum[i + j - 1]:= sum[i + j - 1] + rez[i];
	for i:= n downto 2 do 
	  begin
	  sum[i - 1]:= sum[i - 1] + sum[i] div 10;
	  sum[i]:= sum[i] mod 10;
	  end;
  end;
  {====вывод результата=================}
  for i:= 1 to n + m - 1 do
    write (sum[i]);
end.

Тест:


Дано:	123456789 1234567
Результат:	1524156752330241363

Ключевые термины

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

Краткие итоги

Операции со "сверхбольшими" числами выполняются по алгоритму:

число вводится в строковую переменную.

строка "разбирается на символы, каждый символ помещается в элемент массива, затем переводится в число.

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

аналогично (поразрядно) выполняется операция суммирования двух "сверхбольших" чисел.

Набор для практики

Вопросы.

Каким образом можно ввести с клавиатуры в переменную число, значение которого превышает 2147483647?

Каким образом можно удвоить введенное с клавиатуры число, значение которого превышает 2147483647?

Упражнения.

Вычислить N^K, (N и K>10).

Вычислить N! (N-факториал) - произведение чисел натурального ряда до N включительно.

Страницы:

Справочные сведения:

Форматы целых чисел
Описатель типа	Длина(байт)	Минимальное число	Максимальное число
`Integer`	2 (со знаком)	-32768	+32767
`Shortint`	1 (со знаком)	-128	+127
`Longint`	4 (со знаком)	-2147483648	+2147483647
`Byte`	1 (без знака)	0	255
`Word`	2 (без знака)	0	65535

Учиться производить операции со "сверхбольшими" числами будем на практике.

Задача: Найти произведение сверхбольшого числа на цифру.

Вводим число в СТРОКОВУЮ переменную.

"РАЗБИРАЕМ" ЧИСЛО НА ЦИФРЫ, помещая каждую цифру в элемент массива:


4	5	1	0	9	5	7	2	3	5	9	8

Умножаем каждый элемент на "3":


12	15	3	0	27	0	15	21	6	9	15	27	24

(рис 3.1)

Программа на Бейсике:

input  "введите длинное число"; a$
n = len(a$)
dim a(n), rez(n)
input  "второй сомножитель"; x
for i=1 to n
  a(i)=val(mid$(a$, i, 1))
next
rem=========================
for i=1 to n
  rez(i)=a(i) * x
next
for i=n to 2 step -1
  rem==перенос в старший разряд==
  rez(i - 1) = rez(i - 1) + (rez(i) \ 10)
  rem==остаток в младшем разряде=
  rez(i) = rez(i) mod 10
next
rem====вывод результата==========
for i = 1 to n
  print rez(i);
next

Программа на Паскале:

const 	m=100;
var a, rez: array [1..m] of byte;
  i, n, x, k: integer;
  stroka: string;
begin
  writeln  ('введите длинное число'); readln (stroka);
  n:= length (stroka);
  writeln ('второй сомножитель'); readln (x);
  for i:=1 to n do
    val (copy(stroka, i, 1), a[i], k);
  {==========================}
  for i:=1 to n do
    rez[i]:= a[i] * x;
  for i:=n downto 2 do
    begin
    rez[i - 1]:= rez[i - 1] + rez[i] div 10;
	rez[i]:= rez[i] mod 10;
	end
  {====вывод результата===========}
  for i:=1 to n do
  	write (rez[i]);
end.

Тест:


Дано:	32859305092145 5
Результат:	164296525460725

Задача: Найти сумму двух "сверхбольших" чисел.

Идею решения рассмотрим на примере вычисления суммы двух "сверхбольших" чисел 4510905723569 и 361295487.

(рис 3.2)

Программа на Бейсике:

input "первое слагаемое"; a$
input "второе слагаемое"; b$
n = len(a$)
m = len(b$)
if n > m then max = n else max = m
dim a(max), b(max), sum(max)
rem=========================
for i = 1 to n
  a(i + (max - n)) = val(mid$(a$, i, 1))
next
for i = 1 to m
  b(i + (max - m)) = val(mid$(b$, i, 1))
next
rem=========================
for i = 1 to max
  sum(i) = a(i) + b(i)
next
for i = max to 2 step -1
  sum(i - 1) = sum(i - 1) + sum(i) \ 10
  sum(i) = sum(i) mod 10
next
rem=========================
for i = 1 to max
  print (sum(i));
next

Программа на Паскале:

const 	mm=100;
var a,b, sum: array [1..mm] of byte;
  i, n, m,max, x, k: integer;
  strokaA, strokaB: string;
begin
  writeln ('первое слагаемое'); readln  (strokaA);
  writeln ('второе слагаемое'); readln (strokaB);
  n:= length (strokaA);
  m:= length (strokaB);
  if n>m then max:=n
    else max:=m;
  for i:=1 to n do
    begin
    val(copy(strokaA, i, 1),x,k);
	a[i+(max-n)]:=x;
	end;
  for i:=1 to m do
    begin
	val(copy(strokaB, i, 1),x,k);
	b[i+(max-m)]:=x;
	end;
  {======суммирование===========}
  for i:=1 to max do
    sum[i]:= a[i]+b[i];
  for i:=max downto 2 do
    begin
	sum[i-1]:=sum[i-1] + sum[i] div 10;
	sum[i]:= sum[i] mod 10;
	end;
  {====вывод результата===========}
  for i:=1 to max do
    write (sum[i]);
end.

Тест:


Дано:	236754569081 937501
Результат:	236755506582

Задача Найти произведение двух сверхбольших чисел.

Идею решения иллюстрирует схема (рис. 3.3):

(рис 3.3)

суммируем два массива - Sum и сдвинутые на 1 позицию влево элементы массива Rez; Результат заносим в Sum;

берем следующий элемент массива В (находящийся левее); повторяем с шага 2;

выводим на экран содержимое массива Sum.

Программа на Бейсике:

input "первое слагаемое"; a$
input "второе слагаемое"; b$
n = len(a$)
m = len(b$)
dim a(n), b(m), rez(n), sum(n + m)
rem======разбор на цифры============
for i = 1 to n
  a(i) = val(mid$(a$, i, 1))
next
for i = 1 to m
  b(i) = val(mid$(b$, i, 1))
next
rem==произведение на j-ую цифру=========
for j = m to 1 step -1
  for i = 1 to n
    rez(i) = a(i) * b(j)
  next
  for i = n to 2 step -1
    rez(i - 1) = rez(i - 1) + rez(i) \ 10
	rez(i) = rez(i) mod 10
  next
  rem====сумма со сдвигом==========
  for i = 1 to n
    sum(i + j - 1) = sum(i + j - 1) + rez(i)
  next
  for i = n to 2 step -1
    sum(i - 1) = sum(i - 1) + sum(i) \ 10
	sum(i) = sum(i) mod 10
  next
next
rem====вывод результата==============
for i = 1 to n + m - 1
  print sum(i);
next

Программа на Паскале:

const mm=100;
var a,b, rez,sum: array [1..mm] of byte;
  i, j, n, m, max, x, k: integer;
  strokaA, strokaB: string;
begin
  writeln ( 'первый сомножитель'); readln (strokaA);
  writeln ( 'второй сомножитель'); readln (strokaB);
  n:= length(strokaA);
  m:= length(strokaB);
  {======разбор на цифры===============}
  for i:= 1 to n do
    begin
	val(copy(strokaA, i, 1),x,k);
	a[i]:= x;
	end;
  for i:= 1 to m do
    begin
	val(copy(strokaB, i, 1),x,k);
	b[i]:= x;
	end;
  {==произведение на j-ую цифру============}
  for j:= m downto 1 do 
    begin
	for i:= 1 to n do
	  rez[i]:= a[i] * b[j];
	for i:= n downto 2 do 
	  begin
	  rez[i - 1]:= rez[i - 1] + rez[i] div 10;
	  rez[i]:= rez[i] mod 10;
	  end;
	{====сумма со сдвигом==============}
	for i:= 1 to n do
	  sum[i + j - 1]:= sum[i + j - 1] + rez[i];
	for i:= n downto 2 do 
	  begin
	  sum[i - 1]:= sum[i - 1] + sum[i] div 10;
	  sum[i]:= sum[i] mod 10;
	  end;
  end;
  {====вывод результата=================}
  for i:= 1 to n + m - 1 do
    write (sum[i]);
end.

Тест:


Дано:	123456789 1234567
Результат:	1524156752330241363

Ключевые термины

Краткие итоги

Операции со "сверхбольшими" числами выполняются по алгоритму:

число вводится в строковую переменную.

строка "разбирается на символы, каждый символ помещается в элемент массива, затем переводится в число.

аналогично (поразрядно) выполняется операция суммирования двух "сверхбольших" чисел.

Набор для практики

Вопросы.

Каким образом можно ввести с клавиатуры в переменную число, значение которого превышает 2147483647?

Каким образом можно удвоить введенное с клавиатуры число, значение которого превышает 2147483647?

Упражнения.

Вычислить N^K, (N и K>10).

Вычислить N! (N-факториал) - произведение чисел натурального ряда до N включительно.

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Задачи Операции со сверхбольшими числами

Ключевые термины

Краткие итоги

Набор для практики

Ключевые термины

Краткие итоги

Набор для практики

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!