Добрый день и с праздником!
Задачка родилась из практики, но для "Алгоритмов", наверное, не очень подходит.
В Windows есть такая штука, как ImageList (IL) — хранилище для картинок одинакового размера в виде одного большого (длинного) изображения. Одна из "замечательных" особенностей IL — если к нему добавить новую картинку, то (внутри) происходит следующее:
— создаётся копия внутреннего изображения с дополнительным "местом" для новой картинки,
— в это дополнительное место вставляется добавляемое изображение,
— старое изображение удаляется.
IL способен также добавлять изображения из другого IL. Алгорит его действий такой-же, только место выделяется сразу для всех добавляемых картинок.
Если в IL последовательно добавлять картиноки, то общее время работы растет (приблизительно) в арифметической прогрессии.
Попробуем уменьшить трудозатраты добавления картинок. Будем считать, что трудозатраты добавления к списку из N1 картинок другого списка из N2 картинок — пропорциональны N1 + N2. Сами картинки пусть загружаются извне, и затраты на их загрузку учитывать не будем (как общие для всех возможных алгоритмов).
Для начала, примем что составление списка из двух картинок требует 2 единицы времени:
(1) (1) |трудозатраты
\ / |
2 | = 2
Тогда, при последовательной загрузке 4-х изображений "тупым" способом, потребуется 9 единиц времени:
(1) (1) |трудозатраты
\ / |
2 (1) | = 2
\ / |
3 (1) | = 2 + 3
\ / |
4 | = 2 + 3 + 4 = 9
Если мы предварительно разобъем на две группы по две картинки, то получим:
(1)(1) (1)(1) |трудозатраты
\ / \ / |
2 2 | = 4
\ / |
\ / |
4 | = 4 + 4 = 8
А теперь вопросы (уже, наверное, понятно какие
)
— Составить оптимальный алгоритмы загрузки для произвольного N
— оценить трудозатраты для этого оптимального алгоритма.
Евгений
Здравствуйте, mrhru, Вы писали:
M>Добрый день и с праздником!
[skipped]
M>Если мы предварительно разобъем на две группы по две картинки, то получим:
M>M>(1)(1) (1)(1) |трудозатраты
M> \ / \ / |
M> 2 2 | = 4
M> \ / |
M> \ / |
M> 4 | = 4 + 4 = 8
M>
M>А теперь вопросы (уже, наверное, понятно какие )
M> — Составить оптимальный алгоритмы загрузки для произвольного N
M> — оценить трудозатраты для этого оптимального алгоритма.
Чего-то мне кажется, что оптимальный алгоритм — это двоичное дерево и затраты — 2^(N-1).
WBR, Serg Matskov.
... << RSDN@Home 1.0 beta 6a >>
Здравствуйте, mSerg, Вы писали:
...
M>>А теперь вопросы (уже, наверное, понятно какие )
M>> — Составить оптимальный алгоритмы загрузки для произвольного N
M>> — оценить трудозатраты для этого оптимального алгоритма.
S>Чего-то мне кажется, что оптимальный алгоритм — это двоичное дерево и затраты — 2^(N-1).
Это можно проверить на примере, для N = 8
Двоичное дерево:
(1)(1) (1)(1) (1)(1) (1)(1) |трудозатраты
\ / \ / \ / \ / |
2 2 2 2 | = 2 + 2 + 2 + 2 = 8
\ / \ / |
\ / \ / |
4 4 | = 4 + 4 = 8
\ / |
8 | = 8
итого | = 8 + 8 + 8 = 24
(Обозначим затраты через [])
Комбинируем по другому (с учётом того, что [1] + [1] + [1] = [2] + [1] = [3]
(1)(1)(1) (1)(1)(1) (1)(1) |трудозатраты
\ / / \ / / \ / |
3 3 2 | = 3 + 3 + 2 = 8
\ / / |
6 / | = 3 + 3 = 6
\ / |
8 | = 8
итого | = 8 + 6 + 8 = 22 !
А вот ещё быстрее:
(1)(1)(1) (1)(1)(1) (1)(1) |трудозатраты
\ / / \ / / \ / |
3 3 2 | = 3 + 3 + 2 = 8
\ \ / |
\ 5 | = 3 + 2 = 5
\ / |
8 | = 8
итого | = 8 + 5 + 8 = 21 !!!
Так что ...
Евгений
Здравствуйте, mrhru, Вы писали:
[skipped]
M>Так что ...
А если все за один шаг:
(1)(1)(1)(1)(1)(1)(1)(1) |трудозатраты
\ \ \ \ / / / / |
\ \ \ \/ / / / |
\ \ \ | / / / |
\ \ \ |/ / / |
\ \ \|/ / / |
\ \ | / / |
\ \ |/ / |
\ \| / |
\ | / |
\ |/ |
\| |
8 итого | = 8
Тогда ни одна картинка не будет загружаться 2 раза.
WBR, Serg Matskov.
... << RSDN@Home 1.0 beta 6a >>
Здравствуйте, mrhru, Вы писали:
M>...
Чорт! ((с) А.П.Чехов)
Извиняюсь, напутал.
Для двоичного дерева так и остаётся
Двоичное дерево:
(1)(1) (1)(1) (1)(1) (1)(1) |трудозатраты
\ / \ / \ / \ / |
2 2 2 2 | = 2 + 2 + 2 + 2 = 8
\ / \ / |
\ / \ / |
4 4 | = 4 + 4 = 8
\ / |
8 | = 4 + 4 = 8
итого| = 8 + 8 = 24
(Обозначим затраты через [])
Комбинируем по другому (с учётом того, что для слияния трёх картинок надо — [1] + [1] + [1] = [2] + [2] + [1] = [5])
(1)(1)(1) (1)(1)(1) (1)(1) |трудозатраты
\ / / \ / / \ / |
3[5] 3[5] 2 | = 5 + 5 + 2 = 10
\ / / |
6 / | = 3 + 3 = 6
\ / |
8 | = 6 + 2 = 8
итого| = 10 + 6 + 8 = 24
Т.е. — не двоичное, но те же результаты
А вот быстрее:
(1)(1)(1) (1)(1)(1) (1)(1) |трудозатраты
\ / / \ / / \ / |
3[5] 3[5] 2 | = 5 + 5 + 2 = 10
\ \ / |
\ 5 | = 3 + 2 = 5
\ / |
8 | = 3 + 5 = 8
итого| = 10 + 5 + 8 = 23 !!!
Евгений
Здравствуйте, mSerg, Вы писали:
S>Здравствуйте, mrhru, Вы писали:
S>[skipped]
M>>Так что ...
S>А если все за один шаг:
S>S>(1)(1)(1)(1)(1)(1)(1)(1) |трудозатраты
S> \ \ \ \ / / / / |
S> \ \ \ \/ / / / |
S> \ \ \ | / / / |
S> \ \ \ |/ / / |
S> \ \ \|/ / / |
S> \ \ | / / |
S> \ \ |/ / |
S> \ \| / |
S> \ | / |
S> \ |/ |
S> \| |
S> 8 итого | = 8
S>
S>Тогда ни одна картинка не будет загружаться 2 раза.
S>WBR, Serg Matskov.
Sorry, я чегой-то туплю с утра. Наверное не выспался
WBR, Serg Matskov.
... << RSDN@Home 1.0 beta 6a >>
Здравствуйте, mSerg, Вы писали:
....
S>Sorry, я чегой-то туплю с утра. Наверное не выспался
Совершенно аналогично
Евгений
Здравствуйте, mrhru, Вы писали:
M>M>(1)(1)(1) (1)(1)(1) (1)(1) |трудозатраты
M> \ / / \ / / \ / |
M> 3[5] 3[5] 2 | = 5 + 5 + 2 = 10
M>Т.е. - не двоичное, но те же результаты
[/code]
M>[ccode]
M>(1)(1)(1) (1)(1)(1) (1)(1) |трудозатраты
M> \ / / \ / / \ / |
M> 3[5] 3[5] 2 | = 5 + 5 + 2 = 10
M>
Может я чего не понял, но 5 + 5 + 2 = 12
Здравствуйте, Kluge, Вы писали:
...
K>Может я чего не понял, но 5 + 5 + 2 = 12
Мдя.
Лучше всего завтра и на свежую голову.
Евгений
Здравствуйте, mrhru, Вы писали:
M>Лучше всего завтра и на свежую голову.
Оставь голову в покое
