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

Дата 15.12.2007, 20:44 (ссылка)

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

Загрузка ...

Эксперт

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

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

pompei, а если это переменные типа SuperPuperClass? И перегруженного оператора ^ нет (а если есть, может он работает тоже как-то super puper)

EnShTe1N

Дата 16.12.2007, 10:08 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(Silent_s @ 14.12.2007, 22:17)

Прикольные задачки!) А они для личного обдумывания? smile

Silent_s, если что будет не понятно, то можеш спрашивать. А так постарайся решить сам

Silent_s

Дата 16.12.2007, 11:09 (ссылка)

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

Загрузка ...

Шустрый

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

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

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

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

Мой блог

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

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

Загрузка ...

Опытный

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

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

Введите с клавиатуры 10 чисел. Затем выведите сначала одно самое большое, потом 2 самых больших и, наконец, 3 самых больших.
Можно использовать циклы, условную инструкцию if ... then ... else и переменные типа int. Больше ни чего smile

решение(может кривое, но лучше не придумал):

Код


#include <iostream>
using namespace std;

int main()
{
    int k, max = 0, max2 = 0, max3 = 0;
    cout << "Введитe 10 чисел" << endl << endl;

    for (int i = 1; i<=10; ++i)
    {
      cin >> k;
      if(k>max)
      {
          max3 = max2;
          max2 = max;
          max = k;
      }
      else
      {
          if ((k<=max)&&(k>max2))
          {
              max3 = max2;
              max2 = k;
          }
          else
          {
              if ((k<=max2)&&(k>max3))
                  max3 = k;
          }
       }
   }
    cout << "наибольшее число: " << max << endl;
    cout << "наибольшие 2 числа: " << max << "; " << max2 << endl;
    cout << "наибольшие 3 числа: " << max << "; " << max2 << "; " << max3 << endl;
    return 0;
}

жаль спойлера нет.

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

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

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

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

Загрузка ...

Опытный

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

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

вот еще одна задача.
Определите функцию, которая возвращает ссылку на хотя бы один седловой элемент матрицы или NULL (NIL), а также "координаты" на этот узловой элемент (седловым элементом называется элемент, который наименьший в своей строке и одновременно наибольший в своем столбце (и наоборот)).

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

Код


#include <iostream>
using namespace std;
int *LineMinMax(int a[], int m1, int m2, int number, bool max, int &column)
{
    int *buf;
    buf=&a[number*m2];
    column = 0;
    int i=1;
    while (i<m2)
    {
        if (!max)
        {
        if (a[number*m2+i]<*buf)
            {
                buf=&a[number*m2+i];
                column = i;
            }
        else
            if (a[number*m2+i]==*buf)
                column = -1;
        }
        else
        {
            if (a[number*m2+i]>*buf)
            {
                    buf=&a[number*m2+i];
                    column = i;
            }
            else
                if (a[number*m2+i]==*buf)
                column = - 1;
        }
        i++;

    }
    if (column<0) return NULL;
    else return buf;
}
int *ColumnMinMax(int a[], int m1, int m2, int number, bool max, int &line)
{
    int *buf;
    buf = &a[number]; line = 0;
    int i=1;
    while (i<m1)
    {
        if (!max)
        {
            if (a[i*m2+number]<*buf)
            {
                buf = &a[i*m2+number];
                line = i;
            }
            else
            {
                if (a[i*m2+number]==*buf)
                    line = -1;
            }
        }
        else
        {
            if (a[i*m2+number]>*buf)
            {
                buf = &a[i*m2+number];
                line = i;
            }
            else
            {
                if (a[i*m2+number]==*buf)
                    line = -1;
            }
        }
        i++;
    }
    if (line < 0) return NULL;
    else return buf;
}
/*следующая функция возвращает указатель на седловой элемент или NULL */
int *findsedl (int a[],int m1, int m2, int &line, int &column)
{
    int *minmaxL = NULL, *minmaxC = NULL;
    bool find=0; //1 если будет найден седловой элемент
    int i=0;
    while ((i<m1) && !find)
    {
        //сначала ищем минимум в ряде i
        minmaxL=LineMinMax((int *)a,m1,m2,i,0, column);
        if (minmaxL!=NULL) //зачит в ряде i есть минимальный элемент. Теперь надо проверить столбец
                         // в котором находится этот элемент. Если он Max - то этот элемент седловой
        {
            minmaxC=ColumnMinMax((int *)a,m1,m2,column,1,line);
            if (minmaxL==minmaxC)
                find = 1;
        }
        i++;
    }
    if (!find)
    {
        //седловой элемент, при условиях в ряду минимум, в столбце максимум, не нашли, пробуем
        //наоборот
        i=0;
        while ((i<m1)&&!find)
        {
            minmaxL=LineMinMax((int *)a,m1,m2,i,1,column);
            if (minmaxL!=NULL)
            {
                minmaxC = ColumnMinMax((int *)a,m1,m2,column,0,line);
                if (minmaxL==minmaxC)
                    find = 1;
            }
            ++i;
        }
    }
    if (find) return minmaxL;
    else return NULL;
}

int main()
{
    int a[3][4] = {{2,-5,-5,11},{8,4,-4,9},{-5,-5,-4,10}};
    int *sedl, line, column;
    cout << "Матрица m:" << endl;
    for(int i=0;i<3; ++i)
    {
        for (int j=0;j<4; j++)
            cout << a[i][j] << "   ";
        cout << endl;
    }
    sedl = findsedl((int *)a,3,4,line,column);
    if (sedl!=NULL)
    {
        cout << "седловой элемент: a[" << line << "," << column << "] = " << *sedl;
        cout << " (нумерация элементов с нуля)" << endl;
    }

    else cout << "седловой элемент не найден" << endl;
    return 0;
}

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

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

djamshud

Дата 16.9.2010, 00:19 (ссылка)

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

Загрузка ...

Пердупержденный

Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 23.11.2009

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

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

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

'Cuz I never walk away from what I know is right
Alice Cooper - Freedom

Дата 16.9.2010, 00:48 (ссылка)

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

Загрузка ...

Опытный

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

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

djamshud, мне тоже кажется, что кода очень много smile

. Буду благодарен, если объясните про кеширование.

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

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

djamshud

Дата 16.9.2010, 13:06 (ссылка)

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

Загрузка ...

Пердупержденный

Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 23.11.2009

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

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

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

'Cuz I never walk away from what I know is right
Alice Cooper - Freedom

Дата 16.9.2010, 18:43 (ссылка)

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

Загрузка ...

Опытный

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

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

djamshud, да, правильно поняли. Максимум каждый раз пересчитываю. что ж.. переделаю smile

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

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

Дата 19.9.2010, 16:54 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Код


#include <iostream>
#include <string.h>
using namespace std;

struct node{
    char *name;
    node *next;
};

int main()
{
    char s[80], *s2;
    node *head = 0;
    cout << "Вводите имена для списка 1 (не более 80и символов)" << endl;
    for(int i=0; i<5; ++i)
    {
        cin >> s;
        s2 = new char[strlen(s)+1];
        strcpy(s2,s);
        head = addnode(s2,head);
    }
    cout << "Вывод списка" << endl;
    showlist(head);
    cout << "Записей в списке: " << calcnodes(head) << "." << endl;
    //тперь будем удалять текущий узел и выводить список на экран
    while(head)
    {
        head=deletenode(head);
        showlist(head);
        cout<<endl;
    }
    clearlist(head);
    return 0;
}
//добавление новых элементов:
node  *addnode(char *s, node *head)
{
    node *n;
    n = new node;
    n->name = s;
    if(!head)
    {
        n->next = n;
        head = n;
    }
    else
    {
        n->next = head->next;
        head->next = n;
    }
    return n;
}
//вывод списка:
void showlist(node *head)
{
    node *buf;
    if (head)
    {
        buf = head;
        head = head->next;
        while (buf!=head)
        {
            cout << head->name << endl;
            head = head->next;
        }
        cout << head->name << endl;
    }
    else
        cout << "Список пуст" <<endl;
}
//подсчет количества элементов:
int calcnodes(node *head)
{
    node *buf;
    int i=0;
    if(head)
    {
        buf = head;
        head = head->next;
        while(buf!=head)
        {
            i++;
            head = head->next;
        }
        i++;
        return i;
    }
    else return 0;
}
//удаление текущего элемента:
node *deletenode(node *head)
{
    //придется каждый раз проходить список полностью
    if(head)
    {
        if (head==head->next)
        {
            delete head;
            head = 0;
        }
        else
        {
            node *curr = head;
            while(head->next!=curr)
                head = head->next;
            head->next = curr->next;
            delete []curr->name;
            delete curr;
        }
    }
    return head;
}
//очистка списка:
void clearlist(node *head)
{
    node *curr;
    if(head)
    {
        curr = head->next;
        head->next = 0;
        head = curr;
        while (head)
        {
            curr = head->next;
            delete []head->name;
            delete head;
            head = curr;
        }
    }
}

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

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

vnf

Дата 19.9.2010, 17:02 (ссылка)

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

Загрузка ...

Шустрый

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

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

я бы всё в класс упаковал, привыкайте к ООП

Дата 19.9.2010, 17:29 (ссылка)

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

Загрузка ...

Опытный

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

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

vnf, спасибо за замечание, я бы тоже упаковал (если б на паскале писал). Просто в с++ пока не дошел до раздела, посвященному ООП - стараюсь материал осваивать последовательно smile

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

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

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

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

Загрузка ...

Опытный

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

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

снова я.. вернулсо..
отсортировать массив слиянием по следующему алгоритму:

Цитата

1. Разобьем сортируемый массив на 2 половины - (a1 и b1), каждую из которых будем рассматривать как массив, состоящий из упорядоченных участков единичной длины.
2. Соединим их, применяя алгоритм слияния к упорядоченным участкам; один участок пары будем брать из массива А1, а другой - из массива В1. Результаты слияния какждой пары участков будем заносить попеременно в два новых массива - А2 и В2. в новых массивах упорядоченные участки будут иметь длину, равную сумме длин исходных участков, т.е. 2.
3. Сольем теперь упорядоченные участки массивов А2 и В2, попеременно записывая результаты в освободившиеся массивы А1 и В1. Длина упорядоченных участков снова удвоится и станет равной 4.
4. Будем повторять слияние массивов, каждый раз меняя ролями пары массивов (А1,В1) и (А2,В2), пока длина упорядоченного участка не сравняется с длинной исходного массива. В этот момент сортировку можно считать оконченной.

. Вобщем данного алгоритма я придерживался (потому что если точно его следовать, то сортировка проводилась корректно, только если количество элементов в исходном массиве было кратно степени двойки). Кода получилось много, но работает smile

Код


#include <iostream>
using namespace std;

void merge(int *A,int *B, int *rA, int *rB, int D) // первая половина, вторая, количество элементов в первой
                                                    // половине, во второй, количество элементов в группе соотв.
{
    int n=*rA+*rB;
    int A2[n], B2[n];
    int ia1 = 0;
    int ib1 = 0;
    int ia2 = 0;
    int ib2 = 0;
    /* ^^ текущий элемент в массиве А, Б, А2, Б2 соответственно^^ */

    int iap;
    int ibp;
    /*^^ дабы не выйти за границы групп элементов */

    int i = 0;
    while(ia1<*rA && ib1<*rB)
    {
        iap = ia1 + D; //устанавливаем сколько элементов может быть в группе
        if(iap>*rA) iap = *rA; //элементов в группе не может быть больше количества элементов в массиве
        ibp = ib1 + D;
        if(ibp>*rB) ibp = *rB;
        if(!i) //группы элементов записываем поочередно в массив A2 и B2
        {
            while(ia1<iap && ib1<ibp)
            {
                if(A[ia1]<B[ib1])
                {
                    A2[ia2] = A[ia1];
                    ia1++;
                }
                else
                {
                    A2[ia2] = B[ib1];
                    ib1++;
                }
                ia2++;
            }
            if(ia1==iap) //сливаем массив B
            {
                while(ib1<ibp)
                {
                    A2[ia2] = B[ib1];
                    ib1++;
                    ia2++;
                }
            }
            else //сливаем массив А
            {
                while(ia1<iap)
                {
                    A2[ia2] = A[ia1];
                    ia1++;
                    ia2++;
                }
            }
        }
        else
        {
            //все то же самое, только заполняем половинку B2
            while(ia1<iap && ib1<ibp)
            {
                if(A[ia1]<B[ib1])
                {
                    B2[ib2] = A[ia1];
                    ia1++;
                }
                else
                {
                    B2[ib2] = B[ib1];
                    ib1++;
                }
                ib2++;
            }
            if(ia1==iap) //сливаем массив b
            {
                while(ib1<ibp)
                {
                    B2[ib2] = B[ib1];
                    ib1++;
                    ib2++;
                }
            }
            else //сливаем массив А
            {
                while(ia1<iap)
                {
                    B2[ib2] = A[ia1];
                    ia1++;
                    ib2++;
                }
            }
        }
        i=!i;
    }
    if(ia1==*rA) //сольем B без обработки
        if(!i)
            while(ib1<*rB)
            {
                A2[ia2] = B[ib1];
                ia2++;
                ib1++;
            }
        else
            while(ib1<*rB)
            {
                B2[ib2] = B[ib1];
                ib2++;
                ib1++;
            }
    else
        if(!i)
            while(ia1<*rA)
            {
                A2[ia2] = A[ia1];
                ia2++;
                ia1++;
            }
        else
            while(ia1<*rA)
            {
                B2[ib2] = A[ia1];
                ib2++;
                ia1++;
            }
    *rA = ia2;
    *rB = ib2;
    //копируем массив а2 в а1;
    for(int i=0;i<*rA;i++)
        A[i] = A2[i];
    //delete []A2;
    // копируем массив  б2 в б1
    for(int i=0;i<*rB;i++)
        B[i]=B2[i];
    //delete []B2;
}

void mergesort(int *A,int n)
{
    int a[n], b[n];
    int a_count,b_count; //количество элементов в массива a1 и b1 соответственно

    /* распределяем массив А между a и b */
    a_count = 0;
    b_count = 0;
    int j = 0;
    for(int i = 0; i<n; ++i, j = !j)
    {
      if(!j)
      {
        a[a_count] = A[i];
        a_count++;
      }
      else
      {
          b[b_count] = A[i];
          b_count++;
      }

    }

    /*длина упорядоченного участка в начале = 1 */
    int D = 1;

    j=1; //j будет показывать шаг
    while(D<n)
    {
        cout << "step " << j << ":" << "\n";
        cout << "first part: ";
        int k=0;
        //отобразим массивы a и b
        for(int i = 0; i<a_count; i++, k++)
        {
            if(k==D)
            {
                cout << "   ";
                k=0;
            }
            else
                if(i!=0)
                    cout << ",";
            cout << a[i];

        }
        cout << endl << "second part:";
        k=0;
        for(int i = 0; i<b_count; i++, k++)
        {
            if(k==D)
            {
                cout << "   ";
                k=0;
            }
            else
                if(i!=0)
                    cout << ",";
            cout << b[i];

        }
        cout << endl;
        merge(a,b,&a_count,&b_count,D);
        j++;
        D *= 2;
    }
    /* Массив отсортирован. он находится в массиве a.
       Теперь его нужно скопировать в массив А, что бы
       показать из главной процедуры
    */
    for(int i =0; i<a_count; i++)
        A[i] = a[i];

}

int main()
{
    const int n = 7;
    int a[] = {1,3,2,5,4,6,8,7,9,10,16,15,11,14,12,13};
    cout << "array before sorting: ";
    for(int i=0;i<n;++i)
        if(i<n-1)
            cout << a[i] << ", ";
        else
            cout <<a[i] << endl;
    mergesort(a,n);
    /* отобразим отсортированный массив */
    cout << endl << "array is sorted: ";
    for(int i=0;i<n;i++)
    {
        cout << a[i];
        if(i<n-1)
            cout << ",";
        else
            cout << endl;
    }
    return 0;
}

на всякий я всё подробно откомментировал.
Следующим этапом буду сортировать строки в текстовом файле(надо бы обойтись тремя файлами).

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

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

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

Дата 12.11.2010, 12:02 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 11.11.2010, 14:36

)

Следующим этапом буду сортировать строки в текстовом файле(надо бы обойтись тремя файлами).

т.е. загрузить, отсортировать и выгрузить нельзя? Предполагается, что файл огромного размера?
Тогда делать нужно так:
1. сделать массив, хранящий индексы на строки исходного файла (читаешь исходный файл построчно и записываешь текущее положение в файле)
2. сортируешь массив (естественно, сравнивая строки, а не их положение)
3. создаешь результирующий текстовый файл.

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

Дата 12.11.2010, 12:46 (ссылка)

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

Загрузка ...

Эксперт

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

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

bsa, а если строк в файле так много, что массив, хранящий индексы на строки исходного файла не помещается в память?

Это сообщение отредактировал(а) baldina - 12.11.2010, 12:49

Дата 12.11.2010, 12:51 (ссылка)

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

Загрузка ...

Опытный

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

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

все верно. Если считывать в память, то файл можно отсортировать и более эффективно по скорости, однако файл может не поместиться в оперативку.
С индексами интересней, но был бы смысл, если бы они уменьшили количество операций ввода вывода. И кода будет больше...

Ща, я уже почти написал smile

.

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

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

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

Дата 12.11.2010, 14:28 (ссылка)

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

Загрузка ...

Опытный

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

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

Код


/*
 имеется текстовый файл, строки которого не упорядочены. Упорядочите их
 при помощи сортировки слиянием
 */
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

/* функция получает путь и имя файла, возвращает указатель на полный путь */
char *get_full_patch(const char *patch, const char *fname)
{
    char *dest;
    int l;
    l=strlen(patch)+strlen(fname);
    dest = new char[l];
    dest = strcpy(dest,patch);
    dest = strcat(dest,fname);
    return dest;
}

/* функция составляет полный путь к файлу и открывает его.
*/
FILE *OpenFile(const char *patch, const char *fname, const char *mode)
{
    char *fullpatch;
    fullpatch = get_full_patch(patch,fname);
    FILE *f = fopen(fullpatch,mode);
    delete []fullpatch;

    return f;
}

/* функция сливает файлы а и б с заданным шагом, перезаписывая исходный файл
   a_count & b_count изменяем, что бы знать, по сколько считывать строк
   из файла (что бы делить можно было делить файл на части, если количество
   строк в нем не кратно степени двойки)
*/
void merge(const char *patch, const char *fname, int D)
{
    const int n = 100;
    char sbufA[n]; //буфер для чтения и сравнения строк
    char sbufB[n]; //буфер для чтения и сравнения строк


    /* откроем сортируемый файл для записи, временные файлы - для чтения */
    FILE *f = OpenFile(patch,fname,"wt");
    FILE *ftemp_a = OpenFile(patch,"temp_a","rt");
    FILE *ftemp_b = OpenFile(patch,"temp_b","rt");
    fgets(sbufA,n,ftemp_a);
    fgets(sbufB,n,ftemp_b);
    while(!feof(ftemp_a) && !feof(ftemp_b))
    {
        int i = 0;
        int j = 0;
        while(i < D && j < D && !feof(ftemp_a) && !feof(ftemp_b))
        {
            if(strcmp(sbufA,sbufB) < 0)
            {
                fputs(sbufA,f);
                fgets(sbufA,n,ftemp_a);
                i++;
            }
            else
            {
                fputs(sbufB,f);
                fgets(sbufB,n,ftemp_b);
                j++;
            }
        }
        if(i==D) //копируем остаток группы из файла Б
            while(j<D && !feof(ftemp_b))
            {
                fputs(sbufB,f);
                fgets(sbufB,n,ftemp_b);
                j++;
            }
        else
            if(j==D) //копируем остаток группы из файла А
                while(i<D && !feof(ftemp_a))
                {
                    fputs(sbufA,f);
                    fgets(sbufA,n,ftemp_a);
                    i++;
                }
    }

    /* вышли из цикла. Если в каком-либо файле что-то осталось
       копируем это в файл f
     */
    if(feof(ftemp_a))
        while(!feof(ftemp_b))
        {
            fputs(sbufB,f);
            fgets(sbufB,n,ftemp_b);
        }
    else
        if(feof(ftemp_b))
            while(!feof(ftemp_a))
            {
                fputs(sbufA,f);
                fgets(sbufA,n,ftemp_a);
            }

    fclose(f);
    fclose(ftemp_a);
    fclose(ftemp_b);
}

/* функция принимает путь к файлу и имя файла, копирует строки из него
   попеременно в файл А и в файл Б (a_count строк в файл А; b_count строк
   в файл Б)
   */
void CpyStringsFromFile(const char *patch, const char *fname, int D, int *strings_count)
{
    //char *fullpatch;
    int new_strings_count = 0;
    const int n = 100;
    char sbuf[n];
    /* открываем 3 файла:
       первый только для чтения. Это исходный файл.
       второй - для половины строк из исходного файла
       третий - для оставшейся половины
       */
    FILE *f = OpenFile(patch,fname,"rt");
    FILE *ftemp_a = OpenFile(patch,"temp_a","wt");
    FILE *ftemp_b = OpenFile(patch,"temp_b","wt");

    /* приступаем к копированию строк */
    while(!feof(f))
    {
        for(int i = 0; i<D && !feof(f);i++)
        {
            if(fgets(sbuf,n,f) != 0)
            {
                fputs(sbuf,ftemp_a);
                new_strings_count++;
            }
        }
        for(int i = 0; i<D && !feof(f);i++)
        {
            if(fgets(sbuf,n,f) != 0)
            {
                fputs(sbuf,ftemp_b);
                new_strings_count++;
            }
        }
    }

    /* строки скопировали. теперь можно закрыть файлы */
    fclose(f);
    fclose(ftemp_a);
    fclose(ftemp_b);

    /* выведем количество строк в файле */
    *strings_count = new_strings_count;
}


/* функция принимает путь к файлу, строки которого надо упорядочить по-возрастанию
 и сортирует файл */
void SortMerge(const char *patch, const char *fname)
{
    /* в начале длина упорядоченного участка = 1 */
    int D = 1;
    int strings_count;

    CpyStringsFromFile(patch,fname,D,&strings_count);
    while(D<strings_count)
    {
        merge(patch,fname,D);
        D *= 2;
        if(D<strings_count)
            /* копируем строки во временные файлы */
            CpyStringsFromFile(patch,fname,D,&strings_count);
    }

    /*раз вышли--
                знач отсортировали */

}

int main()
{
    SortMerge("/home/oem/Developed/Cpp/study/exercise/8.13.2/untitled1/","xxx.txt");
    cout << "file is sorted \n";
    return 0;
}

работает

. единственное что, не замерял время на сортировку файла. и не удалял временные файлы.
вообще думал что не справлюсь, так как сначала видел решение с использованием 4х файлов. эт потом понял как чо smile

... добавил.
А можно измерить скорость, если главную процедуру переписать следующим образом?:

Код


int main()
{
    timeval tp = {0,0}, tp2={0,0};
    gettimeofday(&tp,0);
    SortMerge("/home/oem/Developed/Cpp/study/exercise/8.13.2/untitled1/","xxx.txt");
    gettimeofday(&tp2,0);
    cout << "file is sorted (" << tp2.tv_sec - tp.tv_sec << "," <<  tp2.tv_usec - tp.tv_usec << "s)"  << "\n";
    return 0;
}

результат близок к правде, вот только смущает число после запятой (мерил секундомером, целая часть - совпадает с тем, что выдает программа).
на сортировку 3'163'420 строк тратится (28,684137s).
И да.. так кажется, что работа с файлом происходит не напрямую, как я ожидал, а через какой-то буфер. Сделал такой вывод, потому что светодиод, сигнализирующий обращение к жесткому диску, лишь изредка моргал и не было характерного "треска".

Это сообщение отредактировал(а) Чoо - 12.11.2010, 18:13

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

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

Дата 13.11.2010, 13:15 (ссылка)

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

Загрузка ...

Опытный

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

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

Дан большой текстовый файл с длиной строк не более 100 символов. Распечатайте 15 последних строк файла

Код


/* Дан большой текстовый файл с длиной строк не более 100 символов.
   Распечатайте 15 последних строк файла
   */
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    const int n = 100;
    char buf[n];
    long pos = 0;
    int fsize;
    int s_count = 0; //количество строк
    FILE *in = fopen("/home/oem/Developed/Cpp/study/exercise/8.13.3/untitled1/xxx.txt","rt");
    if(!in)
        return 0;  
    /* для начала определим размер файла */
    fseek(in,0,SEEK_END);
    fsize = ftell(in);

    /* последниее 15 строк займут не более 1500 байт, так как максимальный
       размер строки не превышает 100 символов. 1 символ = 1байт
       */
    if(fsize>1500)
        pos = fsize - 1500;
    fseek(in,pos,SEEK_SET);

    /*подсчитаем сколько строк от текущей позиции*/
    while(!feof(in))
        if(fgets(buf,n,in) !=0)
            s_count++;

    /* от позиции pos - s_count строк.
       Возвращаемся на pos и повторяем считывание, пока i не станет
       равно s_count-15. После этого можно будет вывести последние 15 строк файла
    */
    fseek(in,pos,SEEK_SET);
    for(int i = 0; i < s_count-15; i++)
        fgets(buf,n,in);

    /*выводим строки*/
    while(!feof(in))
        if(fgets(buf,n,in)!=0)
            cout << buf;

    fcloseall();
    return 0;
}

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

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

Дата 13.11.2010, 17:21 (ссылка)

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

Загрузка ...

Опытный

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

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

еще задача.. Нужна помощь..

Цитата

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

Для того, что бы воспользоваться алгоритмом бинарного поискА, мне нужно знать количество строк в файле, а так же уметь позиционироваться на нужную строку в файле.
Если я, что бы получить количество строк в файле, буду все их считывать, начиная от первой, возникает вопрос: смысл бинарного поискА, если я и так уже перебрал все строки. Так же, что бы установить указатель на нужную строку, мне нужны индексы (смещения) строк.
Намекните, куда копать, если не трудно..

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

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

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

Дата 13.11.2010, 23:24 (ссылка)

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

Загрузка ...

Эксперт

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

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

Чoо, ты с базами данных не работал? Особенно, от 1C: Предприятие. Так вот, там есть такая вещь, как индексные файлы. Т.е. файл содержащие индексную информацию о базе. Тебе нужно сделать такой же. Для этого необходимо сначала полностью прочитать словарь...

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

Дата 14.11.2010, 00:19 (ссылка)

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

Загрузка ...

Опытный

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

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

bsa, с базами данных работал (из серъезных - c firebird).
Я вот еще перечитал ваше сообщение, про сортировку большого файла, с использованием индексом. Вобщем начал делать, но там возникли вопросы. Поскольку заранее неизвестно количество строк, то и память выделить по ходу считывания строк - не получится (во всяком случае с массивами как это сделать я не знаю пока что), разве что используя списки, что в принципе и делаю. Может так же тогда поступить: сделать индексный файл, затем считать его в массив и приступить к сортировке?
Соотв. в этой задаче: сформировать индексный файл, считать его в массив, приступить к поиску?

Если всё понял правильно, то где разместить информацию о количестве проиндексированных строк(по интуиции, разместил бы первой записью)?

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

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

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

Дата 14.11.2010, 02:36 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 14.11.2010, 01:19

)

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

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

Цитата(Чoо @ 14.11.2010, 01:19

)

разве что используя списки

это очень медленно. Ты, надеюсь, знаешь, что случайный доступ к элементам списка невозможен с такой же скоростью, как к элементам простого массива?

Цитата(Чoо @ 14.11.2010, 01:19

)

Если всё понял правильно, то где разместить информацию о количестве проиндексированных строк(по интуиции, разместил бы первой записью)?

Количество строк равно количеству записей в индексном файле. Размер записи известен (4 или 8 байт). Путем нехитрого деления можно получить количество строк. Размер файла можно узнать используя: filesize = lseek(file, 0, SEEK_END);

Цитата(Чoо @ 14.11.2010, 01:19

)

Может так же тогда поступить: сделать индексный файл, затем считать его в массив и приступить к сортировке?

совсем не обязательно - он тоже может в память не поместиться. Ты должен будешь сортировать индексы прямо в файле.

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

Jmylia

Дата 14.11.2010, 02:42 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 12.10.2009
Где: Кривой Рог

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

Цитата(EnShTe1N @ 9.12.2007, 23:39)

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

Цитата

2. Даны переменные a и b. Напишите программу, которая будет менять значения этих переменных местами.

Решение:

Код


#include "stdafx.h"
#include <locale.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>


void main ()
{
    setlocale(LC_ALL, "");
    printf("Программа меняет местами значения переменных a и b. \n");
    printf("Для продолжения нажмите любую клавишу \n");
    _getch();
    double a,b;
    printf("Введите число а: \n");
    scanf("%lf", &a);
    printf("Введите число b: \n");
    scanf("%lf", &b);
    printf("После обработки компьютером число а=%lf, а b=%lf", b,a);
    _getch();
}

Цитата

3. Найдите x в степени 4, выполнив наименьшее возможное число умножений. То же самое для 5. x в степени 7. 6. x в степени 22.

Что бы не расписовать три задачи, решил написать три в одной:

Код


#include "stdafx.h"
#include <locale.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>


void main ()
{
    setlocale(LC_ALL, "");
    printf("Ищем x в степени 4, x в степени 7 и x в 22-ом стпени. \n");
    printf("Для продолжения нажмите любую клавишу \n");
    _getch();
    double x,x1,x2,x3;
    printf("Введите число x: \n");
    scanf("%lf", &x);
    x1=pow(x,4);
    x2=pow(x,7);
    x3=pow(x,22);
    printf("\n x в степени 4 равен: %lf;\n x в степени 7 равен: %lf;\n x в 22-ом степени равен: %lf;", x1,x2,x3);
    _getch();
}

Цитата

7. Даны 2 числа. Вывести наибольшее из них.

Восьмую не делал, сделал только седьмую, исходник ниже, в восьмой тоже самое только еще дописать число d и два условия

if (a<d<b)

и вот такое

if (d<d<a)

ну для большей четкости еще можно

if (a=b=d)

Код


#include "stdafx.h"
#include <stdio.h>
#include <locale.h>
#include <conio.h>
#include <math.h>

void main()
{
    setlocale(LC_ALL, "");
    printf("Дано 2 числа. Вывести наибольшее из них на екран. \n");
    printf("Для продолжения, нажмите любую клавишу. \n");
    _getch();
    double a,b;
    printf("Введите любое число: \n");
    scanf("%lf", &a);
    printf("Еще раз введите любое число, а программа выберит большее из них: \n");
    scanf("%lf", &b);

    if (a>b)
        printf("Программа опредилила что число a-%lf больше чем число b-%lf", a,b);
    if (a<b)
        printf("Программа опредилила что число a-%lf меньше от числа b-%lf", a,b);
    if (a=b)
        printf("Программа опредилила что число a-%lf равно числу b-%lf", a,b);
    _getch();
}

Цитата

11. Выведите на правильном русском языке, сколько прошло лет с указанного года (между 1 и 2006 годом н.э.) до 2007г. Например, если введено 1986, то надо вывести "21 год", а если 2002, то "5 лет".

Решение:

Код


#include "stdafx.h"
#include <math.h>
#include <locale.h>
#include <conio.h>
#include <stdio.h>

void main ()
{
    setlocale(LC_ALL, "");
    double a,b,c;
    printf("Введите любой год н.е. с 1 по 2010 включно. \n");
    scanf("%i", &u);
    c=2010;
    b=c-a;
    printf("С %u по 2010 проишло %u год(а)", a,b);
    _getch();
}

Цитата

15. Вычислите: a в степени b, b >= 0.

Решение:

Код


#include "stdafx.h"
#include <conio.h>
#include <math.h>
#include <locale.h>

void main ()

{
    double a,b;
    setlocale(LC_ALL, "");
    printf("Вычислите: a в степени b, b >=  0. \n");
    printf("Для продолжения вычисления нажмите любую клавишу. \n");
    _getch();
    printf("Введите число a: \n");
    scanf_s("%lf", &a);
    printf("Введите число b: \n");
    scanf_s("%lf", &b);
    a=pow(a,b);
    printf("Результат: a=%lf", a);
    _getch();
}

Теперь те что не решил: первая, мы как бы такого ен проходили, но думаю с ней проблем не будет, 9-ю почти решил, только ошибки поисправлять, чучуть не хватило времени, 10 не совсем понял, да и не понял как подсчитать дни. если например год высокостный, и как задать такой алгоритм?

Вот №12 интерестная, а если брать длину конверта и открытки в числах, и их ввести с клавиатуры и задать такое что если (припустим длина конверта а а длина открпытки б), а>b вывсти на экран ответ, открытку можно вложить не згиная, но если a<b то вывести что нужно згинать, а еще было бы интереснее если нужно было учитывать и высоту конверта с открыткой - дополнительный цыкл...

Над 13 и 14 нужно подумать, не хотелось, думаю завтра буду решать, а 16-я бомба, нас не учили подключать графику, мы пишем только примитивные калькуляторы!)

Добавлено через 4 минуты и 32 секунды
Прокоментируйте пожалуйста мои решения и еще назрел такой вопрос: как правильно выводить отображения целого числа? Потмоу что я использую значение %lf, другие, компилятор не хочет принимать (например %i или %d, может их нужно подключить, тогда как?) и выводи на монитор ответ целого числа в виде x=19.00000 b=271.00000 Как сделать что бы целые числа были без точки в виде: x=19 b=271

Спасибо!)

Crafty

Дата 14.11.2010, 02:58 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Jmylia @ 14.11.2010, 02:42

)

учим С++

А где здесь С++? У вас тут сплошной С.

Jmylia

Дата 14.11.2010, 12:16 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 17
Регистрация: 12.10.2009
Где: Кривой Рог

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

Цитата(Crafty @ 14.11.2010, 02:58)

Цитата(Jmylia @ 14.11.2010, 02:42

)

учим С++

А где здесь С++? У вас тут сплошной С.

Упс, это я перепутал, первый семестр, учим С, это второй семестр С++

Говорите полностью на С ... А ошибки какие-то есть? Правильность и логичность написания программы присутствуют?

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

Дата 14.11.2010, 15:05 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

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

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

Jmylia, ты халтурщик и сачок! Я конечно рад, что ты знаешь стандартную библиотеку, но тут задания не на эти знания, а на знание математики и основ программирования.

Цитата(Jmylia @ 14.11.2010, 03:42

)

2. Даны переменные a и b. Напишите программу, которая будет менять значения этих переменных местами.

В задании было указано не вывести, а обменять значения. Т.е. чтобы в конце программы значения a и b были обменены (проверять отладчиком).

Цитата(Jmylia @ 14.11.2010, 03:42

)

...используя только умножение.

Цитата(Jmylia @ 14.11.2010, 03:42

)

7. Даны 2 числа. Вывести наибольшее из них.

решение в одну строчку.

Цитата(Jmylia @ 14.11.2010, 03:42

)

11. Выведите на правильном русском языке, сколько прошло лет с указанного года (между 1 и 2006 годом н.э.) до 2007г. Например, если введено 1986, то надо вывести "21 год", а если 2002, то "5 лет".

Должно быть так: 5 лет, 2 года, или 1 год.

Цитата(Jmylia @ 14.11.2010, 03:42

)

15. Вычислите: a в степени b, b >= 0.

... используя только умножение.

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

Дата 14.11.2010, 21:26 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(bsa @ 14.11.2010, 02:36

)

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

просто не знал про эту функцию. В учебнике до постановки задачи эта функция не рассматривалась. Стараюсь метериал усваивать последовательно. Хотя, уже начинаю чувствовать, что надо искать справочники. Без них ни как...

Цитата(bsa @ 14.11.2010, 02:36

)

да, задумался вчера со списками. Поэтому приостановил вчера решение задачи. В данном случае, проблема списка будет заключаться в том, что что-бы перейти скажем к среднему элементу, надо будет последовательно перебрать все другие элементы (в любом направлении, если список двусвязный). Вычислить адрес памяти нужного элемента - не возможно. Другое дело массив. Нужен 10й элемент массива, хранящий элементы типа long, очевидно, что адрес этого элемента будет: адрес нулевого + 10 * 4. Хотя и адрес высчитывать не понадобится, все за нас сделает компилятор. правильно понял, на счет скорости? smile

Цитата(bsa @ 14.11.2010, 02:36

)

Количество строк равно количеству записей в индексном файле.

да.. не подумал просто..

Цитата(bsa @ 14.11.2010, 02:36

)

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

**
кстати, как вам решение задачи http://forum.vingrad.ru/index.php?showtopi...t&p=2246278 ?

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

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

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

Дата 14.11.2010, 23:51 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 14.11.2010, 22:26

)

Хотя, уже начинаю чувствовать, что надо искать справочники. Без них ни как...

Тема с часто задаваемыми вопросами прикреплена в разделе.

Цитата(Чoо @ 14.11.2010, 22:26

)

правильно понял, на счет скорости?

да

Цитата(Чoо @ 12.11.2010, 15:28

)

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

Конечно через буфер. Если бы буферов не было, то скорость работы программ была бы просто катастрофической. Можно работать без буфера, но для этого нужно использовать более низкоуровневое API.

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

Дата 15.11.2010, 02:32 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(Чoо @ 13.11.2010, 12:15

)

Дан большой текстовый файл с длиной строк не более 100 символов. Распечатайте 15 последних строк файла

Ещё вариант:

Код

#define N 100

void sCount(FILE * file, int & cnt)
{
    char buf[N];

    while(fgets(buf, N, file))
        cnt++;

    rewind(file);
}

void sPrint(FILE * file, char * str, int cnt)
{
    fgets(str, N, file);
    if(cnt <= 0)
        cout << str;

    if(!feof(file))
        sPrint(file, str, cnt - 1);
}

int main()
{
    int         s_count = 0;          
    int         s_print = 15;
    char        buf[N];
    FILE       *in      = fopen("file_name.txt","rt");

    if(!in) return 0; 

    sCount(in, s_count);
    sPrint(in, buf, s_count - s_print);

    cout << endl;    
    fclose(in);
    return 0;
}

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

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Дата 15.11.2010, 02:49 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(bsa @ 14.11.2010, 14:05

)

Jmylia, ты халтурщик и сачок!

bsa, по-моему, он просто прикалывается... smile

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

Дата 15.11.2010, 03:18 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(Чoо @ 13.11.2010, 16:21

)

еще задача.. Нужна помощь..

попробуем...

Цитата(Чoо @ 13.11.2010, 16:21

)

Для того, что бы воспользоваться алгоритмом бинарного поискА, мне нужно знать количество строк в файле

возможно и так, но не обязательно, достаточно знать размер файла.

Цитата(Чoо @ 13.11.2010, 16:21

)

а так же уметь позиционироваться на нужную строку в файле.

Цитата(Чoо @ 13.11.2010, 16:21

)

Если я, что бы получить количество строк в файле, буду все их считывать, начиная от первой, возникает вопрос: смысл бинарного поискА, если я и так уже перебрал все строки.

Цитата(Чoо @ 13.11.2010, 16:21

)

Так же, что бы установить указатель на нужную строку, мне нужны индексы (смещения) строк.

тут думать надо... smile

Цитата(Чoо @ 13.11.2010, 16:21

)

Намекните, куда копать, если не трудно..

думаю, можно так попробовать:

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

Вроде всё...   smile

Добавлено через 2 минуты и 9 секунд
У меня есть одна мысля. Если что, завтра (уже сегодня, но к вечеру) покумекаю...

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

Дата 15.11.2010, 09:52 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Dov @ 15.11.2010, 02:32

)

Ещё вариант:

мм.. вижу реккурсию smile

.
пока что данный вариант что-то не заработал, еще подумаю над этим. на терминал выводит такую непонятную вещь и очень много:

Код


X'^H,X'^H,X'^H,X'^H,X'^H,X'^

хотя вот получение количества строк мне тут не нравится: sCount(in, s_count); (перебор каждой строки). Хотел время вывода строк из текстового файла размером в 25 мб замерить по-быстрому, сравнить, но пока не получилось smile

Цитата(Dov @ 15.11.2010, 03:18

)

возможно и так, но не обязательно, достаточно знать размер файла.

поспорю

. Длина каждой строки ограничена в 100 символов. т.е. она может быть и 1 символ и 10 итд. следовательно середина файла - не есть гарантия того, что это середина количества строк.

Цитата(Dov @ 15.11.2010, 03:18

)

Цитата(Чoо @ 13.11.2010, 16:21 Найти цитируемый пост)
а так же уметь позиционироваться на нужную строку в файле.
smile

ну зная индекс строки - установить указатель на нее не вопрос конечно smile

.

Над приведенным ниже алгоритмом подумаю чуть позже, уже в универ сильно опаздываю smile

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

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

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

Дата 15.11.2010, 15:04 (ссылка)

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

Загрузка ...

Опытный

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

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

а.. ну не работало, потому что я по-невнимательности указал не файл, а директорию, в которой он находится. Однако из рекурсии программа не выходит почему-то. Пишет Segmentation fault. что-то в рекурсии не то. Заменил ее на цикл while с предусловием - всё ок. примерно 0,7 секунд тратится на поиск и вывод последних 15 строк (всего строк 3 163 420
В моем решении 0,125. ну это естественно, так как я не перебираю все строки.
Осталось разобраться почему рекурсия не пошла.

Цитата(Чoо @ 15.11.2010, 09:52

)

поспорю smile.

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

Это сообщение отредактировал(а) Чoо - 15.11.2010, 15:20

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

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

Дата 15.11.2010, 21:32 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(Чoо @ 15.11.2010, 14:04

)

Осталось разобраться почему рекурсия не пошла.

Может ты чего-то в функциях изменил?

Попробуй такой вариант, без рекурсии:

Код

#define N 100
int main()
{
    char  buf[N];
    int   s_print = 15;
    FILE *in      = fopen("file_name.txt", "rt");

    if(!in) return 0;
    
    if(s_print)
    {
        fseek(in, 0, SEEK_END);
        for(int k = ftell(in); s_print; k -= 2)
        {
            if(fseek(in, k, SEEK_SET) != 0)
            {
                fseek(in, 0, SEEK_SET);
                break;
            }            
            if(fgetc(in) == '\n')
                s_print--;
        }
    }
    else
    {
        puts("...");
        fclose(in);
        return 0;
    }

    while(!feof(in))
    {
        fgets(buf, N, in);
        if(buf[strlen(buf) - 1] == '\n')
            buf[strlen(buf) - 1] = '\0';
        puts(buf);
    }

    fclose(in);
    return 0;
}

Я, правда, особо не тестил, но если что, можно подправить.

Это сообщение отредактировал(а) Dov - 15.11.2010, 21:36

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

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

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

По поводу бинарного поиска в файле. Вот примерчик, нужно потестировать, ибо руки не дошли. Немного коряво написал, наверняка там что-то нужно доделать, но думаю, что направление ты поймёшь. Что-то бестолковка сегодня совсем не варит... из-за жары, наверно.

Код

#define N 20
int main()
{
    char     buf[N];
    char  *  key  = "qwerty";
    FILE  *  file = fopen("file_name.txt", "rt");
    int      left, mid, right, cmp;

    fseek(file, 0, SEEK_END);
    left  = 0;
    right = ftell(file);
 
    while(left < (right - 1))
    {
        mid = (left + right) / 2;
        fseek(file, mid, SEEK_SET);

        while(!fseek(file, -2, SEEK_CUR) && ftell(file) > 0 && fgetc(file) != '\n')
            ;

        mid = ftell(file);

        fgets(buf, N, file);
        if(buf[strlen(buf) - 1] == '\n')
            buf[strlen(buf) - 1] = '\0';

        if((cmp = strcmp(key, buf)) == 0)
            break;

        cmp < 0 ? right = mid : left = mid + strlen(buf) + 1;
    }
    printf("%s%sfound!\n", key, cmp ? " not " : " ");
    fclose(file);
    return 0;
}

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

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

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

Загрузка ...

Опытный

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

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

Цитата(Dov @ 15.11.2010, 21:32

)

Может ты чего-то в функциях изменил?

да не, ни чего не менял, кроме пути к файлу. Может какое-то ограничение на количество точек входа? (я такое вообще не встречал). Вобщем суть в чем: маленький файл если взять, то в рекурсию входит и так же норм выходит smile

. А если взять файл из 3 с лишним млн. строк, то он на каком-то этапе вылетает (не могу в отладчике узнать где конкретно).
Второй вариант чуть позже потестю.
По поводу бинарного поиска. Так же гляну позже - в принципе по словесному описанию понял куда копать. Спасибо. Задачу хочу решить сперва сам, пусть хоть и будет криво.. Но пока решать даже и не начал. Что-то с индексами напутал в задаче с сортировкой большого файла. Точнее даже не с индексами..
вот функция открытия файла:

Код


/* функция получает путь и имя файла, возвращает указатель на полный путь */
char *get_full_patch(const char *patch, const char *fname)
{
    char *dest;
    int l;
    l=strlen(patch)+strlen(fname);
    dest = new char[l];
    dest = strcpy(dest,patch);
    dest = strcat(dest,fname);
    return dest;
}

/* функция составляет полный путь к файлу и открывает его.
*/
FILE *OpenFile(const char *patch, const char *fname, const char *mode)
{
    char *fullpatch;
    fullpatch = get_full_patch(patch,fname);
    FILE *f = fopen(fullpatch,mode);
    delete []fullpatch;

    return f;
}
void CpyRecordsToFiles(const char *patch, const char *f_ix_nm, int divider)
{
    long *buf; //буфер для индекса
    FILE *f = OpenFile(patch,f_ix_nm,"r");
    FILE *ftemp_a = OpenFile(patch,"temp_a","w"); // <<<<-вот тут ошибка при освобождении строки fullpatch
    FILE *ftemp_b = OpenFile(patch,"temp_b","w");

    //тут в принципе не важно, что - ошибка возникает раньше
    /* записи скопировали. теперь можно закрыть файлы */
}

ну и собственно вызов, при котором возникает ошибка:

Код


CpyRecordsToFiles(patch,"index",divider);
//или так:
const char *f_ix_nm = "index";
CpyRecordsToFiles(patch,f_ix_nm,divider);

а если в вызывающей функции сделать так:

Код


int SortMerge(const char *patch, const char *fname) 
{
...
}
//передача в эту функцию параметров происходит следующим образом:
SortMerge("/home/oem/Developed/Cpp/study/exercise/8.13.2 with indexing/untitled2/","index")

то ни какой ошибки не возникает. Я уже час пытаюсь понять в чем прикол..
Может нельзя выделять память в одной функции, а освобождать в другой (get_full_patch и OpenFile)? (про это еще не читал).

Это сообщение отредактировал(а) Чoо - 15.11.2010, 22:38

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

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

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

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(Чoо @ 15.11.2010, 21:25

)

Задачу хочу решить сперва сам, пусть хоть и будет криво..

Вот это правильно, давай работай. Потом расскажешь. Удачи!!!

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

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

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

Загрузка ...

Опытный

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

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

вообще суть существования последних двух функций в том, что нельзя сформировать полный путь к файлу из составных частей при вызове функции fopen. Может есть, да я не знаю и изобрел вот эти вот костыли...

Добавлено через 41 секунду

Цитата(Dov @ 15.11.2010, 22:40

)

Вот это правильно, давай работай. Потом расскажешь. Удачи!!!

спасибо

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

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

Дата 16.11.2010, 11:11 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Код


char *get_full_patch(const char *patch, const char *fname)
{
    char *dest;
    int l;
    l=strlen(patch)+strlen(fname);
    dest = new char[l];
    dest = strcpy(dest,patch);
    dest = strcat(dest,fname);
    return dest;
}

А атк причина ошибки в том, что память выделялась по одному адресу, а освободить я пытался по другому. я думал, что после return dest fullpatch будет указывать на тот же участок памяти, что и dest.

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

Код


FILE *OpenFile(const char *patch, const char *fname, const char *mode)
{
    char *fullpatch = 0;
    int l=strlen(patch)+strlen(fname);
    fullpatch = new char[l];
    strcpy(fullpatch,patch);
    fullpatch = strcat(fullpatch,fname);
    FILE *f = fopen(fullpatch,mode);
    delete []fullpatch;
    return f;
}

подскажите плз, как можно передать в функцию fopen составной путь (состоящий из пути к файлу и его имени)?

***
о.. пошло.. как раз тогда когда собрался сдаться... ошибка в строке

Код


int l=strlen(patch)+strlen(fname);

в итоге переполнение массива, та как я не выделил память под нулевой символ. => кривое освобождение памяти

Это сообщение отредактировал(а) Чoо - 16.11.2010, 13:07

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

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

Дата 16.11.2010, 18:09 (ссылка)

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

Загрузка ...

Опытный

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

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

сделал я задачу сортировки большого файла с использованием индексов. Честно говоря расстроен, так как на сортировку затрачено времени примерно раз в 5 больше (153,755 сек против 28-29 сек без индексов). Отметки времени еще не расставлял, что бы узнать на каком этапе требуется много времени.
вот решение с индексированием:

Код


/*
 имеется текстовый файл, строки которого не упорядочены. Упорядочите их
 при помощи сортировки слиянием
 */
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
using namespace std;

#define n 100

/* функция составляет полный путь к файлу и открывает его*/
FILE *OpenFile(const char *patch, const char *fname, const char *mode)
{
    char *fullpatch = 0;
    int l=strlen(patch)+strlen(fname)+1;
    fullpatch = new char[l];
    strcpy(fullpatch,patch);
    fullpatch = strcat(fullpatch,fname);
    FILE *f = fopen(fullpatch,mode);
    delete []fullpatch;

    return f;
}

long GetFileSize(const char *patch, const char *fname)
{
    long f_size;
    FILE *f = OpenFile(patch,fname,"r");
    if(!f)
        return 0;
    fseek(f,0,SEEK_END);
    f_size = ftell(f);
    fclose(f);
    return f_size;
}

/* функция сливает файлы c индексами в один*/
void merge(const char *patch, const char *f_ix_nm, const char *fname, int D)
{
    int f_size = GetFileSize(patch,f_ix_nm);
    char sbuf_a[n]; //буфер для чтения и сравнения строк
    char sbuf_b[n]; //буфер для чтения и сравнения строк
    long pos_a,pos_b; //буферы для помещения индекса

    /* откроем файл индексов для записи */
    FILE *f_ix = OpenFile(patch,f_ix_nm,"w");
    /*файлы индексов и сортируемый файл - для чтения*/
    FILE *ftemp_a = OpenFile(patch,"temp_a","r");
    FILE *ftemp_b = OpenFile(patch,"temp_b","r");
    FILE *f = OpenFile(patch,fname,"rt");

    /* получим индексы строк */
    fread(&pos_a,4,1,ftemp_a);
    fread(&pos_b,4,1,ftemp_b);
    while(!feof(ftemp_a) && !feof(ftemp_b))
    {
        int i = 0;
        int j = 0;
        while(i < D && j < D && !feof(ftemp_a) && !feof(ftemp_b))
        {
            /*получаем строки по смещению в pos_a и pos_b */
            fseek(f,pos_a,SEEK_SET);
            fgets(sbuf_a,n,f);
            fseek(f,pos_b,SEEK_SET);
            fgets(sbuf_b,n,f);

            /*сравниваем полученные строки и в соответствии с результатом сравнения
              записываем индексы в индексный файл
            */
            if(strcmp(sbuf_a,sbuf_b) < 0)
            {
                fwrite(&pos_a,4,1,f_ix);
                fread(&pos_a,4,1,ftemp_a);
                i++;
            }
            else
            {
                fwrite(&pos_b,4,1,f_ix);
                fread(&pos_b,4,1,ftemp_b);
                j++;
            }
        }
        if(i==D) //копируем остаток группы из файла Б
            while(j<D && !feof(ftemp_b))
            {
                fwrite(&pos_b,4,1,f_ix);
                fread(&pos_b,4,1,ftemp_b);
                j++;
            }
        else
            if(j==D) //копируем остаток группы из файла А
                while(i<D && !feof(ftemp_a))
                {
                    fwrite(&pos_a,4,1,f_ix);
                    fread(&pos_a,4,1,ftemp_a);
                    i++;
                }
    }
    /* вышли из цикла. Если в каком-либо файле что-то осталось
       копируем это в файл f
     */
    if(feof(ftemp_a))
        while(!feof(ftemp_b))
        {
            fwrite(&pos_b,4,1,f_ix);
            fread(&pos_b,4,1,ftemp_b);
        }
    else
        if(feof(ftemp_b))
            while(!feof(ftemp_a))
            {
                fwrite(&pos_a,4,1,f_ix);
                fread(&pos_a,4,1,ftemp_a);
            }

    /*закрываем открытые файлы */
    fclose(f_ix);
    fclose(ftemp_a);
    fclose(ftemp_b);
    fclose(f);
}

/* делит индексный файл пополам
   Шаг D для того, ято бы случайно не разорвать группу индексов.
*/
void CpyRecordsToFiles(const char *patch, const char *f_ix_nm, int D)
{
    long buf; //буфер для индекса
    FILE *f = OpenFile(patch,f_ix_nm,"r");
    FILE *ftemp_a = OpenFile(patch,"temp_a","w");
    FILE *ftemp_b = OpenFile(patch,"temp_b","w");

    /*приступаем к распределению индексов по половинкам */
    while(!feof(f))
    {
        for(int i = 0; i<D && !feof(f);++i)
        {
            if(fread(&buf,4,1,f))
                fwrite(&buf,4,1,ftemp_a);
        }
        for(int i =0;i < D && !feof(f);++i)
        {
            if(fread(&buf,4,1,f))
                fwrite(&buf,4,1,ftemp_b);
        }
    }
    /* записи скопировали. теперь можно закрыть файлы */
    fclose(f);
    fclose(ftemp_a);
    fclose(ftemp_b);
}



/* функция индексирует строки в файле
   возвращает единицу, если файл проиндексирован.
*/
int indexing(const char *patch, const char *fname)
{
    char buf[n];
    long pos = 0; //указатель на начало строки в файле
    long f_size; //размер сортируемого файла

    /* открываем сортируемый файл */
    FILE *f = OpenFile(patch,fname,"rt");
    if(!f)
        return 0;

    /*создаем индексный файл */
    FILE *findex = OpenFile(patch,"index","w");
    if(!f)
        return 0;

    /*получаем размер сортируемого файла */
    f_size = GetFileSize(patch,fname);
    while(!feof(f) && pos != f_size)    //если текущая позиция равна размеру файла, то по ней строки не будет
    {
        fwrite(&pos,4,1,findex);
        fgets(buf,n,f);
        pos = ftell(f);
    }
    /* закрываем сортируемый и индексный файлы */
    fclose(f);
    fclose(findex);
    return 1;
}

int GetRecordsCount(const char *patch)
{
    int f_size = GetFileSize(patch,"index");
    return f_size/4;
}

/* функция принимает путь к файлу, строки которого надо упорядочить по-возрастанию
 и сортирует файл */
int SortMerge(const char *patch, const char *fname)
{
    /* в начале длина упорядоченного участка = 1 */
    int D = 1;
    int strings_count;

    /*создаем индексный файл*/
    if(!indexing(patch,fname))
        return 0;

    /*определяем количество строк в исходном файле */
    strings_count = GetRecordsCount(patch);

    while(D<strings_count)
    {
        CpyRecordsToFiles(patch,"index",D);
        merge(patch,"index",fname,D);
        D *=2;
    }
    /* отсортировали файл с индексами. Теперь создадим отсортированный файл
       в порядке следования индексов*/
    FILE *f_ix = OpenFile(patch,"index","r");
    FILE *f = OpenFile(patch,fname,"rt");
    FILE *f_sorted = OpenFile(patch,"sorted.txt","wt");
    cout << "sorted.txt be created...\n";
    long pos;
    char buf[n];
    while(!feof(f_ix) && fread(&pos,4,1,f_ix))
    {
        fseek(f,pos,SEEK_SET);
        fgets(buf,n,f);
        fputs(buf,f_sorted);
    }
    fclose(f_ix);
    fclose(f);
    fclose(f_sorted);
    return 1;
}

int main()
{
    timeval tp = {0,0}, tp2={0,0};
    gettimeofday(&tp,0);
    if(SortMerge("/home/oem/Developed/Cpp/study/exercise/8.13.2 with indexing/untitled2/","xxx.txt"))
    {
        gettimeofday(&tp2,0);
        cout << "file is sorted (" << tp2.tv_sec - tp.tv_sec << "," <<  tp2.tv_usec - tp.tv_usec << "s)"  << "\n";
    }
    else
        cout << "FAILED to sort file\n";
    return 0;
}

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

Это сообщение отредактировал(а) Чoо - 16.11.2010, 18:16

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

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

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

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

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 16.11.2010, 19:09

)

Не поможет. Так как из файла читается минимум 1 кластер (2-4 КБ).

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

Дата 16.11.2010, 18:41 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(bsa @ 16.11.2010, 18:22

)

Не поможет. Так как из файла читается минимум 1 кластер (2-4 КБ).

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

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

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

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

Дата 17.11.2010, 00:40 (ссылка)

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

Загрузка ...

Эксперт

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

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

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

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

Дата 17.11.2010, 00:47 (ссылка)

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

Загрузка ...

Опытный

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

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

bsa, я сравнивал с вариантом, когда делил исходный файл пополам (точнее на две половины), а потом эти половины сливал снова в один файл.

Добавлено через 56 секунд
вот с этим: http://forum.vingrad.ru/index.php?showtopi...t&p=2246278 smile

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

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

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

Дата 17.11.2010, 00:56 (ссылка)

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

Загрузка ...

Эксперт

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

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

вот только как при этом ты уложился в 3 файла?

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

Дата 17.11.2010, 01:07 (ссылка)

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

Загрузка ...

Опытный

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

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

bsa, в смысле как? в один момент времени существовало не более 3х файлов: file_a, file_b и f. после распределения f по первым двум f можно было затирать...
Я сейчас подумал над временной сложностью для последнего решения (первое сейчас еще пересмотрю). Если все учел правильно, то за одну фазу происходит N считываний при делении индексного файла на две части, N считываний из индексного файла (уже половинок, а не целого файла) при слиянии и еще N считываний из сортируемого файла, опять же во время слияния. В итоге имеем утроеное N. И так, полное рассчетное время будет выглядеть как: T = const * 3N * log2n
Там где log2 - 2 нижним индексом. Время на получения индексного файла я не учитывал - разовая операция. Занимает примерно секунду при 3х миллионах строк.

Добавлено @ 01:11
в первом решении T = const * 2N * log2n.
Значит можно быстрее сделать, так как достаточно одного просмотра строк на каждом этапе.

странно... может я неправильно считаю временную сложность, так как в этом случае скорость сортировки должна бы была упасть только в 1,5 раза, но не в 5

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

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

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

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

Дата 17.11.2010, 11:09 (ссылка)

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

Загрузка ...

Эксперт

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

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

Чoо, в первом случае у тебя была последовательная работа с файлами. А во втором - случайный доступ. Он хуже ускоряется буферами, чем первый.

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

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

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

Загрузка ...

Опытный

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

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

bsa, ааа... теперь понятно, спсибо за помощь.
**
ну раз с данной задачей справились, перехожу к следующей, а именно: к бинарному поиску. Если успею, сегодня напишу решение smile

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

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

Дата 17.11.2010, 20:40 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

Код


/*
    В текстовом файле находится словарь, по одному слову в строке.
    Запрограммируйте поиск заданного слова, приспособив для этой
    цели алгоритм двоичного поиска
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define N 100

/* функция составляет полный путь к файлу и открывает его*/
FILE *OpenFile(const char *patch, const char *fname, const char *mode)
{
    char *fullpatch = 0;
    int l=strlen(patch)+strlen(fname)+1;
    fullpatch = new char[l];
    strcpy(fullpatch,patch);
    fullpatch = strcat(fullpatch,fname);
    FILE *f = fopen(fullpatch,mode);
    delete []fullpatch;

    return f;
}

/*функция определяет размер файла*/
long GetFileSize(const char *patch, const char *fname)
{
    long f_size;
    FILE *f = OpenFile(patch,fname,"r");
    if(!f)
        return 0;
    fseek(f,0,SEEK_END);
    f_size = ftell(f);
    fclose(f);
    return f_size;
}


/*функция индексирует заданный файл.
  Возвращает двойку, если файл проиндексирован.
             единицу, если не проиндексирован,
             0 - при ошибке
*/
int indexing(const char *patch, const char *fname)
{
    char buf[N];
    long pos = 0; //указатель на начало строки в файле
    long f_size; //размер сортируемого файла

    /* открываем сортируемый файл */
    FILE *f = OpenFile(patch,fname,"rt");
    if(!f)
        return 0;

    /*пробуем открыть индексный файл. Если он отсутствует
      то создаем, если он существует, то спрашиваем пользователя
      о необходимости создать его
    */
    FILE *findex = OpenFile(patch,"index","r");
    if(!findex)
    {
        /*создаем индексный файл */
        findex = OpenFile(patch,"index","w");
        if(!findex)
        {
            fclose(f);
            return 0;
        }
    }
    else
    {
        /*индексный файл существует, спрашиваем пользователя
          необходимо ли его переписать*/
        cout << "Index file exists. Overwrite it? (y/n)\n";
        char c[1];
        cin >> c;

        if((strcmp(c,"y")==0) || (strcmp(c,"Y"))==0)
        {
            /*создаем индексный файл */
            fclose(findex);
            findex = OpenFile(patch,"index","w");
            if(!findex)
            {
                fclose(f);
                return 0;
            }
        }
        else
        {
            fclose(findex);
            fclose(f);
            return 1;
        }
    }


    /*получаем размер индексируемогофайла */
    f_size = GetFileSize(patch,fname);
    while(!feof(f) && pos != f_size)    //если текущая позиция равна размеру файла, то по ней строки не будет
    {
        fwrite(&pos,4,1,findex);
        fgets(buf,N,f);
        pos = ftell(f);
    }
    /* закрываем индексируемый и индексный файлы */
    fclose(f);
    fclose(findex);
    return 2;
}

/*функция осуществляет бинарный поиск в заданном файле. При успехе возвращает
  единицу, иначе - 0*/
int BinarySearch(const char *patch, const char *fname, const char *word)
{
    int result;
    /*сначала пробуем проиндексировать файл*/
    cout << "Indexation file, please wait...\n";
    result = indexing(patch,fname);
    if(result == 2)
        cout << "File is indexed. Continue search...\n";
    else
    if(result == 1)
        cout << "Indexation aborted. Continue search...\n";
    else
    {
        cout << "Indexation failed, search impossible, sorry...\n";
        return 0;
    }

    /* количество строк в индексируемом файле */
    long s_count = GetFileSize(patch,"index")/4; //4  -  размер типа long

    /*приступаем к поиску*/
    int left = 0;
    int right = s_count-1;
    long ix; //индекс строки
    char buf[N]; //буфер для приема строк
    FILE *f = OpenFile(patch,fname,"rt");
    if(!f)
        return 0;
    FILE *f_ix = OpenFile (patch,"index","r");
    if(!f_ix)
        return 0;
    while(left <= right)
    {
        /*середина участка поиска */
        int middle = (left + right)/2;
        fseek(f_ix,middle*4,SEEK_SET);
        fread(&ix,4,1,f_ix);
        fseek(f,ix,SEEK_SET);
        fscanf(f,"%s",buf);
        result = strcmp(buf,word);
        if(result>0)
            right = middle-1;
        else
            if(result<0)
                left = middle+1;
            else
                return 1;
    }
    return 0;
}

int main()
{
    char buf[N];
    for(;;)
    {
        cout << "Enter a search word: ";
        cin >> buf;
        if(BinarySearch("/home/oem/Developed/Cpp/study/exercise/8.13.4/untitled1/","xxx.txt",buf))
            cout << "Word found\n";
        else
            cout << "Word not found\n";
        cout << "Find another word? (y/n)";
        cin >> buf;
        if(strcmp(buf,"y")!=0)
            if(strcmp(buf,"Y")!=0)
                break;
    }
    return 0;
}

поиск производится шустро smile

. Решил сначала индексировать файл, а потом осуществлять поиск.
Сейчас рассмотрю вариант, что предлагали выше smile

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

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

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

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

Загрузка ...

Опытный

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

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

Dov, ваш вариант интересней будет. разобрал его. У меня слишком много кода и всё усложнено как-то.

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

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

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

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(Чoо @ 17.11.2010, 21:15

)

У меня слишком много кода и всё усложнено как-то.

Эт точно. Такое количество кода трудно переваривать, а то, что комментируешь это хорошо.
Вот интересный момент:

Код

        cout << "Index file exists. Overwrite it? (y/n)\n";
        char c[1];
        cin >> c;

        if((strcmp(c,"y")==0) || (strcmp(c,"Y"))==0)

Зачем так сложно? smile

Вот немного переделал, вроде так попроще:

Код

#define N 20
int main()
{
    char     buf[N];
    char  *  key  = "qwerty";
    FILE  *  file = fopen("file_name.txt", "rt");
    int      left, mid, right, cmp = 0;

    fseek(file, 0, SEEK_END);
    left  = 0;
    right = ftell(file);
 
    while(left < right)
    {
        mid = (left + right) / 2;
        fseek(file, mid, SEEK_SET);

        while(mid > 0 && fgetc(file) != '\n')
        {
            mid -= 2;
            fseek(file, mid < 2 ? 0 : mid, SEEK_SET);
        }

        fgets(buf, N, file);
        if(buf[strlen(buf) - 1] == '\n')
            buf[strlen(buf) - 1] = '\0';

        if((cmp = strcmp(key, buf)) == 0)
            break;

        cmp < 0 ? right = mid : left = mid + strlen(buf) + 1;
    }
    printf("%s%sfound!\n", key, cmp ? " not " : " ");
    fclose(file);
    return 0;
}

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

Дата 18.11.2010, 01:11 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Dov @ 18.11.2010, 00:22

)

Зачем так сложно? smile

можно было еще сделать как в главной функции Main smile

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

Цитата(Dov @ 18.11.2010, 00:22

)

Вот немного переделал

обязательно разберу чуть по-позже, неясности кое-какие есть (в принципе пошагово проверить не проблема, потому не спрашиваю smile

.

комментарии... ну с ними проще как-то.. Когда-то пренебрегал подробными комментами, пока не понадобилось "ковырять" старые проекты

Добавлено @ 01:12
кстати вот не знал, что так можно:

Код


cmp < 0 ? right = mid : left = mid + strlen(buf) + 1;

конечно разобрал что к чему, но такую запись не видел еще smile

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

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

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

Дата 18.11.2010, 10:04 (ссылка)

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

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

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

Цитата(Чoо @ 18.11.2010, 00:11

)

можно было еще сделать как в главной функции Main . Ну вообще задумка там была производить индексирование только в том случае, если проиндексированный файл поменялся.

Чoо, я не про это говорю. Зачем сравнивать строки(), если можно сравнить символы?

Код

if((strcmp(c,"y")==0) || (strcmp(c,"Y"))==0)

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

Дата 18.11.2010, 16:01 (ссылка)

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

Загрузка ...

Опытный

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

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

Dov,

Код


        char r;
        cin >> r;
        if(r != 'y' && r != 'Y')
                break;

так надо?

**добавил**
Dov, разобрался с исходником. Меня смущало, что в цикле:

Код


        while(mid > 0 && fgetc(file) != '\n')
        {
            mid -= 2;
            fseek(file, mid < 2 ? 0 : mid, SEEK_SET);
        }

вы отнимали 2, а не единицу. Возникли вопросы почему так. В отладчике посмотрел: у меня русские буквы кодируются двумя байтами (вопрос - почему? В принципе догадываюсь: поскольку работаю в юникоде, русские буквы кодируются двумя байтамИ, а английские одним. Верно?),и, в принципе, программа не выходила за пределы строки. Если же англоязычный словарь, то получалось, что mid мог перейти и на предыдущую строку и продолжить перемещаться назад. и программа просто висла.
пример словаря:

Код


aedi
citcat
clatter
dettimd
dlim
dniksne
ebel
ecneita

ищем слово ebel.

Если декрементировать mid, то всё ищет и не виснет.
и еще сократил:

Код


        fgets(buf, N, file);
        if(buf[strlen(buf) - 1] == '\n')
            buf[strlen(buf) - 1] = '\0';

до

Код


fscanf(file,"%s",buf);

**добавил**

Цитата(Чoо @ 18.11.2010, 16:01

)

В отладчике посмотрел: у меня русские буквы кодируются двумя байтами (вопрос - почему?

сообразил... это потому что у меня словарь в юникоде smile

.

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

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

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

Дата 22.11.2010, 18:21 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

Класс "комплексное число".
    Объявите класс "Комплексное число", полями которого являются
    действительная и мнимая части числа, а методами - сложение и умножение
    на другое комплексное число, определение модуля и вывод на экран.

мое решение:

Код


/*
    Класс "комплексное число".
    Объявите класс "Комплексное число", полями которого являются
    действительная и мнимая части числа, а методами - сложение и умножение
    на другое комплексное число, определение модуля и вывод на экран.
 */
#include <iostream>
#include <math.h>
using namespace std;

class clx {
    int realpart, imaginarypart; //действительная и мнимая части соотв.
public:
    /*методы */
    void clx_sum(clx); //прибавляет к комплексному числу другое комплексное число
    void clx_mul(clx); //умножает КЧ на другое КЧ
    float clx_mod(); // находит модуль КЧ
    int get_realpart(); //получает действительную часть
    int get_imaginarypart(); //получает мнимую часть
    void clx_print(char*) const; //выводит КЧ на экран
    //конструкторы
    clx(int,int);
    clx() {realpart = 0; imaginarypart = 0;}
    //деструктор необязателен
};
void clx::clx_sum(clx x)
{
    /* z = (x1 + x2; y1 + y2 */
    realpart += x.get_realpart();
    imaginarypart += x.get_imaginarypart();
}
void clx::clx_mul(clx x)
{
    /* z = (x1*x2 - y1*y2; x1*y2 + x2*y1) */
    int r = realpart; //времянка, что бы не потерять первоначальное значение действительной части
    realpart = r * x.get_realpart() - imaginarypart * x.get_imaginarypart();
    imaginarypart = r * x.get_imaginarypart() + x.get_realpart() * imaginarypart;
}
float clx::clx_mod()
{
    /* МОДУЛЬ = КОРЕНЬ(x^2 + y^2) */
    return sqrt(pow(realpart,2) + pow(imaginarypart,2));
}
int clx::get_realpart()
{
    return realpart;
}
int clx::get_imaginarypart()
{
    return imaginarypart;
}

void clx::clx_print(char *name) const
{
  cout << name <<"(" <<realpart << ";" << imaginarypart << ")";
}

clx::clx(int real, int imaginary)
{
    realpart = real;
    imaginarypart = imaginary;
}

int main()
{
    clx a(3,4), b(2,3);
    cout << "a = ";
    a.clx_print("a"); cout << " + "; b.clx_print("b"); cout << endl;
    a.clx_sum(b);
    a.clx_print("a"); cout << endl;

    cout << "a = ";
    a.clx_print("a"); cout << " * "; b.clx_print("b"); cout << endl;
    a.clx_mul(b);
    a.clx_print("a"); cout <<endl;

    cout << "mod(a) = " << a.clx_mod() << endl;

    return 0;
}

правда я не понимаю предупреждение:

Цитата

warning: deprecated conversion from string constant to ‘char*’

почему преобразование устаревшее, и как сделать неустаревшим smile

.

Добавлено через 56 секунд
это ругается на

Код


a.clx_print("a"); cout << endl;

и все вызовы метода print

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

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

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

Дата 22.11.2010, 18:24 (ссылка)

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

Загрузка ...

Эксперт

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

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

Должно быть:

Код

void clx_print(const char*)

Это сообщение отредактировал(а) bsa - 22.11.2010, 18:24

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

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

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

Загрузка ...

Опытный

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

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

bsa, оказывается все просто smile

вот еще одну задачу решил:

Цитата

    Класс "Прямоугольник".
    Объявите класс "прямоугольник" с полями: int x1, y1, x2, y2
    (координаты левого верхнего и правого нижнего углов) и методами:
        пересечься с другим прямоугольником;
        проверить, попадает ли точка в данный прямоугольник;
        масштабировать при условии неподвижности левого верхнего угла;
        передвинуть по плоскости без вращения;

Код


/*
    Класс "Прямоугольник".
    Объявите класс "прямоугольник" с полями: int x1, y1, x2, y2
    (координаты левого верхнего и правого нижнего углов) и методами:
        пересечься с другим прямоугольником;
        проверить, попадает ли точка в данный прямоугольник;
        масштабировать при условии неподвижности левого верхнего угла;
        передвинуть по плоскости без вращения;
 */
#include <iostream>
using namespace std;

struct pos_rectangle{
    int x1, y1, x2, y2;
};

class rectangle{
    pos_rectangle p;
public:

    /*пересекает текущий прямоугольник с  другим прямоугольником*/
    void cross(rectangle);
    /*проверяет попадает ли точка в прямоугольник */
    bool test(int,int);
    /*передвигает прямоугольник по плоскости на заданные координаты (левый верхний угол)*/
    void move(int, int);
    /*масштабирование*/
    void zoom(float); //в качестве параметра будем передавать множитель.
    /*следующий метод получает координаты прямоугольниква*/
    pos_rectangle get_pos() {return p;}
    /*конструкторы*/
    rectangle(int x1,int y1,int x2, int y2) {
        /*обеспечим, что бы первое значение всегда было меньше второго*/
        if(x1<x2)
        {
            p.x1 = x1;
            p.x2 = x2;
        }
        else
        {
            p.x1 = x2;
            p.x2 = x1;
        }
        /*аналогично */
        if(y1<y2)
        {
            p.y1 = y1;
            p.y2 = y2;
        }
        else
        {
            p.y1 = y2;
            p.y2 = y1;
        }
    }
    rectangle() {
        p.x1 = 0;
        p.x2 = 0;
        p.y1 = 0;
        p.y2 = 0;
    }
};
void rectangle::cross(rectangle dest)
{
    pos_rectangle p_dest;
    int x,y;
    p_dest = dest.get_pos();
    /*будем передвигать левый верхний угол первого прямоугольника внутри координат второго
      до тех пор, пока координаты нижнего правого угла первого прямоугольника не выйдут
      за координаты нижнего правого угла второго прямоугольника

      Будем добиваться такого пересечения:
                -----------------
                |               |
                |       --------|--------
                |       |       |       |
                -----------------       |
                        |               |
                        -----------------
    */


    if((dest.test(p.x1,p.y1) && !dest.test(p.x2,p.y2)) ||
       (rectangle::test(p_dest.x1,p_dest.y1) && !rectangle::test(p_dest.x2,p_dest.y2)) )
        cout << "Rectangle \"a\" crossed rectangle \"b\"\n"; //пересеклись
    else
        /*перемещаем левый угол в середину второго прямоугольника*/
    {
        /*вычислим координаты*/
        x = (p_dest.x1+p_dest.x2)/2;
        y = (p_dest.y1+p_dest.y2)/2;
        rectangle::move(x,y);
        rectangle::cross(dest);
    }
}
bool rectangle::test(int x, int y)
{
    if(x >= p.x1 && x <= p.x2 && y >= p.y1 && y <= p.y2)
        return true;
    else
        return false;
}
void rectangle::move(int x, int y)
{
    int l = p.x2 - p.x1;
    p.x1 = x;
    p.x2 = x + l;
    l = p.y2 - p.y1;
    p.y1 = y;
    p.y2 = y + l;
}
void rectangle::zoom(float f)
{
    p.x2 *=f;
    p.y2 *=f;
}

int main()
{
    rectangle a(0,0,10,6), b(3,3,30,26);
    pos_rectangle A,B;
    A = a.get_pos();
    B = b.get_pos();
    /*покажем координаты*/
    cout << "Rectangle a[(" << A.x1 << "," << A.y1 << "),(" << A.x2 << "," << A.y2 << ")]\n";
    cout << "Rectangle b[(" << B.x1 << "," << B.y1 << "),(" << B.x2 << "," << B.y2 << ")]\n";
    a.cross(b);
    A = a.get_pos();
    cout << "Rectangle a[(" << A.x1 << "," << A.y1 << "),(" << A.x2 << "," << A.y2 << ")]\n";
    cout << "a * 2:\n";
    a.zoom(2);
    A = a.get_pos();
    cout << "Rectangle a[(" << A.x1 << "," << A.y1 << "),(" << A.x2 << "," << A.y2 << ")]\n";
    return 0;
}

можно было бы сделать еще метод принт, что бы не было безобразия с выводом координат прямоугольников smile

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

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

Дата 23.11.2010, 15:24 (ссылка)

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

Загрузка ...

Опытный

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

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

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

следующая задача:

Цитата

    Класс "рекурсивный список".
    Объявите класс, который реализует односвязный рекурсивный список строк
    в свободной памяти. Список представляется двумя указателями: указателем на
    строку в свободной памяти (поле info) и указателем на список же, только
    более короткий(поле tail). В частном случае одноэлементного списка
    этот указатель равен 0

я не понял что требуется: написать класс, рекурсивность которого проявляется только во время считывания элементов списка?
при других операциях работы со списком (добавление элемента и удаление элемента) я рекурсии не наблюдаю.

при удалении рекурсию можно сделать только что бы установить указатель на удаляемый элемент.
а при добавлении - если список делаем упорядоченным. Однако в задании сказано про рекурсивный список а не упорядоченный.

Это сообщение отредактировал(а) Чoо - 23.11.2010, 15:32

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

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

Дата 23.11.2010, 17:30 (ссылка)

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

Загрузка ...

Опытный

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

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

вобщем сделал класс только с рекурсивным выводом списка. непонятно что требовалось в задании.

Код


/*
    Класс "рекурсивный список".
    Объявите класс, который реализует односвязный рекурсивный список строк
    в свободной памяти. Список представляется двумя указателями: указателем на
    строку в свободной памяти (поле info) и указателем на список же, только
    более короткий(поле tail). В частном случае одноэлементного списка
    этот указатель равен 0
 */
#include <iostream>
#include <string.h>
using namespace std;

/*элемент списка*/
struct element{
    char *info;
    element *tail;

    /*введем конструктор, который будет выделять память для нового
      элемента (под строку) и заполнять его
    */
    element(const char *s){
        info = new char[strlen(s)+1];
        strcpy(info,s);
        tail = 0;
    }
    /*введем деструктор, который будет освобождать память, занимаемую
      строкой */
    ~element(){
        delete []info;
    }
};

/*собственно класс, реализующий список*/
class list{
private:
    element *head; //голова списка
    /*приватные методы*/
    void show_rec(element *curr); //принимает указатель на текущий элемент и выводит его и все последующие
    void show_rec_rev(element *curr); //аналогично, но в обратном порядке
public:
    /*конструктор*/
    list() {head = 0;}
    /*деструктор*/
    ~list(); //в деструкторе надо освободить память, занимаемую элементами списка и строками в них

    /*методы*/
    void add(const char *s); //добавляет элемент в список
    void del(const char *s);  //удаляет элемент из списка. pre - для указателя на предыдущий элемент
    void show(); //выводит все элементы списка на экран
    void showreverse(); //выводит все элементы списка с хвоста
};
/*деструктор*/
list::~list()
{
    while(head)
    {
        element *p = head->tail;
        delete head;
        head = p;
    }
}

/*определение методов*/
void list::add(const char *s)
{
    if(!head)
        head = new element(s);
    else
    {
        element *p = new element(s);
        p->tail = head;
        head = p;
    }
}
void list::del(const char *s)
{
    element *pre = 0, *curr = head;
    while(curr)
    {
        if(strcmp(s,curr->info) == 0)
        {
            /*удаляем текущий элемент и корректируем указатели*/
            if(pre)
                pre->tail = curr ->tail;
            delete curr;
            break;
        }
        else
        {
            pre = curr;
            curr = curr->tail;
        }
    }
}

/*секция выводит список в прямом порядке*/
void list::show()
{
    show_rec(head);
}
void list::show_rec(element *curr)
{
    if(!curr) return;
    cout << curr->info << endl;
    list::show_rec(curr->tail);
}
/*^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^*/

/*секция выводит список в обратном порядке*/
void list::showreverse()
{
    show_rec_rev(head);
}
void list::show_rec_rev(element *curr)
{
    if(!curr) return;
    show_rec_rev(curr->tail);
    cout << curr->info << endl;
}
/*^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^*/

int main()
{
    list l;
    char s[2];
    s[1] = 0;
    for(char c = 'a'; c < 'i'; c++)
    {
        s[0] = c;
        l.add(s);
    }
    cout << "вывод с головы списка:\n";
    l.show();
    cout << "вывод с хвоста списка:\n";
    l.showreverse();
    cout << "удалили одну строку (\"f\") и вывели список с хвоста:\n";
    l.del("f");
    l.showreverse();
    return 0;
}

Это сообщение отредактировал(а) Чoо - 24.11.2010, 10:40

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

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

Дата 25.11.2010, 19:56 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

    Система из трех классов. Объявите систему классов: "Точка", "Прямоугольник",
    "Эллипс". Определите методы, которые перемещают фигуру по плоскости, изменя-
    ют е размеры и выводят на экран.

Код


/*
    Система из трех классов. Объявите систему классов: "Точка", "Прямоугольник",
    "Эллипс". Определите методы, которые перемещают фигуру по плоскости, изменя-
    ют е размеры и выводят на экран.
 */
#include <stdio.h>


class point{
protected:
    int pos_x, pos_y;
public:
    point(int x, int y) {pos_x = x; pos_y = y;}
    virtual void show();
    virtual void resize(int factor) {};
    virtual void set_pos(int newpos_x, int newpos_y);
};
/*определение методов*/
void point::show()
{
    printf("координаты точки:\n     x: %d\n     y: %d\n", pos_x, pos_y);
}
void point::set_pos(int newpos_x, int newpos_y)
{
    printf("МЕНЯЕМ ПОЛОЖЕНИЕ...\n");
    pos_x = newpos_x; pos_y = newpos_y;
    printf("новые ");
    show();
}

class rectangle:public point{
private:
    int height, width; //высота и ширина понадобятся при перемещении прямоугольника
    void get_size();
protected:
    int pos_x2, pos_y2; //координаты прямоугольника можно задать 2-мя точками
public:
    rectangle(int x1, int y1, int x2, int y2);
    void show();
    void resize(int factor);
    void set_pos(int newpos_x, int newpos_y); //переопределяем, так как надо будет менять пары координат
};
/*конструктор*/
rectangle::rectangle(int x1, int y1, int x2, int y2):point(x1,y1),pos_x2(x2), pos_y2(y2)
{
    get_size();
}

/*определение методов*/
void rectangle::get_size()
{
    if((width = pos_x2 - pos_x)<0)
        width *= -1;
    if((height = pos_y2 - pos_y)<0)
        height *= -1;
}

void rectangle::show()
{
    printf("координаты прямоугольника:\n     верхний левый угол: %d;%d\n     нижний правый угол: %d;%d\n",
           pos_x, pos_y, pos_x2, pos_y2);
}
void rectangle::resize(int factor)
{
    /*перемещаем только правый нижний угол, взависимости от множителя
      положительный множитель - перемещаем вправо вниз,
      отрицательный - влево вверх, пока координаты угла больше нуля
    */
    printf("МЕНЯЕМ РАЗМЕР...\n");
    if(factor)
    {
        pos_x2 *= factor;
        pos_y2 *= factor;
    }
    else
        if(factor<0)
        {
            pos_x2 /= -factor;
            pos_y2 /= -factor;
        }
    get_size();
    printf("новые ");
    show();
}
void rectangle::set_pos(int newpos_x, int newpos_y)
{
    /*координаты задаем левым верхним углом прямоугольника.
      не забываем менять координаты првого нижнего угла */
    printf("МЕНЯЕМ ПОЛОЖЕНИЕ...\n");
    pos_x = newpos_x; pos_x2 = pos_x + width;
    pos_y = newpos_y; pos_y2 = pos_y + height;
    printf("новые ");
    show();
}

class ellipse:public point{
    int radius; //окружность определяется одной точкой и радиусом от нее.
public:
    ellipse(int x, int y, int r):point(x,y),radius(r) {} ;
    void show();
    void resize(int factor);
};
/*реализация класса*/
void ellipse::resize(int factor)
{
    printf("МЕНЯЕМ РАЗМЕР...\n");
    //ноль не обрабатываем
    radius = factor > 0 ? radius * factor : radius / (-factor);
    printf("новые ");
    show();
}
void ellipse::show()
{
    printf("коордынаты эллипса:\n     x: %d\n     y: %d\n     r: %d\n", pos_x, pos_y, radius);
}

int main()
{
    point *p;
    p = new point(100,500);
    p->show();
    p->resize(0); //ни чо не делает
    p->set_pos(10,50);
    delete p;

    /*дань полиморфизму =) */
    p = new rectangle(0,0,20,10);
    p->show();
    p->resize(2);
    p->set_pos(5,5);
    delete p;

    /*опять же полиморфизм*/
    p = new ellipse(10,10,6);
    p->show();
    p->resize(-2);
    p->set_pos(15,15);
    delete p;

    return 0;
}

прокомментируйте, если не трудно

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

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

Дата 26.11.2010, 10:23 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 25.11.2010, 19:56

)

class point{
protected:
    int pos_x, pos_y;
public:
    point(int x, int y) {pos_x = x; pos_y = y;}
    virtual void show();
    virtual void resize(int factor) {};
    virtual void set_pos(int newpos_x, int newpos_y);
};

1. используется protected, т.е. pos_x и pos_y доступны в производных классах. вроде бы класс предназначен для наследования. об этом говорит и наличие виртуальных функций. но в классах, которые могут быть базовыми, делают виртуальные деструкторы. для избежания проблем в будущем))
2. что означает resize в применении к point??
3. чего виртуального в функции set_pos? если у любой фигуры есть точка отсчета (origin), то его изменение не зависит от фигуры.

Код


class rectangle:public point{

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

Код


class point {...}; // не геом фигура

class shape {
private:
  point origin;
public:
  virtual ~shape() {}
  void move (const point& distance) { origin += distance; }
  virtual void draw () const = 0;
  point get_origin () const;
...
};

class geom_point : public shape {...};
class rect : public shape {...};

Это сообщение отредактировал(а) baldina - 26.11.2010, 10:25

Дата 26.11.2010, 15:51 (ссылка)

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

Загрузка ...

Опытный

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

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

baldina,
1. - protected объявил для того, что бы можно было получить доступ к полям класса только из методов самого класса, а так же из производных классов.
2. resize в применении к поинт - ни чего не делает, т.к. точка - она точкА, ее невозможно масштабировать.
3. про точку отсчета немного недопонял:
в 10 строке вашего класса получение точки отсчета. Метод будет вызываться из производных классов(как и move), однако точка отсчета представлена только координатами одной точки x и y. И теперь мне не понятно, если прямоугольник будет производным классом от shape, то как будет задано его положение на сетке координат, ведь координаты одной точки для него не достаточны.
move так же меняет координаты одной точки.

Это сообщение отредактировал(а) Чoо - 26.11.2010, 15:58

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

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

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

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 26.11.2010, 15:51

)

1. - protected объявил для того, что бы можно было получить доступ к полям класса только из методов самого класса, а так же из производных классов.

говорю же. если класс должен быть базовым - деструктор объявляется виртуальным

Цитата(Чoо @ 26.11.2010, 15:51

)

. про точку отсчета немного недопонял

точка отсчета - одна, она не зависит от фигуры. это ноль в локальной системе координат фигуры

Цитата(Чoо @ 26.11.2010, 15:51

)

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

достаточно. вот что бы отобразить, помимо origin надо знать еще width и height, а что бы переместить и origin вполне хватит

Код


                      width
                -----------------
                |               | height
                |       --------|--------
                |       |       |       | height
                +----------------       |
            origin1     |               |
                        +----------------
                    origin2   width

Добавлено @ 16:21

Код


class rectangle:public shape{
private:
    int height, width; 
public:
    rectangle(int x1, int y1, int x2, int y2) : shape(x1, y1), width(x2-x1), height(y2-y1) {}
    void show() {
       point o = get_origin ();
       draw_rectangle (o.x, o.y, o.x+width, o.y+height);
    }
};

Добавлено через 10 минут и 8 секунд
кстати. функция resize, где factor - целое число, принимающее отрицательные значения (при уменьшении), выглядит несколько странно.
проще factor иметь действительным (double) и использовать только операцию умножения. уменьшение будет при значениях от 0 до 1.
а вообще - почитайте про аффинные преобразования, это простой и универсальный инструмент для перемещения, масштабирования, поворота и их комбинаций. все программы 2D и 3D графики используют их.

Это сообщение отредактировал(а) baldina - 26.11.2010, 16:22

Дата 26.11.2010, 16:36 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 26.11.2010, 15:51

)

2. resize в применении к поинт - ни чего не делает, т.к. точка - она точкА, ее невозможно масштабировать.

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

Дата 26.11.2010, 17:44 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(baldina @ 26.11.2010, 16:16

)

да, понял. Спасибо. Затупил что-то smile

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

Код


/*
    Система из трех классов. Объявите систему классов: "Точка", "Прямоугольник",
    "Эллипс". Определите методы, которые перемещают фигуру по плоскости, изменя-
    ют е размеры и выводят на экран.
 */
#include <stdio.h>

struct point{
    int x,y;
};

/*абстрактная геометрическая фигура*/
class shape {
private:
  point origin;
public:
  shape() {origin.x = 0; origin.y = 0;}
  virtual ~shape() {}
  void move (const point &distance);
  virtual void draw () const = 0;
  virtual void resize(int factor) = 0;
  point get_origin () const;
};
void shape::move(const point &distance)
{
    origin.x += distance.x;
    origin.y += distance.y;
    printf("ИЗМЕНИЛИ ПОЛОЖЕНИЕ...\n");
    draw();
}
point shape::get_origin() const
{
    return origin;
}

/*точка*/
class geom_point:public shape{
public:
    void draw() const;
    void resize(int factor) {printf("изменение размеров точки невозможно!\n");}
};
void geom_point::draw() const
{
    point p;
    p = get_origin();
    printf("Координаты точки (x;y): %d;%d\n",p.x,p.y);
}

/*эллипс*/
class ellipse:public shape{
    int radius;
public:
    void draw() const;
    void resize(int factor);
};
void ellipse::draw() const
{
    point p;
    p = get_origin();
    printf("Координаты эллипса (x;y): %d;%d\n     радиус: %d\n",p.x,p.y,radius);
}
void ellipse::resize(int factor)
{
    printf("МЕНЯЕМ РАЗМЕР...\n");
    if(radius)
      radius = factor > 0 ? radius * factor : radius / (-factor);
    else
      radius = factor > 0 ? radius + factor : radius + (-factor);
    draw();
}

/*прямоугольник*/
class rectangle:public shape{
    int width, height;
public:
    rectangle() { width = 0; height = 0;}
    void draw() const;
    void resize(int factor);
};
void rectangle::draw() const
{
    point p;
    p = get_origin();
    printf("Координаты прямоугольника (x;y): %d;%d\n     ширина: %d\n     высота: %d\n",p.x,p.y,width, height);
}
void rectangle::resize(int factor)
{
    printf("МЕНЯЕМ РАЗМЕР...\n");
    if(factor>0)
    {
        width = width != 0 ? width * factor : width + factor;
        height = height != 0 ? height * factor : height + factor;
    }
    else
        if(factor<0)
        {
            width = width != 0 ? width / (-factor) : width + (-factor);
            height = height !=0 ? height / (-factor) : height + (-factor);
        }
    draw();
}

int main()
{
    shape *s;
    s = new geom_point;
    s->draw();
    s->move((point){3,-4});
    delete s;

    s = new ellipse;
    s->draw();
    s->move((point){5,5});
    s->resize(-2);
    delete s;

    s = new rectangle;
    s->draw();
    s->move((point){-1,-1});
    s->resize(-5);
    delete s;

    return 0;
}

Всё правильно понял?
однако не получилось избваиться от метода resize для точки.

Добавлено @ 17:46
и непонятно почему в объявлении метода draw константа. он же ни чего не принимает и ни чего не возвращает..
(а это нужно для того, что бы случайно не изменить содержимое полей объекта, что-то медленно все вспоминаю)

Это сообщение отредактировал(а) Чoо - 26.11.2010, 18:13

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

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

Дата 29.11.2010, 09:41 (ссылка)

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

Загрузка ...

Эксперт

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

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

Чoо,
1. добавьте в point конструктор и операторы +,+=,*,*=
это позволит сделать код короче и яснее
2. можно resize не делать виртуальным. достаточно хранить коэф. масштабирования, а при рисовании (и прочих операциях) умножать на него координаты точек.

Код


class shape {
 ...
 private:
   point origin;
   double factor;
 protected:
   point transform (const point& p) const
   {
      return origin + p*factor;
   }
 public:
   shape (const point& o = point(0,0)) : origin (o), factor(1.) {}
   void resize (double f) const { factor *= f; }
   double get_scale () const { return factor; }
 ...
};
...
void rectangle::draw() const
{
    printf("Прямоугольник (ширина, высота): %lf %lf\n", width, height);
    printf("\tМасштабный коэф.: %lf\n", get_scale());
    // левый нижний угол
    point lb =  transform(point(0,0));
    // правый верхний угол
    point rt =  transform(point(width,height));
    printf("\tКоординаты (x1,y1,x2,y2): %lf %lf %lf %lf\n", lb.x, lb.y, rt.x, rt.y);
}

Это сообщение отредактировал(а) baldina - 29.11.2010, 09:44

Дата 30.11.2010, 20:38 (ссылка)

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

Загрузка ...

Опытный

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

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

baldina, спасибо, что помогаете smile

переделал решение, вот результат:

Код


/*
    Система из трех классов. Объявите систему классов: "Точка", "Прямоугольник",
    "Эллипс". Определите методы, которые перемещают фигуру по плоскости, изменя-
    ют е размеры и выводят на экран.
 */
#include <stdio.h>

class point{
public:
    int x,y;
    point() {x = 0; y = 0;}
    point(int pos_x, int pos_y) {x = pos_x; y = pos_y;}
    /*перегружаем операторы +,*,=, +=, *=  */
    point operator +(point p2);
    point operator *(point p2);
    point operator =(point p2);
    void operator +=(point p2);
    void operator *=(point p2);

};
point point::operator +(point p2)
{
    point tmp;
    tmp.x = x + p2.x;
    tmp.y = y + p2.y;
    return tmp;
}
point point::operator *(point p2)
{
    point tmp;
    tmp.x = x * p2.x;
    tmp.y = y * p2.y;
    return tmp;
}

point point::operator =(point p2)
{
    x = p2.x;
    y = p2.y;
    return *this;
}
void point::operator +=(point p2)
{
    x = x + p2.x;
    y = y + p2.y;
}
void point::operator *=(point p2)
{
    x = x*p2.x;
    y = y*p2.y;
}

/*абстрактная геометрическая фигура*/
class shape {
private:
  point origin;
  double factor;
public:
  shape (const point &o) : origin (o), factor(1.) {}
  virtual ~shape() {}

  void move (const point &distance);
  void resize (const double f);

  point get_origin () const {return origin;}
  double get_scale () const {return factor;}

  virtual void draw () const = 0;
};
void shape::move(const point &distance)
{
    origin = distance;
    printf("ИЗМЕНИЛИ ПОЛОЖЕНИЕ...\n");
    draw();
}
void shape::resize(const double f)
{
    printf("ПОМЕНЯЛИ МАСШТАБНЫЙ КОЭФФИЦИЕНТ...\n");
    factor *= f;
    draw();
}


/*точка*/
class geom_point:public shape{
public:
    geom_point():shape((point){0,0}){};
    geom_point(const point &o):shape(o){};
    void draw() const;
};
void geom_point::draw() const
{
    point p;
    p = get_origin();
    printf("Координаты точки (x;y): %d;%d\n",p.x,p.y);
}

/*эллипс*/
class ellipse:public shape{
    int radius;
public:
    ellipse():shape((point){0,0}),radius(0){};
    ellipse(const point &o, int r):shape(o),radius(r){};
    void draw() const;
};
void ellipse::draw() const
{
    point p;
    p = get_origin();
    printf("Координаты эллипса (x;y): %d;%d\n     радиус: %f\n",p.x,p.y,radius*get_scale());
}

/*прямоугольник*/
class rectangle:public shape{
    int width, height;
public:
    rectangle():shape((point){0,0}),width(0), height(0){};
    rectangle(const point &o, int w, int h):shape(o),width(w), height(h){};
    void draw() const;
};
void rectangle::draw() const
{
    point p;
    p = get_origin();
    double factor = get_scale();
    printf("Координаты прямоугольника (x;y): %d;%d\n     ширина: %f\n     высота: %f\n",p.x,p.y,width*factor, height*factor);
}

int main()
{
    shape *s;
    s = new geom_point((point){2,3});
    s->draw();
    s->move((point){3,-4});
    delete s;

    printf("\n");

    s = new ellipse((point){0,0},3);
    s->draw();
    s->move((point){5,5});
    s->resize(0.5);
    delete s;

    printf("\n");

    s = new rectangle((point){0,0},5,4);
    s->draw();
    s->move((point){-1,-1});
    s->resize(5);
    delete s;

    return 0;
}

Надеюсь, что в этот раз всё правильно smile

.
на выходных решил еще одну задачу:

Цитата

    Объявите класс file для работы с файловой системой (удаление, переименование,
    чтение и запись атрибутов). Унаследуйте от него класс catalog для работы с
    каталогами (получение массива файлов, находящихся в каталоге) и вспомогательный
    класс filter, объект которого должен передаваться в метод получения содержимого

Код


/*
    Объявите класс file для работы с файловой системой (удаление, переименование,
    чтение и запись атрибутов). Унаследуйте от него класс catalog для работы с
    каталогами (получение массива файлов, находящихся в каталоге) и вспомогательный
    класс filter, объект которого должен передаваться в метод получения содержимого
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <time.h>
#include <dirent.h>
#include <errno.h>

struct filter{
    char extention[20]; //расширение файла
    /*можно было бы сделать больше полей, но пришлось бы писать больше кода для обработки*/
};

class file{
private:
    void get_premission(short bit, int shift, bool prot); //пока не знаю, куда запихнуть эту функцию, поэтому
                                                          //поместил ее в методы. Самма функция работает корректно
                                                          //но выглядит коряво
public:
    virtual ~file() {};
    void delete_file(const char *name);
    void rename_file(const char *old_name, const char *new_name);
    int attribute_read(struct stat *buf, const char *filename); //вернет ноль, если удастся получить аттрибуты, иначе - -1.
    void show_attribute(const char *filename); //просто показывает атрибуты файла (не все) как в команде ls -l.
                           //Вместо имени пользователя и группы будет отображено только ID
    void attribute_write() {}; //не реализовал. Слишком нудно для учебной задачи :)
};
void file::rename_file(const char *old_name, const char *new_name)
{
    if(rename(old_name,new_name))
        printf("ошибка переименования!\n");
    else
        printf("файл успешно переименован\n");
}
void file::delete_file(const char *name)
{
    remove(name);
}
int file::attribute_read(struct stat *buf, const char * filename)
{
    if(stat(filename,buf)==0)
        return 0;
    return -1;
}
void file::get_premission(short bit,int shift, bool prot)
{
    switch(bit << shift)
    {
    case S_IXUSR:
        if(prot)
            if(shift!=6)
                printf("--s");
            else
                printf("--t");
        else
            printf("--x");
        break;
    case S_IWUSR:
        printf("-w");
        if(prot)
            if(shift != 6)
                printf("S");
            else
                printf("T");
        else
            printf("-");
        break;
    case S_IXUSR | S_IWUSR:
        printf("-w");
        if(prot)
            if(shift!=6)
                printf("s");
            else
                printf("t");
        else
            printf("x");
        break;
    case S_IRUSR:
        printf("r-");
        if(prot)
            if(shift!=6)
                printf("S");
            else
                printf("T");
        else
            printf("-");
        break;
    case S_IXUSR | S_IRUSR:
        printf("r-");
        if(prot)
            if(shift!=6)
                printf("s");
            else
                printf("t");
        else
            printf("x");
        break;
    case S_IWUSR | S_IRUSR:
        printf("rw");
        if(prot)
            if(shift!=6)
                printf("S");
            else
                printf("T");
        else
            printf("-");
        break;
    case S_IRWXU:
        printf("rw");
        if(prot)
            if(shift!=6)
                printf("s");
            else
                printf("t");
        else
            printf("x");
        break;
    default:
        printf("--");
        if(prot)
            if(shift!=6)
                printf("S");
            else
                printf("T");
        else
            printf("-");
    }
}

void file::show_attribute(const char *filename)
{
    struct stat buf;
    if(attribute_read(&buf,filename)!=0)
    {
        printf("Не удалось получиь аттрибуты...\n");
        return;
    }

    /*применяем макросы, что бы узнать тип файла*/
    if(S_ISREG(buf.st_mode))
        printf("-");
    else
    if(S_ISDIR(buf.st_mode))
        printf("d");
    else
    if(S_ISCHR(buf.st_mode))
        printf("c");
    else
    if(S_ISBLK(buf.st_mode))
        printf("b");
    else
    if(S_ISSOCK(buf.st_mode))
        printf("s");
    else
    if(S_ISFIFO(buf.st_mode))
        printf("p");
    else
    if(S_ISLNK(buf.st_mode))
        printf("l");
    else
        printf("uncnown_type");

    /*смотрим биты setuid, setgid и sticky
      их значения пригодятся позже (ни чего лучше
      безобразия дальше по коду не придумал)
    */
    bool setuid = 0, setgid = 0, sticky = 0;
    switch (buf.st_mode & 07000)
    {
    case S_ISVTX:
        sticky = 1; break;
    case S_ISVTX | S_ISGID:
        sticky = 1;
        setgid = 1; break;
    case S_ISVTX | S_ISUID:
        sticky = 1;
        setuid = 1; break;
    case S_ISGID:
        setgid = 1; break;
    case S_ISGID | S_ISUID:
        setgid = 1;
        setuid = 1; break;
    case S_ISUID:
        setuid = 1; break;
    case S_ISUID | S_ISGID | S_ISVTX:
        setuid = 1;
        setgid = 1;
        sticky = 1;
    }

    /*получаем права владельца*/
    get_premission(buf.st_mode & 0700,0,setuid);
    /*права группы*/
    get_premission(buf.st_mode & 070,3,setgid);
    /*права других пользователей*/
    get_premission(buf.st_mode & 07,6,sticky);

    /*выводим количество ссылок на файл*/
    printf("     %d ",buf.st_nlink);
    /*выводим ID владельца файла*/
    printf("%d     ",buf.st_uid);
    /*выводим ID группы-владельца*/
    printf("%d     ",buf.st_gid);
    /*выводим размер файла*/
    printf("%d  ",buf.st_size);
    /*покажем дату последней модификации файла*/
    struct tm *t;
    t = gmtime(&buf.st_mtime);
    char time[17];
    strftime(time,17,"%F %R",t);
    printf("%s ",time);
    /*имя файла*/
    printf("%s\n",filename);


}

class catalog:public file
{
    char *dirname;
    char **filelist; //список файлов хранится тут
    int files_count;  //количество файлов в списке
public:
    void get_filelist(const filter filt);           //получает список файлов в дирректории dirname
    //конструкторы-деструкторы
    catalog(const char *name);
    ~catalog();
};
catalog::catalog(const char *name)
{
    dirname = new char[strlen(name)+1];
    strcpy(dirname,name);
    files_count = 0;
    filelist = NULL;
}
catalog::~catalog()
{
    delete []dirname;
    /*очищаем список файлов*/
    for(int i = 0; i < files_count; ++i)
    {
        delete [] filelist[i];
    }
    delete []filelist;
}

void catalog::get_filelist(const filter filt)
{
    DIR *dir;
    char *buf;
    int filelist_size = 0; //количество указателей в массиве filelist
    struct dirent *entry;
    struct stat attrib;

    files_count = 0;
    /* открыть указанный каталог, если возможно. */
    dir = opendir(dirname);
    if(dir == NULL)
    {
        printf("Error opening %s: %s", dirname, strerror(errno));
        return;
    }
    entry = readdir(dir);
    while(entry != NULL)
    {
        if(((entry->d_name !=".") || (entry->d_name !="..")) &&
           ((strcmp(filt.extention,"")==0) || (strstr(entry->d_name,filt.extention))))
        {
            buf = new char[strlen(entry->d_name)+1];
            strcpy(buf,entry->d_name);
            if(attribute_read(&attrib,entry->d_name) == 0)
            {
                /*в задании сказано формировать только массив обычных файлов*/
                if(S_ISREG(attrib.st_mode))
                {
                    files_count++;
                    /*перераспределяем память, если это необходимо
                      при повторном вызове метода память так же перераспределится
                    */
                    if(filelist_size<files_count)
                    {
                        filelist_size = files_count * 2;
                        filelist = (char**) realloc((char**)filelist,sizeof(char**)*filelist_size);
                    }
                    filelist[files_count-1] = new char[strlen(entry->d_name)+1];
                    strcpy(filelist[files_count-1],entry->d_name);
                }
            }
        }
        entry = readdir(dir);
    }
    /*заполнили список файлов. Перераспределяем память, так как возхможно, что выделена лишняя*/
    filelist = (char**)realloc((char**)filelist,sizeof(char**)*files_count);
    closedir(dir);
    /*отобразим список файлов*/
    for(int i = 0; i < files_count; ++i)
    {
        printf("%s\n",filelist[i]);
    }

}

int main()
{
    catalog *d;
    filter filt = {".txt\0"};
    d = new catalog("/home/oem/Developed/Cpp/study/exercise/2.2.7.2/untitled2-build-desktop");
    printf("Список файлов в дирректории:\n");
    d->get_filelist(filt);
    for(;;)
    {
        printf("Введите имя файла, атрибуты которого хотите поулчить. Для выхода нажмите просто <enter>...\n");
        char name[255];
        gets(name);
        if(strcmp(name,"")==0)
            break;
        d->show_attribute(name);
        printf("\n");
    }
    for(;;)
    {
        printf("Введите имя файла, который хотите переименовать. Для выхода нажмите <enter>...\n");
        char name[255];
        gets(name);
        if(strcmp(name,"")==0)
            break;
        char new_name[255];
        printf("Введите новое имя файла...\n");
        gets(new_name);
        d->rename_file(name,new_name);
        printf("\nСписок файлов в дирректории:\n");
        d->get_filelist(filt);
        printf("\n");
    }
    for(;;)
    {
        printf("Введите имя файла, который хотите удалить. Для выхода нажмите <enter>...\n");
        char name[255];
        gets(name);
        if(strcmp(name,"")==0)
            break;
        d->delete_file(name);
        printf("\nСписок файлов в директории:\n");
        d->get_filelist(filt);
        printf("\n");
    }
    delete d;
    return 0;
}

решал под линукс. Еще хотел отсортировать файлы по-имени, но это в задачу не входит. Хотя можно было бы ввести метод сортировки smile

.
если для тренировки, такая система классов подойдет. Если писать реальную систему, то я бы писал не пару дней, что слишком лениво делать на этапе обучения.

Это сообщение отредактировал(а) Чoо - 30.11.2010, 20:41

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

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

Дата 2.12.2010, 19:48 (ссылка)

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

Загрузка ...

Опытный

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

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

По последним задачам, там все правильно?

Следующая задача.

Цитата

    Клонирование объекта. объявите некоторый класс и анпишите
    вирутальный метод, возвращающий копию объекта. Заместите его
    в производном классе.

Код


/*
    Клонирование объекта. объявите некоторый класс и анпишите
    вирутальный метод, возвращающий копию объекта. Заместите его
    в производном классе.
 */
#include <stdio.h>

class someclass{
public:
    int field1; //делаем видимым, что бы можно было изменить вне методов класса. Это не хорошо, но для примера норм.
    someclass() {}
    virtual ~someclass() {}
    virtual someclass *copyobj();
};
someclass *someclass::copyobj()
{
    someclass *c;
    c = new someclass;
    c->field1 = field1;
    return c;
}

class childclass:public someclass{
public:
    childclass() {}
    ~childclass() {}
    childclass *copyobj();
};
childclass *childclass::copyobj()
{
    childclass *c;
    c = new childclass;
    c->field1 = field1;
    return c;
}

int main()
{    
    someclass *c, *s;
    c = new someclass;
    c->field1 = 100500;
    //должны создать копию объекта с, где field1 = 100500;
    s = c->copyobj();
    delete c;
    delete s;

    c = new childclass;
    c->field1 = 300;
    s = c->copyobj();
    delete c;
    delete s;

    return 0;
}

вот тут не знаю. по идее я делаю копию, вроде результат есть smile

. но может это надо делать иначе? Пробовал через создание временного объекта, но он временный и уничтожается до того, как я его уничтожу сам smile

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

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

Дата 3.12.2010, 00:32 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

    Список из полиморфных объектов. Спроектируйте класс "список" таким
    образом, что бы он был способен хранить элементы различных типов,
    производных от базового типа "Элемент". В Класс "Элемент" добавьте
    виртуальный метод print() для вывода элемента в стандартный поток.

Код


/*
    Список из полиморфных объектов. Спроектируйте класс "список" таким
    образом, что бы он был способен хранить элементы различных типов,
    производных от базового типа "Элемент". В Класс "Элемент" добавьте
    виртуальный метод print() для вывода элемента в стандартный поток.
 */

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

/*элемент списка
  Сделаем абстрактным.
*/
struct element{
    element *next; //указатель на следующий элемент присущ любому элементу списка
    virtual void print() = 0;
};

/*элемент хранит имя и фамилию некоего индвида*/
struct element_ns:public element{
    char *name,
         *surname;
    //element_ns *next;

    /*конструктор, выделяющий память для полей элемента*/
    element_ns(const char *nm, const char *snm)
    {
        name =(char*) malloc(sizeof(char)*strlen(nm)+sizeof(char));
        strcpy(name,nm);

        surname=(char *) malloc(sizeof(char)*strlen(snm)+sizeof(char));
        strcpy(surname,snm);

        next = 0; //для нового элемента всегда 0.
    }

    /*деструктор, освобождающий память, занимаемую полями объекта, перед уничтожением объекта*/
    ~element_ns()
    {
        free(name);
        free(surname);
    }

    /*методы класса*/
    void print()
    {
        printf("Элемент класса element_ns: %s, %s\n", name, surname);
    }
};

/*Элемент хранит марку автомобиля и его номер*/
struct element_car:public element{
    char *brand;
    int number;
    //element_car *next;

    /*в конструкторе выделяем память для поля brand, номер по-умолчанию 0*/
    element_car(const char *br, const int no)
    {
        brand = (char*)malloc(sizeof(char)*strlen(br)+sizeof(char));
        strcpy(brand,br);
        number = no;
        next = 0;
    }

    /*в деструкторе освобождаем память, занимаемую brand*/
    ~element_car()
    {
        free(brand);
    }

    /*методы класса*/
    void print()
    {
        printf("Элемент класса element_car: марка: %s; номер: %d\n", brand, number);
    }

};

/*элемент хранит какие-то числа :)*/
struct element_somenumbers:public element{
    int n1,
        n2,
        n3;
    //element_somenumbers *next;

    element_somenumbers(int a, int b, int c)
    {
        n1 = a;
        n2 = b;
        n3 = c;
        next = 0;
    }
    void print()
    {
        printf("Элемент класса element_somenumbers: no.1: %d, no.2: %d, no.3: %d\n",n1, n2, n3);
    }
};

/*класс, реализующий список*/
class list{
private:
    element *head; //голова списка
public:
    /*конструктор*/
    list() {head = 0;}
    /*деструктор*/
    ~list(); //в деструкторе надо освободить память, занимаемую элементами списка и строками в них

    /*методы*/
    void add(const char *nm, const char *snm);
    void add(const char *brand, const int number);
    void add(int a, int b, int c);
    void show(); //выводит все элементы списка на экран
};
list::~list()
{
    while(head)
    {
        element *p = head->next;
        delete head;
        head = p;
    }
}
void list::add(const char *nm, const char *snm)
{
    if(!head)
        head = new element_ns(nm,snm);
    else
    {
        element *p = new element_ns(nm,snm);
        p->next = head;
        head = p;
    }
}
void list::add(const char *brand, const int number)
{
    if(!head)
        head = new element_car(brand,number);
    else
    {
        element *p = new element_car(brand,number);
        p->next = head;
        head = p;
    }
}
void list::add(int a, int b, int c)
{
    if(!head)
        head = new element_somenumbers(a,b,c);
    else
    {
        element *p = new element_somenumbers(a,b,c);
        p->next = head;
        head = p;
    }
}
void list::show()
{
    element *curr = head;
    while(curr)
    {
        curr->print();
        curr = curr->next;
    }

}

int main()
{
    list *o;
    o = new list;
    o->add(1,2,3);
    o->add("Ford", 666);
    o->add("Il", "Sh");
    o->add("opel",777);
    o->add(7,7,7);
    o->add("Ch", "OO");
    o->show();
    delete o;
    return 0;
}

Добавлено @ 00:32
решил с malloc потренироваться smile

Это сообщение отредактировал(а) Чoо - 3.12.2010, 00:51

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

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

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

Дата 6.12.2010, 14:37 (ссылка)

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

Загрузка ...

Эксперт

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

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

Чoо, ты на каком языке пишешь?

Цитата(Чoо @ 3.12.2010, 01:32

)

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

На С++ это должно быть так:

Код

#include <cstdio>
#include <cstdlib>
#include <cstring>

А по хорошему, вообще используй iostream... Или пиши на Си.

хочешь ты того или не хочешь, но sizeof(char) == 1.

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

Дата 6.12.2010, 14:46 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(bsa @ 6.12.2010, 14:37

)

Чoо, ты на каком языке пишешь?

честно говоря не знаю, каша в голове smile

Цитата(bsa @ 6.12.2010, 14:37

)

хочешь ты того или не хочешь, но sizeof(char) == 1.

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

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

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

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

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

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

Загрузка ...

Эксперт

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

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

Чoо, а кто говорил про проблемы компиляции? Читать неудобно!

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

Дата 6.12.2010, 16:56 (ссылка)

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

Загрузка ...

Опытный

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

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

bsa, оК, учту в следующих задачах.
Единственное что, по предыдущему замечанию, есть непонятки. Почему плохо использовать стандартные библиотеки Си в программах на с++ ? smile

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

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

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

Дата 6.12.2010, 18:23 (ссылка)

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

Загрузка ...

Эксперт

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

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

Чoо, потому что на С++ все это решается гораздо проще и оптимальней.

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

Дата 6.12.2010, 19:30 (ссылка)

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

Загрузка ...

Опытный

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

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

bsa, тоесть библиотеки типа cstring в принципе выполняют то же самое, что и string.h, только отличаются более эфективной реализацией?

Это сообщение отредактировал(а) Чoо - 6.12.2010, 19:31

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

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

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

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

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

Загрузка ...

Эксперт

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

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

В С++ string.h зовется cstring. Отличий почти нет, разве что все стандартные символы (функции, переменные) помещены в пространство имен std. Это касается всех стандартных сишных хидеров (cstdio, cstdlib...)

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

Дата 7.12.2010, 13:12 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Код


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

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

Код


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

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

***
решил еще одну задачу.

Цитата

    Класс "Слово". Объявите класс "слово", полем которого является массив символов
    в свободной памяти с конструктором копирования и методами:
        - поулчить длину слова
        - определить расстояние между слвоами
        - сравнить объект с другим словом
    Класс должен иметь статическое поле, определяющее порядок следования букв в алфавите.

Код


/*
    Класс "Слово". Объявите класс "слово", полем которого является массив символов
    в свободной памяти с конструктором копирования и методами:
        - поулчить длину слова
        - определить расстояние между слвоами
        - сравнить объект с другим словом
    Класс должен иметь статическое поле, определяющее порядок следования букв в алфавите.
 */
#include <iostream>
using namespace std;

class word{
    char *w;
    int pos_char(const char c); //возвращает позицию символа в маске
    void cpy(char *dest, const char *src);
public:
    static char *mask;

    word():w(0){};
    word(const char *s)
    {
        w = new char[get_length()+1];
        cpy(w,s);
    }
    word(const word &p)
    {
        w = new char[p.get_length()+1];
        cpy(w,p.w);
    }
    ~word()
    {
        delete []w;
    }

    /*методы*/
    char *get_word()
    {
        return w;
    }

    int get_length() const
    {
        int i;
        for(i = 0; w[i]; ++i);
        return i;
    }
    int dist(const word &p); //находит расстояние между словами
    int cmp(const word &p);  //сравнивает объект с другим объектом. Результат выглядит так же, как и в strcmp
};
/*определим порядок следования символов (в объявлении класса было нельзя)*/
char *word::mask = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                  "abcdefghijklmnopqrstuvwxyz";
void word::cpy(char *dest, const char *src)
{
    for(int i = 0; src[i]; dest[i] = src[i], ++i);
}

int word::dist(const word &p)
{
    /*будем искать расстояние Kевенштейна по Вагнеру-Фишеру
      цена замены = цена вставки = цена удаления = 1
    */
    int l = 0; //расстояние

    int m = get_length()+1;
    int n = p.get_length()+1;

    /* инициализируем массив расстояний */
    int **d = 0;
    d = new int*[m];
    for(int i = 0; i < m; ++i)
        d[i] = new int [n];

    for(int i = 0; i < m; ++i)
        for(int j = 0; j< n; ++j)
        {
            if(!i && !j)
                d[i][j] = 0; //случай, когда обе строки не имеют ни одного символа
            else
            if(!i && j)
                d[i][j] = j; //первая строка - 0, вторая содержит символы => d(0,j) = j;
            else
            if(i && !j)
                d[i][j] = i; // d(i,0) = i;
            else            //i и j > 0                
            {
            int cost = w[i-1] == p.w[j-1] ? 0 : 1; //определяем цену замены
             d[i][j] = min(min(
                     d[i-1][j] + 1,         //цена удаления
                     d[i][j-1] + 1),      //цена вставки
                     d[i-1][j-1] + cost);  //цена замены
            }
        }
    if(d)
    {
        l = d[m-1][n-1];
        /*освобождаем память*/
        for(int i = 0; i < m; ++i)
            delete [] d[i];
        delete []d;
    }
    return l;
}
int word::pos_char(const char c)
{
    int i;
    for(i = 0; c!=mask[i] && mask[i]; ++i); //на всякий случай контролируем выход за пределы массива
    return i;
}

int word::cmp(const word &p)
{
    int i;
    for(i = 0; w[i] && p.w[i]; ++i)
    {
        if (pos_char(w[i]) < pos_char(p.w[i]))
            return -1;
        if (pos_char(w[i]) > pos_char(p.w[i]))
            return 1;
    }
    if (get_length() < p.get_length())
        return -1;
    else
    if (get_length() > p.get_length())
        return 1;
    return 0;
}

int main()
{
    word w("array");
    word w2("around");
    cout << "расстояние между словами: " << w.dist(w2) << endl;
    char r;
    switch(w.cmp(w2))
    {
    case -1:
        r = '<';
        break;
    case 1:
        r = '>';
        break;
    default:
        r = '=';
    }
    cout << w.get_word() << r << w2.get_word() << endl;
    return 0;
}

я так понял по условию, что вместо strcmp и getlng надо сделать свои функции. Ну а если их реализовывать самостоятельно, то значит не использовать cstring => придется реализовать и strcpy.
Результат вроде правильынй smile

Хотя вот конструктор не использовал, хоть и сделал его (передавал объект не по значению, а по ссылке)

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

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

Дата 7.12.2010, 15:34 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

    Класс "Депозитный вклад".
    Объявите класс "депозитный вклад", полями которого является:
        - денежная сумма
        - дата последнего перерасчета
    а методами:
        - добавить сумму
        - начислить проценты
        - снять с вклада только проценты
    Статическое поле - годовой процент.

как-то слишком просто...

Код


/*
    Класс "Депозитный вклад".
    Объявите класс "депозитный вклад", полями которого является:
        - денежная сумма
        - дата последнего перерасчета
    а методами:
        - добавить сумму
        - начислить проценты
        - снять с вклада только проценты
    Статическое поле - годовой процент.
 */
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;

class deposit{
    float balance;
    time_t date_of_recalc;
    void set_time();
public:
    const static float percent;
    deposit();
    deposit(const float money);

    void add_money(const float money);
    void assessmnt_percent();
    void rent_percent();

};
const float deposit::percent = 0.03;
/*конструкторы*/
deposit::deposit()
{
    balance = 0;
    set_time();
    printf("%s  Cоздан депозитный вклад под %.02f годовых\n  Баланс: %.02f$\n\n",ctime(&date_of_recalc),percent,balance);
}
deposit::deposit(const float money)
{
    balance = money;
    set_time();
    printf("%s  Cоздан депозитный вклад под %.02f годовых\n  Баланс: %.02f$\n\n",ctime(&date_of_recalc),percent,balance);
}

/*методы*/
void deposit::set_time()
{
    date_of_recalc = time(NULL);
}

void deposit::add_money(const float money)
{
    balance += money;
    set_time();
    printf("%s  Приход: +%.2f$\n  Баланс: %.02f$\n\n",ctime(&date_of_recalc),money,balance);

}
void deposit::assessmnt_percent()
{
    balance += balance * percent;
    set_time();
    printf("%s  Начислены проценты: +%.2f$\n  Баланс: %.02f$\n\n",ctime(&date_of_recalc),balance*percent,balance);
}
void deposit::rent_percent()
{
    balance -= balance*percent;
    set_time();
    printf("%s  Сняты проценты: -%.2f$\n  Баланс: %.02f$\n\n",ctime(&date_of_recalc),percent,balance);
}

int main()
{
    deposit d;
    sleep(1);
    d.add_money(100.36);
    sleep(1);
    d.assessmnt_percent();
    sleep(1);
    d.rent_percent();


    return 0;
}

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

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

Дата 7.12.2010, 18:03 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

Класс "Стек".
Объявите класс "Стек" с методами push() и pop(). Сделайте это на основе массива

тоже все просто. Память решил выделять так, как советовали ранее: каждый раз в 2 раза больше от имеющегося.

Код


/*
   Класс "Стек".
   Объявите класс "Стек" с методами push() и pop(). Сделайте это на основе массива
 */
#include <iostream>
#include <cstdlib>
using namespace std;

class stack{
    int *st; //указатель на массив чисел
    int curr; //индекс текущего элемента
    int size; //размер массива (кол-во элементов)
public:
    stack():st(0),curr(0),size(0) {};
    ~stack(){delete []st;}
    void push(int);
    int pop();
    int count();

};
void stack::push(int x)
{
    /*выделяем или перераспределяем память*/
    if(curr == size)
    {
        if(!size)
            size += 2;
        else
          size = size *2;
        st = (int *) realloc(st,4*size); //4 байта * кол-во элементов
    }
    st[curr] = x;
    ++curr;
}
int stack::pop()
{
    if(st)
    {
        int x = st[curr-1];
        --curr;
        /*освободим память, если ее выделено в 4 раза больше,чем нужно*/
        if(curr <= size / 4)
        {
            size /= 2;
            st = (int *) realloc(st,4*size);
        }
        return x;
    }
    return 0;
}
int stack::count()
{
    return curr+1;
}


int main()
{
    stack s;
    for(int i = 0; i<20; ++i)
        s.push(i);
    for(;s.count()-1;)
        cout << s.pop() << "  ";

    return 0;
}

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

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

Дата 7.12.2010, 18:39 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

    Класс "очередь".
    Объявите класс "очередь" с методами put() и get().
    Сделайте это на основе связанного списка.

Код


/*
    Класс "очередь".
    Объявите класс "очередь" с методами put() и get().
    Сделайте это на основе связанного списка.
 */

#include <iostream>
using namespace std;

struct el{
    int value;
    el *next;
    el(){value = 0; next = 0;}
    el(const int v):value(v),next(0) {};
};

class stack{
     el *head;
     int count;
public:
     stack():head(0),count(0){};
     ~stack(); //нужно будет пройтись по списку и очистить его
     void put(const int v);
     int get();
     int get_count(){return count;}
};
stack::~stack()
{
    while(head)
    {
        el *curr = head->next;
        delete head;
        head = curr;
    }
}
void stack::put(const int v)
{
    if(!head)
        head = new el(v);
    else
    {
        el *p = new el(v);
        p->next = head;
        head = p;
    }
    ++count;
}
int stack::get()
{
    if(head) //на случай, если программист не контролирует наличие элементов в стеке
    {
        int result = head->value;
        el *p = head->next;
        delete head;
        head = p;
        --count;
        return result;
    }
    return 0;
}

int main()
{
    stack s;
    for(int i = 0; i<20; ++i)
        s.put(i);
    for(;s.get_count();)
        cout << s.get() << "  ";

    return 0;
}

все так же просто

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

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

mimik

Дата 7.12.2010, 19:00 (ссылка)

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

Загрузка ...

не Rohoss Я

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

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

Цитата(Чoо @ 7.12.2010, 18:39

)

Код


for(;s.get_count();)        
    cout << s.get() << "  ";

почему for а не while?

Дата 7.12.2010, 20:23 (ссылка)

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

Загрузка ...

Опытный

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

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

mimik, для разнообразия smile

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

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

Дата 7.12.2010, 21:36 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата

    Класс "очередь с приоритетами".
    Объявите класс "очередь с приоритетами", который наследует класс очередь.
    Каждый элемент очереди имеет приоритет - целое число. Первым обслуживается
    элемент с самым высоким приоритетом.

честно говоря, я не смог унаследовать класс el :(. Убил пару часов времени - ни как. Наверное надо было изначально проектировать приложение иначе..
но в задании говорили только о наследовании класса "очередь". Вобщем вопрос: можно было как-то унаследовать el? (единственный вариант, который вижу, это наследование, с переопределением поля next.
потом бы пришлось бы наследовать очередь с переопределением поля head, но так кажется, что этот вариант будет через одно место...

Код


/*
    Класс "очередь с приоритетами".
    Объявите класс "очередь с приоритетами", который наследует класс очередь.
    Каждый элемент очереди имеет приоритет - целое число. Первым обслуживается
    элемент с самым высоким приоритетом.
 */

#include <iostream>
using namespace std;


struct el{
    int value;
    int priority; //добавил
    el *next;
    el(){value = 0; next = 0; priority = 0;}
    el(const int v):value(v),next(0) {priority = 0;}
    el(const int v, const int prior):value(v),priority(prior) {}; //добавил
};

class stack{
protected:
     el *head;
     int count;
public:
     stack():head(0),count(0){};
     ~stack(); //нужно будет пройтись по списку и очистить его
     virtual void put(const int v);
     virtual void put(const int v, const int prior){};
     virtual int get();
     int get_count(){return count;}
};
stack::~stack()
{
    while(head)
    {
        el *curr = head->next;
        delete head;
        head = curr;
    }
}
void stack::put(const int v)
{
    if(!head)
        head = new el(v);
    else
    {
        el *p = new el(v);
        p->next = head;
        head = p;
    }
    ++count;
}
int stack::get()
{
    if(head) //на случай, если программист не контролирует наличие элементов в стеке
    {
        int result = head->value;
        el *p = head->next;
        delete head;
        head = p;
        --count;
        return result;
    }
    return 0;
}


//наследуем класс "стек"
class stack_ext:public stack{
public:
    void put(const int v, const int prior);
    // поскольку элементы упорядочены по приоритету, метод get переопределять не нужно
};
void stack_ext::put(const int v, const int prior)
{
    if(!head)
        head = new el(v,prior);
    else
    {
        /*будем упорядочивать элементы по-убыванию приоритета.
          Это позволит при взятии элементов не производить лишний поиск*/
        el *pre = 0;
        el *curr = head;
        el *p = new el(v,prior);
        while(curr && p->priority > curr->priority)
        {
            pre  = curr;
            curr = curr->next;
        }
        if(!pre)
        {
            /*добавляем в начало списка*/
            p->next = head;
            head = p;
        }
        else
        {
            /*добавляем, ориентируясь на указатель на предыдущий элемент*/
            pre->next = p;
            p->next = curr;
        }
    }
    ++count;
}

int main()
{
    stack *s;
    s = new stack();
    for(int i = 0; i<20; ++i)
        s->put(i);
    for(;s->get_count();)
        cout << s->get() << "  ";
    delete s;
    cout << endl;
    /*стек с приоритетами*/
    s = new stack_ext();
    //для демонстрации ввел вручную 4 числа с разным приоритетом
    s->put(10,5);
    s->put(11,6);
    s->put(12,0);
    s->put(13,0);

    for(;s->get_count();)
        cout << s->get() << "  ";
    delete s;

    return 0;
}

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

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

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

Дата 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, то будет.

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

Дата 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

Дата 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

Дата 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

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

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

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

Загрузка ...

Эксперт

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

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

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

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

Дата 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

Дата 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

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

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

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

Загрузка ...

Эксперт

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

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

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

)

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

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

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

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

Дата 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

Дата 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

Дата 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

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

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

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

Загрузка ...

Эксперт

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

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

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

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

Дата 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

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

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

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

Загрузка ...

Эксперт

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

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

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

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

Дата 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

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

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

Загрузка ...

Опытный

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

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

глянул. что-то вообще ни чего не понял. В функции вычитания увидел ссылку на книгу Кнута, в трех томах. Глянул что там написано. Вопщем вычитание сделано на основе алгоритма, в котором не предусмотрены операции с отрицательными значениями. Далее Кнут пишет по поводу обратного и добавочного кода, которые можно использовать при работе с отрицательными числами. Может я что-то не понял?

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

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

Дата 16.12.2010, 20:42 (ссылка)

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

Загрузка ...

Опытный

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

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

во.. сделал почти.. Пока еще с обратными кодами. Все работает, за исключением:
1. Есть положительные нули и отрицательные smile

2. в строке 169 я рассчитываю, что два раза вызовится конструктор копирования (для tmp1 и tmp2). Он так и вызвается, в отладчике если смотреть, в нем происходит копирование данных при двух вызовах. Однако содержимое tmp1 совсем не меняется, что приводит к краху программы. Что я не правильно написал?

Код


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

#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 new_size);
    void lv_inc(); //инкрементирует value

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

public:
    longvalue(){get_image("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)
{
    bool out = false; //установится как только состоится вывод хотя бы одного элемента
    if(!p.value[p.size-1])
        strm << "+";
    else
        strm << "-";
    for(int i = p.size-2; i>=0; --i)
        if((i>0 && p.value[i]) || out)
        {
            strm << p.int_to_char(p.value[i]); //дружественный функции имеют доступ к полям и методам только через объект
            out = true;
        }
        else
            if(i==0)
                strm << p.int_to_char(p.value[i]);
    return strm;
}
/*операция извлечения из потока*/
std::istream& operator >>(std::istream& strm, longvalue &p)
{
    char *result = (char*)malloc(255); //пока что так :(
    std::cin >> result;
    int size = strlen(result);
    result = (char*)realloc(result,size+1);
    result[size] = '\0'; //realloc не оконечивает выделенную память нулем
    free(p.value);
    p.get_image(result);
    return strm;
}
/*нахождение суммы*/
longvalue longvalue::operator +(const longvalue &p)
{
    longvalue tmp1 = *this, tmp2 = p; //2 слагаемых
    if(tmp1.value[tmp1.size-1])
    {
        //первое слагаемое надо дополнить до двух, предварительно обратив знаковый разряд в ноль
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
        tmp1.inverse();
    }
    if(tmp2.value[tmp2.size-1])
    {
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.inverse();
    }

    tmp1.add(tmp2);
    if(tmp1.value[tmp1.size-1])
    {
        //получили отрицательное число. Его нужно преобразовать из обратного кода в прямой
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
        tmp1.inverse();
    }
    return tmp1;
}

void longvalue::allign(longvalue &p, const int new_size)
{
    int sign = p.value[p.size-1];
    p.value = (int*)realloc(value,new_size*4);
    for(int i = p.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,p.size);
    else
        if(p.size < this->size)
            allign(p,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;

    if(carry)
    {
        //остался перенос в старший разряд. Его нужно прибавить к результату
        this->lv_inc();
    }
}
void longvalue::lv_inc()
{
    int* value_tmp = (int*)malloc(size*4);
    value_tmp[0] = 1;
    for(int i = 1; i < size; ++i)
        value_tmp[i] = 0;
    longvalue tmp(value_tmp,size);
    this->add(tmp);
}

longvalue longvalue::operator -(const longvalue &p)
{
    longvalue tmp1(p), tmp2(*this);
    if(tmp1.value[tmp1.size-1])
        tmp1.value[tmp1.size-1] = !tmp1.value[tmp1.size-1];
    else
        tmp1.inverse();

    if(tmp2.value[tmp2.size-1])
    {
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.inverse();
    }
    tmp2.add(tmp1);
    if(tmp2.value[tmp2.size-1])
    {
        //получили отрицательное число. Его нужно преобразовать из обратного кода в прямой
        tmp2.value[tmp2.size-1] = !tmp2.value[tmp2.size-1];
        tmp2.inverse();
    }
    return tmp2;
}

/*сравнивает 2 значения друг с другом*/
int longvalue::valuecmp(const longvalue &p1, const longvalue &p2) const
{
    if(p1.value[p1.size-1] && !p2.value[p2.size-1])
        return -1;
    if(!p1.value[p1.size-1] && p2.value[p2.size-1])
        return 1;

    /*так как в начале числа могут присутствовать начальные нули
      сравнения старших разрядов не достаточно*/
    int i = p1.size - 2;
    int j = p2.size -2;
    while(i>=0 && j>=0)
    {
        if(i < j)
        {
            if(p2.value[j]>0)
            {
                if(!p1.value[p1.size-1]) //положительность второго значения проверять не обязательно
                    return -1;
                else
                    return 1;
            }
            else
                --j;
        }
        else
        if(i==j)
        {
            if(p1.value[i] > p2.value[j])
            {
                if(!p1.value[p1.size-1])
                    return 1;
                else
                    return -1;
            }
            if(p1.value[i] < p2.value[j])
            {
                if(!p1.value[p1.size-1])
                    return -1;
                else
                    return 1;
            }
            --i;
            --j;
        }
        else
        if(i > j)
        {
            if(p1.value[i]>0)
            {
                if(!p1.value[p1.size-1])
                    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;
}

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;
    using std::cin;

    longvalue a;
    longvalue b;
    cout << "Введите двоичное число a>";
    cin >> a;
    cout << "Введите двоичное число b>";
    cin >> b;


    cout << "сложение:\n";
    longvalue c = a + b;
    cout << "(" << a << ")   +   ("<< b << ")   =   " << c << endl;
    cout << "вычитание:\n";
    c = a - b;
    cout << "(" << a << ")   -   ("<< b << ")   =   " << c << endl;
    cout << "сравнение:\n";
    if(a<b)
        cout << "(" << a << ")   <   ("<< b << ")" << endl;
    else
    if(a>b)
        cout << "(" << a << ")   >   ("<< b << ")" << endl;
    else
        cout << "(" << a << ")   =   ("<< b << ")" << endl;


    return 0;
}

Добавлено через 1 минуту и 36 секунд
да, умножение и деление не делал

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

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

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

Дата 16.12.2010, 23:27 (ссылка)

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

Загрузка ...

Эксперт

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

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

Чoо, вообще-то обратный код из прямого (и обратно) получается путем инвертирования всех битов и добавления единицы. Таким образом,0b11111111 == -1

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

Дата 17.12.2010, 00:18 (ссылка)

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

Загрузка ...

Опытный

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

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

bsa, обратный код получается инвертированием всех битов:
0b0000 0011 = 3
0b1111 1100 = -3

При сложении бит переноса (если он есть) добавляется к результату сложения.

Код


0b0000 0011 = 3
+
0b1111 1100 = -3
-----------------------
0b1111 1111

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

Код


0b1000 0000 = -0

Код


0b0000 0011 = 3
+
0b1111 1101 = -2
-------------------------
0b0000 0000 (остался знак переноса)
+
0b0000 0001
------------------------
0b0000 0001 = 1 (3-2 = 1);

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

Дополнительный же код получается в 2 этапа:
1. Инверсия всех бит.
2. Дополнение до двух (тот же +1)

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

а в 169 строке, что может быть не так?

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

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

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

Дата 19.12.2010, 10:57 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(Чoо @ 17.12.2010, 01:18

)

bsa, обратный код получается инвертированием всех битов:
0b0000 0011 = 3
0b1111 1100 = -3

Я не понимаю, что ты этим хотел доказать. Проверяется очень просто:
-3 + 3 == 0 - сомнений не вызывает?
0b1111 1100 + 0b0000 0011 = 0b1111 1111, а это уже код -1. Таким образом, -3 == 0b1111 1101.
Ты не путай инверсию битов и инверсию знака. Отрицательное число - это дополнительный код и есть.

Добавлено через 11 минут и 21 секунду

Цитата(Чoо @ 17.12.2010, 01:18

)

При сложении чисел в дополнительном коде мы получаем число в прямом коде, если я правильно понял..

Нет. Ты получаешь число в дополнительном коде, если не происходит переполнения:
0b1111 1101 + 0b1111 1111 = 0b1111 1100 <=> -3 + -1 = -4

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

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

Дата 19.12.2010, 16:19 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(bsa @ 19.12.2010, 10:57

)

Таким образом, -3 == 0b1111 1101.

ну.. это -3 в дополнительном коде. Так как есть дополнение до двух.
Тогда, что бы прояснить ситуацию, как будет выглядить число 3 в обратном и дополнительном коде, и как будет выглядеть число -3 (тоже в обратном и дополнительном коде).
Я так думаю, что так(по порядку как перечислял: прямой, обратный, дополнительный):
3:
0000 0011
0000 0011
0000 0011

-3:
1000 0011
1111 1100
1111 1101

тоесть я руководствовался таким представлением об обратном и дополнительном кодах. Правила сложения одинаковые, только по разному обрабатывается выход за пределы "разрядной сетки".

Добавлено через 2 минуты и 38 секунд

Цитата(bsa @ 19.12.2010, 10:57

)

Я не понимаю, что ты этим хотел доказать.

немножко ошибся smile

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

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

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

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

Дата 19.12.2010, 19:07 (ссылка)

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

Загрузка ...

Эксперт

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

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

почитай пожалуйста про двоичную арифметику.

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

Дата 19.12.2010, 20:02 (ссылка)

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

Загрузка ...

Опытный

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

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

Ну у меня в конспекте по вычислительной технике написано именно так, как я пишу.
Сейчас погуглил, по поводу обратного кода и сложения в обратном коде (не в дополнительном) и вот что нашел:
http://www.ref.by/refs/67/15151/1.html
пункт 1.4.1. Представление чисел со знаками

ну вроде я всё правильно понял, по поводу сложения..

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

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

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

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

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

Загрузка ...

Эксперт

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

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

Чoо, ладно. я понял, о чем речь. Мне и в голову не могло придти, что кто-то будет подобные теоретические изыски вдалбливать в головы новичков.
Имхо, "обратный код" вообще смысла не имеет. Лично я не вижу никакого применения для него. Дополнительный код актуален для чисел с фиксированной точностью. А вот прямой код имеет смысл применять для чисел с неограниченной точностью. Вот только знак не следует хранить в старшем бите. Посмотри на BigDigits, там для знака используется переменная, способная иметь три значения: положительно, нуль и отрицательно. Это сильно упрощает работу с числами.

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

Дата 19.12.2010, 23:24 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(bsa @ 19.12.2010, 22:35

)

Посмотри на BigDigits, там для знака используется переменная, способная иметь три значения: положительно, нуль и отрицательно. Это сильно упрощает работу с числами.

оК

.
Трудно разбираться в чужом коде, но что ж делать... попробую осилить

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

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