Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: алгоритм перестановок  (Прочитано 6579 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 11-09-2009 16:13 » 

алгоритм перестановок

в 256 значной системе счисления дано число состоящее из 2-50 пар цифр, нужно выдать число состоящее из тех же самых цифр, такое что сумма цифр первой половины равна сумме цифр второй половины или указать, что подобного числа не существует

пример:

1234 = 4123 или 1432

{100}234 = imposible

каким алгоритмом можно решить?
Записан

1n c0de we trust
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #1 : 11-09-2009 17:23 » 

Можно попробовать построением дерева Хаффмана, например. В любом случае, жадным алгоритмом.
Записан
Mayor
Специалист

ru
Offline Offline

« Ответ #2 : 11-09-2009 17:33 » 

Можно попробовать построением дерева Хаффмана, например. В любом случае, жадным алгоритмом.

ну то, что жадный это понятно - тк достаточно одного варианта и перебор 100! комбинаций не приемлим по времени выполнения, хотя можно наверное свести задачу к альфа бетта отсечению

я раньше видел хафмана только в компрессии данных

допустим мы получим частоту встречаемости цифр в строке и сможем легко по ним перемещатся ... что нам это даст?
Записан

1n c0de we trust
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #3 : 11-09-2009 17:45 » 

Ты не понял. Частота не нужна. Нужны только веса, которые есть значения "цифр".
Если так будет проще, то твоя задача почти сводится к задаче типа размена монет. Только в виде монет - твои "цифры", а в виде суммы - 1/2 суммы всех "цифр", плюс требование обязательно потратить 1/2 всех монет.
В случае дерева смысл в том, чтобы построить максимально сбалансированное. Не поручусь, что способ Хаффмана - то, что надо. Тут, наверное, лучше строить "от корня", балансируя веса в пределах допустимого общего веса.
« Последнее редактирование: 11-09-2009 17:49 от Вад » Записан
Mayor
Специалист

ru
Offline Offline

« Ответ #4 : 12-09-2009 04:09 » 

дак если нужна сбалансированность, то можно просто отсортировать все цифры, четные кинуть в 1 список не четные в другой:

тогда мы полочим отклонение их сумм не более чем 256

почитал задачу о размене:

по сути нам нужно найти минимальное количество перестановок, чья сумма будет одно из чисел в пределах -+256 - это может напроч завесить алгоритм
« Последнее редактирование: 12-09-2009 04:18 от Mayor » Записан

1n c0de we trust
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines