Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки Украины

Национальный аэрокосмический университет им. Н.Е. Жуковского

Харьковский авиационный институт

Кафедра 304

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовомупроекту

по дисциплине «Теория алгоритмов и математическая логика»

на тему:

Сложение и умножение «длинных» чисел

Выполнила: студентка 325а группы

Савеленко Марина Юрьевна

Проверил: к.т.н., доцент Чернышев Ю.К.

Харьков 2011



РЕФЕРАТ

Пояснительная записка состоит из 17 листов, включает 5 иллюстраций, 1 таблицу, 2 приложения на 4 листах. При ее составлении использовалось 4 источника литературы.

Темой разработки является «Сложение и умножение длинных чисел» с использованием современных средств программирования в среде Visual Studio.

Разработан код программы по алгоритму сложения и умножения «длинных» чисел, размер которых превышает известные типы данных.

Ключевые слова: “длинная арифметика”, “длинные” числа, система счисления и другие.



СОДЕРЖАНИЕ

• РЕФЕРАТ
• ВВЕДЕНИЕ
• 1. ОСНОВЫ ОПЕРАЦИЙ НАД БОЛЬШИМИ ЧИСЛАМИ
• 1.1 Сложение «длинных» чисел
• 1.2 Умножение «длинных» чисел
• 2. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА
• 2.1 Формат входных/выходных данных
• 2.2 Работа программы
• ВЫВОДЫ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ПРИЛОЖЕНИЕ А


ВВЕДЕНИЕ

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

Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А нам необходимо выполнить арифметические действия над очень большими числами. В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.

Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются "длинными". Реализация арифметических операций над такими "длинными" числами получила название "длинной арифметики".

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

На практике "длинная арифметика" применяется в следующих случаях:

1. На компьютеры с процессорами низкой разрядности и микроконтроллерах. Например, на компьютерах и микроконтроллерах с 8-битными процессорами без использования длинной арифметики невозможно выполнить никакие сколько-нибудь полезные вычисления;

2. При решении задач криптографии;

3. При создании математического и финансового программного обеспечения, требования к точности вычислений в котором очень высоки и критичны, а ошибки округления и переполнения недопустимы;

4. Для "спортивных" вычислений знаменитых трансцендентных чисел (, e и т. д.) с высокой точностью;

5. Для решения олимпиадных задач по программированию.

Организация работы с "длинными" числами во многом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения. [1]

На данный момент существует множество различных тем для исследований, таких как: поиск наибольшего общего делителя двух "длинных" чисел; поиск наименьшего общего кратного двух "длинных" чисел; извлечение квадратного корня из "длинного" числа и т.д. Одной из наиболее актуальных тем является тема сложения и перемножения "длинных" чисел. Основной задачей курсового проекта является рассмотрение основных фактов и алгоритмов, используемых для сложения и умножения "длинных" чисел. [3]



1. ОСНОВЫ ОПЕРАЦИЙ НАД БОЛЬШИМИ ЧИСЛАМИ

В языках программирования всегда существует несколько стандартных типов переменных, которые представляют целое число.

Таблица 1.1

Типы переменных в разных языках программирования

Тип в Borland Pascal	Тип в Delphi	Тип в C++	Диапазон значений	Размер одной переменной этого типа
Shortint	Shortint	Char	-128..127	1 байт
Byte	Byte	unsigned char	0..255	1 байт
Integer	Smallint	Short	-32768..32767	2 байта
Word	Word	unsigned short	0..65535	2 байта
Longint	Longint (или Integer)	Int	-2147483648..2147483647	4 байта
Отсутствует	Longword	unsigned int	0..4294967295	4 байта
Отсутствует	Int64	long long	-2^63..2^63-1	8 байт
Отсутствует	Отсутствует	unsigned long long	0..2^64-1	8 байт

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

Несмотря на то, что с помощью стандартных типов можно представить достаточно большие числа, иногда возникает необходимость работать с числами намного больше. Число из 1000 цифр не поместится ни в один регистр. Поэтому компьютерное представление таких чисел и операции над ними приходится реализовывать самостоятельно. При этом время выполнения внешнего алгоритма, использующего такие числа, очень сильно зависит от эффективности их реализации. [3]

Неотрицательное целое число N длины n представляется при позиционной записи в виде:



,

где Base - основание системы счисления, все коэффициенты .

Например, число 12345₁₀ в этой интерпретации будет имеет вид:

.

Длинное число хранится в массиве, где i-й элемент соответствует коэффициенту числа при Baseⁱ. В качестве примера, рассмотрим массив для 12345₁₀: (5, 4, 3, 2, 1). Как видно, цифры хранятся в обратном порядке. Основание системы счисления Base зависит от максимального размера базового типа данных на компьютере и выбирается, исходя из следующих соображений:

1. Основание должно подходить под один из базовых типов данных.

2. Base должно быть как можно больше, чтобы уменьшить размер представления длинного числа и увеличить скорость операций с ними, но достаточно малого размера, чтобы все операции с коэффициентами использовали базовый тип данных.

3. Для удобства можно выбрать Base как степень 10. [4]

1.1 Сложение «длинных» чисел

Операция сложения длинных чисел реализует обычное сложение чисел столбиком. Вспомним, как выполняется такая операция. Пусть надо сложить два числа 1234 и 298. Записываем эти два числа в столбик таким образом, чтобы младшие разряды числа оказались друг под другом. После этого по таблице сложения складываем независимо разряды друг с другом. Если результат превосходит 9, то запоминаем 1, переносим ее в старший разряд, а в текущем разряде записываем младший разряд от результата сложения. И так продолжается до тех пор, пока все разряды не будут учтены. Обратите внимание, что если длина чисел разная, то в старших разрядах более длинного числа сложение производится только с "запомненной" 1 переноса.

1234

298

1532

Если мы храним число в массиве, то нам достаточно неудобно передвигать число с меньшим количеством знаков таким образом, чтобы младшие разряды стояли на одинаковых позициях. Кроме всего прочего результат сложения может состоять из большего количества цифр, чем каждое из слагаемых. В связи с этим нам может потребоваться записать цифру в самое начало (т. е. перед первой). Так как первая цифра записана в ячейке номер 1, то придется сдвинуть все число на одну позицию вправо и только после этого записать старшую цифру. В таком случае реализация становиться очень запутанной с большим количеством случаев и частыми сдвигами числа по массиву. Все это может привести к замедлению программы и большому количеству ошибок при реализации. Чтобы избежать этих трудностей, лучше хранить число «перевернутым», то есть, в первой ячейке массива будет записана младшая цифра (единицы), во второй будут записаны десятки и так далее. Это решает сразу все перечисленные проблемы. Во-первых, все числа теперь записаны так, что их последние цифры находятся друг под другом, во-вторых, чтобы добавить к числу цифру слева, нужно просто дописать ее в конец массива. [2]

1.2 Умножение «длинных» чисел

Говоря об умножении чисел, стоит рассмотреть два случая: умножение длинного числа на короткое (т. е. число, которое помещается в стандартный тип) и умножение двух длинных чисел. Умножение на короткое число будет схоже с умножением на однозначное число. Будем последовательно умножать короткое число на каждую цифру длинного числа, начиная с младшей цифры, записывать результат и некоторую часть произведения переносить в следующий разряд.

Рассмотрим случай, когда оба числа длинные. Обычно умножаются числа последовательно на одну цифру за другой, сохраняя временные результаты. Затем временные значения суммируются с учетом разряда. Однако можно ничего не хранить, а сразу прибавлять к окончательному результату.

Умножение (A, B, результат C):

1. Обнулить C

2. Обнулить

3. Вычислить временный результат, соответствующий умножению i-й цифры A на число B, в процессе вычисления сразу прибавлять его к C, начиная с i-ой позиции. Если получившаяся цифра C больше Base - сделать перенос.

4. Если A не кончилось, увеличить i на единицу и идти на шаг 3. [4]



2. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА

2.1 Формат входных/выходных данных

Входными данными являются числа, размер которых превышает известные типы данных.

Выходными данными являются результаты сложения и умножения входных чисел.

2.2 Работа программы

При первом запуске программы пользователь видит перед собой основное окно программы. Это окно можно увидеть на рис. 2.1.

Рисунок 2.1 - Основное окно программы

Это окно является исходной точкой для всех действий, которые пользователь может сделать в этой программе. Окно содержит поля ввода, поля вывода и кнопки управления.

Нажав кнопку «Инструкция пользователю», пользователь может вызвать описание действий в этой программе. Должно появиться такое соответствующее окно с подсказкой.

Рисунок 2.2 - Инструкция пользователю

длинный число программа сложение умножение

Далее пользователь должен ввести свои исходные данные (два «длинных» числа) в специально предназначенные для этого поля. Здесь можно нажать кнопку «Сброс», чтобы заново ввести данные.

Рисунок 2.3 - Заполнены два поля

После нажатия кнопки «Сложение» в соответствующем поля появляется результат сложения двух исходных «длинных» чисел.



Рисунок 2.4 - Результат сложения

После нажатия кнопки «Умножение» в соответствующем поля появляется результат умножения двух исходных «длинных» чисел.

Рисунок 2.5 - Результат умножения

Теперь пользователь может нажать кнопку «Сброс», чтобы начать всё заново.



ВЫВОДЫ

Целью данной работы была разработка программы для сложения и умножения «длинных» чисел.

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

В соответствии с требованиями, была написана программа, которая позволяет сложить и умножить два «длинных» числа.



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. http://inf.1september.ru/2000/1/art/okul1.htm

2. http://tchikh.dyndns.org/materials/dlinnaya-arifmetika.pdf

3. http://algolist.manual.ru/maths/longnum.php

4. Чернышев Ю.К. Применение ЭВМ для решения задач дискретной математики / Ю.К. Чернышев, М.Л. Угрюмов, В.А. Халтурин, А.Ю. Соколов. - Учеб. пособие. - Х.: Нац. аэрокосм. ун-т «Харьк. авиац. ин-т», 2003. - 75 с.



ПРИЛОЖЕНИЕ А

(Листинг программы)

usingSystem;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Windows.Forms;

namespace WindowsFormsApplication1

{

publicpartialclassMiniCalkulator : Form

{

public MiniCalkulator()

{

InitializeComponent();

}

// Операциясложения

publicbyte[] Add(string str1, string str2)

{

byte[] mass1 = newbyte[str1.Length];

for (int i = 0; i < mass1.Length; i++)

mass1[i] = byte.Parse("" + str1[i]);

byte[] mass2 = newbyte[str2.Length];

for (int i = 0; i < mass2.Length; i++)

mass2[i] = byte.Parse("" + str2[i]);

// Сравниваем длины массивов и меняем их местами.

if (mass2.Length > mass1.Length)

{

byte[] tmass;

tmass = mass2;

mass2 = mass1;

mass1 = tmass;

}

// Если длина 1-го массива превышает длину 2-го массива, то мы

создаем 3-ий нулевой массив и дописываем в него 2-ой. Поэтому 2-ой

массив будет спереди дополнен нулями.

if (mass1.Length > mass2.Length)

{

byte[] tmass = newbyte[mass1.Length];

for (int i = mass2.Length - 1, j = mass1.Length - 1; i >= 0; i--, j--)

{

tmass[j] = mass2[i];

}

mass2 = tmass;

}

// Создаеммассиврезультата

byte[] result = newbyte[mass1.Length + 1];

int n = result.Length - 2;

int m = 0; // разряд

for (int i = n; i >= 0; i--)

{

int a = mass1[i];

int b = mass2[i];

int c = a + b + m;

// если с (результат сложения чисел а и b) больше 9, то мы запоминаем

1 и переносим ее в старший разряд, а в текущем разряде записываем

младший разряд; если же с<9, то св текущем разряде записываем

результат сложения.

if (c > 9)

{

m = 1;

c -= 10;

}

else

m = 0;

result[i + 1] = byte.Parse(c.ToString());

}

// Вывод результата

if (m != 0)

{

result[0] = 1;

}

else

{

byte[] tmass = newbyte[result.Length - 1];

for (int i = 0; i < tmass.Length; i++)

{

tmass[i] = result[i + 1];

}

result = tmass;

}

return result;

}

// Операцияумножения

publicint[] Multi(string str1, string str2)

{

{

int n = str1.Length;

int[] x1 = newint[n];

for (int i = n - 1; i >= 0; i--)

{

x1[i] = int.Parse(str1.Substring(str1.Length - (i + 1), 1));

}

int k = str2.Length;

int[] y1 = newint[k];

for (int i = k - 1; i >= 0; i--)

{

y1[i] = int.Parse(str2.Substring(str2.Length - (i + 1), 1));

}

// Создаем массив результата

int[] res = newint[n + k + 1];

// Выполняем операцию умножения по известному алгоритму

for (int i = 0; i < x1.Length; i++)

for (int j = 0; j < y1.Length; j++)

{

res[i + j] = res[i + j] + x1[i] * y1[j];

res[i + j + 1] = res[i + j + 1] + res[i + j] / 10;

res[i + j] = res[i + j] % 10;

}

// Выводрезультата

int[] tmass = newint[res.Length-2];

for (int i = tmass.Length-1; i >= 0; i--)

{

tmass[i] = tmass[i] + res[i];

}

res = tmass;

returnres;

}

}

// При помощи нажатия этой кнопки в соответсвующее поле выведется

результат сложения больших чисел

privatevoid button1_Click(object sender, EventArgs e)

{

byte[] result = Add(textBox1.Text, textBox2.Text);

for (int i = 0; i < result.Length; i++)

{

textBox3.Text += result[i];

}

}

// При помощи нажатия этой кнопки в соответсвующее поле выведется

результат умножения больших чисел

privatevoid button2_Click(object sender, EventArgs e)

{

int[] res = Multi(textBox1.Text, textBox2.Text);

for (int i = res.Length-1; i >=0; i--)

{

textBox4.Text += res[i];

}

}

// При помощи нажатия этой кнопки все поля очистятся

privatevoid button3_Click(object sender, EventArgs e)

{

textBox1.Clear();

textBox2.Clear();

textBox3.Clear();

textBox4.Clear();

}

// При помощи нажатия этой кнопки появляется окно "Инструкция

пользователю", где отображен соответствующий текст

privatevoid button4_Click(object sender, EventArgs e)

{

MessageBox.Show(" С помощью клавиатуры введите два длинных

числа в специально отведенные поля. Нажав кнопку <Сложение>, вы

получите результат сложения в соответствующем поле. Нажав кнопку

<Умножение>, вы получите результат умножения в соответствующем

поле. Нажав кнопку <Сброс>, все поля очистятся.");

}

}

Размещено на Allbest.ru

...