1 / 1 / 0
Регистрация: 20.11.2009
Сообщений: 21
1

Вывести все возможные маршруты

17.05.2010, 14:08. Показов 834. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Правда сложная, сложнее чем кажется на первый взгляд.
Сам уже отчаялся, самые толковые одногруппники разводят руками,
препод сама признала что мое задание на порядок сложнее чем у остальных
(цель работы - показать что умеешь работать с файлами), но менять отказалась.
Этот форум - последняя надежда =(

Собственно условия:

Из файла заполняется структура:
-Улица
-Кол-во перекрестков
-Список Улиц, с которыми пересекается.

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

Вот, что смог сам реализовать:

Первый файл выглядит так: (Улицы назвал тупо цветами)
C
1
2
3
4
5
6
7
6
White 1 Red
Black 2 Red Green
Blue 2 Green Yellow
Yellow 2 Blue Red
Green 3 Black Blue Red
Red 4 White Yellow Green Black
Сама структура:
C
1
2
3
4
5
typedef struct  {
       char TN[20];                       //Улица
       int R;                                 //Перекрестки
       char Rist [20][20];               //Список пересекающих
}TANAV;
Прога:
C
1
2
3
4
5
6
7
    int i, j, k, N;
    char ALG[20], OTS[20],;          //Начало и конец
    FILE *F1, *F2;                       //Сами файлы
    TANAV tlist[100];
    
    F1 = fopen ("F1.txt", "r");
    F2 = fopen ("F2.txt", "w");
Вот так считывает:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
fscanf(F1, "%d", &N);             // N - вспомогательная переменная, ей обозначил общее кол-во улиц
for (i=0;i<N;i++) {
     fscanf (F1, "%s", tlist[i].TN);
     fscanf (F1, "%d", &tlist[i].R);
     for (j=0;j<tlist[i].R;j++) {
         fscanf (F1, "%s", tlist[i].Rist[j]);
     }
}
 
    printf ("Enter the street you start form: ");           //Запрос начала
    scanf ("%s", ALG);
    printf ("Enter the street you start form: ");           //Запрос конца
    scanf ("%s", OTS);
А вот с алгоритмом решения уже проблемы:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
F2 = fopen ("F2.txt", "w");
fprintf (F2, "Here are all the avaliable routes from street %s to %s: \n\n", ALG, OTS);
    
    for (i=0;i<N;i++){
        if (strcmp(tlist[i].TN, ALG)==0) {     // Находит нужную начальную улицу
           fprintf (F2, "%s", tlist[i].TN);       // Выводит в файл как начало маршрута
           for (j=0;j<tlist[i].R;j++){
               if (strcmp(tlist[i].Rist[j], OTS)==0){           //Проверяет, имеется ли нужный конечный пункт
                      fprintf (F2, ", %s\n.", tlist[i].Rist[j]);   // добавляет его к маршруту
               }
           }
    }
    fclose(F1);
    fclose(F2);
}
Этот кусок выводит маршрут только в случае, если улицы и так пересекаются.

По идее, далее надо сделать замену начальной улицы на ту, с которой пересекается первой
и запускать по-новой цикл, потом еще раз, но убедившись, что эту улицу мы уже проверяли.
Но как это сделать я без понятия.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.05.2010, 14:08
Ответы с готовыми решениями:

Вывести все возможные перестановки слов в предложении
Условие: С клавиатуры вводится предложение, слова в котором разделены символом подчеркивания....

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

Перебрать все возможные суммы элементов массива
Подскажите, пожалуйста, как перебрать все возможные суммы элементов массива. Допустим на вход...

Реализовать все возможные операции для очереди
Доброго времени суток) кому не составит большого труда, прошу помочь с заданием) Реализовать все...

3
Эксперт С++
1936 / 1048 / 109
Регистрация: 29.03.2010
Сообщений: 3,167
17.05.2010, 14:17 2
Задание действительно сложное и интересное, почитайте алгоритм задачи коммивояжера, вот ссылка: http://ru.wikipedia.org/wiki/%... 1%80%D0%B0
ЗЫ: мой однокурсник, сдавал эту задачу в качестве дипломного проекта
1
1 / 1 / 0
Регистрация: 20.11.2009
Сообщений: 21
17.05.2010, 14:33  [ТС] 3
Жесть. Я еще на первом =(

Хотя у меня не совсем такая, мне длинну каждой из улиц учитывать не надо...
0
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
17.05.2010, 15:09 4
В сущности, у вас задан граф улиц и две его вершины, между которыми нужно найти все возможные элементарные пути, т.е. пути, вершины в которых не повторяются. Это гораздо проще задачи коммивояжера.
0
17.05.2010, 15:09
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2010, 15:09
Помогаю со студенческими работами здесь

Собрать в другой массив все возможные комбинации исходного
Всем привет, помогите, пожалуйста. Есть массив строк char *mS={&quot;Один&quot;, &quot;Два&quot;, &quot;Три&quot;,...

Файл: Заменить в файле все возможные слова их синонимами
Даны 2 текстовых файла. Первый файл содержит произвольный текст, а слова в тексте разделены...

Определить все возможные перестановки символов в данной строке
Добрый день, имеется рекурсивный код, задача которого определить все возможные перестановки...

Для заданного n получить все возможные перестановки чисел 1,2,...n
Подскажите, как решается эта задача. Для заданного n получить все возможные перестановки чисел...


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

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

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