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

Чoо

Дата 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

Чoо

Дата 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

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

Чoо

Дата 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

Чoо

Дата 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

bsa

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

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

Загрузка ...

Эксперт

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

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

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

)

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

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

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

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

baldina

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

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

Загрузка ...

Эксперт

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

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

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

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

Чoо

Дата 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

Чoо

Дата 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

Чoо

Дата 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

Чoо

Дата 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

bsa

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

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

Загрузка ...

Эксперт

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

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

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

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

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

Чoо

Дата 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

bsa

Дата 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 в 31 степени - 1.(Соответственно, они помещаются в переменные типа int)

В программах, где это необходимо, следует использовать условный оператор if и оператор цикла while. Другие операторы цикла(for, repeat, do - while), а также другие операторы break, continue, exit, goto использовать не следует.

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

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

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

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

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

9. Даны 4 числа. Если они все различны, выведите "yes", иначе - "no".

10. Определите количество дней в данном году (от 1600 до 3000 года н.э.) по современному календарю

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

12. Даны размеры сторон конверта и открытки. Определите можно ли положить открытку в конверт не сгибая. (Стороны открытки должны быть параллельны сторонам конверта).

13. В первой строке указаны дата рождения Алисы, а во второй - Боба. Даты указаны в формате "год месяц день". Определите кто из низх старше(выведите имя: "Alice" или "Bob").

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

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

16*.Крестики - нолики. Вася и Петя любят играть в крестики - нолики 3х3, но у них неожиданно закончилась бумага. Помогите им - напишите программу, которая позволит им ставить крестики и нолики на экране монитора.

Вроде бы все! Скоро будет продолжение!!!

В этом году поступил в универ, на первом курсе учим С++, вот решил посмотреть что у вас тут за инструктажи и попал на задачки... В общей сложности С++, не сказал бы что учил, но пытался, 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

Спасибо!)

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