Задача на логику Опции

[Tenshi]

В парламенте острова Невезения каждый из N = 6 депутатов имеет не более М = 2 врагов. ( Если А - враг Б, то Б - враг А). Для уменьшения разногласий президент решил преобразовать парламент в двухпалатный.
Составить программу, которая проверяет, можно ли парламент разделить на две палаты так, что быу каждого депутата в своей палате было не более М врагов.

[Michael_Rybak]

ну и что теперь? я тоже много задач знаю. в том числе и на логику.

[Tenshi]

Хотел спросить совета как мне ее решить. Можно и по вежливей общаться

[trew]

теорию вероятности выучи тогда и помощи не надо будет просить

[Michael_Rybak]

Хотел спросить совета как мне ее решить. Можно и по вежливей общаться

можно, конечно можно! давай повежливее, только давай начнем с тебя, ок? твой первый пост написан в приказном тоне. перечитай.

Добавлено через 1 мин.

теорию вероятности выучи тогда и помощи не надо будет просить

М

Флудить не нужно

Добавлено через 3 мин.
Tenshi, по теме: с помощью шести вложенных циклов перебираешь все возможные разделения парламента на 2 палаты, и для каждого из них проверяешь нужное тебе условие. что из этого вызывает затруднения?

[Tenshi]

Писал с компа в универе. Успел написать тока условие быстро.
З.ы. Теорию вероятности не знаю, ибо такого не учил.
З.з.ы. Вызывает затруднение как сравнивать этих самых депутатов.
Вот алгоритм моих действий:

Код

У первого враг 2 и 3
У второго - 3,4 и 1 (по условию Если А - враг Б, то Б - враг А) => заносим второго в другую палату.
У третьего враг 4 и 5
У четвертого враг 5,6 и 3 (по тому же условию) => заносим в другую палату
У пятого враг 6 и 1
У шестого враг 1,2 и 5 (...) => заносим в другую палату


Итого получилось:

В первой палате осталось:
у 1 враг 3 и 5
у 3 враг 5
у 5 враг 1 и 3

Во второй палате:
у 2 враг 4
у 4 враг 2 и 6
у 6 враг 4

Если у кого-нибудь есть время и желание помочь.
З.з.з.ы А как это через циклы сделать йа что-то не пойму?

Сообщение отредактировано: Tenshi - 22.05.2008 14:01

[klem4]

У второго - 3,4 и 1 (по условию Если А - враг Б, то Б - враг А) => заносим второго в другую палату.
У третьего враг 4 и 5

Если у второго во врагах третий, то у третьего помимо 4 и 5 должно быть 2.
И далее такие же ошибки в примере.

[Tenshi]

Второго заносим в другую палату, соответственно в первой палате он уже не является врагом. Однако, если во второй палате находятся 2 и 4 (а по условию на картинке и, следуя из (Если А - враг Б, то Б - враг А) они враги.
Отсюда и такой итог

В первой палате осталось:
у 1 враг 3 и 5
у 3 враг 5
у 5 враг 1 и 3

Во второй палате:
у 2 враг 4
у 4 враг 2 и 6
у 6 враг 4

Добавлено через 11 мин.
Единственно может где я ошибся это в итоговом количестве

Исправлено:

Код

В первой палате:
у 1 враг 3 и 5
у 3 враг 5 и 1
у 5 враг 1 и 3
Во второй палате:
у 2 враг 4 и 6
у 4 враг 2 и 6
у 6 враг 2 и 4

[klem4]

Таак. Смотри:

у 1 враг 3 и 5
у 3 враг 5

Если у 1 есть враг 3, это означает что у 3 есть враг 1, верно ? Значит 1 и 3 в одной палате быть никак не могут.

[Tenshi]

Не более 2 врагов на рыло, если два, то они спокойно могут сосуществовать
Я исправил итог, там вроде правильно

Добавлено через 7 мин.
С условием вроде разобрались, а как написать прогу?
Завтра сдавать курсовую, преподаватель вроде сам невоткнул как ее писать и подсказать не смог =(
Буду рад хотя бы части кода например как сравнить первого, второго и третьего, а дальше думаю аналогичным способом писать. Идей нет совершенно поэтому и спрашиваю =)

Сообщение отредактировано: Tenshi - 22.05.2008 14:45

[klem4]

Опять не верно, первый с третьим не могут быть в одной палате,

у 1 враг 3 и 5
у 3 враг 5 и 1

Они ведь ненавидят друг друга.

[Tenshi]

Стоп, ты не так понял.
У каждого из депутатов в своей палате может быть не более 2 врагов.
У 1 в палате два врага и у остальных по два. Вот в чем суть

[klem4]

если у первого враг - третий, это означает автоматически что у третьего враг - первый, верно ?

[Tenshi]

если у первого враг - третий, это означает автоматически что у третьего враг - первый, верно ?

Именно так

[Michael_Rybak]

З.ы. Теорию вероятности не знаю, ибо такого не учил.

в этой задаче она не понадобится.

З.з.з.ы А как это через циклы сделать йа что-то не пойму?

смотри. у тебя шесть человек. каждый будет либо в палате 1, либо в палате 2. шестью вложенными циклами перебираем, кто в какой палате:

for a := 1 to 2 do // номер палаты, в которую попал депутат A
  for b := 1 to 2 do // номер палаты, в которую попал депутат B
    for с := 1 to 2 do 
      for d := 1 to 2 do 
        for e := 1 to 2 do 
          for f := 1 to 2 do begin

            //проверяем, не нарушается ли условие для депутата А

            a_enemies := 0; // считаем количество врагов А в его палате

            //a и b попали в одну палату и при этом враждуют?
            if (a = b) and (is_enemy[a, b]) the inc(a_enemies); 

            //a и с попали в одну палату и при этом враждуют?
            if (a = с) and (is_enemy[a, с]) the inc(a_enemies); 

            ... // то же для d, e, f

            if a_enemies > m then break; //условие не выполнилось

            //проверяем точно так же для депутата В
            b_enemies := 0;     
            ...

            //проверяем точно так же для депутатов С, D, E, F

            // если ни один break не сработал, решение найдено, выводим его
          end;

[Tenshi]

Мое огромнейшее спасибо

[Tenshi]

Код

is_enemy[a, b]

Непонятно как они задаются и какого типа?

///Ой туплю...сорри вопрос исчерпан =)

Сообщение отредактировано: Tenshi - 22.05.2008 16:53

[Michael_Rybak]

ой. только я ошибся - там не break а continue везде: нам нужно продолжать цикл для следующего значения f, а не прерывать его.

[Tenshi]

А как будет вывод найденного решения выглядеть?

[Tenshi]

Код

program omg;
type
   enemy= set of 'a'..'f';
var
  is_enemy:enemy;
  a,b,c,d,e,f,m:integer;
  a_enemies: integer;
  b_enemies: integer;
  c_enemies: integer;
  d_enemies: integer;
  e_enemies: integer;
  f_enemies: integer;
procedure sortirovka;
begin
  for a:=1 to 2 do
  for b:=1 to 2 do
  for c:=1 to 2 do
  for d:=1 to 2 do
  for e:=1 to 2 do
  for f:=1 to 2 do begin
      a_enemies:=0;
      if (a = b) and (is_enemy[a,b]) the inc(a_enemies);
      if (a = c) and (is_enemy[a,c]) the inc(a_enemies);
      if (a = d) and (is_enemy[a,d]) the inc(a_enemies);
      if (a = e) and (is_enemy[a,e]) the inc(a_enemies);
      if (a = f) and (is_enemy[a,f]) the inc(a_enemies);
      if a_enemies > m then continue;
           b_enemies:=0;
           if (b = a) and (is_enemy[b,a]) the inc(b_enemies);
           if (b = c) and (is_enemy[b,c]) the inc(b_enemies);
           if (b = d) and (is_enemy[b,d]) the inc(b_enemies);
           if (b = e) and (is_enemy[b,e]) the inc(b_enemies);
           if (b = f) and (is_enemy[b,f]) the inc(b_enemies);
           if b_enemies > m then continue;
               c_enemies:=0;
               if (c = a) and (is_enemy[c,a]) the inc(c_enemies);
               if (c = b) and (is_enemy[c,b]) the inc(c_enemies);
               if (c = d) and (is_enemy[c,d]) the inc(c_enemies);
               if (c = e) and (is_enemy[c,e]) the inc(c_enemies);
               if (c = f) and (is_enemy[c,f]) the inc(c_enemies);
               if c_enemies > m then continue;
                    c_enemies:=0;
                    if (d = a) and (is_enemy[d,a]) the inc(d_enemies);
                    if (d = b) and (is_enemy[d,b]) the inc(d_enemies);
                    if (d = c) and (is_enemy[d,c]) the inc(d_enemies);
                    if (d = e) and (is_enemy[d,e]) the inc(d_enemies);
                    if (d = f) and (is_enemy[d,f]) the inc(d_enemies);
                    if d_enemies > m then continue;
                         e_enemies:=0;
                         if (e = a) and (is_enemy[e,a]) the inc(e_enemies);
                         if (e = b) and (is_enemy[e,b]) the inc(e_enemies);
                         if (e = c) and (is_enemy[e,c]) the inc(e_enemies);
                         if (e = d) and (is_enemy[e,d]) the inc(e_enemies);
                         if (e = f) and (is_enemy[e,f]) the inc(e_enemies);
                         if e_enemies > m then continue;
                             f_enemies:=0;
                             if (f = a) and (is_enemy[f,a]) the inc(f_enemies);
                             if (f = b) and (is_enemy[f,b]) the inc(f_enemies);
                             if (f = c) and (is_enemy[f,c]) the inc(f_enemies);
                             if (f = e) and (is_enemy[f,e]) the inc(f_enemies);
                             if (f = d) and (is_enemy[f,d]) the inc(f_enemies);
                             if f_enemies > m then continue;
                             end;
begin
   Writeln ('Kolichestvo vragov m: ',m);
   Readln (m);
   Sortirovka;

end.

Посмотрите пожалуйста где касяки и как вывести результат. Код не работает (В основном конечно из-за прямоты рук >_<)