В парламенте острова Невезения каждый из N = 6 депутатов имеет не более М = 2 врагов. ( Если А - враг Б, то Б - враг А). Для уменьшения разногласий президент решил преобразовать парламент в двухпалатный. Составить программу, которая проверяет, можно ли парламент разделить на две палаты так, что быу каждого депутата в своей палате было не более М врагов.
Michael_Rybak
22.05.2008 16:05
ну и что теперь? я тоже много задач знаю. в том числе и на логику.
Tenshi
22.05.2008 17:04
Хотел спросить совета как мне ее решить. Можно и по вежливей общаться
trew
22.05.2008 17:16
теорию вероятности выучи тогда и помощи не надо будет просить
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 врагов на рыло, если два, то они спокойно могут сосуществовать Я исправил итог, там вроде правильно
Добавлено через 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)
если у первого враг - третий, это означает автоматически что у третьего враг - первый, верно ?
Именно так
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
Мое огромнейшее спасибо
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
Всем Спасибо. За курсовую получил максимум, хоть и решение было неверное, препод поставил за логику
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.