Guest
Новичок
|
   
вот такая задача:
Есть машина. В ней 7 мест, включая водительское. Есть 7 человек, которые поедут. Сколько существует вариантов распределения по местам, если права на вождение есть только у трех.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 14 дек. 2005 12:28 | IP
|
|
Guest
Новичок
|
ИСПРАВЛЯЮСЬ(С УЧЕТОМ ВСЕХ ЗАМЕЧАНИЙ ПИШУ СЛЕДУЩЕЕ)!!!!
Люди, проверьте пожалуйста , все ли я правильно понял!!!
Я не знаю точно что значит O/P, я думаю что это значит что из множества O отбрасываются все элементы множества P, просто мы обозначали вычитание O\P обратной чертой, возможно это принципиально.
А задача такая: проверить истинность данного равенства для множеств A B C:
(A пересечь с (не В))/((не А) U С)=(не А) пересечь(B U C)
У МЕНЯ ПОЛУЧИЛОСЬ(с учетом X/Y=X-Y) что не выполняется!!!
логика простая: тк вычитается(слева от =) не А объединенное с
С, то элементы из не А точно не попадут, а справа(от=) пересечение не А с Объединеием В и С, т.е. справа могут быть
элементы лишь из не А, что противоречит левой части....Я ПРАВ???????????????
ПОМОГИТЕ ПОЖАЛУЙСТА!!!!!!
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 28 янв. 2006 21:25 | IP
|
|
Genrih
Удален
|
Ох и намудрили ...
А логика верна. Еще очевидней становится, если правую часть расписать как (не(A) П В) U (не(A) П C) , где П - сечение
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 28 янв. 2006 21:51 | IP
|
|
Guest
Новичок
|
Помогите с задачей: есть набор положительных целых чисел. Надо составить алгоритм разбиения этих чисел на две группы с равной суммой или доказать что при данном наборе чисел такое разбиение невозмжно
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 9 фев. 2006 10:44 | IP
|
|
Guest
Новичок
|
Цитата: Guest написал 9 фев. 2006 10:44
Помогите с задачей: есть набор положительных целых чисел. Надо составить алгоритм разбиения этих чисел на две группы с равной суммой или доказать что при данном наборе чисел такое разбиение невозмжно
Это NP-полная задача.
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 10 фев. 2006 0:31 | IP
|
|
Guest
Новичок
|
легче не стало....
|
Всего сообщений: Нет | Присоединился: Never | Отправлено: 10 фев. 2006 2:07 | IP
|
|
MrD
Удален
|
Додумывать до конца сейчас некогда, но общая схема такова:
Прежде всего проверить является ли сумма всех чисел (обохначим - S) четным числом. Если нет - понятно.
Если да:
- сортируем набор;
- переносим элементы из текущего набора (M1) в новый набор (M2) по одному начиная с меньших до тех пор, пока сумма чисел в M2 не станет >= S/2;
- если сумма чисел в M2 = S/2 - понятно;
- возвращаем элементы из M2 в M1 по одному начиная с меньших до тех пор, пока сумма чисел в M2 не станет <= S/2;
- ...
Надо прикинуть условие выхода из процесса в случае возврата M1 и M2 в одно из предыдущих состояний (значит разбиение невозможно) и обосновать правильность алгоритма.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 10 фев. 2006 18:03 | IP
|
|
MrD
Удален
|
Был не прав, поторопился. Этот алгоритм не во всех случаях работает. Будет время - додумаю.
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 10 фев. 2006 22:13 | IP
|
|
miss_graffiti
Долгожитель
|
  
Класс NP – класс задач, которые можно решить за полиномиальное время только на недетерминированной Машине Тьюринга: в отличии от обычной МТ может делать предположения. Это задачи у которых есть ответ, найти который трудно, но проверить можно за полиномиальное время.
Класс NP-полных задач – класс задач, не менее сложных, чем любая NP задача. Т.е. решив такие задачи за полиномиальное время можно доказать (P = NP). К этому классу относится задача выполнимости - Задано логическое выражение. Существует ли набор правильных значений, на которых данное выражение будет истиной?(Пока не доказано.)
(с)http://se.math.spbu.ru/Courses/Crypto/2001%5COkomin.html
это так... для общей осведомленности.
|
Всего сообщений: 670 | Присоединился: сентябрь 2005 | Отправлено: 10 фев. 2006 23:04 | IP
|
|
user72
Удален
|
Помогите с задачей!:
Имеются цифры 1,2,3,4,5,6,7,8,9 из них составляются шестизначные числа, причем цифры не повторяются. Сколько будет составлено чисел содержащих 1,2,3? Понятно что Из 9ти цифр можно составить А(9,6) = 9 • 8 • 7 • 6 • 5 • 4 = 60480 шестизначных чисел, но что дальше?
|
Всего сообщений: N/A | Присоединился: N/A | Отправлено: 11 фев. 2006 10:06 | IP
|
|
|
Форум
Комбинаторика и множества
