Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Массив [D7, WinXP]

Archy © (2006-04-28 22:29:00)
как сделать чтоб упорядоченный массив разбить на 2 части с примерно равными суммами значений?
тока чтоб эллементы не перемешивались.

comtat (2006-04-29 23:40:00) [1]
Это известная задача теории расписания и называется
она "задача о разбиении". Она Np- трудна т.е. нет даже полиномиально разрешимого алгоритма.
Но зато сводится к задаче оптимизации в теории расписаний.
Если найдется решение то такое разбиение существует, иначе разбит незя.

Могу написать алгоритм...

Незряж я сеня ходил на эту долбанную лекцию по теории расписания

Cash (2006-04-29 18:14:00) [2]
Archy (28.04.06 23:46) [5]:
Необходимо создавать "непрефиксный код".
Хаффман и Шеннон-Фано с этим хорошо справляются.
Как сказал Strate [6], чтение производить побитово, и подбирать кодовое
слово по этому считанному префиксу. (удобнее всего для этого
использовать дерево кодовых комбинаций как у Хаффмана)
А в случае с префиксным кодом можно из ситуации вылезти с помощью
гамма- и омега- шифрования.

Вот мой любимый линк для развития:
http://algolist.manual.ru

Strate (2006-04-28 23:57:00) [3]
Только нужно постараться, чтобы не было вот такого:

A=1
B=001
C=0011

Тогда невозможно будет правильно интерпретировать строку 00110011

Толи "CC", толи "BAC", то ли "BABA"...

Strate (2006-04-28 23:55:00) [4]
Archy (28.04.06 23:46) [5]

Я так понял, что

a=000001
b=10
c=001
d=11

это алфавит?

Ну, наверное так:

Читаем первый элемент. В вашем случае 1.
Смотрим: подходят пока что только b и d.
Читаем второй. Получилось 11Это уже подходит только под D.
Выяснили, что первая "буква" - D. Отбрасываем её из 1100100000110, остаётся только 00100000110Ну, и так далее.

Терзают смутные сомнения, что это всё можно сделать с помощью операторов AND, OR, NOT, XORи.т.п, тока я не знаю как.

Archy (2006-04-28 23:46:00) [5]
во спасибо!!!! помог!!!!
а вот ещё вопрос:
закончил с кодир-ем, получил, к примеру,
a=000001
b=10
c=001
d=11

как потом будет можно расшифровать сообщение типа:
1100100000110
если все 0 и 1 написанц слитно

Джо (2006-04-28 23:37:00) [6]
> [3] Archy (28.04.06 22:58)
> я тебя немножко не понял, тут же полюбому сумма будет больше
> в 2 раза

Я просто по-спешки описку сделал. Сравнивать, конечно, не с общей суммой, а с ее половиной.
Т.е, имеем массив:
1 2 4 6 9 12 20
Сумма его елементов: 54. Получаем полусумму: 27.
Проходим его еще раз, последовательно подсчититывая сумму:
1 3 7 13 22 34 54
Видно, что на 5-м элементе сумма 22 (меньше полусуммы), а на 6-м уже 34 (больше полусуммы). Следовательно, примерная "середина" или на 5 или 6-м элементе. Выбирай, разница от полусуммы на котором меньше.

Archy (2006-04-28 22:58:00) [7]

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

я тебя немножко не понял, тут же полюбому сумма будет больше в 2 раза

Джо (2006-04-28 22:49:00) [8]
Если правильно понял, то (1) проходим по всему массиву один раз, вычисляя сумму элементов. Затем опять проходим его с начала, суммируя и сравнивая сумму с уже известной общей. Останавливаемся и возвращаемся к пред. результату, если сумма превышена. В таком роде.

Archy (2006-04-28 22:32:00) [9]
НАПР:сумма 2-х первых ел-ов примерно равнялась сумме 3-го 4-го 5-го эл.
(если в массиве 5 эл-ов)

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »