Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
This party getting crazy!
78 / 64 / 1
Регистрация: 22.09.2009
Сообщений: 427
1

Выяснить, есть ли среди N населенных пунктов изолированные города

05.03.2010, 14:37. Показов 2083. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Имеются N населённых пунктов (N≤15), и сеть авиалиний, соединяющих эти города. Сеть задана матрицей связности M(N, N), где M(i, j)=0, если города i и j не связаны между собой, и M(i, j)=l - в противном случае. Выяснить, есть ли среди N населенных пунктов изолированные города (такие, в которые нельзя долететь).

Мне препод сделал наброски, но что-то тут криво...помогите разобраться:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void main(void)
{   clrscr();
const int n=5;
int m[n][n];
randomize();
    for (int i=0;i<n;i++)
{printf("\n");
int s=1;
    for (int j=0;j<n;j++)
{m[i][j]=random(2);
  if (i==j) m[i][j]=0;
  if (i>j) m[i][j]=m[j][i];
  if (m[i][j] == 1) s=0;
printf(" %i",m[i][j]);
}
  if (s) printf("  Город %i является изолированным",i+1);
}
getche();     }
Может что-то можно изменить или упростить? помогите пожалуйста!
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.03.2010, 14:37
Ответы с готовыми решениями:

Выяснить, есть ли среди N населенных пунктов изолированные города
Пожалуйста! помогите отладить 2 программы, они рабочие, но в коде есть мелкие ошибки, которые я не...

Оптимальное расположение населенных пунктов
Помогите пожалуйста, не получается. Начало есть,

Справочник населенных пунктов Красноярского края
Создание АИС «Справочник населенных пунктов Красноярского края» со встроенной справочной системой...

Упорядочить название населенных пунктов района по возрастанию их расстояний до райцентра
Помогите написать программу. Упорядочить название населенных пунктов района по возрастанию их...

10
2923 / 844 / 324
Регистрация: 30.04.2009
Сообщений: 2,633
05.03.2010, 14:52 2
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

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
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
void main(void)
{   
   clrscr();
const int n=5;
int m[n][n];
randomize();
    for (int i=0;i<n;i++)
    {
        printf("\n");       
            for (int j=0;j<n;j++)
            {
                m[i][j]=random(2);
                if (i==j) m[i][j]=0;
                if (i>j) m[i][j]=m[j][i];               
                printf(" %i",m[i][j]);
            }       
    }
    
for (int i=0;i<n;i++)
    {       
        int s=0;
            for (int j=0;j<n;j++)
            {
                s+=m[i][j];             
            }
        if (s==0) printf(" Город %i является изолированным \n");
    }
        
getche();     
}
Добавлено через 31 секунду
попробуй так
0
328 / 312 / 68
Регистрация: 05.11.2009
Сообщений: 712
05.03.2010, 16:11 3
да и в первом варианте всё нормально было...
просто вначале надо заполнить матрицу смежности 0 и 1...
далее просто поиск идёт + проверка на то, чтобы на главной диагонали были 0, а также чтобы была правильно составлена матрица смежности
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (int i=0; i<n; i++)
{
    printf("\n");
    int s = 1;
    for (int j = 0; j < n; j++)
    {
        if (i == j) 
            m[i][j] = 0; //самолёт не может летать сам на свой аэродром
        if (i > j) 
            m[i][j] = m[j][i]; // если он летит с А в В, то также летит с В в А
        if (m[i][j] == 1) 
            s = 0;
        printf(" %i", m[i][j]);
    }
    if(s > 0) 
        printf("  Город %i является изолированным",i+1);
}
для примера матрица смежности
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
то здесь изолирован 4-ый город
0
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
05.03.2010, 16:43 4
Ты с этим вот не в одной группе учишься?
https://www.cyberforum.ru/orde... page2.html
Позорники, гнать вас надо метлой поганой из институтов.
0
This party getting crazy!
78 / 64 / 1
Регистрация: 22.09.2009
Сообщений: 427
05.03.2010, 17:26  [ТС] 5
kravam,
нет, я с ним не учусь в одной группе, и даже в одном городе...значит преподы откуда-то берут наши задачи...кстати, его первая у меня тоже есть. Гнать? за что? за то что я прошу помощи как сделать ту или иную задачу, предоставляя при этом определённый кусок кода? или может, за то, что я ради самообразования ищу задачу, нужную мне, или беру чужую, чтобы стать опытнее, сделать себе несколько исходников? Программистами не рождаются, ими становятся. Позорник тот, кто ничего не делает и не стремится к этому, а начинает только хвататся за голову, когда уже жареный петух в жопу клюёт! есть у меня в группе один такой. Думает что всё прокатит, что как в школе будет...хрен! отчислят и всё! А меня к такому списку приписывать не нужно!

Добавлено через 5 минут
kuroiryuu, спасибо большое! ещё вопрос, у меня программа ругается на вот эту строчку
C
1
int m[n][n]
что здесь не так, подскажите пожалуйста.
0
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
05.03.2010, 17:32 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
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h> 
#include <Windef.h>
 
//Сюда будешь писать сколько тебе надо городов, но помни, что N<= 15
#define kolichestvo_gorodov 11
int main () {
 
 int j, k;
 
 
 //Это вот та самая матрица связности. Заполняешь как хочешь. если надо, могу дать прогу для 
 //генерирования подобной хери. кол скоро значения её могут быть либо 0 либо 1, я
 //написал, что она имеет тип BOOL, что круто. И для э того я добавил ещё загроловочный
 //файл Windef.h
 //Если на твоей машине не пройдёт номер с таким типом, скажи мне, я исправлю всё это
 //дело на тип int
 //Что характерно, это матрица просто ОБЯЗАНА быть симметричной относительно диагонали,
 //которая идёт от левого верхнего угла к правому нижнему углу
 
 BOOL N [kolichestvo_gorodov] [kolichestvo_gorodov]= {
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
  0,  1,  1,  1,  0,  1,  1,  0,  0,  1,  0,  
  0,  1,  0,  0,  0,  0,  1,  0,  0,  0,  0,  
  0,  1,  0,  0,  0,  0,  1,  0,  0,  1,  0,  
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
  0,  1,  0,  0,  0,  0,  1,  0,  0,  1,  0,  
  0,  1,  1,  1,  0,  1,  0,  0,  0,  0,  0,  
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
  0,  1,  0,  1,  0,  1,  0,  0,  0,  1,  0,  
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0};  
 
//Это для проверки, можешь расскоментировать и проверить
//А верхний массив закомментировать
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  
//  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1};  
 
//То же самое
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  
//  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0};  
 
 //Решение задачи заключается в том, чтобы найти нулевые столбцы (или строки, без разницы)
 //Номера таких столбцов или строк и будут номерами искомых городов
 //В этот массив будем запихивать номера городов. Теоретически их может быть kolichestvo_gorodov
 //(в нашем случае 11)
 
 int goroda_bez_svazi [kolichestvo_gorodov];
 
 
 //Обязательно обнулим этот массив
 for (int i= 0; i< kolichestvo_gorodov; i++) {
  goroda_bez_svazi [i]= kolichestvo_gorodov;
 }
 
 
 //ПОехали заполнять 
 k= 0;
 for (int i= 0; i< kolichestvo_gorodov; i++) {
  for (j= 0; j< kolichestvo_gorodov && !N [i] [j]; j++) {    }
  if (j== kolichestvo_gorodov)
   goroda_bez_svazi [k++]= i;
 }
 
 
 
 //ВСё, массив сформирован, осталось только вывести его
 //Выводим до первого нулевого элемента или до конца (если все города без связи)
 if (goroda_bez_svazi [0]== kolichestvo_gorodov) {
  printf ("Vse goroda so svazu\n");
  getchar ();
  return 0;
 }
 
 else {
  j= 0;
  printf ("Nomera gorodov bez svazu\n");
  do {
   printf ("%d ", goroda_bez_svazi [j++]);
  }
  while (j!= kolichestvo_gorodov && goroda_bez_svazi [j]!=11); 
 }
 
 printf ("\n");
 getchar ();
 return 0;
}
Добавлено через 2 минуты
И ещё: когда пишешь свой код, скользкие места комментируй.
1
This party getting crazy!
78 / 64 / 1
Регистрация: 22.09.2009
Сообщений: 427
05.03.2010, 17:35  [ТС] 7
а что за identifier PCONTEXT? на него ругается компилятор...и находит кучу ошибок в циклах for в местах () и ; даже не знаю как быть...
0
быдлокодер
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,679
05.03.2010, 17:40 8
К кому вопрос?
Я не нашёл identifier ни в одном из представленных кодов...
0
328 / 312 / 68
Регистрация: 05.11.2009
Сообщений: 712
05.03.2010, 17:44 9
вместо BOOL напишите bool, и убейте #include <Windef.h>
и будет вам счастье
0
анимешник++
95 / 62 / 7
Регистрация: 03.11.2009
Сообщений: 427
06.03.2010, 15:41 10
да все просто - если строка/солбец нулей - то в город нельзя добраться не из одного другого города (матрица симметрична относительно главной диагонали)

Добавлено через 18 часов 47 минут
немного доработал теорию:
В программе 2 ОБЯЗАТЕЛЬНЫХ условия:
1) Программа симметрична относительно главной диагонали. Суждение: если из города i можно добраться в город j, то и из города j можно добраться в город i.
2) Главная диагональ состоит из единиц. Суждение: т.к. i=j в главной диагонали, то из города i можно добраться в город i.

Добавлено через 11 минут
следовательно вот пример на нахождение изолированных городов
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for(int i=0, int ifunc=0;i<N;i++)
{
    for(int j=0;j<N;j++)
    {
        if(i==j) j++;
        if(a[i][j]==1)
        {
            ifunk=1;
            break;
        }
    }
    if(!ifunk) printf("\nGorod %d izolirovan",i+);
}
по-умолчанию все города изолированы (ifunk=0). Если встречает элемент главной диагонали(i==j), то переходит на следующий элемент (в последнй строке тоже должно нормально сработать). Если встретил единицу, то сразу ifunk=1 - город не изолирован и продолжать искать еще что-либо в этой строке не имеет смысла, поэтому break (вот с этим не уверен). Потом, если город изолирован - все элементы, кроме i==о равны нулю, то выводим его номер РЕАЛЬНЫЙ, а не Сишный. т.е. его номер i+1

А вот о вводе симметричной матрицы и главной диагонали уж позаботьтесь сами =))
0
This party getting crazy!
78 / 64 / 1
Регистрация: 22.09.2009
Сообщений: 427
13.03.2010, 11:02  [ТС] 11
Спасибо! а как ваш кусочек можно объединить с кодом kravam'a? а то всё пытаюсь его отладить, а мне куча ошибок идёт( помогите пожалуйста привести код в порядок!
0
13.03.2010, 11:02
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.03.2010, 11:02
Помогаю со студенческими работами здесь

Написать программу Изолированные города(Описание внутри)
В государстве N городов с номерами 1.2….N. Некоторые города связаны между собой дорогами и образуют...

В одном из населенных пунктов, координаты которых приведены в таблице, предполагается установка радиостанции
В одном из населенных пунктов, координаты которых приведены в таблице, предполагается установка...

Определить, сколько населенных пунктов имеет население свыше 500/100/50 тысяч человек
В районе N населённых пунктов, определить сколько нас.пунктов имеет население V свыше 500тс.чел,...

Как задать разную скорость движения до различных населенных пунктов в anylogic при агентном моделировании?
При использовании в программе ГИС карт появляется возможность использовать существующие дороги. Но...

Выяснить, есть ли среди последовательности указанная пара символов
Данная последовательность Символ x1, x2, ..., xn. Выясните, есть ли среди символов этой...

Выяснить, есть ли среди данных 10 чисел точные квадраты
8. Написать программу, выясняющую, есть ли среди данных 10 чисел точные квадраты. Если такие есть,...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru