- Публикации Andrew
Публикации Andrew
12 публикаций создано Andrew (учитываются публикации только с 12-мая 23)
По типу контента
По пользователю
#263 Очередь
Отправлено от Andrew в 14 ноября 2012 - 15:42 in Структуры данных
#260 Двоичная куча
Отправлено от Andrew в 14 ноября 2012 - 11:07 in Структуры данных
Насчёт тырилки. С википедии наверно можно, я не написал что этл мой текст , а цитировал. Во всяком случае википедия объяснит лучше меня, на раз ты просиш, то к пятнице перепишу и это.
#258 Двоичная куча
Отправлено от Andrew в 10 ноября 2012 - 19:29 in Структуры данных
Куча - структура данных, дерево, элементы которых удовлетворяют некоторым условиям. Существует много разных типов куч, но самой распространённой является двоичная или бинарная куча. Все её элементы должны выполнять два условия:
- Предок больше либо равен потомку в max-куче и меньше либо равен потомку в min-куче.
- У всех предков два потомка, но только у одного предка в куче может быть один потомок-лист
Индекс первого потомка = индекс элемента * 2
Индекс второго потомка (если есть) = индекс элемента * 2 + 1
Класс кучи:
// Перечесление типов кучи enum heapType { MaxHeap, MinHeap }; template <class type> class heap { public: // Конструктор heap(heapType ht = MaxHeap) { length = 0; heapT = ht; } // Перегрузка оператора type& operator[](int index) { return data[index]; } // Всплытие элемента под номером. Возвращает новый номер этого же элемента int shiftUp(int index) { while (index > 1 && data[index / 2] < data[index] && heapT == MaxHeap || index > 1 && data[index / 2] > data[index] && heapT == MinHeap) { swap(data[index], data[index / 2]); index = index / 2; } return index; } // Потопление элемента под номером. Возвращает новый номер этого же элемента int shiftDown(int index) { bool finish = false; while (2 * index <= length && !finish) { int temp = index; if (data[2 * index] > data[temp] && heapT == MaxHeap || data[2 * index] < data[temp] && heapT == MinHeap) temp = 2 * index; if (2 * index + 1 <= length && (data[2 * index + 1] > data[temp] && heapT == MaxHeap || data[2 * index + 1] < data[temp] && heapT == MinHeap)) temp = 2 * index + 1; if (index == temp) finish = true; else swap(data[index], data[temp]); index = temp; } return index; } // Преобразование массива в кучу void build() { for (int i = length / 2; i > 0; i--) shiftDown(i); } // Сортирует кучу по неубыванию void sort() { build(); int t = length; while (length > 1) { swap(data[1], data[length]); length--; shiftDown(1); } length = t; } // Добовляет к этой куче кучу heap void concat(heap heap) { for (int i = 1; i <= heap.length; i++) add(heap[i]); } // Добовление value в кучу. Возвращает новый номер этого же элемента int add(int value) { length++; data[length] = value; return shiftUp(length); } // Удаляет элемент под номером index из кучи int remove(int index) { data[index] = data[1] + 1; shiftUp(index); data[1] = data[length]; length--; if (length) return shiftDown(1); return 0; } // Возвращает первый элемент и удаляет его type first() { if (length) { type temp = data[1]; remove(1); return temp; } else return 0; } // Ставит элемент под номером index на своё место. Возвращает новый номер этого же элемента int test(int index) { int f = shiftUp(index); if (f != index) return f; return shiftDown(index); } // Массив кучи type data[100000]; // Длина кучи int length; // Тип кучи heapType heapT; };
В скором времени напишу и на паскале.
Пример программы:
Увеличение приоритета №1164 на informatics.mccme.ru
Формат входных данных: см. выше.
Формат выходных данных: в качестве ответа на запрос требуется вывести одно число: сообщить, на каком месте массива оказался изменённый элемент. Кроме того, после выполнения всех запросов требуется вывести кучу в её конечном состоянии.
http://informatics.m...hapterid=1164#1
#include <iostream> using namespace std; //ЗДЕСЬ КЛАСС КУЧИ int main() { heap<int> heap; int n; cin >> n; for (int i = 1; i <= n; i++) { int t; cin >> t; heap.add(t); } cin >> n; for (int i = 1; i <= n; i++) { int a, b; cin >> a >> b; heap[a] += b; cout << heap.test(a) << "\n"; } for (int i = 1; i <= heap.length; i++) cout << heap[i] << " "; system("pause > nul"); return 0; }
#96 Размещение в подпрограмме
Отправлено от Andrew в 17 января 2012 - 19:39 in Комбинаторика
#94 Размещение
Отправлено от Andrew в 17 января 2012 - 18:23 in Комбинаторика
LVP (23 декабря 2011 - 12:37) писал:
http://lvp37.ru/inde...BC%D0%BC%D0%B5/
#93 Размещение в подпрограмме
Отправлено от Andrew в 17 января 2012 - 18:18 in Комбинаторика
Размещение обозначается буквой A
Формула размещения
А= n! / ( n-m )!
Теперь устная задача
Задача
Найти сколько вариантов из 3-х букв a b c можно составить 2-х буквенных слов.
Попробуем на бумаге:
(1 перестановка ) a b (3 перестановка ) a c (5 перестановка ) b c
(2 перестановка ) b c (4 перестановка ) c a (6 перестановка ) c b
Получается 6 вариантов.
Теперь проверим нашу формулу
А=3!/(3-2)1=6/1=6
Значит формула правильная.
Ответ: 6 вариантов.
Алгоритм
Тут нам понадобится совместить алгоритм сочетания и алгоритм перестановки .
В алгоритме сочетания ( смотри ниже).
1. Пересохраняем массив p в q.
2. Делаем перестановку из m элементов на ходящихся в массиве q.
3.Теперь меняем элементы с помощью сочетания.
//----------------------------------------------------------------------------------// // Название: GeneralDeployment // // Автор кода(именно кода): Andrew (Krasnobaev) // // Сайт: redcode.do.am (временно пуст) // // Описание: Размещение, занесённое в запись, в качестве метода(классов то тут нет) // //----------------------------------------------------------------------------------// type ArrType = array[0..65536] of byte; DepType = array[0..10000] of ArrType; Comb_Class = record procedure IntGeneralDeployment(ArrLength, DepLength: longint; Arr: ArrType; var DepArr: DepType; var DepCount: LongInt); var p, q: array [0..10000] of byte; i, j, k, d: longint; begin DepCount := 0; for i := 1 to ArrLength do p[i] := i; repeat for i := 0 to DepLength do q[i] := p[i]; while q[0] = 0 do begin while q[0] = 0 do begin inc(DepCount); for i := 1 to DepLength do DepArr[DepCount][i] := Arr[q[i]]; j := DepLength; while q[j - 1] > q[j] do dec(j); k := DepLength; while q[j - 1] > q[k] do dec(k); d := q[j - 1]; q[j - 1] := q[k]; q[k] := d; for i := j to (DepLength + j - 1) div 2 do begin d := q[DepLength + j - i]; q[DepLength + j - i] := q[i]; q[i] := d; end; end; end; j := DepLength; while (j > 0) and (p[j] = j + ArrLength - DepLength) do dec(j); if j > 0 then begin p[j] := p[j] + 1; for i := j + 1 to DepLength do p[i] := p[i - 1] + 1; end; until j = 0; end; end; var Combinatorics: Comb_Class; ArrLength: 0..65536; DepLength, DepCount, i, j: LongInt; Arr: ArrType; DepArr: DepType; begin //Ввод и настройка параметров writeln('Entering:'); read( ArrLength, DepLength ); for i:=1 to ArrLength do read(Arr[i]); //Само размещение Combinatorics.IntGeneralDeployment( ArrLength, DepLength, Arr, DepArr, DepCount ); //Вывод writeln; writeln('Result:'); for i:=1 to DepCount do begin write('Deployment №',i,' is ( '); for j:=1 to DepLength do write(DepArr[i][j],' '); writeln(' );'); end; writeln('There are ',DepCount,' Deployments'); writeln('Press <Enter> to finish :'); readln; end.
#91 Размещение
Отправлено от Andrew в 16 января 2012 - 19:53 in Комбинаторика
#70 Сочетание
Отправлено от Andrew в 12 января 2012 - 06:25 in Комбинаторика
#15 Размещение
Отправлено от Andrew в 22 декабря 2011 - 08:33 in Комбинаторика
- → Публикации Andrew