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

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

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

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

21.03.2014, 06:49. Просмотров 456. Ответов 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. Ответить, являются ли они родственниками
Посмотрите здесь:

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

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

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

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

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

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

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

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

Зная три стороны, определить, являются ли они сторонами треугольника и является ли он прямоугольным - C++
Есть три длины сторон треугольника (например 5,4,3) Нужно выяснить, существует ли такой треугольник, и прямоугольный он или нет. Прогу...

С++ Для трех данных целых чисел проверить, являются ли они тройкой Пифагора - C++
#include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;stdio.h&gt; using namespace std; int main () { int x,y,z; ...

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

заданы координаты трех точек. Напишите программу, которая проверяет, являются ли эти точки вершинами треугольника. - C++
На входе заданы координаты трех точек. Напишите программу, которая проверяет, являются ли эти точки вершинами треугольника. :) ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
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
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
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. Ответить, являются ли они родственниками
Ответ Создать тему
Опции темы

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