Главная /
Программирование на языке C в Microsoft Visual Studio 2010 /
Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: [картинка]Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно поп
Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала - выполняется еще один шаг. Поскольку текущая точка может быть соединена с несколькими другими, то сначала выбирается точка с наименьшим номером. Определите, выполняет ли приведенная программа поставленную задачу (для появснения в программе приведены комментарии):
#define N 7
void step(int, int, int);
int map[N][N]; // карта: map[i,j]!=0, если точки i и j соединены
int road[N]; // маршрут - номера точек карты
int incl[N]; // incl[i]==1, если точка с номером i включена в road
int start; // начальная точка маршрута
int finish; // конечная точка маршрута
int i, j;
int main (void) {
// инициализация массивов
for (i=0; i<N; i++) road[i] = 0;
for (i=0; i<N; i++) incl[i] = 0;
for (i=0; i<N; i++)
for (j=0; j<N; j++) map[i][j] = 0;
// ввод значений элементов карты
map[0][1] = 1; map[1][0] = 1;
map[0][2] = 1; map[2][0] = 1;
map[0][3] = 1; map[3][0] = 1;
map[2][3] = 1; map[3][2] = 1;
map[2][6] = 1; map[6][2] = 1;
map[3][5] = 1; map[5][3] = 1;
map[4][5] = 1; map[5][4] = 1;
map[4][6] = 1; map[6][4] = 1;
map[5][6] = 1; map[6][5] = 1;
printf("Введите через пробел номер начальной и конечной точек: ");
scanf("%d %d", &start, &finish);
road[0] = start; // внести точку в маршрут
incl[0] = 1; // пометить точку как включенную
step(start, finish, 2);
return 0;
}
void step(int s, int f, int p) {
int c; // номер точки, в которую делается очередной шаг
int i;
if (s==f) {
printf("Путь: ");
for (i=0; i<p-1; i++) printf("%d ", road[i]);
printf("\n");
}
else {
// выбор очередной точки
for (c=0; c<N; c++)
// проверка всех вершин
if (map[s][c]!=0 && incl[c]==0) {
// точка соединена с текущей и не включена в маршрут
road[p] = c; // добавление вершины в путь
incl[c] = 1; // пометка вершины как включенной
step(c, f, p+1);
incl[c] = 0;
road[p] = 0;
}
}
}
вопрос
Правильный ответ:
программа не выполняет поставленную задачу, так как в ней используется неверная индексация массива
программа не выполняет поставленную задачу, так как неверно задана рекурсивная функция
программа выполняет поставленную задачу
Сложность вопроса
58
Сложность курса: Программирование на языке C в Microsoft Visual Studio 2010
62
Оценить вопрос
Комментарии:
Аноним
Я помощник профессора! Немедленно заблокируйте этот ваш сайт с ответами на интуит. Немедленно!
27 июн 2019
Аноним
Я помощник профессора! Прямо сейчас сотрите сайт vtone.ru с ответами по интуит. Это невозможно
21 фев 2019
Аноним
Я провалил экзамен, какого чёрта я не нашёл этот чёртов сайт с решениями с тестами intuit до этого
21 ноя 2017
Другие ответы на вопросы из темы программирование интуит.
- # Функция swap() имеет два аргумента-указателя и выполняет обмен значений элементов: void swap(int *pa, int *pb) { int temp; temp = *pa; *pa = *pb; *pb = temp; } В каком случае вызов функции swap() осуществляется неверно?
- # Каким образом должен быть подключен файл some.h, находящийся на два уровня выше, чем главный файл?
- # Какие утверждения являются верными?
- # Почему доступ к элементам многомерного массива происходит значительно медленнее, чем к элементам одномерного?
- # Какое утверждение является верным для динамически распределяемой памяти?