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

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

Войти
Регистрация
Восстановить пароль
 
Dominum
0 / 0 / 0
Регистрация: 16.01.2014
Сообщений: 6
#1

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

21.03.2014, 06:49. Просмотров 440. Ответов 3
Метки нет (Все метки)

Заданы два человека – 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++
Три точки заданы координатами. Определить, лежат ли они на одной прямой C++
Зная три стороны, определить, являются ли они сторонами треугольника и является ли он прямоугольным C++
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. Ответить, являются ли они родственниками
Ответ Создать тему
Опции темы

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