Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Математика
        Комбинаторика и множества
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Математика" «

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ]
Модераторы: Roman Osipov, RKI, attention, paradise
  

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

Эта тема закрыта, новые ответы не принимаются

Переход к теме
<< Назад Вперед >>
Несколько страниц [ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ]

Форум работает на скрипте © Ikonboard.com