[C++知识库]面试算法 - 经典面试编程题目

1.求斐波那契数列的第 n 项的值

斐波那契数列的定义如下：

斐波那契数列的前十个数如下：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

思路：第一，二个数是0，1。第三个数是第一，二个数的相加。第n个数是第n-1，n-2个数的

相加。

代码示例：

#include<stdio.h>
 
int fibonacci(int n)
{
	int f0 = 0, f1 = 1, f, i;
	if(0 == n) return 0;
	if(1 == n) return 1;
	for(i = 2; i <= n; i++)
	{
		f = f0 + f1;	//由前两步的结果得到当前结果
		f0 = f1;		//把原来的前一步当作下一次的前两步
		f1 = f;			//在进行这种向前传递时,注意传递的时序
	}
	return f;
}
void main()
{
	int n;
	printf("你要求fibonacci数列的第几项的值,请输入:");
	scanf("%d", &n);
	printf("f(%d) = %d \n", n, fibonacci(n));
}

2.判断从101到200间有多少个素数，并输出

素数：除了1和本身之外，不能被其他数整除。

#include<stdio.h>
int main(){
  int m,i,j;
  for(i=101;i<=200;i++){
	   for(j=2;j<i;j++){
   		if(i%j==0){
		   	break;
		   }else{
   	    	if(j==i-1){
	    	   	printf("%d  ",i);
 	        }
   		}	   
   	} 
  }
	return 0;
}

3.对于一个字符串，设计一个算法，将包括i位置在内的左侧部分移动到右边，将右侧部分移动到

左边。给定字符串A和它的长度n以及特点位置p，请返回旋转后的结果。

#include<stdio.h>
#include <string.h>

void change(char * a,char *b,int m,int n)
{
   int i = 0;
   n++;

   while(a[i] != '\0')
   {
     b[i] = a[n+i];
     i++;
   }

   for(i = 0; i < n;i++)
   {
     b[m-n+i] = a[i];
   }
     b[m] = '\0';
}


int main()
{
  char a[20] = "abcdefghijk";
  char b[20] ;
  change(a,b,11,9);
  printf("%s\n",b);
  return 0;
} 

4.C语言递归实现n的阶乘（n!）

非负整数n的阶乘可以表示为n! (读作：n的阶乘），其定义如下：
n! = n·(n - 1)? (n - 2)· …·1 (n大于或等于l)，且n = 0时，n! = l
例如，5 ! = 5·4·3·2·1 = 120。
请编写一个程序，读入一个非负整数，计算并输出其阶乘。

思路: 阶乘 就是每次用自己乘以自己-1，然后用自己-1在乘自己-1-1……利用递归的性质可以很好的实现这个过程。

#include <stdio.h>

int factorial(int x)
{
	
	if (x == 0 )
	{
		return 1;
	}
	else 				
		return x*factorial(x-1);
}

int main(int argc, char const *argv[])
{
	int s;
	scanf("%d",&s);
	factorial(s);
	printf("%d! is %d\n",s,factorial(s));
	return 0;
}

5.输入两个正整数 m 和 n，求其最大公约数和最小公倍数

#include<stdio.h>
int main(void)
{
	int m,n;
 	int t;
	int r;
	int product;
	
	printf("请输入2个正整数(空格分隔):");
	scanf("%d %d",&m,&n);
	 
	if(m < n) { //当 m 较小时，将 m 和 n 互换
		t = m;
		m = n;
		n = t;
	}
	 
	product = m * n;
	while(1) {
	  	r = m % n;
		if(r == 0) {
	 		printf("最大公约数是：%d\n最小公倍数是:%d\n",n,product/n);
		   	break;
		}
		else {
			m = n;
			n = r;
	  	} 
	}
 	return 0;
}

6.输入一串字符串和一个字符，统计该字符串中指定字符出现的个数

#include<stdio.h>
#include<string.h>

main()
{	
    char str[100],c;
	int i=0,count=0;
	printf("请输入一个字符串：");
	gets(str);
	printf("请输入指定的查找字符：");
	scanf("%c",&c);
	while(str[i]) /*该循环扫描/遍历字符数组*/
	{	
        if(str[i]==c)
		  count++;
		  i++; 
	}
	printf("%d\n",count);
}