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

Задача «NetWork» - C++

Восстановить пароль Регистрация
 
Includenv
Сообщений: n/a
22.10.2011, 14:23     Задача «NetWork» #1
Интересует именно идея. Код писать не надо.

Условие
В компьютерной сети вашей фирмы n компьютеров. В последнее время свитч, к которому они
подключены, сильно барахлит, и потому не любые два компьютера могут связаться друг с другом.
Кроме того, если компьютер a обменивается информацией с компьютером b, то никакие другие
компьютеры не могут в это время обмениваться информацией ни с a, ни c b. Вам необходимо
вычислить максимальное количество компьютеров, которые могут одновременно участвовать в
процессе обмена информацией.

Формат входного файла
В первой строке файла задано число n (1 ≤ n ≤ 18). Далее идут n строк по n символов, причем
j символ i-й строки равен ‘Y’, если i-й и j-й компьютеры могут обмениваться информацией, иначе
он равен ‘N’. i-й символ i-й строки всегда равен ‘N’, кроме того, матрица символов симметрична.

Формат выходного файла
Выведите максимальное количество компьютеров, которые могут одновременно участвовать в
процессе обмена информацией.

Примеры
Миниатюры
Задача «NetWork»  
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2011, 14:23     Задача «NetWork»
Посмотрите здесь:

C++ c++ scanning network
работа с SNMP (Simlpe network menegement protocol) C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.10.2011, 19:56     Задача «NetWork» #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Includenv Посмотреть сообщение
Интересует именно идея. Код писать не надо.
идея в коде:
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
#include <stdio.h>
 
int main ()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int *mas, i, n, mas2[18], j, tmp, y;
    mas=new int[262144];
    char mas1[18][19];
    scanf("%d\n", &n);
    for(i=0; i<n; i++)
        scanf("%s\n", &mas1[i]);
    for(i=0; i<262144; i++)
        mas[i]=0;
    mas2[0]=1;
    for(i=1; i<n; i++)
        mas2[i]=mas2[i-1]*2;
    for(i=0; i<n; i++)
    {
        for(j=0; j<262144; j++)
            if(mas[j]!=0)
            {
                bool fl=true;
                tmp=j+1;
                for(y=n-1; y>i; y--)
                    if(tmp>=mas2[y])
                        tmp-=mas2[y];
                if(tmp>=mas2[i])
                    fl=false;
                if(fl)
                {           
                    tmp=j+1;
                    for(y=n-1; y>=0; y--)
                        if(tmp>=mas2[y])
                            tmp-=mas2[y];
                        else
                        {
                            if(mas1[i][y]=='Y')
                                mas[j+mas2[y]+mas2[i]]=mas[j]+1;
                        }
                }
            }
        for(j=0; j<n; j++)
            if(mas1[i][j]=='Y')
                mas[mas2[j]+mas2[i]-1]=1;
    }
    int max=0;
    for(i=0; i<262144; i++)
        if(mas[i]>max)
            max=mas[i];
    printf("%d", max*2);
    return 0;
}
эта задача на динамику. вся проблемма в том как оформить варианты (их здесь 262143) задействованных уже комьютеров.
когда-то мне попался такой алгоритм (подходящий для этой задачи):
1 2 3 4 5 6 .... 18 <- номера комьютеров
1 2 4 8 16 32 .... 131072 <- степени 2-ки (начиная со степени 0)
теперь можно одним числом "зашифровать", какие компьютеры уже задействованы.
Например число 13:
№№ компьютеров - 4 (степень двойки равна 8), 3 (степень двойки равна 4), 1 (степень двойки равна 1). Здесь сумма степеней двоек равна 13 и никакого другого варианта для числа 13 Вы не сможете подобрать.
В общем такое "шифрование" и есть основа кода. Что еще не понятно, спрашивайте.
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
22.10.2011, 19:58     Задача «NetWork» #3
Олимпиадная задача
Yandex
Объявления
22.10.2011, 19:58     Задача «NetWork»
Ответ Создать тему
Опции темы

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