VPF::Задачки для новичков! - Форум программистов

bsa

Дата 8.12.2010, 12:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(Чoо @ 7.12.2010, 14:12)

bsa, тогда не понимаю, почему если вместо

Код


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

использовать

Код


#include <сstdio>
#include <сstdlib>
#include <сstring>

решение будет проще и оптимальней?

Нет. Только из-за этого не будет. Но если ты всякие strcmp, strcpy и пр. заменишь на std::string, то будет.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 8.12.2010, 13:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

ааа... Ну до этого я еще не дошел smile

. Это еще предстоит изучать впереди. Пока что только до перегрузки операторов дошел. Впереди еще распределение памяти, обработка исключений, множественное наследование, преобразование типов, только потом пространства имен. Потом следующая часть "стандартная библиотека шаблонов".

Добавлено через 59 секунд
пол книжки уже осилил. Правда небольшая каша, но это временно.

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

Чoо

Дата 11.12.2010, 23:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

Цитата

    Класс "Длинное целое двоичное число".
    Объявите класс "длинное целое двоичное число", объект которого можно
    сконструировать из массива символов. Перегрузите все арифметические операции,
    операции сравнения, извлечение из потока и помещение в поток.

Код


/*
    Класс "Длинное целое двоичное число".
    Объявите класс "длинное целое двоичное число", объект которого можно
    сконструировать из массива символов. Перегрузите все арифметические операции,
    операции сравнения, извлечение из потока и помещение в поток.
 */

#include <iostream>
#include <cstring>
#include <cstdlib>

class longvalue{
    int *value; //массив-образ числа
    int size; //количество элементов в образе (что бы не выйти за границы массива)
    int basis; //основание системы счисления
    static const char *values; //хранит элементы, допустимые в данной системе счисления
    bool valuechk(const char *v, const int basis); //проверяет число на соответствие системе счисления
    int *get_image(const char*p); //получает образ числа (с конца)
    /*преобразует символ в число*/
    int char_to_int(const char c) const;
    char int_to_char(const int i) const;
    char* _get_value(const int* _image,const int _size) const; //возвращает значение образа в виде строки
    int* valuecpy(const int* _value,const int _size) const; //копирует образ числа во вновь выделенную память
public:
    longvalue(const char *v, const int _basis);
    /*нужно определить конструктор копирования, так как если использовать конструктор копирования
      по умолчанию, то он будет копировать только указатель на значение value, что не приемлимо
    */
    longvalue(const longvalue &p);
    ~longvalue()
    {
        free(value);
    }

    char *get_value()
    {
        return _get_value(value,size);
    }

    /*операция сложения*/
    longvalue operator +(const longvalue &p);
    /*операция приравнивания
      при приравнивании объектов важно копировать область памяти, на которую указывает value
    */
    longvalue& operator =(const longvalue &p);

};
longvalue::longvalue(const char *v,const int _basis)
{
    if(valuechk(v,_basis))
    {
        basis = _basis; //перед созданием образа важно знать базис системы счисления
        value = get_image(v);
    }
    else
    {
        basis = 0;
        value = get_image("0");
    }
}
longvalue::longvalue(const longvalue &p)
{
    basis = p.basis;
    value = p.valuecpy(p.value,p.size);
    size = p.size;
}

//функция возвращает 1, елси элементы строки либо 1 либо ноль
//        возвращает 0 в противном случае
bool longvalue::valuechk(const char *v, const int basis)
{
    int l = strlen(v);
    for(int i = 0; i<l; ++i)
    {
        int j = 0;
        while(j<basis && v[i] != values[j])
            ++j;
        if(j==basis)
            return 0;
    }
    return 1;
}

int *longvalue::get_image(const char *p)
{
    size = strlen(p);
    int *result = (int*)malloc(size*4);
    /*можно приступать к копированию*/
    for(int i = size-1, j = 0; i>=0; --i, ++j)
        result[j] = char_to_int(p[i]);
    return result; //Не забывать освобождать память !!!!!!!!!!!!!!!!!!!!!
}

int longvalue::char_to_int(const char c) const
{
    int i;
    for(i = 0; i<=basis; ++i)
        if(c == values[i])
            return i;
    return 0; //на всякий случай
}

char longvalue::int_to_char(const int i) const
{
    return values[i];
}

char *longvalue::_get_value(const int* _image,const int _size) const
{
    char *result = (char *)malloc(_size+1);
    for(int i = _size-1, j=0; i>=0; --i, ++j)
        result[j] = int_to_char(_image[i]);
    return result;
}
int* longvalue::valuecpy(const int *_value,const int _size) const
{
    int* result =(int*) malloc(_size*4);
    for(int i = 0; i< _size; ++i)
        result[i] = _value[i];
    return result;
}

/*операция сложения*/
longvalue longvalue::operator +(const longvalue &p)
{
    /*если базис чисел разный, то возвращаем ноль. не будем считать*/
    if(basis != p.basis || basis==0)
        return longvalue("0",0);

    /*образ числа будем складывать "в столбик"*/
    int *sum=0; //накопитель для суммы. Пока не динамический
    int s; //сумма двух слагаемых
    int carry = 0; //перенос в старший разряд
    int i = 0;
    while(i<size)
    {
        if(i < p.size)
            s = value[i] + p.value[i] + carry;
        else
            s = value[i] + carry;
        sum = (int*)realloc(sum,(i+1)*4);
        sum[i] = s % basis;
        carry = s / basis;
        ++i;
    }
    while(i<p.size)
    {
        //остались еще элементы в объекте p
        s = p.value[i] + carry;
        sum = (int*)realloc((int*)sum,(i+1)*4);
        sum[i] = s % basis;
        carry = s / basis;
        ++i;
    }
    if(carry)
    {
        //остался еще перенос в старший разряд
        sum = (int*)realloc((int*)sum,(i+1)*4);
        sum[i] = carry;
        ++i;
    }
    char *str = _get_value(sum,i);
    longvalue new_obj(str,basis);
    free(str);
    return new_obj;
}

longvalue& longvalue::operator =(const longvalue &p)
{
    basis = p.basis;
    free(value); //освобождаем память, так какследующая инструкция выделяет новую
    value = valuecpy(p.value,p.size);
    size = p.size;
    return *this;
}

const char *longvalue::values = "0123456789ABCDEF";

int main()
{
    longvalue *l = new longvalue("FFF",16);
    longvalue *l2 = new longvalue("F",16);
    longvalue sum("0",0);
    sum = *l + *l2;
    char* s = sum.get_value();
    std::cout << s;
    free(s);
    delete l;
    delete l2;

    return 0;
}

пока что перегрузил только сложение и приравнивание. Что-то на решение понадобилось больше времени, чем планировал. Решил еще вместо двоичного числа, сделать класс для любой системы счисления вплоть до 16чной. ну складывает пока корректно. Потом перегружу извлечение и помещение в поток, что бы не мучаться с тестированием.
Если не устану, сделаю деление, умножение, вычитание, сравнение.
на всякий случай опубликовал результат, вдруг есть где грубые косяки. Лучше их сейчас исправлю, вместо того, что бы иметь кучу головной боли "почему не работает" smile

***
пару косяков нашел, потому редактирую сообщение (косяки касались выделения памяти для копируемых элементов)

Это сообщение отредактировал(а) Чoо - 12.12.2010, 01:12

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

Чoо

Дата 12.12.2010, 02:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

перегрузил операторы извлечения и помещения в поток. К сожалению криво:

Код


/*операция помещения в поток*/
std::ostream& operator <<(std::ostream& strm, const longvalue& p)
{
    /* так как p.get_value() выделяет память, то эта память должна быть освобождена.
       не знаю как ее освободить :(
    */
    return(strm << p.get_value());
}
/*операция извлечения из потока*/
std::istream& operator >>(std::istream& strm, longvalue &p)
{
    char val[100]; //не знаю как распределить динамически :(
    int basis;
    strm >> val >> basis;
    p.basis = basis;
    free(p.value);
    p.value = p.get_image(val);
    return strm;
}

кривость помещения в том, что происходит утечка памяти. Не знаю как сделать правильно :(.
кривость извлечения в том, что не знаю как выделить память для строки динамически, поэтому максимальное число может содержать не > 100 символов.
На сегодня наверное хватит.

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 12.12.2010, 12:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

у тебя два варианта:
1. переписать _get_value() и get_value() с использованием std::string
2. удалить указанные методы вообще и включить их функциональность в operator<<. Кому надо будет получить строку, будут использовать std::stringstream.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 12.12.2010, 14:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

bsa, а если я сделаю так?

Код


/*операция помещения в поток*/
std::ostream& operator <<(std::ostream& strm, const longvalue& p)
{
    char *result = p.get_value();
    strm << result;
    free(result);
    return strm;
}
/*операция извлечения из потока*/
std::istream& operator >>(std::istream& strm, longvalue &p)
{
    char *result = 0;
    char r = 0;
    int size = 0;
    while(1)
    {
        r = getchar();
        if(r!=' ')
        {
            ++size;
            result = (char*)realloc(result,size+1);
            result[size-1] = r;
            continue;
        }
        break;
    }
    int basis;
    strm >> basis;
    p.basis = basis;
    free(p.value);
    if(p.valuechk(result, basis))
        p.value = p.get_image(result);
    else
    {
        p.basis = 0;
        p.value = p.get_image("0");
    }
    return strm;
}

или это уже костыли?
1й вариант - пока исключаю, так как не дошел до std::string
а вот второй, в принципе решение вижу. память тогда выделять не надо, а можно сразу выводить данные в поток (поэлементно), да?

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

Чoо

Дата 14.12.2010, 23:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

вобщем подумал я чуть и атк и не сделал вычитание и все из-за знака числа. Что-то слишком много и долго кодить. Простого решения не вижу. Вопщем из всего задания сделал только: извлечение и помещение в поток, операции сравнения (только < > ==), не полностью операцию сложения (только сложение чисел с одинаковым знаком) и вообще ни как не реализовал вычитание. Умножение и деление - даже не думал делать.
Намного проще бы было, если бы я преобразовывал введенную строку в число, производил вычисления, а потом бы выдавал результат. Что-то слишком сложным путем пошел. Вопщем сдаюсь я smile

. Наверное я ошибся с выбором профессии, раз лениво кодить smile

Код


/*
    Класс "Длинное целое двоичное число".
    Объявите класс "длинное целое двоичное число", объект которого можно
    сконструировать из массива символов. Перегрузите все арифметические операции,
    операции сравнения, извлечение из потока и помещение в поток.
 */

#include <iostream>
#include <cstring>
#include <cstdlib>

class longvalue{
private:
    int *value; //массив-образ числа
    int size; //количество элементов в образе (что бы не выйти за границы массива)
    int basis; //основание системы счисления
    bool positive; //истина, если число положительное, ложь - если отрицательное
    static const char *values; //хранит элементы, допустимые в данной системе счисления
    bool valuechk(const char *v, const int _basis) const; //проверяет число на соответствие системе счисления
    void get_image(const char* p, const int _basis); //получает образ числа (с конца)
    int char_to_int(const char c, const int _basis) const;
    char int_to_char(const int i) const;
    int* valuecpy() const; //копирует образ числа во вновь выделенную память

public:
    longvalue(){value = 0; basis = 0; positive = 1; size = 0;};
    longvalue(const char *v, const int _basis);
    /*нужно определить конструктор копирования, так как если использовать конструктор копирования
      по умолчанию, то он будет копировать только указатель на значение value, что не приемлимо
    */
    longvalue(const longvalue &p);
    ~longvalue()
    {
        free(value);
    }
    /*оператор присвоения
      при приравнивании объектов важно копировать область памяти, на которую указывает value
    */
    longvalue& operator =(const longvalue &p); //изменяет состояние объекта
    /*оператор помещения в поток*/
    friend std::ostream& operator <<(std::ostream& strm, const longvalue &p);
    /*оператор извлечения из потока*/
    friend std::istream& operator >>(std::istream& strm, longvalue &p);
    /*сложение*/
    longvalue operator +(const longvalue &p);
    longvalue sum(const longvalue& p1, const longvalue &p2) const;
    /*вычитание*/
    longvalue operator -(const longvalue &p);
    longvalue sub(const longvalue &p1, const longvalue &p2) const;
    /*сравнение. < -1, == 0, > 1 */
    int valuecmp(const longvalue &p1, const longvalue &p2) const;
    bool operator <(const longvalue &p);
    bool operator >(const longvalue &p);
    bool operator ==(const longvalue &p);



};
//функция возвращает 1, елси элементы строки соответствуют системе счисления
//        возвращает 0 в противном случае
bool longvalue::valuechk(const char *v, const int _basis) const
{
    int l = strlen(v); //длина строки
    int i = 0; //индекс массива v
    if(v[i]=='-')
        ++i;
    for(; i<l; ++i) //индекс i определен раннее
    {
        int j = 0; //индекс для массива values
        while(j<_basis && v[i] != values[j])
            ++j;
        if(j==_basis)
            return 0;
    }
    return 1;
}
void longvalue::get_image(const char *p, const int _basis)
{
    basis = _basis;  //основание системы счисления
    size = strlen(p); //количество цифер

    int first_el = 0;
    int i = size-1;
    if(p[0]=='-')
    {
        positive = false;
        ++first_el; //нулевой элемент - знаковый. не надо его сохранять в массив чисел
        size -= 1; //память под знаковый элемент выделять не нужно
    }
    else
        positive = true;
    value = (int*)malloc(size*4);

    /*можно приступать к копированию*/
    for(int j = 0; i>=first_el; --i, ++j)
        value[j] = char_to_int(p[i],_basis);
}
int longvalue::char_to_int(const char c, const int _basis) const
{
    int i;
    for(i = 0; i<=_basis; ++i)
        if(c == values[i])
            return i;
    return 0; //на всякий случай
}
char longvalue::int_to_char(const int i) const
{
    return values[i];
}
int* longvalue::valuecpy() const
{
    int* result =(int*) malloc(size*4);
    for(int i = 0; i < size; ++i)
        result[i] = value[i];
    return result;
}

longvalue::longvalue(const char *v,const int _basis)
{
    if(valuechk(v,_basis))
        get_image(v,_basis);
    else
        get_image("0",0);
}
longvalue::longvalue(const longvalue &p)
{
    basis = p.basis;
    positive = p.positive;
    size = p.size;
    /*под значение надо выделить новую область памяти*/
    value = p.valuecpy();
}
longvalue& longvalue::operator =(const longvalue &p)
{
    basis = p.basis;
    positive = p.positive;
    size = p.size;
    free(value); //освобождаем память, так какследующая инструкция выделяет новую
    value = p.valuecpy();
    return *this;
}
std::ostream& operator <<(std::ostream& strm, const longvalue& p)
{
    if(!p.positive)
        strm << "-";
    for(int i = p.size-1; i>=0; --i)
        strm << p.int_to_char(p.value[i]); //дружественный функции имеют доступ к полям и методам только через объект
    return strm;
}
/*операция извлечения из потока*/
std::istream& operator >>(std::istream& strm, longvalue &p)
{
    char *result = 0;
    char r = 0;
    int size = 0; //количество символов в строке
    while(1)
    {
        std::cin >> r;
        if(r!=' ')
        {
            ++size;
            result = (char*)realloc(result,size+1);
            result[size-1] = r;
            result[size] = '\0'; //realloc не оконечивает выделенную память нулем
            continue;
        }
        break;
    }
    int basis;
    strm >> basis;
    free(p.value);
    if(p.valuechk(result, basis))
        p.get_image(result,basis);
    else
        p.get_image("0",0);
    return strm;
}
/*нахождение суммы*/
longvalue longvalue::operator +(const longvalue &p)
{
    return sum(*this,p);
}
longvalue longvalue::sum(const longvalue &p1, const longvalue &p2) const
{

    /*если базис чисел разный, то возвращаем ноль. не будем считать*/
    if(p1.basis != p2.basis || p1.basis==0) //если базис первого слагаемого 0, то базис второго слагаемого проверять не надо
        return longvalue("0",0);

    longvalue *result;
    /*образ числа будем складывать "в столбик"*/
    int *sum=0; //накопитель для суммы.
    int s; //сумма двух слагаемых
    int carry = 0; //перенос в старший разряд
    int i = 0;

    /*если оба числа имеют одинаковый знак, их можно складывать*/
    if(p1.positive == p2.positive)
    {
        while(i<p1.size)
        {
            if(i < p2.size)
                s = p1.value[i] + p2.value[i] + carry;
            else
                s = p1.value[i] + carry;
            sum = (int*)realloc(sum,(i+1)*4);
            sum[i] = s % p1.basis;
            carry = s / p1.basis;
            ++i;
        }
        while(i<p2.size)
        {
            //остались еще элементы в объекте p
            s = p2.value[i] + carry;
            sum = (int*)realloc((int*)sum,(i+1)*4);
            sum[i] = s % p1.basis;
            carry = s / p1.basis;
            ++i;
        }
        if(carry)
        {
            //остался еще перенос в старший разряд
            sum = (int*)realloc((int*)sum,(i+1)*4);
            sum[i] = carry;
            ++i;
        }
        result = new longvalue();
        result->value = sum;
        result->positive = p1.positive;
        result->size = i;
        return *result;
    }
    else
    if(!positive)
    {
        /*первое слагаемое отрицательное, второе положительное. Сложение
          можно свести к вычитанию первого слагаемого из второго
          знак корректирвоать не надо, поэтому можно сразу вернуть результат
          вычитания
        */
        return sub(p2,p1);
    }
    else
    {
        /*второе слагаемое отрицательное. Сложение можно свести к вычитанию
          второго слагаемого из первого
          знак корретировать не надо
        */
        return sub(p1,p2);
    }

    //return result;
}

/*нахождение разности*/
longvalue longvalue::operator -(const longvalue &p)
{
    return sub(*this,p);
}
longvalue longvalue::sub(const longvalue &p1, const longvalue &p2) const
{
    /*если базис чисел разный, то возвращаем ноль. не будем считать*/
    if(p1.basis != p2.basis || basis==0) //если базис первого слагаемого 0, то базис второго слагаемого проверять не надо
        return longvalue("0",0);

    longvalue *result; //результат вычитания
    int *sub; //массив, хранящий результат вычитания
    int s; //разность между двумя числами
    int rest = 0; // остаток
    int i = 0;

    /*Если оба числа отрицательные, то складываем их, но оставляем отрицаетльный знак*/
    if(!p1.positive && !p2.positive)
    {

    }
    int r = valuecmp(p1,p2);
    if(r<0)
    {
        //отнимаем p1 из p2
    }
    if(r>0)
    {
        //отнимаем p2 из p1
    }
    //значения равны, возвращаем О
    return longvalue("0",0);
}
/*сравнивает 2 значения друг с другом*/
int longvalue::valuecmp(const longvalue &p1, const longvalue &p2) const
{
    if(p1.positive && !p2.positive)
        return 1;
    if(!p1.positive && p2.positive)
        return -1;

    /*так как в начале числа могут присутствовать начальные нули
      сравнения старших разрядов не достаточно*/
    int i = p1.size - 1;
    int j = p2.size -1;
    while(i>=0 && j>=0)
    {
        if(i < j)
        {
            if(p2.value[j]>0)
            {
                if(p1.positive) //положительность второго значения проверять не обязательно
                    return -1;
                else
                    return 1;
            }
            else
                --j;
        }
        else
        if(i==j)
        {
            if(p1.value[i] > p2.value[j])
            {
                if(p1.positive)
                    return 1;
                else
                    return -1;
            }
            if(p1.value[i] < p2.value[j])
            {
                if(p1.positive)
                    return -1;
                else
                    return 1;
            }
            --i;
            --j;
        }
        else
        if(i > j)
        {
            if(p1.value[i]>0)
            {
                if(p1.positive)
                    return 1;
                else
                    return -1;
            }
            else
                --i;
        }
    }
    return 0; //если вышли из цикла, значит i==j==-1, что означает - значения равны.
}
bool longvalue::operator <(const longvalue &p)
{
    if(valuecmp(*this,p)==-1)
        return true;
    return false;
}
bool longvalue::operator >(const longvalue &p)
{
    if(valuecmp(*this,p)==1)
        return true;
    return false;
}
bool longvalue::operator ==(const longvalue &p)
{
    if(valuecmp(*this,p)==0)
        return true;
    return false;
}

const char *longvalue::values = "0123456789ABCDEF";

Это сообщение отредактировал(а) Чoо - 14.12.2010, 23:17

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 15.12.2010, 14:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(Чoо @ 15.12.2010, 00:06

)

Наверное я ошибся с выбором профессии, раз лениво кодить

Хорошего программиста именно лень и отличает.

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

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 15.12.2010, 15:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

Цитата(bsa @ 15.12.2010, 14:34

)

Хорошего программиста именно лень и отличает.

**
тоесть работать именно с двоичным числом, как работает сам компьютер? (ну применять добавочные и обратные коды тоесть)
только в нашем случае роль разрядной сетки выполняет массив.

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

Чoо

Дата 15.12.2010, 22:22 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

во чо получилось:

Код


/*
    Класс "Длинное целое двоичное число".
    Объявите класс "длинное целое двоичное число", объект которого можно
    сконструировать из массива символов. Перегрузите все арифметические операции,
    операции сравнения, извлечение из потока и помещение в поток.
 */

#include <iostream>
#include <cstring>
#include <cstdlib>



class longvalue{
private:
    int *value; //массив-образ числа
    int size; //количество элементов в образе (что бы не выйти за границы массива)
    static const char *values; //хранит элементы, допустимые в данной системе счисления

    void get_image(const char* p); //получает образ числа (с конца)
    int char_to_int(const char c) const;
    char int_to_char(const int i) const;
    int* valuecpy() const; //копирует образ числа во вновь выделенную память


    void inverse(); //инвертирует значение value и возвращает указатель на новый массив
    void neg(); //дополняет до двух value и возвращает указатель на новый массив

    void allign(longvalue &p, const int old_size, const int new_size);

    /*конструктор, который используется только в neg => надо подумать как от него избавиться,
      так как он вызывает лишнюю путаницу*/
    longvalue(int* _value, int _size)
    {
        value = _value;
        size = _size;
    }

public:
    //longvalue(){value = 0; size = 0;};
    longvalue(const char *v);
    /*нужно определить конструктор копирования, так как если использовать конструктор копирования
      по умолчанию, то он будет копировать только указатель на значение value, что не приемлимо
    */
    longvalue(const longvalue &p);
    ~longvalue()
    {
        free(value);
    }
    /*оператор присвоения
      при приравнивании объектов важно копировать область памяти, на которую указывает value
    */
    longvalue& operator =(const longvalue &p); //изменяет состояние объекта
    /*оператор помещения в поток*/
    friend std::ostream& operator <<(std::ostream& strm, const longvalue &p);
    /*оператор извлечения из потока*/
    friend std::istream& operator >>(std::istream& strm, longvalue &p);
    /*сложение*/
    longvalue operator +(const longvalue &p);
    void add(longvalue &p);
    /*вычитание*/
    longvalue operator -(const longvalue &p);
    /*сравнение. < -1, == 0, > 1 */
    int valuecmp(const longvalue &p1, const longvalue &p2) const;
    bool operator <(const longvalue &p);
    bool operator >(const longvalue &p);
    bool operator ==(const longvalue &p);



};
void longvalue::get_image(const char *p)
{    
    size = strlen(p);
    int char_count = size;
    int first_el = 0;
    if(p[0]=='-')
    {
        ++first_el;
        ++size; //что бы случайно не переполнить "разрядную сетку" добавляем нулевой элемент
        value = (int*)malloc(size*4);
        value[size-2] = 0;
        value[size-1] = 1; //знак отрицательного числа
    }
    else
    {
        ++size; ++size;
        value = (int*)malloc(size*4);
        value[size-2] = 0;
        value[size-1] = 0;
    }
    //образ числа будем харинть в прямом коде (понадобится для умножения и деления)
    for(int i = char_count-1, j = 0; i >= first_el; --i, ++j)
        value[j] = char_to_int(p[i]);
}

int longvalue::char_to_int(const char c) const
{
    int i;
    for(i = 0; i<=2; ++i) //работаем в двоичной системе счисления
        if(c == values[i])
            return i;
    return 0; //на всякий случай
}
char longvalue::int_to_char(const int i) const
{
    return values[i];
}
int* longvalue::valuecpy() const
{
    int* result =(int*) malloc(size*4);
    for(int i = 0; i < size; ++i)
        result[i] = value[i];
    return result;
}

longvalue::longvalue(const char *v)
{
    //работаем с двоичной системой счисления и предполагаем, что данные введены корректно
    get_image(v);
}
longvalue::longvalue(const longvalue &p)
{
    size = p.size;
    /*под значение надо выделить новую область памяти*/
    value = p.valuecpy();
}
longvalue& longvalue::operator =(const longvalue &p)
{
    size = p.size;
    free(value); //освобождаем память, так какследующая инструкция выделяет новую
    value = p.valuecpy();
    return *this;
}
std::ostream& operator <<(std::ostream& strm, const longvalue& p)
{
    if(!p.value[p.size-1])
        strm << "+";
    else
        strm << "-";
    for(int i = p.size-2; i>=0; --i)
        strm << p.int_to_char(p.value[i]); //дружественный функции имеют доступ к полям и методам только через объект
    return strm;
}
/*операция извлечения из потока*/
std::istream& operator >>(std::istream& strm, longvalue &p)
{
    /*пока не реализовано*/
    return strm;
}
/*нахождение суммы*/
longvalue longvalue::operator +(const longvalue &p)
{
    longvalue tmp1(*this), tmp2(p); //2 слагаемых
    if(tmp1.value[tmp1.size-1] && tmp2.value[tmp2.size-1])
    {
        //оба числа отрицательные. Просто складываем и меняем знак
        tmp1.add(tmp2);
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
        return longvalue(tmp1);
    }
    if(tmp1.value[tmp1.size-1])
    {
        //первое слагаемое надо дополнить до двух, предварительно обратив знаковый разряд в ноль
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
        tmp1.neg();
    }
    if(tmp2.value[tmp2.size-1])
    {
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.neg();
    }
    tmp1.add(tmp2);
    return tmp1;
}

void longvalue::allign(longvalue &p, const int old_size, const int new_size)
{
    int sign = p.value[old_size-1];
    p.value = (int*)realloc(value,new_size*4);
    for(int i = old_size-1; i<new_size-1; ++i)
        p.value[i] = 0;
    p.value[new_size-1] = sign;
    p.size = new_size;
}

void longvalue::add(longvalue &p)
{
    //если слагаемые имеют разное количество элементов, дополняем более маленькое
    if(this->size < p.size)
        allign(*this,size,p.size);
    else
        if(p.size < this->size)
            allign(p,p.size,size);
    //оба слагаемых имеют одинаковое количество элементов, что упрощает их сложение
    int* result=0; //накопитель для суммы
    int s; //сумма двух чисел из массивов
    int carry = 0; //перенос в старший разряд
    int i = 0; //индекс массива

    while(i<size)
    {
        s = value[i] + p.value[i] + carry;
        result = (int*)realloc(result,(i+1)*4);
        result[i] = s%2; //2 - двоичная система счисления
        carry = s/2;
        ++i;
    }
    free(this->value);
    this->value = result;
}
longvalue longvalue::operator -(const longvalue &p)
{
    longvalue tmp1(p), tmp2(*this);
    tmp1.neg();
    tmp2.add(tmp1);
    return tmp2;
}

/*сравнивает 2 значения друг с другом*/
int longvalue::valuecmp(const longvalue &p1, const longvalue &p2) const
{
    /*не реализовано*/
    return 0; //если вышли из цикла, значит i==j==-1, что означает - значения равны.
}
bool longvalue::operator <(const longvalue &p)
{
    if(valuecmp(*this,p)==-1)
        return true;
    return false;
}
bool longvalue::operator >(const longvalue &p)
{
    if(valuecmp(*this,p)==1)
        return true;
    return false;
}
bool longvalue::operator ==(const longvalue &p)
{
    if(valuecmp(*this,p)==0)
        return true;
    return false;
}

void longvalue::inverse()
{
    for(int i = 0; i<size; ++i)
        this->value[i] = !this->value[i];
}
void longvalue::neg()
{
    this->inverse();
    int* value_tmp = (int*)malloc(size*4);
    value_tmp[0] = 1;
    for(int i = 1; i < size - 1; ++i)
        value_tmp[i] = 0;
    longvalue tmp(value_tmp,size);
    this->add(tmp);
}

const char *longvalue::values = "0123456789ABCDEF";

int main()
{
    using std::cout;
    using std::endl;
    longvalue a( "-110");
    longvalue b("-0110");
    longvalue c = a - b;
    cout << c << endl;



    return 0;
}

. Весь день убил. Единственное что, при выводе результата не убираю лишние нули. Еще не сделал.
Всё, кроме сложения, вычитания и вывода в поток придется перегружать заново. Но это уже не трудно будет.
Есть сомнения в коде:

Добавлено @ 22:23
на 157 строке. Я там еще прокоментировал. Не уверен, правильно ли я складываю 2 отрицательных числа.

Это сообщение отредактировал(а) Чoо - 15.12.2010, 23:59

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

Чoо

Дата 16.12.2010, 00:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

ан нет. где-то накасячил. не правильно считает, если от отрицательного отнять отрицательное

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 16.12.2010, 13:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Чoо, в дополнительном коде считать не стоит - он используется тогда, когда количество разрядов постоянно. А в нашем случае нет. Более того, следует использовать не int, а uint32_t. Так как в результате умножения у тебя будет uint64_t. В случае int ты это жестко проконтролировать не сможешь.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 16.12.2010, 13:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

Цитата(bsa @ 16.12.2010, 13:21

)

в дополнительном коде считать не стоит - он используется тогда, когда количество разрядов постоянно.

а как тогда считать в прямом? обратный код же, по сути, тоже зависит от количества разрядов. Да и отличается от дополнительного лишь тем, что единица не прибавлена.
Просто я пока не вижу, как по-другому свести операцию вычитания к сложению.

Цитата(bsa @ 16.12.2010, 13:21

)

Более того, следует использовать не int, а uint32_t.

спасибо, что предупредили smile

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

bsa

Дата 16.12.2010, 14:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Чoо, очень просто - не своди. Вычитание делай через вычитание.
Посмотри как сделано здесь: BigDigits.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Чoо

Дата 16.12.2010, 14:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 313
Регистрация: 22.9.2009

Репутация: 4
Всего: 4

bsa, я кстати сейчас прикинул вычисления в обратном коде. там если выходим за границы разрядной сетки, надо эту единиц, которая вышла, прибавить к результату. если единица уходит - значит число положительное. Если нет - отрицательное и нужно инвертировать все разряды кроме знакового - и получим число в прямом коде. Единственное что, число 0 будет представлено двумя числами (если 8 разрядов, то: +0 = 0000 0000; -0 = 1111 1111).
**
смотрю ссылку

--------------------

OS: Debian Squeeze (kernel 3.8.2)
IDE: qtCreator 1.3.1; Eclipse SDK 3.5.2

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »