Тема: Задача на складання алгоритму !!!

Є матриця розміру n x n, є n людей, якщо елемент матриці (i, j) = 1 ((i, j) == (j, i)), то людина i знай з людиною j, чи можна розділити людей на 2 групи так, щоб в кожній з них були тільки незнайомі люди. Написати алгоритм розвязку.

Також буду дуже радий за ваші варіанти де можна  знайти вирішення цієї задачі)))

2

Re: Задача на складання алгоритму !!!

!!! Іди в дупу)))

Подякували: petroandrushchak, leofun012

3

Re: Задача на складання алгоритму !!!

petroandrushchak написав:

Є матриця розміру n x n, є n людей, якщо елемент матриці (i, j) = 1 ((i, j) == (j, i)), то людина i знай з людиною j, чи можна розділити людей на 2 групи так, щоб в кожній з них були тільки незнайомі люди. Написати алгоритм розвязку.

Також буду дуже радий за ваші варіанти де можна  знайти вирішення цієї задачі)))

Краще скинь оригінал завдання.

Junior Django Developer
Подякували: petroandrushchak1

4

Re: Задача на складання алгоритму !!!

Перебором можна, хоч і довго доволі
k = 0
1) береш людину k
2) умовно ділиш всіх інших на дві групи: ті кого людина знає і кого ні
3) перевіряєш кожного з першої групи на факт знайомства з "одногрупниками", якщо є знайомсвто - крок 6.
4) так само перевіряєш другу групу, є знайомство - крок 6.
5) все вийшло, перша умовна група = перша група, друга умовна + людина k = друга група.
6) k = k + 1
7) якщо k = n не можна поділити, вихід 
   інакше перехід на 1)

Maybe a = Just a | Nothing

5

Re: Задача на складання алгоритму !!!

Перебираєш всі можливі варіанти однієї компанії, і дивишся знайомі вони чи ні. Тут є якраз алгоритм: http://ukrbukva.net/print:page,1,4708-G … ektov.html

6 Востаннє редагувалося Regen (18.09.2014 10:33:26)

Re: Задача на складання алгоритму !!!

Singularity написав:

!!! Іди в дупу)))

ахаха, красава)

Don’t do as I have done
Win where I have lost
Have where I have none