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

динамическое программирование - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.69
hastam
0 / 0 / 0
Регистрация: 12.05.2011
Сообщений: 12
03.10.2011, 22:46     динамическое программирование #1
Народ помогите плиз найти алгоритм решения следующей задачи.
На посвящение в студенты собрались все первокурсники. Некоторые из них знают друг друга. Считается, что два незнакомых человека тоже друзья, если у них есть какой-нибудь общий друг. Все ли они друзья между собой?
Формат входного файла:
В первой строке входного файла INPUT.TXT записано целое число N - количество первокурсников. Во второй строке входного файла INPUT.TXT записано целое число K - количество известных непосредственных знакомств. Далее в следующих K строках записано по паре целых чисел Ai и Bi через один пробел, означающих, что первокурсники с номерами Ai и Bi знакомы непосредственно. Ограничения на значения: 1≤N≤1000, 0≤K≤1000000, 1≤Ai≤N, 1≤Bi≤N, i=1..N. Гарантируется, что для предложенного набора данных результат всегда существует. Каждая строка заканчивается переходом на новую строку.

Пример ввода:

4
3
1 2
1 3
2 4

Пример вывода:

YES
Зранее спасибо)
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2011, 22:46     динамическое программирование
Посмотрите здесь:

C++ Динамическое программирование
Динамическое программирование. C++
C++ Динамическое программирование
C++ ДП Динамическое программирование
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
03.10.2011, 23:39     динамическое программирование #2
hastam, блин, у Седжвика обсуждалась такая задача, только вот уже плохо помню, к чему пришли... Сейчас попробую поднять.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
03.10.2011, 23:58     динамическое программирование #3
Это не динамическое программирование.
Представьте, что каждый первокурсник представлен вершиной графа, а наличие прямых дружеских отношений ( то есть непосредственно один знает второго лично ) обозначается ребром.
Для решения задачи нам нужно найти количество компонентов связности, а точнее при 1й компоненте - все друзья, при 2х или больше - не все друзья =).

Что нужно для решения:
* вектор ребер ( при этом не забываем, что граф неориентированный, т.е. необходимо ставить ребро и от i -> j, и от j -> i )
* булевый массив на N элементов, который будет показывать, или мы проверили i-ого первокурсника, изначально заполненного "false"

Теперь просто ищем по следующему алгоритму:
1. Выбираем любую вершину.
2. Пускаем из неё поиск в глубину ( изменяя массив булевого типа - ставим "true" для тех вершин, в которых мы побывали ). При этом функцию поиска вызываем только 1 раз в теле main'а.
3. Просто идём по массиву булевого типа - если хотя бы раз встретили "false" ( т.е. вершину (первокурсника), с которой никто не дружит из найденного круга друзей ), то выводим, что есть незнакомцы среди перваков; если же все элементы массива являются истинной, то выводим, что да, все друзья.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
04.10.2011, 00:05     динамическое программирование #4
Это задача определения связности. Вот:

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
#include <stdio.h>
 
#define uint unsigned int
 
int main()
{
    uint n_elems, // количество элементов
         n_pairs; // количество заранее введённых пар
 
    uint i, u;
    uint * data;
 
    FILE *fd = fopen( "in.txt", "r" );
 
    if( !fd )
       return 1;
 
    fscanf( fd, "%d%d", &n_elems, &n_pairs );
 
    data = (uint*) malloc( sizeof(uint) * n_elems );
 
    for( i = 0; i < n_elems; i++ )
       data[i] = i + 1; /* нумерация с одного... */
 
    /*for( i = 0; i < n_elems; i++ )
       printf( "%4d ", data[i] );
 
    putchar( '\n' );*/
 
    for( i = 0; i < n_pairs; i++ )
    {
        uint a, b; // части пары
        fscanf( fd, "%d%d", &a, &b );
 
        /* printf( "pair: (%d, %d)\n", a, b ); */
 
        /* это значение имеет элемент [a-1] (-1 так как нумеация с 1) */
        uint key = data[a - 1];
 
        for( u = 0; u < n_pairs; u++ )
        {
            /* если этот элемент имеет значение ключа */
            if( data[u] == key )
               data[u] = data[b - 1]; /* назначаем ему значение второй части пары */
        }
 
        /*for( u = 0; u < n_elems; u++ )
            printf( "%4d ", data[u] );
 
        putchar( '\n' );*/
    }
 
    /* это значение первого элемента */
    uint key = data[0];
 
    for( i = 1; i < n_elems; i++ )
    {
        if( data[i] != key ) /* если значение текущего отличается от значения первого */
           break; /* вываливаемся */
    }
 
    /* если мы успешно проверили все связи */
    if( i == n_elems )
       puts( "YES" );
    else
       puts( "NO" );
 
    free( data );
 
    fclose( fd );
 
    return 0;
}
Раскомментируйте функции вывода, чтобы посмотреть работу.
renej
0 / 0 / 0
Регистрация: 05.10.2011
Сообщений: 3
05.10.2011, 17:13     динамическое программирование #5
Цитата Сообщение от x1Mike7x Посмотреть сообщение
Это не динамическое программирование.
Представьте, что каждый первокурсник представлен вершиной графа, а наличие прямых дружеских отношений ( то есть непосредственно один знает второго лично ) обозначается ребром.
Для решения задачи нам нужно найти количество компонентов связности, а точнее при 1й компоненте - все друзья, при 2х или больше - не все друзья =).

Что нужно для решения:
* вектор ребер ( при этом не забываем, что граф неориентированный, т.е. необходимо ставить ребро и от i -> j, и от j -> i )
* булевый массив на N элементов, который будет показывать, или мы проверили i-ого первокурсника, изначально заполненного "false"

Теперь просто ищем по следующему алгоритму:
1. Выбираем любую вершину.
2. Пускаем из неё поиск в глубину ( изменяя массив булевого типа - ставим "true" для тех вершин, в которых мы побывали ). При этом функцию поиска вызываем только 1 раз в теле main'а.
3. Просто идём по массиву булевого типа - если хотя бы раз встретили "false" ( т.е. вершину (первокурсника), с которой никто не дружит из найденного круга друзей ), то выводим, что есть незнакомцы среди перваков; если же все элементы массива являются истинной, то выводим, что да, все друзья.
Вы не могли бы примерно набросать код на с++? Для тех, кто с графами никогда вообще не работал.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
05.10.2011, 18:57     динамическое программирование #6
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
#include <iostream>
#include <vector>
 
std::vector < std::vector < int > > G;
std::vector < bool > used;
 
void dfs( int V )
{
    used.at( V ) = true;
    for ( unsigned i = 0, S = G.at( V ).size(); i < S; ++i )
        if ( !( used.at( G.at( V ).at( i ) ) ) )
            dfs( G.at( V ).at( i ) );
}
 
int main()
{
    int N, K, A, B;
    bool X = true;
    
    std::cin >> N >> K;
    
    G.resize( N );
    used.resize( N );
    used.assign( N, false );
    
    while ( K-- )
    {
        std::cin >> A >> B;
        --A; --B;
        G.at( A ).push_back( B );
        G.at( B ).push_back( A );
    }  
    
    dfs( 0 );
    
    for ( unsigned i = 0, S = used.size(); i < S && X; ++i )
        X &= used.at( i );
        
    std::cout << ( X ? "Yes" : "No" ) << std::endl;
        
    return 0;
}
renej
0 / 0 / 0
Регистрация: 05.10.2011
Сообщений: 3
06.10.2011, 00:41     динамическое программирование #7
x1Mike7x, Большое спасибо, а не могли бы вы подробно закомментировать свой код? И, если знаете, то поделитесь парочкой ссылок по данной теме.
x1Mike7x
 Аватар для x1Mike7x
214 / 127 / 6
Регистрация: 06.11.2010
Сообщений: 234
06.10.2011, 01:52     динамическое программирование #8
Сообщение было отмечено автором темы, экспертом или модератором как ответ
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
#include <iostream>
#include <vector>
 
std::vector < std::vector < int > > G; // Наш граф, для каждой вершины сохраняем список вершин, куда можно добраться за один шаг ( т.е. для каждого первака список его непосредственных друзей )
std::vector < bool > used; // Массив, где отмечаем или мы отметили вершину ( первака ) как просмотренного ( т.е. что у него есть друзья в некотором кругу )
 
void dfs( int V ) // функция поиска в глубину, параметр - номер вершины, которую просматриваем
{
        used.at( V ) = true; // Отмечаем, что мы были в вершине
        for ( unsigned i = 0, S = G.at( V ).size(); i < S; ++i ) // Идём по списку вершин для вершины V
                if ( !( used.at( G.at( V ).at( i ) ) ) ) // Если мы не были в і-ой вершине из списка
                        dfs( G.at( V ).at( i ) ); // то вызываем рекурсивно этот поиск в глубину для і-ой вершины
}
 
int main()
{
        int N, K, A, B;
        bool X = true; /// Переменная, которая будет показывать, или все вершины находятся в 1й компоненте связности, или нет
        
        std::cin >> N >> K;
        
        G.resize( N ); // Задаём, что у нас N вершин-перваков ( и следовательно столько будет списков непосредственных друзей )
        used.resize( N );
        used.assign( N, false ); // Весь массив used заполняем как будто мы не были ни в одной вершине
        
        while ( K-- )
        {
                std::cin >> A >> B; // Читаем связки друзей
                --A; --B; // Учитываем индексацию с 0, а не с 1;
                G.at( A ).push_back( B ); // Добавляем в список нового друга первака А
                G.at( B ).push_back( A ); // Добавляем в список нового друга первака В
        }  
        
        // Вызов функции поиска. Нам всё равно из какой вершины его вызывать, потому что нам нужно проверить всего-лишь или компонент связности больше 1
        dfs( 0 );
        
        // В цикле перебираем массив used, используем побитовое умножение - если хотя бы раз встретится в массиве значение false, то Х станет тоже false и цикл прекратится.
        for ( unsigned i = 0, S = used.size(); i < S && X; ++i )
                X &= used.at( i );
 
        // На основе Х выводим ответ - если Х так и остался true, то выводим "Да", иначе выводим "Нет"               
        std::cout << ( X ? "Yes" : "No" ) << std::endl;
                
        return 0;
}
Почитать про графы ( да и не только ) можно вот здесь: http://e-maxx.ru/algo/
Для конкретно этой задачи темы "Поиск в глубину" и "Поиск компонент связности" ( правда здесь, в задаче, нужны лишь знания, что это такое, т.к. решение сводится просто к поиску в глубину ).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.10.2011, 09:38     динамическое программирование
Еще ссылки по теме:

C++ Динамическое программирование!
Динамическое программирование C++

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

Или воспользуйтесь поиском по форуму:
renej
0 / 0 / 0
Регистрация: 05.10.2011
Сообщений: 3
06.10.2011, 09:38     динамическое программирование #9
x1Mike7x, Большое спасибо, куча вопросов сразу отпала =)
Yandex
Объявления
06.10.2011, 09:38     динамическое программирование
Ответ Создать тему
Опции темы

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