Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 2006.06.04;
Скачать: [xml.tar.bz2];

Вниз

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

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


 
Strate ©   (2006-04-28 23:57) [7]

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

A=1
B=001
C=0011

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

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


 
Cash ©   (2006-04-29 18:14) [8]

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

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


 
comtat ©   (2006-04-29 23:40) [9]

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

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

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



Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2006.06.04;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.46 MB
Время: 0.044 c
15-1147122323
alex-drob
2006-05-09 01:05
2006.06.04
Интернет по MAC


6-1138952697
SiJack
2006-02-03 10:44
2006.06.04
господа зашиваюсь с MAPI помогите


15-1147085436
BAngel
2006-05-08 14:50
2006.06.04
Скачать делфи


2-1147855804
NewBit
2006-05-17 12:50
2006.06.04
Свойство компонентов


15-1147414464
Ламот
2006-05-12 10:14
2006.06.04
Диспетчер сервера терминалов отображает не всех пользователей





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский