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

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

Санкт-Петербургский Государственный Политехнический Университет

Институт прикладной математики и механики

Кафедра Телематики (при ЦНИИ РТК)

Курсовая работа

по дискретной математике

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

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

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

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

Содержание

Введение

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

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

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

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

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

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

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

.3      Реализация деления

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

Заключение

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

Приложения

Введение

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

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

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

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

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

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

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

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

void SetPlus(int a, int b)

{n=0;temp=a;

{=Find(temp);++;

}(temp!=0);=b;(int i=0; i<n; i++)=Plus[1][temp];(temp==0 && a!=0)[a][b]=1;

}[a][b]=temp;

}

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

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

void SetMult(int a, int b)

{temp=0, tempB=b;(tempB>0)

{=Summ(temp, a, 1);=Summ(tempB,1,0);

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

}

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

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

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

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

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

{rez=0, bp=0;ostA=a, ostB=b, tempA, tempB;i=1;(i; ostA>0 || ostB>0; i*=10)

{=ostA%10;=(p)?ostB%10:ObratPlus(ostB%10);+=Plus[Plus[tempA][tempB]][bp]*i;(p==true)=PlusP[tempA][tempB]+PlusP[Plus[tempA][tempA]][bp];

{(Sravn(ostB%10, tempA)||(tempA==ostB%10 && bp!=0))

{=2;

}bp=0;

}/=10;/=10;

}+=bp*i;rez;

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

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

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

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

int Umnog(int a, int b)

{REZ=0;ostB=b;(int j=1; ostB>0; j*=10)

{tempB=ostB%10;tempREZ=0;ostA=a;i=1;dopU=0;(i; ostA>0; i*=10)

{tempA=ostA%10;tempDop=Summ(Mult[tempA][tempB], dopU, 1);+=tempDop%10*i;=Summ(tempDop/10, MultP[tempA][tempB], 1);/=10;

}+=dopU*i;=Summ(REZ,tempREZ*j,1);

ostB/=10;

}REZ;

}

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

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

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

{(Sravn(b, a))

{

*mod=a;0;

}tempA=a;REZ=0;(!Sravn(b,tempA))

{= Summ(tempA, b, 0);= Summ(REZ, 1, 1);

}

*mod=tempA;

return REZ;

}

калькулятор арифметика сложение некорректный

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

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

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

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

bool Sravn(int a, int b)

{(a==0) return false;(b==0) return true;rez=false;ostA=a, ostB=b, temp;n1,n2;(int i=0; ostA>0||ostB>0; i++)

{=0;=0;=ostA%10;(temp!=0)

{=Find(temp);++;

}(temp!=0);=ostB%10;(temp!=0)

{=Find(temp);++;

}(temp!=0);(n1!=n2)(n2>n1)=false;=true;/=10;/=10;

}rez;

}

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

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

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

Заключение

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

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

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

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

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

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

3.      Учебник «Алгоритмы: построение и анализ», автор Кормен, Лейзерсон, Ривест, Штайн. <#"784819.files/image001.jpg">

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

#include <iostream>

#include <conio.h>std::cout;std::cin;std::endl;int razr=8;Plus[razr][razr]; //создаем двухмерный массив (от 0 до 7)PlusP[razr][razr];Mult[razr][razr];MultP[razr][razr];Print(int matrix[][razr], int matrix1[][razr])

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

{(int j = 0; j < razr; j++)<< matrix[i][j] << " ";<< " ";(int j = 0; j < razr; j++)<< matrix1[i][j] << " ";<< endl;

}<< endl;

}

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

{(int i=0; i<razr; i++)(Plus[1][i]==n)

{i;

}-1;

}ObratPlus(int n)

{temp;(int i=0; i<8; i++)(Plus[i][n]==0) temp=i;

return temp;

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

{(a==0) return false;(b==0) return true;rez=false;ostA=a, ostB=b, temp;n1,n2;(int i=0; ostA>0||ostB>0; i++)

{=0;=0;=ostA%10;(temp!=0)

{temp=Find(temp);++;

}(temp!=0);=ostB%10;(temp!=0)

{=Find(temp);++;

}(temp!=0);(n1!=n2)(n2>n1)=false;=true;/=10;/=10;

}rez;

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

{rez=0, bp=0;ostA=a, ostB=b, tempA, tempB;i=1;(i; ostA>0 || ostB>0; i*=10)

{=ostA%10;=(p)?ostB%10:ObratPlus(ostB%10);+=Plus[Plus[tempA][tempB]][bp]*i;(p==true)=PlusP[tempA][tempB]+PlusP[Plus[tempA][tempA]][bp];//вычитание

{(Sravn(ostB%10, tempA)||(tempA==ostB%10 && bp!=0))

{=2;

}bp=0;

}/=10;/=10;

}+=bp*i;rez;

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

{need=false;(p==false)=Sravn(b,a);(p==false && need==true)(-1)*Summ((need)?b:a, (need)?a:b, p);Summ((need)?b:a, (need)?a:b, p);

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

{REZ=0;ostB=b;(int j=1; ostB>0; j*=10)

{tempB=ostB%10;tempREZ=0;ostA=a;i=1;dopU=0;(i; ostA>0; i*=10)

{tempA=ostA%10;tempDop=Summ(Mult[tempA][tempB], dopU, 1);+=tempDop%10*i;=Summ(tempDop/10, MultP[tempA][tempB], 1);/=10;

}+=dopU*i;=Summ(REZ,tempREZ*j,1);/=10;

}REZ;

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

{(Sravn(b, a))

{

*mod=a;0;

}l1=Length(a);l2=Length(b);REZ=0;tempA=a/pow(10,(l1-l2));(int k=1; l1>=l2+k-1; k++)

{min=0;(int i=1; i<razr; i++)

{z=Umnog(i, b);(Sravn(i,min) && !Sravn(z,tempA))=i;

}tempA=Summ(tempA,Umnog(min,b),0);(Length(a) >= Length(b)+k)=tempA*10+(a%int(pow(10,(Length(a)-Length(b)-k+1)))/int(pow(10,Length(a)-Length(b)-k)));=REZ*10+min;

}

*mod=tempA;

return REZ;

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

{temp=0, tempB=b;(tempB>0)

{=Summ(temp, a, 1);=Summ(tempB,1,0);

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

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

{n=0;temp=a;

do

{=Find(temp);++; //из скольких единиц состоит цифра

}(temp!=0);=b;(int i=0; i<n; i++)

{=Plus[1][temp];(temp==0 && a!=0)[a][b]=1;

}[a][b]=temp;

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

{<<endl;Last, mod=0;ost, temp;=abs(a);(ost>0)

{=ost%10;(temp>7)

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

goto n0;

}/=10;

}=abs(b);(ost>0)

{=ost%10;(temp>7)

{

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

}/=10;

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

{'+':(a>=0 && b>=0)=CheckSum(a,b,1);(a<0 && b<0)=-1*CheckSum(abs(a),abs(b),1);=-1*CheckSum(abs(a),abs(b),0);;'-':(a>=0 && b<0)=CheckSum(a,abs(b),1);(a<0 && b>=0)=-1*CheckSum(abs(a),b,1);(a>=0 && b>=0)=CheckSum(a,b,0);=-1*CheckSum(abs(a),abs(b),0);;'*':(a<0 && b>=0 || a>=0 && b<0)=(-1)*Umnog(abs(a),abs(b));=Umnog(abs(a),abs(b));;'/':(b==0)

{(a==0)

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

}

{<<"На ноль делить нельзя! (искл. 0/0)\n"<<endl;:char ans='2';

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

cin>>ans;(ans=='1')(0);1;

}

}(a<0 && b>0 || a>=0 && b<0)=(-1)*Delen(abs(a),abs(b), &mod);=Delen(abs(a), abs(b), &mod);;

}<<a<<" "<<z<<" "<<b<<" = "<<Last;(z=='/')<<" mod "<<mod<<endl;

else<<endl;0;

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

{(LC_ALL, "Russian");(int i=0; i<razr; i++)[0][i]=i;[1][0]=1;[1][1]=3;[1][2]=0;[1][3]=6;[1][4]=2;[1][5]=4;[1][6]=7;[1][7]=5;(int i=0; i<razr; i++)

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

{[i][j]=0;(i,j);

}

}(int i=0; i<razr; i++)

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

SetMult(i,j);

}<<"Калькулятор большой <Конечной> арифметики\n\n";<< "Таблица по сложению: Таблица дополнений по сложению:\n";(Plus, PlusP);<< "Таблица по умножению: Таблица дополнений по умножению:\n";(Mult,MultP);<<"+ - сложить \n- - вычесть \n* - умножить \n/ - разделить\n";<<"Пример ввода операции: Число Операция(+,-,*,/) Число (без пробелов!) или\n Число\n Операция(+,-,*,/)\n Число\n";

char ans='2';(ans!='1')

{a1, b2;Z;>>a1>>Z>>b2;(Z!='+' && Z!='-' && Z!='*' && Z!='/')

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

cin>>Z;

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

if (w==0)

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

}

}0;

}

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

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

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

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

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