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

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

Войти
Регистрация
Восстановить пароль
 
Includenv
Сообщений: n/a
#1

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

22.10.2011, 14:23. Просмотров 657. Ответов 2
Метки нет (Все метки)

Интересует именно идея. Код писать не надо.

Условие
В компьютерной сети вашей фирмы 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++):

работа с SNMP (Simlpe network menegement protocol) - C++
SNMP Ребята может кто работал с этим протоколом подскажите как его обрабатывать в Borland или подкинте примеры по работе с SNMP а то...

network development kit - C++
Пожалуйста, помогите разжиться какой-нибудь информацией по теме. Может у кого есть инфа, подскажите где посмотреть. Может гайд какой или...

Qt Network - C++ Qt
Кто работал с плюшками network-a? сейчас начал смотреть всякие QNetworkAccessManager, QNetworkConfigurationManager и т.п. плюшки, пришел...

Network Shield - Удаление вирусов
Добрый день! Проблема в том, что AVAST Business Protection 6.0.1373 выдает вирус в Network Shield: Last blocked connection:...

Guest network - Cisco
Добрый день! Есть гостевая wi-fi сеть, отдельный влан, он изолирован от всех внутренних адресов, только выход в инет.Интернет работает,...

VMWare network - Сети
Прошу прощения если ошибся разделом. Вся проблема в том, что мне нужно чтобы на виртуальной машине был интернет, на самом компе стоит...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.10.2011, 19:56 #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
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
22.10.2011, 19:58 #3
Олимпиадная задача
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2011, 19:58
Привет! Вот еще темы с ответами:

Affiliates network - PHP
Приветствую господа. вопрос такой: кто-нибудь из вас стыкался с продуктами от http://www.alstrasoft.com а именно с Affiliate Network Pro....

Статус PC в network - C++
В сети расположено 2 компьютера clt-pc1 и clt-pc2 , один включен, а другой нет. Не знаю с чего начать писать консольное приложение,...

Unidentified Network - Сети
Unidentified Network. No Internet access -в трее такок сообщение. При подключении сообщение, что модем или другое оборудование...

stat with network - Visual C++
Здравствуйте как заставить функцию stat(это та что показывает сведения о файле) работать через сеть Спасибо


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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