学步园

1）斐波那契函数

题目描述：

定义Fibonacci数列如下：  
f(n) = 0                      n=0
f(n) = 1                       n=1,2
f(n) = f(n-1) + f(n-2)       n>2

输入n，用最快的方法求该数列的第n项。
分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。

#include <iostream.h>
int Fibona(int n)
{
    int m;
    if(n==0)
        return 0;
    else if(n==1||n==2)
        return 1;
    else
    {
        m=Fibona(n-1)+Fibona(n-2);
        return m;
    }
}

非递归方法：

#include <iostream>
using namespace std;

int fibonacci(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;

	int a = 0;
	int b = 1;
	int c = 0;
	for (int i = 2; i <= n; i++)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

int main(int argc, char **argv)
{
	int num = fibonacci(10);
	cout << num << endl;

	return 0;
}

2）约瑟夫问题

题目描述：

n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。

这个题目的简单变形：
n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），
凡报到3的人退出圈子，问最后留下的是原来第几号的那个人?

#include <stdio.h>

int main()  
{  
    int i,k,m,n,num[50];  
    printf("input number of person:n=");  
    scanf("%d",&n);  
      
    printf("input number of the quit:m=");     
    scanf("%d",&m);                            
      
	int len = n;
    for (i = 0; i < n; i++)  
        num[i] = i + 1;    //给每个人编号  
    i = 0;   //报数  
	k = 3;
      
    while(n > 1)  
    {
        if(k==3)  
        {
			//退出，对应的数组元素置为0
			num[i] = 0;
            k=0;  
            n--;  
        }  

		if (num[i] != 0)
            k++;  
 
		i = (i + 1) % len;
        
    }  

	for (i = 0; i < len && num[i] == 0; i++)
		printf("The last one is NO: %d\n",i+1);

    return 0;  
} 

另有一种简单的算法，是经过公式、及该问题的规律推导出来的，结果很简单，过程较复杂

#include <stdio.h>
#include <stdlib.h>

int LastRemaining(int n, int m)
{
	if (n <1 || m < 1)
		return -1;
	
	int last = 0;
	for (int i = 2; i <= n; i++)
	{
		last = (last + m) % i;
	}
	return last;
}

int main()
{
	printf("%d\n", LastRemaining(7, 3));

	return 0;
}

Reference

http://blog.csdn.net/v_JULY_v/