Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Задача на логику

Автор: Tenshi 22.05.2008 13:21

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

Автор: Michael_Rybak 22.05.2008 16:05

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

Автор: Tenshi 22.05.2008 17:04

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

Автор: trew 22.05.2008 17:16

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

Автор: Michael_Rybak 22.05.2008 17:40

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

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

Добавлено через 1 мин.
Цитата
теорию вероятности выучи тогда и помощи не надо будет просить

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



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

Автор: Tenshi 22.05.2008 17:55

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

Код
У первого враг 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


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

Автор: klem4 22.05.2008 18:05

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


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

Автор: Tenshi 22.05.2008 18:11

Второго заносим в другую палату, соответственно в первой палате он уже не является врагом. Однако, если во второй палате находятся 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 22.05.2008 18:26

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

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


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

Автор: Tenshi 22.05.2008 18:33

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

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

Автор: klem4 22.05.2008 18:58

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

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


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

Автор: Tenshi 22.05.2008 19:13

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

Автор: klem4 22.05.2008 19:22

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

Автор: Tenshi 22.05.2008 19:31

Цитата(klem4 @ 22.05.2008 16:22) *

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

Именно так smile.gif

Автор: Michael_Rybak 22.05.2008 19:34

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

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

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

смотри. у тебя шесть человек. каждый будет либо в палате 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 22.05.2008 19:39

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

Автор: Tenshi 22.05.2008 20:36

Код
is_enemy[a, b]


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

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

Автор: Michael_Rybak 22.05.2008 22:09

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

Автор: Tenshi 23.05.2008 1:52

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

Автор: Tenshi 23.05.2008 3:05

Код
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.


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

Автор: Michael_Rybak 23.05.2008 6:25

я предполагал, что is_enemy[] - двумерный массив 6х6, такой, что is_enemy[x, y] = true тогда и только тогда, когда депутаты номер х и у - враги.

фрагмент реального кода для депутата с будет выглядеть так:

               if (c = a) and (is_enemy[3,1]) the inc(c_enemies);
               if (c = b) and (is_enemy[3,2]) the inc(c_enemies);
               if (c = d) and (is_enemy[3,4]) the inc(c_enemies);
               if (c = e) and (is_enemy[3,5]) the inc(c_enemies);
               if (c = f) and (is_enemy[3,6]) the inc(c_enemies);


а вот в этом месте нужно вывести результат:

if f_enemies > m then continue;
//вот здесь
end;


вывод результата будет такой: выводишь 6 строк вида "депутата Х помещаем в палату У".

Автор: Tenshi 23.05.2008 11:02

переработанный код, но фсе равно не рабочий =(

 program omg;

var
  is_enemy:array [1..6,1..6] of integer;
  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[1,2]) the inc(a_enemies);
	  if (a = c) and (is_enemy[1,3]) the inc(a_enemies);
	  if (a = d) and (is_enemy[1,4]) the inc(a_enemies);
	  if (a = e) and (is_enemy[1,5]) the inc(a_enemies);
	  if (a = f) and (is_enemy[1,6]) the inc(a_enemies);
	  if a_enemies > m then continue;
		   b_enemies:=0;
		   if (b = a) and (is_enemy[2,1]) the inc(b_enemies);
		   if (b = c) and (is_enemy[2,3]) the inc(b_enemies);
		   if (b = d) and (is_enemy[2,4]) the inc(b_enemies);
		   if (b = e) and (is_enemy[2,5]) the inc(b_enemies);
		   if (b = f) and (is_enemy[2,6]) the inc(b_enemies);
		   if b_enemies > m then continue;
			   c_enemies:=0;
			   if (c = a) and (is_enemy[3,1]) the inc(c_enemies);
			   if (c = b) and (is_enemy[3,2]) the inc(c_enemies);
			   if (c = d) and (is_enemy[3,4]) the inc(c_enemies);
			   if (c = e) and (is_enemy[3,5]) the inc(c_enemies);
			   if (c = f) and (is_enemy[3,6]) the inc(c_enemies);
			   if c_enemies > m then continue;
					c_enemies:=0;
					if (d = a) and (is_enemy[4,1]) the inc(d_enemies);
					if (d = b) and (is_enemy[4,2]) the inc(d_enemies);
					if (d = c) and (is_enemy[4,3]) the inc(d_enemies);
					if (d = e) and (is_enemy[4,5]) the inc(d_enemies);
					if (d = f) and (is_enemy[4,6]) the inc(d_enemies);
					if d_enemies > m then continue;
						 e_enemies:=0;
						 if (e = a) and (is_enemy[5,1]) the inc(e_enemies);
						 if (e = b) and (is_enemy[5,2]) the inc(e_enemies);
						 if (e = c) and (is_enemy[5,3]) the inc(e_enemies);
						 if (e = d) and (is_enemy[5,4]) the inc(e_enemies);
						 if (e = f) and (is_enemy[5,6]) the inc(e_enemies);
						 if e_enemies > m then continue;
							 f_enemies:=0;
							 if (f = a) and (is_enemy[6,1]) the inc(f_enemies);
							 if (f = b) and (is_enemy[6,2]) the inc(f_enemies);
							 if (f = c) and (is_enemy[6,3]) the inc(f_enemies);
							 if (f = e) and (is_enemy[6,5]) the inc(f_enemies);
							 if (f = d) and (is_enemy[6,4]) the inc(f_enemies);
							 if f_enemies > m then continue;
					if a_enemies>m then writeln ('Pomeshaem deputata A v palatu 2');
					if b_enemies>m then writeln ('Pomeshaem deputata B v palatu 2');
					if c_enemies>m then writeln ('Pomeshaem deputata C v palatu 2');
					if d_enemies>m then writeln ('Pomeshaem deputata D v palatu 2');
					if e_enemies>m then writeln ('Pomeshaem deputata E v palatu 2');
					if f_enemies>m then writeln ('Pomeshaem deputata F v palatu 2')
					end;
begin
   Writeln ('Kolichestvo vragov m: ',m);
   Readln (m);
   Sortirovka;
   Writeln ('The end');
end.

Автор: klem4 23.05.2008 14:59

const
  n = 6;
type
  TEnemies = set of byte;
  TRelationship = array [1..n] of TEnemies;

function Intersect(const i, j, k: byte; const
 iSet, jSet, kSet: TEnemies): boolean;
begin
  Intersect := (i in jSet + kSet) or (j in iSet + kSet) or (k in iSet + jSet);
end;

var
  r: TRelationship = (
    ([]),     // враги первого (пусто в данном случае)
    ([4]),    // враги второго
    ([4, 5]), // 3
    ([3, 2]), // 4
    ([3]),    // 5
    ([])      // 6
  );

  i, j, k, l, id: byte;
  idx: array [1..3] of byte;

begin
  for i := 1 to n - 2 do
   for j := i + 1 to n - 1 do
    for k := j + 1 to n do
     if not Intersect(i, j, k, r[i], r[j], r[k]) then begin
       id := 0;
       for l := 1 to n do
        if (l <> i) and (l <> j) and (l <> k) then begin
          inc(id); idx[id] := l;
        end;
        if not Intersect(idx[1], idx[2], idx[3], r[idx[1]], r[idx[2]], r[idx[3]]) then
         writeln('Group A: (', i, ',', j, ',', k,
               ') Group B: (', idx[1], ',', idx[2], ',', idx[3], ')');
     end;
end.

Автор: Tenshi 23.05.2008 15:13

Всем Спасибо.
За курсовую получил максимум, хоть и решение было неверное, препод поставил за логику good.gif