Калькулятор большой «конечной» арифметики

Санкт-Петербургский Государственный Политехнический Университет Институт прикладной математики и механики Кафедра Телематики (при ЦНИИ РТК) Курсовая работа по дискретной математике

«Калькулятор большой „конечной“ арифметики»

Работу выполнил: Подорова А. Я.

Проверил: Востров А.В.

Санкт-Петербург 2013

1. Особенности реализации

2. Реализация таблиц малой арифметики

2.1 Реализация построения таблиц сложения и переноса по сложению

2.2 Реализация построения таблиц умножения и переноса по умножению

3. Реализация арифметических действий

3.1 Реализация сложения и вычитания

3.2 Реализация умножения

3.3 Реализация деления

3.4 Реализация сравнения Заключение Список используемой литературы Приложения

Сформировать калькулятор большой «конечной» арифметики i;+,*> (минимум 8 разрядов) для четырех действий (+,-,*,/) на основе малой «конечной» арифметики, где задано правило «+1» и выполняются свойства коммутативности (+,*), ассоциативности (+), дистрибутивности * относительно +, заданы аддитивная единица «0» и мультипликативная единица «1», х*0=0.

По желанию реализовать поиск НОД для двух чисел.

1. Особенности реализации

1. Алгоритм программы содержит в себе построение таблиц (в виде двумерных массивов, по строго заданному правилу «+1») сложения, умножения, переноса по сложению и переноса по умножению.

2. Программа выполняет стандартные бинарные операции (+, -, *, /). На вход берется два числа и одна из данных операций.

3. Программа поддерживает работу с отрицательными числами.

2. Реализация таблиц малой арифметики

2.1 Реализация построения таблиц сложения и переноса по сложению

void SetPlus (int a, int b)

{

int n=0;

int temp=a;

do

{

temp=Find (temp);

n++;

}

while (temp≠0);

temp=b;

for (int i=0; i

temp=Plus[1][temp];

if (temp==0 && a≠0)

PlusP[a][b]=1;

}

Plus[a][b]=temp;

}

На вход функция берет две цифры. Первая цифра раскладывается на сумму единиц, и нужное их количество прибавляется ко второму числу по правилу «+1». Результат: их сумма в нашей арифметике, которая вносится в соответствующую ячейку соответствующей таблицы. Заполнение таблицы сложения и его дополнения идет одновременно.

2.2 Реализация построения таблиц умножения и переноса по умножению

void SetMult (int a, int b)

{

int temp=0, tempB=b;

while (tempB>0)

{

temp=Summ (temp, a, 1);

tempB=Summ (tempB, 1,0);

}

Mult[a][b]=temp%10;

MultP[a][b]=(b==0)?0:temp/10;

}

На вход берется две цифры. При вычитании из второй цифры единицы к промежуточному результату прибавляется первая цифра, это происходит до тех пор, пока второе число не разложится на сумму единиц полностью, т. е. пока tempB не будет равен 0. Т. е. произведение представлено как сумма первой цифры n раз, где n — количество единиц, на которое разложилась вторая цифра.

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

3. Реализация арифметических действий

3.1 Реализация сложения и вычитания

int Summ (int a, int b, bool p)

{

int rez=0, bp=0;

int ostA=a, ostB=b, tempA, tempB;

int i=1;

for (i; ostA>0 || ostB>0; i*=10)

{

tempA=ostA%10;

tempB=(p)?ostB%10:ObratPlus (ostB%10);

rez+=Plus[Plus[tempA][tempB]][bp]*i;

if (p==true)

bp=PlusP[tempA][tempB]+PlusP[Plus[tempA][tempA]][bp];

else

{

if (Sravn (ostB%10, tempA)||(tempA==ostB%10 && bp≠0))

{

bp=2;

}

else bp=0;

}

ostA/=10;

ostB/=10;

}

rez+=bp*i;

return rez;

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

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

Вычитание: Выполняется аналогично сложению, но к цифре первого числа прибавляется дополнение до 0 цифры второго числа. Перенос при этом, равный «-1» (т.е. максимальной цифре в данной арифметике), будет только тогда, когда из меньшей цифры вычитают большую (в остальных случаях перенос равен 0).

3.2 Реализация умножения

int Umnog (int a, int b)

{

int REZ=0;

int ostB=b;

for (int j=1; ostB>0; j*=10)

{

int tempB=ostB%10;

int tempREZ=0;

int ostA=a;

int i=1;

int dopU=0;

for (i; ostA>0; i*=10)

{

int tempA=ostA%10;

int tempDop=Summ (Mult[tempA][tempB], dopU, 1);

tempREZ+=tempDop%10*i;

dopU=Summ (tempDop/10, MultP[tempA][tempB], 1);

ostA/=10;

}

tempREZ+=dopU*i;

REZ=Summ (REZ, tempREZ*j, 1);

ostB/=10;

}

return REZ;

}

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

3.3 Реализация деления

int Delen (int a, int b, int* mod)

{

if (Sravn (b, a))

{

*mod=a;

return 0;

}

int tempA=a;

int REZ=0;

while (!Sravn (b, tempA))

{

tempA= Summ (tempA, b, 0);

REZ= Summ (REZ, 1, 1);

}

*mod=tempA;

return REZ;

}

калькулятор арифметика сложение некорректный На входе два числа (первое — делимое, второе — делитель), и ссылка, по которой нужно передать остаток от деления.

Прописаны все частные случаи деления. Если первое число меньше второго — то сразу выводится результат деления 0, остаток — первое число целиком. Если пользователь вводит деление 0 на 0, выводится сообщение: «Неопределенность. Любое число в промежутке [-222 222 222;222222222],» т. е. интервал со всеми вариантами. В интервале число 2, потому что оно максимальное в данной арифметике. Если пользователь вводит ноль только в качестве делителя, то выводится следующее системное сообщение: «На ноль делить нельзя! (искл. 0/0)» .

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

3.4 Реализация сравнения

bool Sravn (int a, int b)

{

if (a==0) return false;

if (b==0) return true;

bool rez=false;

int ostA=a, ostB=b, temp;

int n1, n2;

for (int i=0; ostA>0||ostB>0; i++)

{

n1=0;

n2=0;

temp=ostA%10;

if (temp≠0)

do

{

temp=Find (temp);

n1++;

}

while (temp≠0);

temp=ostB%10;

if (temp≠0)

do

{

temp=Find (temp);

n2++;

}

while (temp≠0);

if (n1≠n2)

if (n2>n1)

rez=false;

else

rez=true;

ostA/=10;

ostB/=10;

}

return rez;

}

На вход функция принимает два числа, которые необходимо сравнить. Числа сравниваются по каждому разряду, начиная с меньшего. Для этого две цифры одного разряда раскладываются на сумму единиц, и сравнивается их количество. Если больше у первого числа — первое временно объявляется большим, если у второго — второе. Если равно, то большим временно объявляется то число, которое было большим при сравнении цифр прошлого разряда.

На выходе булева переменная, true — первое число больше, false — второе.

Функция сравнения используется в делении и сложении.

Заключение

В ходе выполнения данной работы был сформирован калькулятор большой «конечной» арифметики 8;+,*> для четырех действий (+,-,*,/) на основе малой «конечной» арифметики, с заданным правилом, и выполняются свойства коммутативности (+,*), ассоциативности (+), дистрибутивности * относительно +, заданы аддитивная единица «0» и мультипликативная единица «1», х*0=0. Калькулятор поддерживает работу с отрицательными числами, защищен от некорректного ввода данных.

Расположение чисел данной арифметики в порядке возрастания: 0<1<3<6<7<5<4<2.

Код программы можно легко приспособить для любой конечной арифметики, для этого необходимо знать правило «+1». В принципе, при незначительном изменении программы можно даже сделать так, чтобы пользователь сам вводил необходимую ему конечную арифметику, причем не только для 8 цифр. Также пользователю не доступна реализованная в программе функция сравнения. При заполнении таблиц не учитывалась их симметричность.

Список используемой литературы

1. Учебник Ф. А. Новикова «Дискретная математика для программистов».

2. Учебник по программированию, автор Павловская Т. А.

3. Учебник «Алгоритмы: построение и анализ», автор Кормен, Лейзерсон, Ривест, Штайн.

4. Конспект лекций по дискретной математике.

5. Конспект лекций по программированию.

Приложения

Приложение 1. Пример работы программы

Приложение 2. Листинг программы

#include

#include

using std: cout;

using std: cin;

using std: endl;

const int razr=8;

int Plus[razr][razr]; //создаем двухмерный массив (от 0 до 7)

int PlusP[razr][razr];

int Mult[razr][razr];

int MultP[razr][razr];

void Print (int matrix[][razr], int matrix1[][razr])

{

for (int i = 0; i < razr; i++) //вывод таблиц на экран

{

for (int j = 0; j < razr; j++)

cout << matrix[i][j] << ««;

cout << ««;

for (int j = 0; j < razr; j++)

cout << matrix1[i][j] << ««;

cout << endl;

}

cout << endl;

}

int Find (int n) //используется в сравнении двух чисел и реализации таблице по сложению и переносу по сложению

{

for (int i=0; i

if (Plus[1][i]==n)

{

return i;

}

return -1;

}

int ObratPlus (int n)

{

int temp;

for (int i=0; i<8; i++)

if (Plus[i][n]==0) temp=i;

return temp;

}

bool Sravn (int a, int b)//сравнение. если из меньшего вычитает большее, то меняет местами числа.

{

if (a==0) return false;

if (b==0) return true;

bool rez=false;

int ostA=a, ostB=b, temp;

int n1, n2;

for (int i=0; ostA>0||ostB>0; i++)

{

n1=0;

n2=0;

temp=ostA%10;

if (temp≠0)

do

{temp=Find (temp);

n1++;

}

while (temp≠0);

temp=ostB%10;

if (temp≠0)

do

{

temp=Find (temp);

n2++;

}

while (temp≠0);

if (n1≠n2)

if (n2>n1)

rez=false;

else

rez=true;

ostA/=10;

ostB/=10;

}

return rez;

}

int Summ (int a, int b, bool p)//сложение

{

int rez=0, bp=0;

int ostA=a, ostB=b, tempA, tempB;

int i=1;

for (i; ostA>0 || ostB>0; i*=10)

{

tempA=ostA%10;

tempB=(p)?ostB%10:ObratPlus (ostB%10);

rez+=Plus[Plus[tempA][tempB]][bp]*i;

if (p==true)

bp=PlusP[tempA][tempB]+PlusP[Plus[tempA][tempA]][bp];

else//вычитание

{

if (Sravn (ostB%10, tempA)||(tempA==ostB%10 && bp≠0))

{

bp=2;

}

else bp=0;

}

ostA/=10;

ostB/=10;

}

rez+=bp*i;

return rez;

}

int CheckSum (int a, int b, bool p)//проверка a>b, если нет, меняет местами, а результат в сложении умножает на -1

{

bool need=false;

if (p==false)

need=Sravn (b, a);

if (p==false && need==true)

return (-1)*Summ ((need)?b:a, (need)?a:b, p);

return Summ ((need)?b:a, (need)?a:b, p);

}

int Umnog (int a, int b)//умножение

{

int REZ=0;

int ostB=b;

for (int j=1; ostB>0; j*=10)

{

int tempB=ostB%10;

int tempREZ=0;

int ostA=a;

int i=1;

int dopU=0;

for (i; ostA>0; i*=10)

{

int tempA=ostA%10;

int tempDop=Summ (Mult[tempA][tempB], dopU, 1);

tempREZ+=tempDop%10*i;

dopU=Summ (tempDop/10, MultP[tempA][tempB], 1);

ostA/=10;

}

tempREZ+=dopU*i;

REZ=Summ (REZ, tempREZ*j, 1);

ostB/=10;

}

return REZ;

}

int Delen (int a, int b, int* mod) //функция деления

{

if (Sravn (b, a))

{

*mod=a;

return 0;

}

int l1=Length (a);

int l2=Length (b);

int REZ=0;

int tempA=a/pow (10,(l1-l2));

for (int k=1; l1>=l2+k-1; k++)

{

int min=0;

for (int i=1; i

{

int z=Umnog (i, b);

if (Sravn (i, min) && !Sravn (z, tempA))

min=i;

}tempA=Summ (tempA, Umnog (min, b), 0);

if (Length (a) >= Length (b)+k)

tempA=tempA*10+(a%int (pow (10,(Length (a)-Length (b)-k+1)))/int (pow (10,Length (a)-Length (b)-k)));

REZ=REZ*10+min;

}

*mod=tempA;

return REZ;

}

void SetMult (int a, int b) //реализация таблицы по умножению и переноса по умножению

{

int temp=0, tempB=b;

while (tempB>0)

{

temp=Summ (temp, a, 1);

tempB=Summ (tempB, 1,0);

}

Mult[a][b]=temp%10;

MultP[a][b]=(b==0)?0:temp/10;

}

void SetPlus (int a, int b) //реализация таблицы по сложению и переноса по сложению

{

int n=0;

int temp=a;

do

{

temp=Find (temp);

n++; //из скольких единиц состоит цифра

}

while (temp≠0);

temp=b;

for (int i=0; i

{

temp=Plus[1][temp];

if (temp==0 && a≠0)

PlusP[a][b]=1;

}

Plus[a][b]=temp;

}

int Work (int a, int b, char z) //рабочий интерфейс

{

cout<

int Last, mod=0;

int ost, temp;

ost=abs (a);

while (ost>0)

{

temp=ost%10;

if (temp>7)

{

cout<<" Неверный ввод, попробуйте снова! n" <

goto n0;

}

ost/=10;

}

ost=abs (b);

while (ost>0)

{

temp=ost%10;

if (temp>7)

{

cout<<" Неверный ввод, попробуйте снова! n" <

goto n0;

}

ost/=10;

}

switch (z) //свич для различных действий

{

case '+':

if (a>=0 && b>=0)

Last=CheckSum (a, b,1);

else

if (a<0 && b<0)

Last=-1*CheckSum (abs (a), abs (b), 1);

else

Last=-1*CheckSum (abs (a), abs (b), 0);

break;

case '-':

if (a>=0 && b<0)

Last=CheckSum (a, abs (b), 1);

else

if (a<0 && b>=0)

Last=-1*CheckSum (abs (a), b,1);

else

if (a>=0 && b>=0)

Last=CheckSum (a, b,0);

else

Last=-1*CheckSum (abs (a), abs (b), 0);

break;

case '*':

if (a<0 && b>=0 || a>=0 && b<0)

Last=(-1)*Umnog (abs (a), abs (b));

else

Last=Umnog (abs (a), abs (b));

break;

case '/':

if (b==0)

{

if (a==0)

{

cout<<" Неопределенность. Любое число в промежутке [-222 222 222;222222222]n" <

goto n0;

}

else

{

cout<<" На ноль делить нельзя! (искл. 0/0)n" <

n0:char ans='2';

cout<< «Для продолжения нажмите любую ЦИФРУ (кроме 1) или БУКВУ, для выхода 1n» ;

cin>>ans;

if (ans=='1')

exit (0);

else

return 1;

}

}

if (a<0 && b>0 || a>=0 && b<0)

Last=(-1)*Delen (abs (a), abs (b), &mod);

else

Last=Delen (abs (a), abs (b), &mod);

break;

}

cout<<" «<<» «<<» = «<

if (z=='/')

cout<<" mod «<

else

cout<

return 0;

}

int main () //в случае другого правила, заменить данную таблицу

{

setlocale (LC_ALL, «Russian»);

for (int i=0; i

Plus[0][i]=i;

Plus[1][0]=1;

Plus[1][1]=3;

Plus[1][2]=0;

Plus[1][3]=6;

Plus[1][4]=2;

Plus[1][5]=4;

Plus[1][6]=7;

Plus[1][7]=5;

for (int i=0; i

{

for (int j=0; j

{

PlusP[i][j]=0;

SetPlus (i, j);

}

}

for (int i=0; i

{

for (int j=0; j

SetMult (i, j);

}

cout<<" Калькулятор большой <�Конечной> арифметикиnn" ;

cout << «Таблица по сложению: Таблица дополнений по сложению: n» ;

Print (Plus, PlusP);

cout << «Таблица по умножению: Таблица дополнений по умножению: n» ;

Print (Mult, MultP);

cout<<" + - сложить n- - вычесть n* - умножить n/ - разделитьn" ;

cout<<" Пример ввода операции: Число Операция (+,-,*,/) Число (без пробелов!) илиn Числоn Операция (+,-,*,/)n Числоn" ;

char ans='2';

while (ans≠'1')

{

int a1, b2;

char Z;

cin>>a1>>Z>>b2;

while (Z≠'+' && Z≠'-' && Z≠'*' && Z≠'/')

{

cout<<" Введите операцию корректно:" ;

cin>>Z;

}

int w=Work (a1, b2, Z);

if (w==0)

{

cout<<" Для выхода введите — 1, для продолжения любую БУКВУ или ЦИФРУ (кроме 1) n" ;

cin>>ans;

}

}

return 0;

}

Приложение 3. Таблицы сложения и умножения, переносов по сложению и умножению

Таблица по сложению.

Таблица дополнений по сложению.

Таблица по умножению.

Таблица дополнений по умножению.