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

Правильно ли работает программа? - C++

Восстановить пароль Регистрация
 
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
20.10.2011, 11:11     Правильно ли работает программа? #1
Программа должна определить маршрут заданной длины из заданной вершины. Но я сомневаюсь в ее правильной работе. Посоветуйте и покритикуйте!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Graph::routeVer(int f, int l)
{
    for(int i = 0; i < n; i++)
    {
        if (a[f][i] == 1)
        {
            f = i;  // вершина
            l--;    //длина
            cout << "Следующая вершина -> " << i + 1 << endl;
        }
 
        if(l == 0)
            break; 
        
        if(i == n-1) 
            i = 0; 
    }
}
Добавлено через 16 часов 18 минут
Кто нибудь знает плз
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.10.2011, 12:48     Правильно ли работает программа? #2
amor1k, Здесь много вопросов. Я не знаю как выглядит матрица смежности в Вашем случае, но маршрут очевидно будет возвращаться и в ранее пройденные вершины (например из первой во вторую, из второй в первую, из первой снова во вторую и т.д.). А если из вершины есть несколько путей, то (см комментарии):
Цитата Сообщение от amor1k Посмотреть сообщение
if (a[f][i] == 1)
{
f = i; // вершина
l--; //длина //вот здесь l неправильно уменьшать
cout << "Следующая вершина -> " << i + 1 << endl;
}
И наконец, если начальная вершина не связана ни с какой другой, то вместо ответа - нет пути, цикл будет бесконечным...
-=ЮрА=-
Заблокирован
Автор FAQ
20.10.2011, 12:52     Правильно ли работает программа? #3
amor1k, давай всё задание, в общем случае алгоритм не верен, мы всё время уменьшаем длинну прохода
Цитата Сообщение от amor1k Посмотреть сообщение
l--
, и почему то считаем что перешли на другую вершину, вобщем хочу посмотреть увязку

Цитата Сообщение от amor1k Посмотреть сообщение
void Graph::routeVer(int f, int l)
в программе. Как я понимаю есть клеточное поле, вершины - это закрашенные клетки, и нам нужно со входа на выход пройти - тут как миним 3 цикла нужно - проход по матрице 2-цикла и возврат к проходу когда от новой вершины проход просчитать нужно, как то так...
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
20.10.2011, 15:37  [ТС]     Правильно ли работает программа? #4
Матрица смежности:
0 1 0 0 0 1 1
1 0 0 0 0 1 1
0 0 0 1 1 1 1
0 0 1 0 1 0 0
0 0 1 1 0 1 1
1 1 1 0 1 0 1
1 1 1 0 1 1 0

Задание и есть полное. Дан неор. граф (надо свой граф по своему множеству, он сверху). А я написал один из 12 пунктов) Если кто может, помогите написать остальные..)
1) определить маршрут заданной длины из заданной вершины
2) цепь между двумя заданными вершинами
3) простую цепь заданной длины из заданной вершины
4) простую цепь двумя заданными вершинами
5) простой цикл содержащий заданную вершину
6) метод определяющий эксцентриситет вершины (максимальное расстояние)
7) расстояние между заданными вершинами
8) метод, определяющий является ли граф связным
9) множество вершин образующие периферию (эксцентриситет равен диаметру)
10) метод, определяющий радиус графа (минимальный эксцентриситет вершин)
11) метод определяющий диаметр (максимальный эксцентриситет из всех)
12) множество вершин, образующих центр графа

ПОМОГИТЕ НАПИСАТЬ ПРОГРАММЫ!!! Или объясните подробно как их делать!! Пожалуйста
-=ЮрА=-
20.10.2011, 16:33
  #5

Не по теме:

amor1k, буду честен мне не хватает теории, это по моему к транспортным задачам относится, пороюсь дома может откопаю расчётку по финансам когда-то делали там похожее для графика работ было...Правда и рад помочь но сам пока думаю как подступиться

amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
20.10.2011, 16:50  [ТС]     Правильно ли работает программа? #6
не не не) Это Теория графов, так называется предмет. Помоему что-то из раздела дискретки... Только у нас в программировании.
-=ЮрА=-
Заблокирован
Автор FAQ
20.10.2011, 17:01     Правильно ли работает программа? #7
amor1k, а есть хоть какая то теория???Ну хоть какую то формулу или выкладку посмотреть, может что и соорудить смогу
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
20.10.2011, 17:28  [ТС]     Правильно ли работает программа? #8
тут есть маленькая теория о графах) http://vuz.exponenta.ru/PDF/teogr.html
вот чуть по лучше http://book.itep.ru/10/grap1021.htm
-=ЮрА=-
Заблокирован
Автор FAQ
20.10.2011, 17:33     Правильно ли работает программа? #9
amor1k, я ничего не обещаю но попробую помочь, если выйдет сегодня/завтра отпишусь в топике!Спасибо за ссылки
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
20.10.2011, 17:54  [ТС]     Правильно ли работает программа? #10
Не за что, надеюсь на вашу помощь)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.10.2011, 17:57     Правильно ли работает программа? #11
Цитата Сообщение от amor1k Посмотреть сообщение
1) определить маршрут заданной длины из заданной вершины
- если маршрутов несколько, вывести любой или все возможные?
- разрешено ли посещать еще раз вершины в которых уже были?
- разрешено ли двигаться по ребрам по которым уже передвигались?
amor1k
Студент
 Аватар для amor1k
147 / 147 / 24
Регистрация: 18.01.2011
Сообщений: 469
20.10.2011, 18:38  [ТС]     Правильно ли работает программа? #12
valeriikozlov, думаю нужно выводить любой, т.к. нужно искать по длине. Я сам еще не понял до конца, но думаю, что нужно показать маршрут как в моем примере.
На счет 2 и 3 пункта (вашего), думаю что нет. Ведь мы же ищем маршрут, а если все время двигаться, то маршрут может быть очень длинным)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.10.2011, 19:33     Правильно ли работает программа?
Еще ссылки по теме:

C++ Не правильно работает программа
C++ Почему программа не работает правильно?
C++ Программа работает не совсем правильно

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.10.2011, 19:33     Правильно ли работает программа? #13
Цитата Сообщение от amor1k Посмотреть сообщение
На счет 2 и 3 пункта (вашего), думаю что нет.
Ну если нет, то что-нибудь такое:
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
#include<iostream>
using namespace std;
int n, a[10][10];
void routeVer(int f, int l, int col, int *mas, bool *mas_kontr)
{
    int i;
    if(col==l+1)
    {
        for(i=0; i<=l; i++)
            cout<<mas[i]<<" ";
        cout<<endl;
        return;
    }
    for( i = 0; i < n; i++)
    {
        if (a[f][i] == 1 && !mas_kontr[i])
        {
            mas_kontr[i]=true;
            mas[col]=i;
            routeVer(i, l, col+1, mas, mas_kontr);
            mas_kontr[i]=false;
        }
    }
}
int main()
{
   freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);  
  scanf("%d", &n);
  int i, j;
  for(i=0; i<n; i++)
  {
      for(j=0; j<n; j++)
          scanf("%d", &a[i][j]);
 
  }
  int mas[10];
  mas[0]=0;
  bool mas1[10];
  for(i=0; i<n; i++)
      mas1[i]=false;
  mas1[0]=true;
  routeVer(0, 3, 1, mas, mas1);// здесь l задал равной 3, можете переделать.
 
  return 0;
}
Yandex
Объявления
20.10.2011, 19:33     Правильно ли работает программа?
Ответ Создать тему
Опции темы

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