Программирование на языке C в Microsoft Visual Studio 2010 - тест 18

Какая рекурсия называется прямой?

Какие утверждения являются верными?

Какие утверждения являются неверными?

Какое достоинство имеет использование рекурсии?

Какие достоинства имеет использование рекурсии?

Какие утверждения являются верными?

В каком случае вычисление факториала выполняется с помощью рекурсивной функции?

В каком случае для вычисления факториала не используется рекурсия?

Задана функция вычисления факториала:
		
long fact(long n) 
{
	if (n==0 || n==1) return 1;
	return (n * fact(n-1));
}

Какое утверждение является верным?
		

Задана функция вычисления факториала:
		
long fact(long n) 
{
	return (n>1) ? n * fact(n-1) : 1;
}

Когда завершится рекурсивный процесс?
		

Задана функция вычисления факториала:
		
long fact(long n) 
{
	return (n>1) ? n * fact(n-1) : 1;
}

При каком значении завершится рекурсивный процесс?
		

Задана функция вычисления факториала:
		
long fact(long n) 
{
	return (n>1) ? n * fact(n-1) : 1;
}

Какое утверждение является неверным?

Что такое глубина рекурсии?

Что такое текущий уровень рекурсии?

Что такое базовый уровень рекурсии?

В какой программе используется косвенная рекурсия?

В какой программе используется прямая рекурсия?

Какие утверждения являются верными для приведенной программы?

void fillOnly(int);
void free_n(int);
void fill_n(int);

int main (void)
 {
	int n = 1; 
	int in = 1; 

	printf("\n Enter a length of string (naturel number): ");
	in = scanf_s("%i", &n);

	if (in != 1 || n < 1 || n > 15)
     {
		printf("\n Error input. Press any key to exit: ");
		_getch();
		exit(0);
	}
	puts("\n\tResult:");

	fill_n(n);

	printf("\n\n Press any key to exit: ");
	_getch();
	return 0;
}

void fillOnly(int n) {
	if (n == 1)
		printf("\t%+3d\n", 1);
	else {
		fillOnly(n-1);
		printf("\t%+3d\n", n);
		free_n(n-1);
	}
}

void free_n(int n)
 {
	if (n == 1)
		printf("\t%+3d\n", -1);
	else {
		fillOnly(n-1);
		printf("\t%+3d\n", -n);
		free_n(n-1);
	}
}

void fill_n(int n)
 {
	if (n == 1)
		printf("\t%+3d\n", 1);
	else {
		if (n == 2)
			printf("\t%+3d\n\t%+3d\n", 1, 2);
		else {
			fillOnly(n-1);
			printf("\t%+3d\n", n);
			fill_n(n-2);
		}
	}
}
		
		

Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала - выполняется еще один шаг. Поскольку текущая точка может быть соединена с несколькими другими, то сначала выбирается точка с наименьшим номером. Для решения задачи задана программа (для появснения в программе приведены комментарии):

#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);?
		

Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала - выполняется еще один шаг. Поскольку текущая точка может быть соединена с несколькими другими, то сначала выбирается точка с наименьшим номером. Определите, выполняет ли приведенная программа поставленную задачу (для появснения в программе приведены комментарии):

#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;
			}
	}
}

Необходимо решить задачу поиска пути между двумя городами. Карта дорог представлена в виде графа: Процесс поиска представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в котороую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала - выполняется еще один шаг. Поскольку текущая точка может быть соединена с несколькими другими, то сначала выбирается точка с наименьшим номером. Для решения данной задачи задана программа (для появснения в программе приведены комментарии):

#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=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[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) {
				// точка соединена с текущей и не включена в маршрут
				road[p] = c;		// добавление вершины в путь
				incl[c] = 1;		// пометка вершины как включенной
				step(c, f, p+1);
				incl[c] = 0;
				road[p] = 0;
			}
	}
}

Какие утверждения являются неверными для приведенной программы?

Необходимо написать программу, которая будет определять, является ли заданная строка палиндромом (палиндром - это слово, которое читается одинаково слева направо и справа налево). Решение данной задачи основывается на просмотре строки одновременно слева направо и справа налево и сравнении соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом. Какая программа выполняет поставленную задачу?

Приведенная программа должна определять, является ли заданная строка палиндромом (палиндром - это слово, которое читается одинаково слева направо и справа налево). В программе выполняется просмотр строки одновременно слева направо и справа налево и сравнение соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом:

char s[100];
int pal(char s[100]);

int main()
{ 
	printf("\nВведите строку: "); 
	gets(s);
	if (pal(s)) printf("Строка является палиндромом");
	else  printf("Строка не является палиндромом");
	return 0;
}

int pal(char s[100])
{ 
	int l; char s1[100];
	
	if (strlen(s) = 1) return 1;
	else {
		l=s[0]==s[strlen(s)-1];
		strncpy(s1, s+1, strlen(s)-2);
		s1[strlen(s)-2]='\0';
		return l&&pal(s1);
	}
}
	
Выполняет ли программа поставленную задачу?		
		

Приведенная программа должна определять, является ли заданная строка палиндромом (палиндром - это слово, которое читается одинаково слева направо и справа налево). В программе выполняется просмотр строки одновременно слева направо и справа налево и сравнение соответствующих символов. Если в какой-то момент символы не совпадают, делается вывод о том, что строка не является палиндромом, если же удается достичь середины строки и при этом все соответствующие символы совпали, то строка является палиндромом:

char s[100];
int pal(char s[100]);

int main()
{ 
	printf("\nВведите строку: "); 
	gets(s);
	if (pal(s)) printf("Строка является палиндромом");
	else  printf("Строка не является палиндромом");
	return 0;
}

int pal(char s[100])
{ 
	int l; char s1[100];
	
	if (strlen(s)<1) return 1;
	else {
		l=s[0]==s[strlen(s)-1];
		strncpy(s1, s+1, strlen(s)-2);
		s1[strlen(s)-2]='\0';
		return l&&pal(s1);
	}
}
	
Какое граничное условие имеет реализованная в программе рекурсия?		
		

Какая программа верно вычисляет сумму элементов массива с помощью рекурсии?

Что произойдет при выполнении программы?

int summa(int N, int a[6]);

int main()
{
	int i,n;
	int a[6] = {8, 65, 10, 2, 4, 1};
	n = sizeof(a)/sizeof(a[0]);
	printf("Сумма: %d", summa(n-1, a));
}

int summa(int N, int a[6])
{
	return a[N]+summa(N-1, a);
}
			
		

Что произойдет при выполнении программы?

int summa(int N, int a[6]);

int main()
{
	int i,n;
	int a[6] = {8, 65, 10, 2, 4, 1};
	n = sizeof(a)/sizeof(a[0]);
	printf("Сумма: %d", summa(n-1, a));
}

int summa(int N, int a[6])
{
	if (N==0) return a[0]; 
	else return a[N]+summa(N-1, a);
}
			
		

Какие новые объекты создаются при рекурсивном вызове функции?

Какое утверждение являотся верным?

Какие утверждения являются неверными?

Задана функция вычисления факториала:

long fact (int n){
    if ( n<1 ) return 1;
    else return n*fact(n-1);
} 
	
Какой будет последовательность вызов, если в функции main задать long result=fact(3)?
		

 (1)  

 (2)  

 (3)  

Задана функция вычисления факториала:

long fact (int n){
    if ( n<1 ) return 1;
    else return n*fact(n-1);
} 
	
Какая последовательность вызовов будет неверной, если в функции main задать long result=fact(3)?
		

 (1)  

 (2)  

 (3)  

В функции main выполняется вызов рекурсивной функции fact(): long result=fact(3). Вызовы функции выполняются в приведенной последовательности: Каким образом должна выглядеть функция fact()?
		

Какие из перечисленных задач могут быть решены с помощью рекурсии?

В арифметической прогрессии каждый следующий член равен предыдущему, увеличенному на разность прогрессии: a{i} = a{i-1} + d. Приведенная программа содержит рекурсивную функцию для вычисления заданного члена арифметической прогрессии:

int Sum(int x, int step, int n)
{ 
        if (n==1) return(x);
        else return(Sum(x, step, n-1)+step);
}

int main()
{ 
        int x, s, n;
		int pr;
		printf("Введите первый член, число элементов и разность прогрессии:");
		scanf("%d %d %d", &x, &n, &s);
        <Вызов функции sum()>
		printf("pr = %d", pr);
		return 0;
} 

Пользователь вводит данные для вычисления через пробел в следующей последовательности: первый член арифметической прогрессии, разность прогрессии, количестов элементов. В какой последовательности эти параметры должны быть заданы при вызове рекурсивной функии sum()?		

В арифметической прогрессии каждый следующий член равен предыдущему, увеличенному на разность прогрессии: a{i} = a{i-1} + d. Приведенная программа содержит рекурсивную функцию для вычисления заданного члена арифметической прогрессии:

int Sum(int x, int step, int n)
{ 
        if (n==1) return(x);
        else return(Sum(x, step, n-1)+step);
}

int main()
{ 
        int x, s, n;
		int pr;
		printf("Введите первый член, число элементов и разность прогрессии:");
		scanf("%d %d %d", &x, &n, &s);
        <Вызов функции sum()>
		printf("pr = %d", pr);
		return 0;
} 

Пользователь вводит данные для вычисления через пробел в следующей последовательности: первый член арифметической прогрессии, разность прогрессии, количестов элементов. Какая последовательность задания этих параметров является неверной для вызова рекурсивной функии sum()?