Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > C/C++ > C++ > С++ для начинающих
Войти
Регистрация
Восстановить пароль
Правила Карта форума Темы раздела Блоги Социальные группы Поиск Сообщения за день  
 
Рейтинг 4.53/47: Рейтинг темы: голосов - 47, средняя оценка - 4.53
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
1

Задача "Домино"

18.04.2013, 07:16. Показов 9363. Ответов 10
Метки нет (Все метки)
Студворк — интернет-сервис помощи студентам
Пожалуйста помогите с задачей)) Ни как не могу решить

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).
Из костяшек можно выкладывать цепочки, соединяя пары костяшек короткими сторонами, если количества точек на соседних с местом соединения половинках костяшек равны.
Некоторые костяшки были удалены из полного набора. Требуется определить, какое минимальное количество цепочек нужно выложить из оставшихся в наборе костяшек, чтобы каждая из них принадлежала ровно одной цепочке.
Задание:
Напишите программу, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.
Входные данные:
В первой строке входного файла содержится одно целое число M (0≤M≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая і-я из последующих N строк содержит по два числа Ai и Bі. Это количества точек на половинках i-й удалённой костяшки.
Выходные данные:
Единственная строка выходного файла должна содержать одно целое число L – минимальное количество цепочек.
Пример:
input.txt
7
2
7 5
3 4
output.txt
2
Решение на С++
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 18.04.2013, 07:16
Ответы с готовыми решениями:

Задача про Домино-2
Пожалуйста, помогите срочно!! Желательно код, или помогите переделать задачу про домино ранее на...

Домино
нужна программа домино исходник для курсака

Кости домино
Написать проект, в котором случайным образом рисуется кость домино, а затем все кости, которые к...

Шахматное домино
Комплект шахматного домино состоит из 32 костяшек 2×1, каждый из квадратов которой окрашен в черный...

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

10
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 16:55  [ТС] 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
using namespace std;
 
const int MAX=10000;
int a[MAX][MAX],step[MAX],c[MAX],kolnv[MAX+1];
int N,M,i,j,cc=0,res=0,nech; 
 
void DFS(int v);
void Init();
 
void main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    Init();
    for(i=0;i<=M;i++)
    {
        for(j=i;j<=M;j++)
        {
            if(a[i][j]==1)
            {
                step[i]++;
                step[j]++;
            }
        }
    }
    for(i=0;i<=M;i++)
    {
        if(step[i]==0)
            c[i]=255;
        else
            if(c[i]==0)
            {
                cc++;
                DFS(i);
            }
    }
    for(i=0;i<=M;i++)
    {
        nech=step[i]%2;
        if(nech==0)
            kolnv[c[i]]++;
    }
    for(i=1;i<=cc;i++)
    {
        if(kolnv[i]==0)
            res=res+1;
        else
            res=res+kolnv[i]/2;
    }
    cout<<res;
}
 
void Init()
{
    cin>>M>>N;
    for(i=0;i<=M;i++)
    {
        for(j=0;j<=M;j++)
        {
            a[i][j]=1;
        }
    }
    for(int k=1;k<=N;k++)
    {
        cin>>i>>j;
        a[i][j]=0;
        a[j][i]=0;
    }
}
 
void DFS(int v)
{
    c[v]=cc;
    for(i=0;i<=M;i++)
        if(a[v][i]==1&&c[i]==0)
            DFS(i);
}
Пожалуйста, можете сказать где здесь ошибка
0
Модератор
Эксперт С++
13329 / 10631 / 6352
Регистрация: 18.12.2011
Сообщений: 28,390
05.06.2013, 17:15 3
Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.
0
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 17:17  [ТС] 4
Как можно исправить? Подскажите пжлста, завтра последний день нужно сдать
0
Модератор
Эксперт С++
13329 / 10631 / 6352
Регистрация: 18.12.2011
Сообщений: 28,390
05.06.2013, 17:29 5
Не могу понять, что функция делает,
но внутри цикла должно быть что-то типа
C++
1
2
3
4
5

 if(a[v][i]==1&&c[i]==0)
 {
           if(v==i)return;
           DFS(i);
}
это предотвратит зацикливание
0
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 18:50  [ТС] 6
Спасибо за помощь,но если так то не правильно выводится ответ.

Если чё я списал отсюда:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

const
  maxM = 100;
var
  fi, fo: text;
  nabor: array[0..maxM, 0..maxM] of byte; {1 - kostyashka est' v nabore; 0 - net}
  power: array[0..maxM] of integer;       {stepen' vershiny}
  comp: array[0..maxM] of integer;        {k kakoy komponente prinadlejut vershina}
  numodd: array[1..maxM + 1] of integer;  {kol-vo nechetnyh vershin v komponente}
  N, M, i, j: integer;
  a, b, curcomp: integer;
  result: integer;
 
  procedure dfs(what: integer);
  var
    i: integer;
  begin
    comp[what] := curcomp;
    for i := 0 to M do
      if (nabor[what, i] = 1) AND (comp[i] = 0) then
        dfs(i);
  end;
 
begin
 
{INPUT}
  fillchar(nabor, sizeof(nabor), 1);
  assign(fi, 'domino.dat');
  reset(fi);
  readln(fi, M);
  readln(fi, N);
  for i := 1 to N do
  begin
    readln(fi, a, b);
    nabor[a, b] := 0;
    nabor[b, a] := 0;
  end;
  close(fi);
 
{POWERS}
  for i := 0 to M do
    for j := i to M do
    if nabor[i, j] = 1 then
    begin
      inc(power[i]);
      inc(power[j]);
    end;
 
{CONNECTIVE COMPONENTS}
  for i := 0 to M do
    if power[i] = 0 then
      comp[i] := 255
    else
    if comp[i] = 0 then
    begin
      inc(curcomp);
      dfs(i);
    end;
 
{EULER'S RULE}
  for i := 0 to M do
    if odd(power[i]) then
      inc(numodd[comp[i]]);
 
{RESULT}
  for i := 1 to curcomp do
    if numodd[i] = 0 then
      result := result + 1
    else
      result := result + numodd[i] div 2;
 
{OUTPUT}
  assign(fo, 'domino.sol');
  rewrite(fo);
  writeln(fo, result);
  close(fo);
end.
Добавлено через 4 минуты
Или я неправильно переписал на С++? На самом деле этот код выводит ответ правильно, но автоматическая проверка сервера дает лишь 5 баллов

Добавлено через 1 час 9 минут
Помогите пожалуйста)) заранее благодарен)
0
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 18:57 7
Цитата Сообщение от zss Посмотреть сообщение
Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.
вы уверены?
0
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 20:02  [ТС] 8
или проверка сервера тупит? можете что нибудь добавить aram_gyumri )
0
404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 20:19 9
Duntes, задача откуда?
0
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
06.06.2013, 01:29  [ТС] 10
мне просто задали по предмету "Структура и алгоритмы обработки данных". эта задача на графах и использует метод в ширину.
0
0 / 0 / 1
Регистрация: 25.11.2011
Сообщений: 10
09.06.2013, 16:15  [ТС] 11
пжлста помогите!
0
09.06.2013, 16:15
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 09.06.2013, 16:15
Помогаю со студенческими работами здесь

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

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

Свой квиксорт с домино и буфетчицами!
Доброго времени суток! В общем идея проста: сделать псевдо рекурсивную сортировку разделением,...

Реализовать точки на костях домино
Точки на костях Домино (Время: 1 сек. Память: 16 Мб Сложность: 25%) Для того, чтобы заработать...

Игра в домино (программа написана, но выдает ошибки)
Имеется N костей игры домино. На каждой кости имеется два числа (каждое от 0 до 6). Требуется...

Найти наибольшую сумму костей домино игрока
У игрока есть k костей домино - прямоугольников 2x1. Он кладет их на доску так, чтобы не возникало...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru