IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> задача про домино, поиск наибольшей замыкающейся последовательности
сообщение
Сообщение #1


Гость






Здравствуйте.
Поставили перед нами такую задачe. Дано n кубиков домино, как известно они имеют номера с двух сторон, но в задаче сказано, что для данного случая они не ограничены цифрой 6, т.е. значения с обеих сторон могут быть боле 6, например 16 и 12 и т.п. (какие - то разумные пределы конечно есть, но просто больше чем в настоящих, т.е. чем 6). Задние состоит в том, чтобы найти самую длинную замкнутую цепочку.... Если честно теряюсь в догадках и по вопросу алгоритма и по вопросу реализации....
Надеюсь на Вашу помощь.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

При этом, если граф изначально несвязный, рассматриваем каждую компоненту связности отдельно.

EDIT: удалил неправильные мысли

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Ну, поскольку ты не написал, на каком языке тебе нужно решение - вот так программа выглядит на Паскале (если костяшек больше 28, измени MAX)...
{$M $C000,0,650000}
const
max = 28;
yes : boolean = false;

max_num = 20; { <--- Максимальное число на костяшке домино !!! }

var
m :array [0..max_num,0..max_num] of boolean;
n :byte;
cep,best :array [1..max*2] of byte;
p,maxlen :integer;

procedure ReadData;
var i,a,b : byte;
begin
p:=1; maxlen:=0;
assign(input,'dm.txt'); reset(input);
fillchar(cep,sizeof(cep),0);
fillchar(m,sizeof(m),false);
readln(n);
for i:=1 to n do begin
readln(a,b);
m[a,b]:=true; m[b,a]:=true;
end;
close(input);
end;

procedure WriteResults;
var i : integer;
begin
writeln(maxlen div 2);
if (maxlen>1) then begin
i:=1;
while (i<pred(maxlen)) do begin
write(' <', best[i], ' ', best[i+1],'> :');
inc(i,2);
end;
write(' <', best[pred(maxlen)], ' ', best[maxlen], '>');
end;
writeln;
end;

procedure s_cep;
begin
if (p-1>maxlen) then begin
move(cep,best,p-1);
maxlen:=p-1;
yes:=(maxlen div 2=n);
end;
end;

function exist(k:integer):boolean;
var i : integer;
begin
i:=0; while (i<=max_num) and not(m[k,i]) do inc(i);
exist:=(i<=max_num);
end;

procedure make_cep(f:integer);
var s:integer;
begin
if yes then exit;
if (m[f,f]) then begin
m[f,f]:=false;
cep[p]:=f; cep[succ(p)]:=f; inc(p,2);
if exist(f) then make_cep(f) else s_cep;
dec(p,2);
m[f,f]:=true;
end else
for s:=0 to max_num do
if (m[f,s]) then begin
m[f,s]:=false; m[s,f]:=false;
cep[p]:=f; cep[succ(p)]:=s; inc(p,2);
if exist(s) then make_cep(s) else s_cep;
dec(p,2);
m[f,s]:=true; m[s,f]:=true;
end;
end;

var i:integer;
begin
ReadData;
for i:=0 to max_num do make_cep(i);
WriteResults;
end.


При исходном файле
Цитата
5
1 2
1 3
2 16
3 6
5 16

Программа вывела результат:
Цитата
5
<5 16> : <16 2> : <2 1> : <1 3> : <3 6>


Тестируй...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Извини не подскажешь решение этой задачи на Си, а то я чувствую, что не переведу сам....
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской

Репутация: -  0  +


2volvo
Понимаешь (ничего, что на ты?) дело в том, что у нас по самому Си пары 4 прошло, а вот графами даже не пахнет.... я понять немогу на кого расчитаны эти задания....


2Michael_Rybak

Примерно понятно, но к сожалению базы не хватает
Не подскажешь где это можно прочесть на русском языке?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






Что-то в этом духе:
#include <stdio.h>
#include <mem.h>

enum bool {
false = 0, true = 1
};

const int max = 28;
const int max_num = 20;

bool yes = false;
bool m[max_num + 1][max_num + 1] = {false};

int n;
int cep[2 * max + 1] = {0};
int best[2 * max + 1];
int p, maxlen;
// cep,best :array [1..max*2] of byte;
// p,maxlen :integer;

int read_data() {
int i, a, b;
FILE *f;

if((f = fopen("DM.TXT", "rt")) == NULL) {
fprintf(stderr, "Cannot open input file.\n");
return 1;
}

// fillchar(cep,sizeof(cep),0);
// fillchar(m,sizeof(m),false);
p = 1; maxlen = 0;
fscanf(f, "%d", &n); // readln(n);
for(i = 1; i <= n; ++i) {
fscanf(f, "%d %d", &a, &b); // readln(a,b);
m[a][b] = m[b][a] = true;
}
fclose(f); // close(input);
return 0;
}

void write_results() {

int i;
printf("%d\n", maxlen / 2);
if(maxlen > 1) {
i = 1;
while(i < maxlen - 1) {
printf(" <%d %d> :", best[i], best[i+1]);
i += 2;
}
printf(" <%d %d>", best[maxlen - 1], best[maxlen]);
}
printf("\n");
}

void s_cep() {

if(p - 1 > maxlen) {
memmove(&best[0], &cep[0], (p - 1)*sizeof(int));
// move(cep,best,p-1);
maxlen = p - 1;
yes = (maxlen / 2 == n) ? true:false;
}
}

bool exist(int k) {
// var i : integer;
int i = 0;

while((i <= max_num) && (m[k][i] == false)) i += 1;
return (i <= max_num) ? true:false;
}

void make_cep(int f) {

int s;

if(yes == true) return;

if(m[f][f] == true) {
m[f][f] = false;
cep[p] = f; cep[p + 1] = f; p += 2;
if(exist(f) == true) make_cep(f); else s_cep();
p -= 2;
m[f][f] = true;
}
else
for(s = 0; s <= max_num; ++s)
if(m[f][s] == true) {
m[f][s] = m[s][f] = false;
cep[p] = f; cep[p + 1] = s; p += 2;
if(exist(s) == true) make_cep(s); else s_cep();
p -= 2;
m[f][s] = m[s][f] = true;
}
}

int main() {
int i;

read_data();
for(i = 0; i <= max_num; ++i) make_cep(i);
write_results();
return 0;
}

(тестовый пример проходит, погоняй еще, может я где-то ошибся при переносе на С...)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской

Репутация: -  0  +


Огромнео спасибо, протестирую, но спасибо за это решение огромное...
Если я ещё не совсем достал, то очень хотелось бы разобраться хотя бы в этом конкретнои примере , т.е. комментарии к решению услышать...если возможно конечно

Если омжно узнать, а заголовочник что должен в себе содержать, просто я взял один сурс файл и скинул туда исходник при запуске получил свдения об отсутствии header. Что в него вписать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Ну, это во-первых, зависит от твоего компилятора. Ты ж молчишь, я тебе привел решение, работающее на Turbo C++ 3.0 (1990 года выпуска). Тут мне ничего больше не понадобилось, только этот CPP... В других компиляторах может быть по-другому.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской

Репутация: -  0  +


понятно, да на будущее учту, что точность формулировки крайне важна... Мне бы на C, а компилятор Visual C 2005
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
Не подскажешь где это можно прочесть на русском языке?


Погугли "поиск максимального цикла" или "гамильтонов цикл".

Вообще, вынужден я тут признать, что это я глупость написал:

Цитата
Дело в том, что, если бы эту задачу можно было решать эффективно, то таким же алгоритмом можно было бы искать гамильтонов цикл - если он есть, то наше решение его выдаст, если нету - выдаст меньший цикл.


Глупость потому, что гамильтонов цикл обязан проходить по каждой вершине ровно 1 раз, а цикл по доминошкам - нет.

Вообще забей на это, как я понимаю, переборное решение тебя в любом случае устраивает, так что просто разбирайся с кодом volvo
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской

Репутация: -  0  +


Понятно, но все равно тебе спасибо

Очень прошу volvo перевести это решение на чистый С, чтобы оно работало под компилятор Visual C 2005 ... просто у нас завтро проверка что делать никто не знате, пытаться что то доказывать преподу дело гиблое...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ты может BuildLog запости, не у всех ведь есть VC.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Цитата
Очень прошу volvo перевести это решение на чистый С
А где, собственно, ты увидел отклонения от чистого С? Программа полностью соответствует Стандарту, компилируется и работает в GCC, а если VC НЕ компилирует такие программы - то это его проблемы.

У меня VC, кстати, именно по этой причине и нету.

Ну, хорошо. Вот это попробуй (убрал я тип bool, на который давалось предупреждение... Теперь нет предупреждений вообще...):
#include <stdio.h>
#include <mem.h>

#define max_num 20
#define max 28

int m[max_num + 1][max_num + 1] = {};
int yes = 0;

int n;
int cep[2 * max + 1] = {0};
int best[2 * max + 1];
int p, maxlen;

int read_data() {
int i, a, b;
FILE *f;

if((f = fopen("DM.TXT", "rt")) == NULL) {
fprintf(stderr, "Cannot open input file.\n");
return 1;
}

p = 1; maxlen = 0;
fscanf(f, "%d", &n);
for(i = 1; i <= n; ++i) {
fscanf(f, "%d %d", &a, &b);
m[a][b] = m[b][a] = 1;
}
fclose(f);
return 0;
}

void write_results() {

int i;
printf("%d\n", maxlen / 2);
if(maxlen > 1) {
i = 1;
while(i < maxlen - 1) {
printf(" <%d %d> :", best[i], best[i+1]);
i += 2;
}
printf(" <%d %d>", best[maxlen - 1], best[maxlen]);
}
printf("\n");
}

void s_cep() {

if(p - 1 > maxlen) {
memmove(&best[0], &cep[0], (p - 1)*sizeof(int));
maxlen = p - 1;
yes = (maxlen / 2 == n) ? 1 : 0;
}
}

int exist(int k) {
int i = 0;

while((i <= max_num) && (!m[k][i])) i += 1;
return (i <= max_num) ? 1 : 0;
}

void make_cep(int f) {

int s;
if(yes) return;

if(m[f][f]) {
m[f][f] = 0;
cep[p] = f; cep[p + 1] = f; p += 2;
if(exist(f)) make_cep(f); else s_cep();
p -= 2;
m[f][f] = 1;
}
else
for(s = 0; s <= max_num; ++s)
if(m[f][s]) {
m[f][s] = m[s][f] = 0;
cep[p] = f; cep[p + 1] = s; p += 2;
if(exist(s)) make_cep(s); else s_cep();
p -= 2;
m[f][s] = m[s][f] = 1;
}
}

int main() {
int i;

read_data();
for(i = 0; i <= max_num; ++i) make_cep(i);
write_results();
return 0;
}
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской

Репутация: -  0  +


Запустил, а этот visual собака ругается и вот это выкидыват

1>c:\documents and settings\vbproffi\my documents\visual studio 2005\projects\srav\srav\main.c(2) : fatal error C1083: Cannot open include file: 'mem.h': No such file or directory

Ещё, понимаю что ужасно достал уже всех с этой задачей, но если бы небльшие поясннеия к исходнику (мы вообще то здаём не на компах а как бы так на проверку, потому от чатси галвное продемонстрировать понимание решения), вот собственно хотелось бы его понять

Сообщение отредактировано: Nucris -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Nucris @ 9.10.2006 14:35) *

1>c:\documents and settings\vbproffi\my documents\visual studio 2005\projects\srav\srav\main.c(2) : fatal error C1083: Cannot open include file: 'mem.h': No such file or directory


А может, попробуй создать пустой mem.h да и всё unsure.gif
А не получится - посмотри хоть какую нибудь прогу, которая компилится на этом жутком вижуале smile.gif, из экзамплов там, и посмотри, че там в хедерах такого особоннего надо писать.

Кроме того, если вы сдаете не на компах - в чем проблема, скачай себе эти 17 метров MINGW и всё круто будет. Или, могу тебе старый добрый ТС 3.0 выслать, он 3 метра весит. Кстати, volvo, мой ТС 3.0 не понимает "int m[max_num + 1][max_num + 1] = {};"

Цитата(Nucris @ 9.10.2006 14:35) *

Ещё, понимаю что ужасно достал уже всех с этой задачей, но если бы небльшие поясннеия к исходнику (мы вообще то здаём не на компах а как бы так на проверку, потому от чатси галвное продемонстрировать понимание решения), вот собственно хотелось бы его понять


Как раз наоборот - намного приятнее, когда хочешь разобраться, чем когда хочешь просто сдать.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






Цитата
Кстати, volvo, мой ТС 3.0 не понимает "int m[max_num + 1][max_num + 1] = {};"
Ребят, вам шашечки, или ехать? Первая программа работала на TC - не понравилось, теперь работает в ICC/GCC - опять нехорошо...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 16
Пол: Мужской

Репутация: -  0  +


Вышли пожалуйста на lit12@bk.ru
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ура!

Короче я вот спросил на форуме TopCoder'a, и там ulzha родил гениальную мысль.

Вот полученная им цепочка рассуждений:

1. Представим все возможные числа на доминошках - вершинами в графе, а сами доминошки - ребрами. Теперь перед нами стоит задача построения самого длинного замкнутого маршрута, проходящего через каждое ребро не больше 1 раза, а через каждую вершину - произвольное кол-во раз.

2. Пусть в графе n вершин и m ребер. Добавим к каждой вершине цикл длины m+1, т.е. m новых, фиктивных вершин.

Получится, что, если в начальном графе существовал замкнутый маршрут, проходящий через каждую вершину как минимум один раз, то в новом графе, дополненном циклами, обязательно существует маршрут длины большей, чем n*(m+1) - ведь из каждой вершины мы можем пройтись по ее дополнительному циклу.

Понятно, что верно и обратное утверждение: получить в новом графе маршрут длины большей, чем n*(m+1), можно *только* посетив каждую вершину оригинального графа как минимум один раз.

3. M. R. Garey, D. S. Johnson и R. Endre Tarjan показали, что поиск гамильтонова цикла в планарном, кубическом, 3-связном графе является NP-полной задачей.

4. Кубический граф - такой, у которого степень каждой вершины равна 3. Получается, замкнутый маршрут в таком графе не может побывать в какой-нибудь вершине больше одного раза - ведь это означало бы, что ее степень - как минимум 4.

5. Сведем это воедино.
  • Рассмотрим кубический, планарный, 3-связный (n, m) граф. Добавим к каждой вершине цикл длины m+1.
  • Найдя такой цикл, мы однозначно сможем определить (критерий - ребер в найденном цикле больше n(m+1)), существует ли в изначальном графе цикл, проходящий через каждую вершину как минимум 1 раз; если существует, то мы его уже построили - просто удаляем фиктивные ребра из ответа
  • В кубическом графе никакой цикл не может проходить в какую-нибудь вершину больше 1 раза, поэтому фактически мы научились строить гамильтонов цикл (в случае его существования)
  • Итак, мы свели NP-полную задачу к исходной, т.е. показали, что, умея решать задачу про доминошки за полиномиальное время, научимся решать за такое же время NP-полную задачу.

Браво, ulzha!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 20.09.2017 10:58
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"