сколькими способами можно распределить 12 комнат под 12 учебных кабинетов

2

Ответы и объяснения

2013-12-16T16:58:49+00:00
Одним способом на один учебный кабинет одна комната и всё
2013-12-16T16:59:06+00:00
Пусть имеем некоторое множество и систему его подмножеств. Требуется найти минимальное количество подмножеств, покрывающих исходное множество. Задачу можно представить с помощью двудольного графа: к первой доле относятся элементы первого множества, ко второму - подмножества (одно подмножество - одна вершина). Вершины первой и второй долей соединяются ребром, если множество вершины второй доли содержит элемент вершины первого множества. Требуется удалить как можно больше вершин из второй доли с инцидентными ей ребрами, но чтобы каждой вершине первой доли осталось хотя бы одно инцидентное ребро. 
Пусть, например, исходное множество содержит 12 элементов {1,2,...12}, а система подмножеств следующая: {2, 3}, {4, 8, 10}, {1, 6}, {6, 9}, {2, 11}, {5, 7}, {4, 5, 12}, {8, 11}, {3, 9}, {11}. Тогда в алгебраической форме (на NP-языке) эта задача выглядит следующим образом 
Project Cover2 
Module Main2 
Var x1 As Boolean 
Var x2 As Boolean 
Var x3 As Boolean 
Var x4 As Boolean 
Var x5 As Boolean 
Var x6 As Boolean 
Var x7 As Boolean 
Var x8 As Boolean 
Var x9 As Boolean 
Var x10 As Boolean 
Var x11 As Boolean 
Var x12 As Boolean 

Con c1 As x2+x3>=1 
Con c2 As x4+x8+x10>=1 
Con c3 As x1+x6>=1 
Con c4 As x6+x9>=1 
Con c5 As x2+x11>=1 
Con c6 As x5+x7>=1 
Con c7 As x4+x5+x12>=1 
Con c8 As x8+x11>=1 
Con c9 As x3+x9>=1 
Con c10 As x11>=1 

Con e1 As 
Minimize(x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12) 
или
12*12= 144 варианта...

спасибо,но я это тоже в интернете видела)не совсем то))
Ну тогда тут один вариант,1 способ......как то так