IT公司面试题收集整理-C相干-八皇后和斐波那契数列【递归的常用小程序】

IT公司面试题收集整理---C相关---八皇后和斐波那契数列【递归的常用小程序】

1.N!的递归算法

#include<stdio.h>
int find(int n)
{
	if(n==1){
		return 1;
	}else{
		return find(n-1)*n;
	}
}
int main(void)
{
	int n;
	printf("请输入N!中的N值：");
	scanf("%d",&n);
	printf("%d\n",find(n));
	return 0;
}

2.斐波那契数列1

#include<stdio.h>
int f(int n)
{
	if(n<1){
		return 0;
	}else if(n==1||n==2){
		return 1;
	}else{
		return f(n-1)+f(n-2);
	}
}
int main(void)
{
	int n,i;
	printf("请输入斐波那契数列个数n：");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		printf("%d ",f(i));
	printf("\n");
	return 0;
}

3.斐波那契数列2

#include<stdio.h>
int N;
int PRE=1;
int AFTER=1;
int RESULT=0;
/*时间复杂度最低*/
int main(void)
{
	int n,i;
	printf("请输入斐波那契数列个数n：");
	scanf("%d",&n);
	N=n;
	printf("1 1 ");
	for(i=2;i<n;i++)
	{
		RESULT=PRE+AFTER;
		PRE=AFTER;
		AFTER=RESULT;
		printf("%d ",RESULT);
	}
	printf("\n");
	return 0;
}

4.斐波那契数列3

#include<stdio.h>
int N;
int PRE=1;
int AFTER=1;
int RESULT=0;
/*递归控制循环的斐波那契数列*/
int f(int n)
{
	if(n>2){
		f(n-1);
		RESULT=PRE+AFTER;
		PRE=AFTER;
		AFTER=RESULT;
		printf("%d ",RESULT);
	}else{
		printf("1 1 ");
	}
	return RESULT;
}
int main(void)
{
	int n;
	printf("请输入斐波那契数列个数n：");
	scanf("%d",&n);
	N=n;
	f(n);
	printf("\n");
	return 0;
}

5.汉诺塔问题

#include<stdio.h>
void hannuo(int n,char x,char y,char z)
{
	if(n==1)
		printf("%c->%c\n",x,z);
	else
	{
		hannuo(n-1,x,z,y);
		printf("%c->%c\n",x,z);
		hannuo(n-1,y,x,z);
	}
}

int main(void)
{
	int n;
	printf("请输入汉诺塔的层数：");
	scanf("%d",&n);
	printf("汉诺塔的步骤为：\n");
	hannuo(n,'A','B','C');
	return 0;
}

6.八皇后问题

#include <stdio.h>
#define ROW 8
#define COL 8
#define NUM 8
int a[ROW][COL];
int k = 0;
int put( int n)
{
	int i, j;
	//输出八皇后棋盘
	if( n > NUM)
	{
		printf( "----------%06d----------\n", ++k);
		for( i = 0; i < ROW; i ++)
		{
			for( j = 0; j < COL; j ++)
				printf( "%s  ", a[i][j] == 1 ? "○" : "●");
			printf( "\n\n");
		}
		printf( "--------------------------\n\n");
		return -1;
	}
	// 尝试行中的每个位置
	for( j = 0; j < COL; j ++)
	{
		int flag = 0;
		for( i = 0; i < n - 1; i ++)
		{
			// 是否同列
			if( a[i][j] == 1)
			{
				flag = 1;
				break;
			}
			// 是否左斜角
			if( j - ( n - 1 - i) >= 0 && a[i][j - ( n - 1 - i)] == 1)
			{
				flag = 1;
				break;
			}
			// 是否右斜角
			if( j + ( n - 1 - i) < COL && a[i][j + ( n - 1 - i)] == 1)
			{
				flag = 1;
				break;
			}
		}
		if( flag == 0)
		{
			a[n-1][j] = 1;
			if( put( n + 1) == -1)
			{
				a[n-1][j] = 0;
			}else
				return 0;
		}
	}
	return -1;
}
int main()
{
	put(1);
	return 0;
}