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

Заданы два человека – p и q. Ответить, являются ли они родственниками - C++

Восстановить пароль Регистрация
 
Dominum
0 / 0 / 0
Регистрация: 16.01.2014
Сообщений: 6
21.03.2014, 06:49     Заданы два человека – p и q. Ответить, являются ли они родственниками #1
Заданы два человека – p и q. Ответить, являются ли они родственниками.

Заданы n человек и два массива натуральных чисел mother[n] и father[n], такие, что mother[i] – номер матери i-го человека, а father[i] – номер его отца, для каждого i, удовлетворяющего неравенствам 0 <= i<= n-1.

Искал в интернете, нашел только одну программу и то на киберфоруме - Дописать программу (Заданы два человека – p и q. Ответить, являются ли они родственниками)

Программа работает, но только на близких ячейках, типа 0-2 1-2 3-5 6-8, но мне нужно что бы программа выявляла родственников не только по близким ячейкам, но и по дальним, типа 8-3 8-1 6-4, то есть программа проверяет есть ли связь между этими ячейками, если есть, то они "РОДСТВЕННИКИ", если нет, то "Не родственники".
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.03.2014, 06:49     Заданы два человека – p и q. Ответить, являются ли они родственниками
Посмотрите здесь:

C++ Определить являются ли числа упорядоченными по возрастанию
Исправьте код, выдает ошибку (заданы коэффициенты квадратного уравнения. Найти его действительные корни, если они существуют.) C++
Заданы две прямые уравнениями вида y=kx+b. Определить, являются ли они параллельными C++
C++ ввести с клавиатуры два числа, узнать являются ли они соседними по коду Грея
Ввести с клавиатуры два слова. Проверить, являются ли они анаграммами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Eldies
89 / 80 / 28
Регистрация: 06.02.2014
Сообщений: 119
22.03.2014, 11:08     Заданы два человека – p и q. Ответить, являются ли они родственниками #2
Если нарисовать всех этих людей и связи между ними, то получится граф.
Если p и q находятся в одной компоненте связности, то они - родственники.

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
#include <iostream>
#include <vector>
#include <queue>
 
// возвращает true, если first и second находятся в одной компоненте связности
bool areConnected(std::vector<std::vector<int>>&  graph, int first, int second)
{
    std::vector<bool> visited(graph.size(), false);
    std::queue<int> to;
 
    to.push(first);
    visited[first] = true;
 
    while (!to.empty())
    {
        int now = to.front();
        to.pop();
        for (int i = 0; i < graph[now].size(); ++i)
            if (!visited[graph[now][i]])
            {
                visited[graph[now][i]] = true;
                to.push(graph[now][i]);
            }
    }
 
    return visited[second];
}
 
void main(void)
{
    int n = 10;
    int mother[10]={-1,-1,1,-1,-1,4,5,5,7,-1};
    int father[10]={-1,-1,0,-1,-1,3,2,-1,6,-1};
 
    std::vector<std::vector<int>> graph(n);
    // преобразуем в более удобный вид
    for(int i = 0; i < n; ++i)
    {
        if (mother[i] != -1)
        {
            graph[i].push_back(mother[i]);
            graph[mother[i]].push_back(i);
        }
        if (father[i] != -1)
        {
            graph[i].push_back(father[i]);
            graph[father[i]].push_back(i);
        }
    }
 
    int first = 0; // q
    int second = 1; // p
    
    if (areConnected(graph, first, second))
        std::cout << "relatives\n";
    else
        std::cout << "not relatives\n";
 
    std::system("pause");
}
Dominum
0 / 0 / 0
Регистрация: 16.01.2014
Сообщений: 6
27.03.2014, 17:10  [ТС]     Заданы два человека – p и q. Ответить, являются ли они родственниками #3
Программа не работает. Я так понимаю ты её сделал на VS 2010. Я код вставил, и когда я построил проект у меня тупо выводится сообщение "relatives". А должно быть так, что я ввожу номер графа и он делает проверку. При этом родственниками должны быть те элементы графа, который имеет общего предка или пра-пра-пра предка и т.д. Типа 6-7 родственники потому что элемента 5 общий и он предок. А 0-5 не родственники, потому что 6 элемента не существует.
Eldies
89 / 80 / 28
Регистрация: 06.02.2014
Сообщений: 119
28.03.2014, 08:40     Заданы два человека – p и q. Ответить, являются ли они родственниками #4
1) Программа "не работает", т.к. я не делал ввод.
Родственные отношения заданы в строках 31-33.
номера людей, которые проверяются на родство - в строках 51-52.

2) в первом сообщении сказано,
Цитата Сообщение от Dominum Посмотреть сообщение
программа проверяет есть ли связь между этими ячейками, если есть, то они "РОДСТВЕННИКИ"
Если родственниками считаются только те, кто имеет общего предка, нужно делать по-другому:
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
79
#include <iostream>
#include <vector>
#include <queue>
 
// возвращает true, если first и second имеют общего предка
bool haveCommonAncestor(std::vector<std::vector<int>>&  graph, int first, int second)
{
    std::vector<bool> visitedByFirst(graph.size(), false);
    std::vector<bool> visitedBySecond(graph.size(), false);
    std::queue<int> to;
 
    // посещаем всех предков first
    to.push(first);
    visitedByFirst[first] = true;
    while (!to.empty())
    {
        int now = to.front();
        to.pop();
        for (int i = 0; i < graph[now].size(); ++i)
            if (!visitedByFirst[graph[now][i]])
            {
                visitedByFirst[graph[now][i]] = true;
                to.push(graph[now][i]);
            }
    }
 
    if (visitedByFirst[second])
        return true;
 
    to.push(second);
    visitedBySecond[second] = true;
    while (!to.empty())
    {
        int now = to.front();
        to.pop();
        for (int i = 0; i < graph[now].size(); ++i)
        {
            if (visitedByFirst[graph[now][i]])
                return true;
            if (!visitedBySecond[graph[now][i]])
            {
                visitedBySecond[graph[now][i]] = true;
                to.push(graph[now][i]);
            }
        }
    }
    return false;
}
 
void main(void)
{
    int n = 10;
    int mother[10]={-1,-1,1,-1,-1,4,5,5,7,-1};
    int father[10]={-1,-1,0,-1,-1,3,2,-1,6,-1};
 
    std::vector<std::vector<int>> graph(n);
    // преобразуем в более удобный вид
    for(int i = 0; i < n; ++i)
    {
        if (mother[i] != -1)
            graph[i].push_back(mother[i]);
        if (father[i] != -1)
            graph[i].push_back(father[i]);
    }
 
    int first; // q
    int second; // p
    std::cout << "Input number of first human: ";
    std::cin >> first;
    std::cout << "Input number of second human: ";
    std::cin >> second;
 
    if (haveCommonAncestor(graph, first, second))
        std::cout << "relatives\n";
    else
        std::cout << "not relatives\n";
 
    std::system("pause");
}
Yandex
Объявления
28.03.2014, 08:40     Заданы два человека – p и q. Ответить, являются ли они родственниками
Ответ Создать тему
Опции темы

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