IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Переборные задачи
сообщение
Сообщение #1


Гость






Здравствуйте!
Кто-нибудь объясните как происходит перебор вариянтов в след. задаче: есть кучка камне(20) нужно раскидать их на две кучки наиболее близкого веса. Может кто подскажет, Алгоритм как это делать.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Новичок
*

Группа: Пользователи
Сообщений: 49
Пол: Мужской

Репутация: -  0  +


1. Создаешь. Два массива по 10 эл. И массив с 20-ю камнями.
2. Вводишь с клавы, или присваеваешь значение каждому камню.
3. Сортируешь массив с камнями...
4. Первые 10 эл. массива с камнями присваеваешь одноу из массиво с 10-эл. Другие 10 - другой половине...
Это мой вариант...


--------------------
На самом деле самого дела нет. В самой деятельности заключена самость дела и наоборот. Наоборот получим оборот на, таким образом перевернем образ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Женский

Репутация: -  0  +


хм.. по моему тогда они не будут равными.. если отсортировать камни и присвоить 1-ые 10 1-ому массиву а 2-ые 10 2-ому..


--------------------
непонимающая..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Четыре квадратика
****

Группа: Пользователи
Сообщений: 579
Пол: Мужской

Репутация: -  4  +


Каждый камень можно положить или в первую кучку, или во вторую (третьего не дано). Тогда заведем такой массив А(его еще называют характеристический вектор):
A[i]=0, если i-й камень в 1-й кучке,
A[i]=1, если i-й камень во 2-й кучке.

Осталось только построить все возможные такие векторы, и посмотреть, в каком случае разница будет минимальной.

Пример всех массивов для трех камней:
Код

0 0 0 (все камни в 1-й кучке)
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1 (все камни во 2-й кучке)

Кстати, можно заметить, что это - двоичные представления чисел от нуля до 2^3 - 1= 8. То есть чтобы сгенерировать такие массивы, можно брать числа от 0 до 2^20 - 1 (то есть до 1 048 575) и раскладывать в двоичную систему счисления

Варианты с сортировками ИМХО не проходят. Я так уже обломался один раз (можно даже вспомнить топик в этом разделе, там такая же задача примерно была)


--------------------
Закон добровольного труда Зимерги:
Люди всегда согласны сделать работу, когда необходимость в этом уже отпала
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 22.11.2017 0:41
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"