Практическая работа№1 по дисциплине: Теория алгоритмов наименование работы: Решение задач с многоразрядными целыми числами.


Смоленский колледж телекоммуникаций
(филиал) федерального государственного образовательного
бюджетного учреждения высшего профессионального образования
«Санкт-Петербургский государственный университет телекоммуникаций
им. проф. М.А. Бонч-Бруевича»
УТВЕРЖДАЮ
Зам. директора по УР
_____________ И. В. Иванешко
«___» ___________ 2014г РАССМОТРЕНО
на заседании предметной (цикловой) комиссии
программно - вычислительных дисциплин
Протокол № _____
«___»___________2014г
Председатель комиссии_
__ О.О. Шаманова _________

Практическая работа№1
по дисциплине: Теория алгоритмов
наименование работы: Решение задач с многоразрядными целыми числами.
для специальностей: 230115, 09.02.03
работа рассчитана на 2 часа
составлена преподавателем: Скряго О.С.
Смоленск, 2014
1. Цель работы: овладеть навыками составления алгоритмов выполнения основных арифметических операций над многоразрядными целыми числами.
2. Литература:
2.1. Балюкевич, Э.Л. Математическая логика и теория алгоритмов [Электронный ресурс]: учебное пособие/ Балюкевич Э.Л., Ковалева Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2009.— 188 c. ISBN:978-5-374-00220-1
2.2. Верещагин, Н.К. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции [Электронный ресурс]/ Верещагин Н.К., Шень А.— Электрон. текстовые данные.— М.: МЦНМО, 2012.— 160 c. ISBN:978-5-4439-0014-8
2.3. Гаврилов, Г.П. Задачи и упражнения по дискретной математике [Электронный ресурс]: учебное пособие/ Гаврилов Г.П., Сапоженко А.А.— Электрон. текстовые данные.— М.: ФИЗМАТЛИТ, 2009.— 416 c. ISBN:978-5-9221-0477-7
3. Подготовка к работе:
3.1. Повторить тему «Арифметика многоразрядных целых чисел».
3.2. Подготовить бланк отчета (см.п.7).
3.3. Ответить на вопросы допуска:
3.3.1. Какие числа называются «длинными»?
3.3.2. Перечислите способы хранения длинных чисел?
3.3.3. Перечислите достоинства и недостатки каждого способа хранения?
4. Основное оборудование: ПЭВМ
5. Задание:
Выполните задания согласно варианту.
Выполните сложение двух многоразрядных целых чисел, используя обратный массив, и сделайте проверку.
Выполните вычитание двух многоразрядных целых чисел, используя обратный массив, и сделайте проверку.
Выполните умножение двух многоразрядных целых чисел, используя обратный массив, и сделайте проверку.
.Разработать программу, выполняющую умножение 2-х больших чисел. Написать комментарии к каждой строчке программы.
Таблица 1. Исходные данные
Варианта № первое число второе число
1 25658652 212122
2 135645746 24536
3 85515245 1215451
4 65487636 35655
5 121656541 56414
6 45765325 12455
7 96545236 234223
8 8984534 47851
9 23564563 354656
10 96687612 544345
11 88732332 12546
12 4324535 453210
13 5245335 245453
14 545435691 123453
15 98952133 57879
5.5* Выполнить задание из таблице 2 согласно варианту.
Таблица 2.
вариант 1 Составить программу сравнения двух многозначных чисел (количество знаков в записи чисел более 20).
2 Составить программу, суммирующую два натуральных многозначных числа с количеством знаков более 20.
3 Составить программу вычисления степени an, если a > MaxInt, n > 10.
4 Составить программу вычисления числа 264 – 1, в результате сохранить все цифры.
5 Составить программу вычисления 100!.
6 Составить программу извлечения точного квадратного корня из n-разрядного числа (n > 40).
7 Составить программу вычисления точного значения n!, где n > 12.
8 Составить программу вычисления точного значения nn, где n > 10.
9 Составить программу деления числа a на число b, если a, b — многозначные числа.
10 Составить программу вычисления 100! + 2100.
11 Составить программу вычисления 100! – 2100.
12 Составить программу вычисления 7123.
13 Составить программу вычисления 30! – 230.
14 Составить программу вычисления 30! + 230
15 Составить программу вычисления 723
6. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ.
6.1. Ознакомиться с заданием.
6.2. Определить номер варианта (в соответствии с номером в журнале).
6.3. Выполнить задание 5.1-5.3 письменно.
6.4. Сообщить преподавателю о выполненных заданиях.
6.5. Повторить правила техники безопасности:
Правила техники безопасности в компьютерном классе.
Перед началом работы необходимо убедиться в отсутствии видимых повреждений аппаратуры.
Работа с компьютером производится строго по указаниям преподавателя.
Запрещается:
Разъединять или соединять разъемы аппаратуры;
Прикасаться к экрану монитора;
Включать и выключать аппаратуру без указания преподавателя;
Класть какие-либо предметы на монитор, системный блок или клавиатуру;
Работать во влажной одежде, а также влажными или грязными руками;
Пытаться самостоятельно исправлять возникшую в аппаратуре неисправность.
Включите компьютер.
Включите в сеть стабилизатор напряжения (если он имеется).
Включите принтер (если он имеется).
Включите монитор.
Включите системный блок (большая кнопка на передней панели).
Выключение компьютера.
Завершите выполнение всех программ.
Выполните команду: Пуск Завершение работы Выключить компьютер (Alt+F4→ Завершение работы).
Выключите системный блок.
6.6. Приступить к выполнению заданий 5.4 -5.5.
6.7.Оформить отчет.
7. Содержание отчета:
7.1. Название и цель работы.
7.2 Ответы на вопросы допуска.
7.2. Указать номер варианта, привести условия задач своего варианта.
7.3. Представить выполненные задания согласно варианта, текст программы с комментариями.
7.4. Ответы на контрольные вопросы.
8. Контрольные вопросы:
8.1. Описать сложение двух больших чисел?
8.2. Описать вычитание двух больших чисел?
8.3. Описать умножение двух больших чисел?
8.4. Почему нельзя выполнить арифметические действия с большими числами обычными операциями?
8.5. Где применяются алгоритмы работы с большими числами?
Составил преподаватель __________________________Скряго О.С.
9. Приложение:
Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются иногда «длинными».
Диапазон чисел, которые можно представить в ячейках памяти ЭВМ, ограничен. Для работы с числами, лежащими вне этого диапазона, требуется применение специальных приемов для размещения таких чисел в памяти и их обработки.
Для представления многоразрядного числа в памяти ЭВМ можно каждую его цифру хранить как элемент массива: самую младшую цифру - количество единиц - в первом элементе массива, количество десятков - во втором и т.д. Старшие незанятые элементы массива следует заполнить нулями.
Для решения различных типов задач длинной арифметики применяется один и тот же принцип. Каждая цифра числа хранится в отдельном элементе массива. Для удобства добавления нового разряда числа хранятся в обратном порядке, причем длину числа можно хранить в отдельной переменной или в нулевом элементе массива.

Задача сложения
Задача решается таким же образом, как и при сложении в столбик. Производим сложение по каждому разряду отдельно. Если сумма больше 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;

Пример № 1.
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.
Пример № 2.
Var
 buf        : integer;           //полученное число, в результате умножения
    des        : integer;           //счетчик "десяток"
    n,m        : integer;           //счетчики длины строки
    i,j,q      : integer;           //переменные для работы со строкой и массивами
   x1,x2      : string;            //сюда вводим числа в виде строк
   c,d: array[1..50]   of integer; //массивы для хранения и оперирования с числами
   res: array[1..2500] of integer; //результат вычислений
 
begin
   write('Введите первое число: ');
   readln(x1);
   n:=length(x1);
   write('Введите второе число: ');
   readln(x2);
   m:=length(x2);
   //перенос первого числа в массив
   i:=1;
     repeat
      val(x1[i],c[i],q);
      i:=succ(i);
     until i>n;
   //перенос второго числа в массив  
   i:=1;
     repeat
      val(x2[i],d[i],q);
      i:=succ(i);
      until i>m;
    //умножение двух чисел (умножение "столбиком")
    for i:=1 to length(x1) do
   begin
      for j:=1 to length(x2) do
      begin
      buf:=c[i]*d[j]+des+res[i+j-1];
      res[i+j-1]:=buf mod 10;
      des:=buf div 10;
      end;
    res[i+j]:=des;
  end;
    //вывод полученного числа
    if res[1]=0 then
    for i:=2 to length(x1)-length(x2)+1 do write(res[i])
    else
    for i:=1 to length(x1)-length(x2)+1 do write(res[i]);
    readln;
end.

Приложенные файлы

  • docx F16
    Скряго О.С.
    Размер файла: 36 kB Загрузок: 0

Добавить комментарий