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

> Внимание!

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

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

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


Гость






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


Гость






Цитата
Очень прошу 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;
}
 К началу страницы 
+ Ответить 

Сообщений в этой теме
Zenon   задача про домино   8.10.2006 12:31
Michael_Rybak   Для перебора может быть полезен критерий: в графе …   8.10.2006 13:49
volvo   Ну, поскольку ты не написал, на каком языке тебе н…   8.10.2006 14:07
Гость   Извини не подскажешь решение этой задачи на Си, а …   8.10.2006 15:26
Nucris   2volvo Понимаешь (ничего, что на ты?) дело в том, …   8.10.2006 16:04
volvo   Что-то в этом духе: #include <stdio.h> #incl…   8.10.2006 17:50
Nucris   Огромнео спасибо, протестирую, но спасибо за это р…   8.10.2006 20:06
volvo   Ну, это во-первых, зависит от твоего компилятора. …   8.10.2006 20:49
Nucris   понятно, да на будущее учту, что точность формулир…   8.10.2006 21:50
Michael_Rybak   Погугли "поиск максимального цикла" ил…   9.10.2006 3:46
Nucris   Понятно, но все равно тебе спасибо Очень прошу vo…   9.10.2006 16:49
Michael_Rybak   Ты может BuildLog запости, не у всех ведь есть VC.   9.10.2006 17:14
volvo   А где, собственно, ты увидел отклонения от чистого…   9.10.2006 17:21
Nucris   Запустил, а этот visual собака ругается и вот это …   9.10.2006 18:35
Michael_Rybak   1>c:\documents and settings\vbproffi…   9.10.2006 19:39
volvo   Ребят, вам шашечки, или ехать? Первая программа ра…   9.10.2006 19:45
Michael_Rybak   Ура! Короче я вот спросил на форуме TopCoder…   10.10.2006 16:09
Nucris   Вышли пожалуйста на lit12@bk.ru   9.10.2006 19:48


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

 





- Текстовая версия 29.03.2024 12:02
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name