Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.80
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
#1

Задача "Домино" - C++

18.04.2013, 07:16. Просмотров 1949. Ответов 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
Решение на С++
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2013, 07:16     Задача "Домино"
Посмотрите здесь:

Структуры... Задача: "База сотрудников небольшой фирмы" C++
C++ Игра "Домино"
C++ Найти ошибку в решении "Числа - палиндрома" (задача с acmp)
Перевод из двоичной системы в десятичную, задача 2.30 "Как программировать на С++" C++
C++ Вычислить значение суммы. Задача с использованием "длинной арифметики".
Задача "Кто старше?" (подскажите где ошибка в коде) C++
Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Duntes
0 / 0 / 0
Регистрация: 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);
}
Пожалуйста, можете сказать где здесь ошибка
zss
Модератор
Эксперт С++
6184 / 5787 / 1874
Регистрация: 18.12.2011
Сообщений: 14,782
Завершенные тесты: 1
05.06.2013, 17:15     Задача "Домино" #3
Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 17:17  [ТС]     Задача "Домино" #4
Как можно исправить? Подскажите пжлста, завтра последний день нужно сдать
zss
Модератор
Эксперт С++
6184 / 5787 / 1874
Регистрация: 18.12.2011
Сообщений: 14,782
Завершенные тесты: 1
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);
}
это предотвратит зацикливание
Duntes
0 / 0 / 0
Регистрация: 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 минут
Помогите пожалуйста)) заранее благодарен)
dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 18:57     Задача "Домино" #7
Цитата Сообщение от zss Посмотреть сообщение
Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.
вы уверены?
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 20:02  [ТС]     Задача "Домино" #8
или проверка сервера тупит? можете что нибудь добавить aram_gyumri )
dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
05.06.2013, 20:19     Задача "Домино" #9
Duntes, задача откуда?
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
06.06.2013, 01:29  [ТС]     Задача "Домино" #10
мне просто задали по предмету "Структура и алгоритмы обработки данных". эта задача на графах и использует метод в ширину.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2013, 16:15     Задача "Домино"
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
09.06.2013, 16:15  [ТС]     Задача "Домино" #11
пжлста помогите!
Yandex
Объявления
09.06.2013, 16:15     Задача "Домино"
Ответ Создать тему
Опции темы

Текущее время: 06:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru