Массив

← →
Archy (2006-04-28 22:29) [0]

как сделать чтоб упорядоченный массив разбить на 2 части с примерно равными суммами значений?
тока чтоб эллементы не перемешивались.

← →
Archy (2006-04-28 22:32) [1]

НАПР:сумма 2-х первых ел-ов примерно равнялась сумме 3-го 4-го 5-го эл.
(если в массиве 5 эл-ов)

← →
Джо © (2006-04-28 22:49) [2]

Если правильно понял, то (1) проходим по всему массиву один раз, вычисляя сумму элементов. Затем опять проходим его с начала, суммируя и сравнивая сумму с уже известной общей. Останавливаемся и возвращаемся к пред. результату, если сумма превышена. В таком роде.

← →
Archy (2006-04-28 22:58) [3]

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

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

← →
Джо © (2006-04-28 23:37) [4]

> [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 23:46) [5]

во спасибо!!!! помог!!!!
а вот ещё вопрос:
закончил с кодир-ем, получил, к примеру,
a=000001
b=10
c=001
d=11

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

← →
Strate © (2006-04-28 23:55) [6]

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 и.т.п, тока я не знаю как.

Только нужно постараться, чтобы не было вот такого:

A=1
B=001
C=0011

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

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

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

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

Это известная задача теории расписания и называется
она "задача о разбиении". Она Np- трудна т.е. нет даже полиномиально разрешимого алгоритма.
Но зато сводится к задаче оптимизации в теории расписаний.
Если найдется решение то такое разбиение существует, иначе разбит незя.

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

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

Массив Найти похожие ветки