Обсуждение участника:KirillKutirev - История изменений

KirillKutirev: /* Пример */

2014-01-07T20:28:28Z

‎Пример

KirillKutirev: /* Пример */

2014-01-07T19:52:26Z

‎Пример

KirillKutirev: /* Пример */

2014-01-07T19:48:41Z

‎Пример

KirillKutirev: /* Пример */

2014-01-07T19:48:11Z

‎Пример

KirillKutirev в 19:28, 7 января 2014

2014-01-07T19:28:10Z

KirillKutirev: /* Реализация */

2014-01-07T19:26:39Z

‎Реализация

KirillKutirev: /* Реализация */

2014-01-07T19:18:36Z

‎Реализация

KirillKutirev: /* Реализация */

2014-01-07T19:18:00Z

‎Реализация

KirillKutirev: /* Реализация */

2014-01-07T19:16:34Z

‎Реализация

KirillKutirev: /* Реализация */

2014-01-07T08:11:28Z

‎Реализация

@@ Строка 44: / Строка 44: @@
 | Массив 1 || used || used || used || used || 5
 |-
-| Массив 2 || delete || delete || 6 || <tex>\infty</tex> || <tex>\infty</tex>
+| Массив 2 || deleted || deleted || 6 || <tex>\infty</tex> || <tex>\infty</tex>
 |}
@@ Строка 51: / Строка 51: @@
 | Массив 1 || used || used || used || used || used
 |-
-| Массив 2 || delete || delete || delete || 11 || <tex>\infty</tex>
+| Массив 2 || deleted || deleted || deleted || 11 || <tex>\infty</tex>
 |}

@@ Строка 16: / Строка 16: @@
 ==Пример==
-Для примера возьмем строку "абракадабра"
+Для примера возьмем строку "абракадабра".
 {| class="wikitable"
@@ Строка 26: / Строка 26: @@
 |}
-На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив
+На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
 {| class="wikitable"
 | Массив 1 || used || used || 2 || 2 || 5

@@ Строка 32: / Строка 32: @@
 | Массив 2 || 2 || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex> || <tex>\infty</tex>
 |}
 На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).

← Предыдущая		Версия 19:48, 7 января 2014
Строка 16:		Строка 16:

	==Пример==		==Пример==
		+	Для примера возьмем строку "абракадабра"
		+
		+	{\| class="wikitable"
		+	! Буква \|\| д \|\| к \|\| б \|\| р \|\| а
		+	\|-
		+	\| Массив 1 \|\| 1 \|\| 1 \|\| 2 \|\| 2 \|\| 5
		+	\|-
		+	\| Массив 2 \|\| <tex>\infty</tex> \|\| <tex>\infty</tex> \|\| <tex>\infty</tex> \|\| <tex>\infty</tex> \|\| <tex>\infty</tex>
		+	\|}
		+
		+	На первом шаге два минимальных элемента - это первые две ячейки первого массива. Их сумму сохраняем во второй массив
		+	{\| class="wikitable"
		+	\| Массив 1 \|\| used \|\| used \|\| 2 \|\| 2 \|\| 5
		+	\|-
		+	\| Массив 2 \|\| 2 \|\| <tex>\infty</tex> \|\| <tex>\infty</tex> \|\| <tex>\infty</tex> \|\| <tex>\infty</tex>
		+	\|}
		+	В первом массиве остались неиспользованным только 3 ячейки.
		+
		+	На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
		+	{\| class="wikitable"
		+	\| Массив 1 \|\| used \|\| used \|\| used \|\| used \|\| 5
		+	\|-
		+	\| Массив 2 \|\| 2 \|\| 4 \|\| <tex>\infty</tex> \|\| <tex>\infty</tex> \|\| <tex>\infty</tex>
		+	\|}
		+
		+	На третьем шаге два минимальных элемента - это первые две ячейки второго массива.
		+	{\| class="wikitable"
		+	\| Массив 1 \|\| used \|\| used \|\| used \|\| used \|\| 5
		+	\|-
		+	\| Массив 2 \|\| delete \|\| delete \|\| 6 \|\| <tex>\infty</tex> \|\| <tex>\infty</tex>
		+	\|}
		+
		+	На четвертом шаге складываются две оставшиеся ячейки.
		+	{\| class="wikitable"
		+	\| Массив 1 \|\| used \|\| used \|\| used \|\| used \|\| used
		+	\|-
		+	\| Массив 2 \|\| delete \|\| delete \|\| delete \|\| 11 \|\| <tex>\infty</tex>
		+	\|}

	==Реализация==		==Реализация==

← Предыдущая		Версия 19:28, 7 января 2014
Строка 14:		Строка 14:

	На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.		На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно <tex>n</tex> итераций.
		+
		+	==Пример==

	==Реализация==		==Реализация==

@@ Строка 18: / Строка 18: @@
 Поскольку мы не ограничены по памяти, очень удобно использовать вместо двух одномерных массивов один двумерный. Это избавит код от громоздких "if".
    n // количество элементов
    s1 = 0, s2 = 1 // указатели на строки, которые выполняют функции первого и второго массивов в описании алгоритма
    h1 = 0, h2 = 0 // указатели на первый элемент первой строки и второй строки соответственно
    t1 = n, t2 = 0 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
    check = 0 // считает на сколько стало меньше элементов
-  temp // переменная, на которую ссылаются самые нижние листья дерева
    class vert{ // класс - лист дерева, которое, по сути, строится в коде хаффмана
    public:
@@ Строка 38: / Строка 36: @@
    };
    make(int str1, int str2, int pos1, int pos2)// функция, которая суммирует, задает указатели и значения переменных val и left
      sum[s2][t2].w = sum[str1][pos1].w + sum[str2][pos2].w

@@ Строка 76: / Строка 76: @@
        s2++
        h2 = t2 = 0
-  return sum[s1][h1] // возвращает вершину дерева, получить код каждого символа можно получить за logn
+    return sum[s1][h1] // возвращает вершину дерева, получить код каждого символа можно получить за logn

@@ Строка 23: / Строка 23: @@
    t1 = n, t2 = 0 // указатели на ячейки массивов сразу после последнего элемента в этих массивах
    check = 0 // считает на сколько стало меньше элементов
-   // ... чтение данных
+   temp // переменная, на которую ссылаются самые нижние листья дерева
-   '''while''' check < n
+  class vert{ // класс - лист дерева, которое, по сути, строится в коде хаффмана
-     '''while''' h1 < t1 // проходим по массиву, выполняющему роль первого; внутри этого цикла мы ищем минимумы и записываем суммы
+   public:
-       '''if''' h2 == t2
+    val // значение кодового символа {0,1}
-         sum[s2][t2] = sum[s1][h1] + sum[s1][h1+1]
+    w // сумма в данном поддереве
-         '''if''' t1 - h1 == 1
+    left // самый левый элемент начального массива в данном поддереве, чтобы упростить поиск при спуске
-           sum[s2][t2] = sum[s2][t2] - sum[s1][h1+1]
+    check // проверка на то, является ли данный лист самым нижним в дереве
-         h1 = h1 + 2
+     *nextl, *nextr // указатели на левого и правого детей
-         t2++
+    vert(){
-       '''else'''
+      check = 1;
-         '''if''' sum[s1][h1] < sum[s2][h2]
+      val = 0;
-           '''if''' sum[s1][h1+1] < sum[s2][h2]
-             sum[s2][t2] = sum[s1][h1] + sum[s1][h1+1]
+  };
-             h1 += 2
             '''else'''
-             sum[s2][t2] = sum[s1][h1] + sum[s2][h2]
+               '''if''' sum[s1][h1].w < sum[s2][h2+1].w
-             h1++
+                 make(s2,s1,h2,h1)
-             h2++
+                 h1++
-           t2++
+                 h2++
-         '''else'''
+               '''else'''
-           '''if''' sum[s1][h1] < sum[s2][h2+1]
+                 make(s2,s2,h2,h2+1)
-             sum[s2][t2] = sum[s2][h2] + sum[s1][h1]
+                 h2+=2
-             h1++
+               t2++
-             h2++
+           check++ // учитываем то, что элементов стало на 1 меньше
-           '''else'''
+      s1 = s2 // строки меняются ролями, соответственно все их параметры тоже
-             sum[s2][t2] = sum[s2][h2] + sum[s2][h2+1]
+      h1 = h2
-             h2+=2
+      t1 = t2
-           t2++
+      s2++
-      check++ // учитываем то, что элементов стало на 1 меньше
+      h2 = t2 = 0
-    s1 = s2 // строки меняются ролями, соответственно все их параметры тоже
+  return sum[s1][h1] // возвращает вершину дерева