Главная /
Программирование на языке C в Microsoft Visual Studio 2010 /
Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: [картинка]Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно поп
Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала - выполняется еще один шаг. Поскольку текущая точка может быть соединена с несколькими другими, то сначала выбирается точка с наименьшим номером. Для решения задачи задана программа (для появснения в программе приведены комментарии):
#define N 8
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=1; i<=N; i++) road[i] = 0;
for (i=1; i<=N; i++) incl[i] = 0;
for (i=1; i<=N; i++)
for (j=1; j<=N; j++) map[i][j] = 0;
// ввод значений элементов карты
map[1][2] = 1; map[2][1] = 1;
map[1][3] = 1; map[3][1] = 1;
map[1][4] = 1; map[4][1] = 1;
map[3][4] = 1; map[4][3] = 1;
map[3][7] = 1; map[7][3] = 1;
map[4][6] = 1; map[6][4] = 1;
map[5][6] = 1; map[6][5] = 1;
map[5][7] = 1; map[7][5] = 1;
map[6][7] = 1; map[7][6] = 1;
printf("Введите через пробел номер начальной и конечной точек: ");
scanf("%d %d", &start, &finish);
road[1] = start; // внести точку в маршрут
incl[1] = 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=1; i<=p-1; i++) printf("%d ", road[i]);
printf("\n");
}
else {
// выбор очередной точки
for (c=1; c<=N; c++)
// проверка всех вершин
if (map[s][c]!=0 && incl[c]==0) {
// точка соединена с текущей и не включена в маршрут
<Рекурсивный вызов - вариант 1>
road[p] = c; // добавление вершины в путь
incl[c] = 1; // пометка вершины как включенной
<Рекурсивный вызов - вариант 2>
incl[c] = 0;
road[p] = 0;
<Рекурсивный вызов - вариант 3>
}
}
}
В каком из отмеченных мест программы необходимо выполнить рекурсивный вызов функции step(c, f, p+1);
?
вопрос
Правильный ответ:
в строке
Рекурсивный вызов - вариант 1
в строке
Рекурсивный вызов - вариант 2
в строке
Рекурсивный вызов - вариант 3
Сложность вопроса
82
Сложность курса: Программирование на языке C в Microsoft Visual Studio 2010
62
Оценить вопрос
Комментарии:
Аноним
Спасибо за тесты по интуиту.
31 авг 2020
Аноним
Зачёт сдал. Мчусь отмечать отмечать победу над тестом интут
10 сен 2016
Аноним
Если бы не данные ответы - я бы не осилил c этими тестами intuit.
19 май 2016
Другие ответы на вопросы из темы программирование интуит.
- # Какая локальная переменная, заданная в приведенном фрагменте кода, располагается в сегменте данных и существует все время, пока работает программа? int test(); int a = 1; int main (void) { int b, s; extern int x; static int c; s = test(); return 0; } int test() { int t = a; return t; } int x = 4;
- # Чему будет равно значение переменной f при попытке пользователя вычислить значение 5^6? int a, b, res = 0; char op; int f = 1; printf("Введите 1й операнд: "); scanf("%d", &a); printf("Введите знак операции: "); scanf("%s", &op); printf("Введите 2й операнд: "); scanf("%d", &b); switch (op) { case '+': res = a+b; break; case '-': res = a-b; break; case '*': res = a*b; break; case '/': res = a/b; break; default: printf("Неизвестная операция\n"); f = 0; } f = f*2; if (f) printf ("Результат: %d", res);
- # Чему будет равно значение переменной i в результате выполнения приведенной программы? #include <stdio.h> #define N 10 #define M 5 int main() { int i; int arr1[N] = {3, 4, 5, 4}; int arr2[M] = {1, 6, 3, 7, 9}; i = sizeof(arr1)/sizeof(arr1[0]) + sizeof(arr2)/sizeof(arr2[0]); printf("i = %d\n", i); return 0; }
- # В результате выполнения какой программы на экран будут выведены числа от 1 до 10 и для каждого числа его квадрат?
- # Требуется написать программу, которая копирует введенную пользователем строку str1 в строку str2 в обратном порядке. Например, если пользователь ввел строку string, то str2 в результате выполнения данной программы должна быть равна gnirts. Какая программа выполняет поставленную задачу?