Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача на логику
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Tenshi
В парламенте острова Невезения каждый из N = 6 депутатов имеет не более М = 2 врагов. ( Если А - враг Б, то Б - враг А). Для уменьшения разногласий президент решил преобразовать парламент в двухпалатный.
Составить программу, которая проверяет, можно ли парламент разделить на две палаты так, что быу каждого депутата в своей палате было не более М врагов.
Michael_Rybak
ну и что теперь? я тоже много задач знаю. в том числе и на логику.
Tenshi
Хотел спросить совета как мне ее решить. Можно и по вежливей общаться
trew
теорию вероятности выучи тогда и помощи не надо будет просить blink.gif
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


Если у кого-нибудь есть время и желание помочь.
З.з.з.ы А как это через циклы сделать йа что-то не пойму?
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 врагов на рыло, если два, то они спокойно могут сосуществовать smile.gif
Я исправил итог, там вроде правильно

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

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


Они ведь ненавидят друг друга.
Tenshi
Стоп, ты не так понял.
У каждого из депутатов в своей палате может быть не более 2 врагов.
У 1 в палате два врага и у остальных по два. Вот в чем суть
klem4
если у первого враг - третий, это означает автоматически что у третьего враг - первый, верно ?
Tenshi
Цитата(klem4 @ 22.05.2008 16:22) *

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

Именно так smile.gif
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
Мое огромнейшее спасибо good.gif
Tenshi
Код
is_enemy[a, b]


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

///Ой туплю...сорри вопрос исчерпан =)
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.


Посмотрите пожалуйста где касяки и как вывести результат. Код не работает (В основном конечно из-за прямоты рук >_<)
Michael_Rybak
я предполагал, что 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
переработанный код, но фсе равно не рабочий =(
 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
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
Всем Спасибо.
За курсовую получил максимум, хоть и решение было неверное, препод поставил за логику good.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.