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

@Duntes · Регистрация: 25.11.2011

Author24 — интернет-сервис помощи студентам

Пожалуйста помогите с задачей)) Ни как не могу решить

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 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
Решение на С++

@Duntes · 05.06.2013, 16:55 **[ТС]**

C++

#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 · 05.06.2013, 17:15

Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.

@Duntes · 05.06.2013, 17:17 **[ТС]**

Как можно исправить? Подскажите пжлста, завтра последний день нужно сдать

@zss · 05.06.2013, 17:29

Не могу понять, что функция делает,
но внутри цикла должно быть что-то типа

C++

 if(a[v][i]==1&&c[i]==0)
 {
           if(v==i)return;
           DFS(i);
}

это предотвратит зацикливание

@Duntes · 05.06.2013, 18:50 **[ТС]**

Спасибо за помощь,но если так то не правильно выводится ответ.

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

Pascal

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 · 05.06.2013, 18:57

Сообщение от zss

Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.

вы уверены?

@Duntes · 05.06.2013, 20:02 **[ТС]**

или проверка сервера тупит? можете что нибудь добавить aram_gyumri

)

@dr.curse · 05.06.2013, 20:19

Duntes, задача откуда?

@Duntes · 06.06.2013, 01:29 **[ТС]**

мне просто задали по предмету "Структура и алгоритмы обработки данных". эта задача на графах и использует метод в ширину.

@Duntes · 09.06.2013, 16:15 **[ТС]**

пжлста помогите!

@Duntes 0 / 0 / 1 Регистрация: 25.11.2011 Сообщений: 10
		1
	Задача "Домино" 18.04.2013, 07:16. Показов 9559. Ответов 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

@zss Модератор 13507 / 10757 / 6412 Регистрация: 18.12.2011 Сообщений: 28,712
	05.06.2013, 17:15	3
	Рекурсивная функция DFS() написана явно неправильно. У неё нет условия выхода из рекурсии. 0

@Duntes 0 / 0 / 1 Регистрация: 25.11.2011 Сообщений: 10
	05.06.2013, 17:17 [ТС]	4
	Как можно исправить? Подскажите пжлста, завтра последний день нужно сдать 0

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	05.06.2013, 18:57	7
	Сообщение от zss Рекурсивная функция DFS() написана явно неправильно. У неё нет условия выхода из рекурсии. вы уверены? 0

@Duntes 0 / 0 / 1 Регистрация: 25.11.2011 Сообщений: 10
	05.06.2013, 20:02 [ТС]	8
	или проверка сервера тупит? можете что нибудь добавить aram_gyumri ) 0

@dr.curse 404 / 360 / 36 Регистрация: 11.10.2010 Сообщений: 1,907
	05.06.2013, 20:19	9
	Duntes, задача откуда? 0

@Duntes 0 / 0 / 1 Регистрация: 25.11.2011 Сообщений: 10
	06.06.2013, 01:29 [ТС]	10
	мне просто задали по предмету "Структура и алгоритмы обработки данных". эта задача на графах и использует метод в ширину. 0

@Duntes 0 / 0 / 1 Регистрация: 25.11.2011 Сообщений: 10
	09.06.2013, 16:15 [ТС]	11
	пжлста помогите! 0