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

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

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

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

18.04.2013, 07:16. Просмотров 2104. Ответов 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++
Я записал код, однако эту часть надо автоматизировать, поможете? КОД: } #include <iostream> using namespace std; int main()...

Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при чтении "0x334e2c64" - C++
доброго времени суток. Необработанное исключение в "0x76f015de" в "контрольная 1 задача 2.exe": 0xC0000005: Нарушение прав доступа при...

В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно" - C++
В зависимости от времени года "весна", "лето", "осень", "зима" определить погоду "тепло", "жарко", "холодно", "очень холодно". Я так...

Смоделировать выбор "наугад" одной кости домино из полного набора костей этой игры - C++
Помогите пожалуйста:cry: Смоделировать выбор "наугад" одной кости домино из полного набора костей этой игры (0–0, 0–1, ..., 6–6). Вывести...

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

Реализовать классы "Воин", "Пехотинец", "Винтовка", "Матрос", "Кортик" (наследование) - 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
Модератор
Эксперт С++
6358 / 5922 / 1919
Регистрация: 18.12.2011
Сообщений: 15,219
Завершенные тесты: 1
05.06.2013, 17:15 #3
Рекурсивная функция DFS() написана явно неправильно.
У неё нет условия выхода из рекурсии.
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
05.06.2013, 17:17  [ТС] #4
Как можно исправить? Подскажите пжлста, завтра последний день нужно сдать
zss
Модератор
Эксперт С++
6358 / 5922 / 1919
Регистрация: 18.12.2011
Сообщений: 15,219
Завершенные тесты: 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
388 / 344 / 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
388 / 344 / 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
мне просто задали по предмету "Структура и алгоритмы обработки данных". эта задача на графах и использует метод в ширину.
Duntes
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 10
09.06.2013, 16:15  [ТС] #11
пжлста помогите!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2013, 16:15
Привет! Вот еще темы с ответами:

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

Создать абстрактный класс "Издание" и производные классы "Книга", "Статья", "Электронный ресурс" - C++
1. Создать абстрактный класс Издание с методами, позволяющими вывести на экран информацию об издании, а также определить является ли данное...

Создать класс "Книга" с полями "название книги", "количество страниц", "год издания" - C++
Создать класс Книга поля: название книги,количество страниц,год издания методы: вычислить сколько лет книге и количество дней прошедших...

Создать класс "Вентилятор" содержащий в себе классы: "Двигатель", "Контроллер", "Пульт управления" - C++
Помогите с кодом написания задачи, не понимаю как написать классы в классе. Нужно создать класс &quot;вентилятор&quot; содержащий в себе классы:...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.06.2013, 16:15
Ответ Создать тему
Опции темы

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