Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
СМОЛЕНСКИЙ КОЛЛЕДЖ ТЕЛЕКОММУНИКАЦИЙ
(филиал) ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕНННОГО ОБРАЗОВАТЕЛЬНОГО БЮДЖЕТНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»
|
УТВЕРЖДАЮ Зам. директора по УПР _____________ И. В. Ильющенков «___» ___________ 2013г |
РАССМОТРЕНО на заседании цикловой комиссии программно - вычислительных дисциплин Протокол № _____ «___»___________2013г. Председатель комиссии __________Мохнач О.А. |
По дисциплине: Теория алгоритмов
Наименование работы: Умножение больших целых чисел.
Для специальности: 230115
Работа рассчитана на 2 часа
Составлена преподавателем Мохнач О.А.
г. Смоленск
2013 г.
2. ЛИТЕРАТУРА: Голицына О. Л., Попов И. И. Основы алгоритмизации и программирования. М.: ФОРУМ – ИНФРА-М, 2008.
Конспект.
3. ВОПРОСЫ ДЛЯ ДОМАШНЕЙ ПОДГОТОВКИ:
4. ОБОРУДОВАНИЕ: ПЭВМ
5. ЗАДАНИЕ.
5.1. Разработать программу, выполняющую умножение 2-х больших чисел. Написать комментарии к каждой строчке программы.
|
№ варианта |
1 число |
2 число |
|
1 |
635 |
1234567 |
|
2 |
467 |
1235768 |
|
3 |
1267 |
234567 |
|
4 |
908 |
234789 |
|
5 |
5804 |
345678 |
|
6 |
6705 |
876543 |
|
7 |
1234 |
765432 |
|
8 |
6543 |
65432 |
|
9 |
5876 |
54321 |
|
10 |
1267 |
87654 |
5.2. Реализовать сложение (*вычитание, *деление чисел)
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Повторить правила техники безопасности:
При работе и техническом обслуживании ПК необходимо соблюдать следующие меры предосторожности:
• Запрещается во время работы ПК размыкать и замыкать разъемные соединения.
• источники света должны быть расположены так, чтобы не засвечивать экран монитора, не создавать резких бликов на экране и не светить из-за монитора в глаза человека, работающего с ПК;
Не кладите на монитор бумагу, ткани и прочее, что может нарушить вентиляцию.
Включение ПК должно производиться в следующей последовательности:
Перед выключением компьютера завершите все работающие программы и подождите 1-2 сек. (это необходимо, если на ва шем ПК предусмотрено кэширование дисков). Далее необходимо:
• выключить системный блок;
• выключить принтер (если он был включен);
• выключить монитор.
6.2. Задать числа любым способом.
6.5. Реализовать алгоритм умножения длинных чисел.
6.6. Вывести на экран произведение.
6.7. Протестировать программу на различных исходных данных.
6.8. Оформить отчет.
8.1. Понятие и цель арифметических действий с длинными числами.
8.2. Алгоритмы работы с длинными целыми числами.
Длинная арифметика.
При решении определенного ряда задач, возникают ситуации, когда результаты или промежуточные вычисления не могут храниться ни в одном из допустимых типов языка программирования. Тогда необходимо обращаться к разделу программирования, который называется длинной арифметикой.
Для решения различных типов задач длинной арифметики применяется один и тот же принцип. Каждая цифра числа хранится в отдельном элементе массива. Для удобства добавления нового разряда числа хранятся в обратном порядке, причем длину числа можно хранить в отдельной переменной или в нулевом элементе массива.
Задача сложения
Задача решается таким же образом, как и при сложении в столбик. Производим сложение по каждому разряду отдельно. Если сумма больше 9, берем остаток от деления числа на 10 и не забываем прибавить количество десятков к следующему по старшинству разряду.
Программный код:
program A+B;
var
s1,s2:string;
a,b:array[1..100] of integer;
len,i,c:integer;
begin
c:=0;
ReadLn(s1);
ReadLn(s2);
len:=length(s1); {разбиение строк в элементы массивов}
for i:=1 to len do
a[len-i+1]:=Ord(s1[i])-48;
len:=length(s2);
for i:=1 to len do
b[len-i+1]:=Ord(s2[i])-48;
if length(s1)>length(s2) then len:=length(s1)
else len:=length(s2);
for i:=1 to len do
begin
c:=c+a[i]+b[i]; {переменная c будет в дальнейшем использоваться для переноса числа в следующий ряд}
a[i]:=c mod 10; {результат сложения запишем в массив а}
c:=c div 10;
end;
if c>0 then begin
len:=len+1;
a[len]:=c;
end;
for i:=len downto 1 do {вывод результата}
Write(a[i]);
end.
Задача вычитания
Данная программа осуществляет нахождения разности двух целых чисел, не позволяющих хранить их в переменных допустимых типов какого-либо языка программирования.
В отличии от задачи сложения, мы не можем выбирать по длине какого числа будем двигаться, поэтому прежде требует проверить конечный результат на его знак. Это освобождает от дальнейших трудностей. Непосредственно нахождения разности ничем не отличается от нахождения разности путем "вычитания в столбик".
program A-B;
Function CompLong(s1,s2:string):integer; {функция CompLong сравнивает две строки как большие числа}
var
a,len1,len2,i:integer;
b:boolean;
begin
a:=0;
b:=true;
len1:=length(s1);
len2:=length(s2);
if len1>len2 then begin a:= 1; b:=false; end;
if len1<len2 then begin a:=-1; b:=false; end;
if b then
for i:=1 to len1 do
begin
if Ord(s1[i])-48>Ord(s2[i])-48 then begin a:= 1; break; end;
if s1[i]<s2[i] then begin a:=-1; break; end;
end;
CompLong:=a;
end;
var
s1,s2:string;
i,len,c,x:integer;
a,b:array[1..1000] of integer;
begin
ReadLn(s1); c:=0;
ReadLn(s2);
len:=length(s2);
for i:=1 to len do
b[len-i+1]:=Ord(s2[i])-48;
len:=length(s1);
for i:=1 to len do
a[len-i+1]:=Ord(s1[i])-48;
if Complong(s1,s2)<0 then begin
Write(f2,'-');
len:=length(s2);
for i:=1 to len do begin
x:=a[i];
a[i]:=b[i];
b[i]:=x;
end;
end;
for i:=1 to len do
begin
c:=c+a[i]-b[i]+10;
a[i]:= c mod 10; {результат будет храниться в массиве a}
if c < 10 then c:=-1 else c:=0;
end;
while (a[len]=0) and (len>1) do len:=len-1;
for i:=len downto 1 do {вывод результата}
Write(a[i]);
end.
Задача умножения
program A*B;
var
s1:string;
b,i,c: integer;
a:array[0..10] of integer;
begin
c:=0;
ReadLn(s1);
ReadLn(b);
a[0]:=length(s1);
for i:=1 to a[0] do
a[a[0]-i+1]:=Ord(s1[i])-48;
for i:=1 to a[0] do
begin
a[i]:=c+a[i]*b;
c:=a[i] div 10;
a[i]:=a[i] mod 10;
end;
While c>0 do
begin
a[0]:=a[0]+1;
a[a[0]]:=c mod 10;
c:=c div 10;
end;
if a[a[0]]=0 then Write(0)
else
for i:=a[0] downto 1 do
Write(a[i]);
end.
На основе этих программ могут быть созданы программы нахождения факториала, возведения в степень и т.д. позволяющие работать с большими числами. Следует также учесть, что для экономии памяти в каждой ячейке массива можно хранить больше чем одну цифру числа.