VPF::Двоичная куча, задача про колокола

Dev1L

Дата 13.1.2008, 13:31 (ссылка)

(голосов:1)

Загрузка ...

Новичок

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

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

Вот такая задачка:

Как известно, очереди с приоритетами часто используются для моделирования последовательности событий, которые должны происходить в разные моменты времени. Реализуйте очередь с приоритетами на основе пирамиды (двоичной кучи) и на её основе решите следующую задачу.
Дано N колоколов, которые управляются некоторым механизмом. Колокол с номером i в первый раз ударит в момент ti и затем будет ударять через каждые ti секунд. Требуется определить, какой из колоколов ударит K-м по счету (или какие колокола, если ударят несколько одновременно).
Ограничения: N до 1000, K до 1000000. Указание к решению. Каждый элемент очереди будет содержать два поля – приоритет и номер колокола (поэтому удобно создать соответствующий тип данных с помощью struct). В роли приоритета будет выступать время, когда следует нанести очередной удар.

Код


#include<stdio.h>
#include<stdlib.h>
typedef struct {
 // int value;
    int  key;
} ITEM;

class HEAP {
public:
    ITEM *h;
    int  size;
    
    HEAP(unsigned int n) {
       size = 0;
       h = (ITEM*) malloc( sizeof(ITEM) * n);
    }
    
    ~HEAP() {
        if(h) free(h);
    }

    int add(ITEM x) {
       h[++size]=x;
       checkup(size);
       return 1;
    }

    int extract_min(ITEM *x) {
      if(size ==0) return 0;
      *x = h[1];
      h[1] = h[size--];
      checkdown(1);
      return 1;
    }

private:  
    void checkup(int c) {
        int p;
        p = c / 2;
        if( p == 0 )return;
        if(h[p].key > h[c].key) {
           ITEM tmp;
           tmp = h[p]; h[p] = h[c]; h[c] = tmp;
           checkup(p);
        }
    }
    
    void checkdown(int p) {
        int c;
        c = 2*p;
        if( c > size ) return;
        if( c+1 <= size && h[c + 1].key < h[c].key ) c++;

        if( h[c].key < h[p].key ) {
          ITEM tmp;
          tmp =  h[c]; h[c] = h[p]; h[p] = tmp;
          checkdown(c);
       }
    }
};

int main() {
    HEAP heap(1000);
    int n, i;
    ITEM x;

    scanf("%d", &n);

    for(i = 0; i < n; i++){
       scanf("%d", &x.key);
       heap.add(x);
    }

    while( heap.extract_min(&x) ) {
       printf("%d ", x.key);
    }

    return 0;
}

формирует двоичную кучу

Вопрос: Как связать с задачей?

Заранее спасибо

Dev1L

Дата 15.1.2008, 14:44 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Код


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

typedef struct {
    int value;
    int  key;
} ITEM;

class HEAP {           //   создаем класс heap (двоичная куча)
public:
    ITEM *h;
    int  size;

    HEAP(unsigned int n) {
       size = 0;
       h = (ITEM*) malloc( sizeof(ITEM) * n);  //выделение памяти
    }

    ~HEAP() {
        if(h) free(h);
    }

    int add(ITEM x) {   //  добавляем новый элемент в конец кучи
       h[++size]=x;     //размер кучи +1 , т.к
                        // число шагов всплытия меньше чем высота дерева
       checkup(size);   // смотрим на родителя и проверяем свойство кучи
       return 1;
    }

    int extract_min(ITEM *x) {   // извлечение минимального элемента
      if(size ==0) return 0;     // если размер кучи равен 0 выход
      *x = h[1];                // отложим вершину кучи в сторону,
                                //чтобы в конце вернуть ее в качестве результата
      h[1] = h[size--];         // самый последний элемент в вершину кучи
      checkdown(1);             // "топим" его
      return 1;
    }
private:
    void checkup(int c) {          //    проверка сверху
        int p;                     // p-ключ родителя с-ключ ребенка
        p = c / 2;
        if( p == 0 )return;
                                   // сравниваем ключ ребенка с ключем родителя
        if(h[p].key > h[c].key) {  // если ключ родителя больше ключа ребенка
           ITEM tmp;
           tmp = h[p]; h[p] = h[c]; h[c] = tmp; //меняем их местами
           checkup(p);              // проверка сверху для нового родителя
        }
    }
    
    void checkdown(int p) {         //  проверка снизу
        int c;                      // p-ключ родителя с-ключ ребенка
        c = 2*p;
        if( c > size ) return;

        if( c+1 <= size && h[c + 1].key < h[c].key ) c++;
        if( h[c].key < h[p].key ) { // если ключ ребенка меньше ключа родителя
          ITEM tmp;
          tmp =  h[c]; h[c] = h[p]; h[p] = tmp; //меняем их местами
          checkdown(c);   // проверка снизу для нового ребенка
       }
    }
};

int main() {
    HEAP heap(1000);
    int n, i, k, j, z;
    ITEM x;

    scanf("%d", &n);                 // ввод количества колоколов
    scanf("%d", &k);                 // счет

    for(i = 0; i < n; i++){          // ввод элементов с приоритетами

       scanf("%d", &x.value);        // номер колокола
       scanf("%d", &x.key);          // его время
       heap.add(x);                  // добавляем элемент
    }
    for(i = 0; i < k; i++){
    while( heap.extract_min(&x) ) {  // извлекаем минимальный элемент
       j=x.value;                    // смотрим номер этого колокола
       x.value=x.value+x.key;        // прибавляем к приоритету этого элемента
       }                             // временной промежуток того колокола
    }
     printf("%d ", j);               // выводим результат
    return 0;
}

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