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

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

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

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

21.03.2014, 06:49. Просмотров 469. Ответов 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, то есть программа проверяет есть ли связь между этими ячейками, если есть, то они "РОДСТВЕННИКИ", если нет, то "Не родственники".
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.03.2014, 06:49
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Заданы два человека – p и q. Ответить, являются ли они родственниками (C++):

Заданы две прямые уравнениями вида y=kx+b. Определить, являются ли они параллельными - C++
Заданы две прямые уравнениями вида y=kx+b. Определить, являются ли они параллельными (k1=k2) или перпендикулярными (k1=1/k2).

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

Ввести с клавиатуры два слова. Проверить, являются ли они анаграммами - C++
Ввести с клавиатуры два слова. Проверить, являются ли они анаграммами, то есть возможно ли из всех букв одного слова составить другое....

ввести с клавиатуры два числа, узнать являются ли они соседними по коду Грея - C++
Добрый день, форумчане. Поступил я в университет, начал учить С++ Начались домашние задания, но я совсем не понимаю что к чему. Нужна...

Задаются два двузначных числа. Определить, являются ли они зеркальным отображение друг друга - C++
Можете решить эту простую задачу. И объяснить как вы ее решили. Задача должна решаться так, я ввожу два числа и программа сравнивает их на...

Два мальчика купили билеты в кино. До начала сеанса они решили поиграть в щелбаны. Они называют по одной цифр - C++
Два мальчика купили билеты в кино. До начала сеанса они решили поиграть в щелбаны. Они называют по одной цифре билета. У кого цифра...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
22.03.2014, 11:08 #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");
}
1
Dominum
0 / 0 / 0
Регистрация: 16.01.2014
Сообщений: 6
27.03.2014, 17:10  [ТС] #3
Программа не работает. Я так понимаю ты её сделал на VS 2010. Я код вставил, и когда я построил проект у меня тупо выводится сообщение "relatives". А должно быть так, что я ввожу номер графа и он делает проверку. При этом родственниками должны быть те элементы графа, который имеет общего предка или пра-пра-пра предка и т.д. Типа 6-7 родственники потому что элемента 5 общий и он предок. А 0-5 не родственники, потому что 6 элемента не существует.
0
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
28.03.2014, 08:40 #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");
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.03.2014, 08:40
Привет! Вот еще темы с ответами:

Три точки заданы координатами. Определить, лежат ли они на одной прямой - C++
Задачи довольно простые. Я проста не разбираюсь в этом языке программирование. Проста срочно нужны решение. Думаю дальнейшем его...

Исправьте код, выдает ошибку (заданы коэффициенты квадратного уравнения. Найти его действительные корни, если они существуют.) - C++
Помогите, пожалуйста :cry: Написал программу к задачке - выдает ошибку Заданы коэффициенты квадратного уравнения. Найти его...

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

Для трех данных целых чисел проверить, являются ли они тройкой Пифагора - C++
Для трех данных целых чисел проверить, являются ли они тройкой Пифагора.


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

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

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