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

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

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

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

18.04.2013, 07:16. Просмотров 2026. Ответов 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++
Помогите пожалуйста:cry: Смоделировать выбор "наугад" одной кости домино из полного набора костей этой игры (0–0, 0–1, ..., 6–6). Вывести...

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

Игра "Домино" - C++
есть ли уже готовая программа на с++?

Задача решена только нужна "нитра" фишки по ускорению - C++
Задача такая, создать файл заданного размера к примеру 500 мегабайтов, в него на генерировать рандомно данные а потом их отсортировать в...

Найти ошибку в решении "Числа - палиндрома" (задача с acmp) - C++
У меня WA на 4-ом тесте. #include <stdio.h> #include <stdio.h> #include <math.h> #include <cstdio> #include <algorithm> ...

Задача "Кто старше?" (подскажите где ошибка в коде) - C++
Здравствуйте!подскажите где может быть ошибка, на сайте показывает частичное решение, Условие: Программа принимает три числа: возраст...

Перевод из двоичной системы в десятичную, задача 2.30 "Как программировать на С++" - 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
Модератор
Эксперт С++
6283 / 5886 / 1906
Регистрация: 18.12.2011
Сообщений: 15,104
Завершенные тесты: 1
05.06.2013, 17:15     Задача "Домино" #3
Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 17:17  [ТС]     Задача "Домино" #4
Как можно исправить? Подскажите пжлста, завтра последний день нужно сдать
zss
Модератор
Эксперт С++
6283 / 5886 / 1906
Регистрация: 18.12.2011
Сообщений: 15,104
Завершенные тесты: 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++
Тема: «Задачи на длинную арифметику» Задача: Вычислить точное значение суммы 1^2 + 2^2 + 3^2 + ... + n^2 (n ≥ 20000). Пожалуйста,...

Задача "Гигабашня": минимальное расстояние до этажа со счастливым номером - C++
Гигабашня — самое высокое и глубокое здание в Киберленде. В ней 17 777 777 777 этажей, пронумерованных от  - 8 888 888 888 до...

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

Задача из книги "Програмирование - принципы и практика использования C++" - C++
Кто читал ету книгу, помогите разобратся с задачей с 12 главы. Никак не могу скомпилировать простую программу. Вот ее код: #include...

Структуры... Задача: "База сотрудников небольшой фирмы" - C++
По каждому сотруднику вводится следующая информация: • Фамилия, имя, отчество; • год и дата рождения; • пол; • стаж работы по...


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

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

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