recursion_loop.cpp

我自己写的vc数据结构的作业

#include <iostream>
#include <string>

using namespace std;

static long Factorial(const long n)       //求阶乘n!
{
	return (0==n || 1==n)?1:n*Factorial(n-1);
}

static long Fib(const long n)             //斐波那契数列
{
	return (0==n || 1==n)?1:Fib(n-1)+Fib(n-2);
}

static void PrintFibArray(long number,long first=1,long second=1)
{
	long* f=new long[number+1];
	f[0]=first;
	f[1]=second;
	for(int i=2;i<=number;i++)
		f[i]=f[i-2]+f[i-1];

	cout<<"输出斐波那契数列："<<endl;
	cout<<"firstNum="<<first<<",secondNum="<<second<<"个数n="<<number<<endl;
	for(int i=0;i<=number;i++)
		cout<<f[i]<<' ';
	cout<<endl;
}


//著名的汉诺塔问题
static void Move(const char x, const int n, const char z)
{
	cout<<"把圆盘"<<n<<" 从柱子 "<<x<<" 移动到 "<<z;
	cout<<endl;
}

static void Hanoi(const int n, const char x, const char y, const char z)
{
    if (1 == n)
        Move(x, 1, z);          // 如果只有一个盘，则直接将它从x移动到z
    else
    {
        Hanoi(n - 1, x, z, y);  // 把1 ~ n - 1个盘从x移动到y，用z作为中转
        Move(x, n, z);          // 把第n个盘从x移动到z
        Hanoi(n - 1, y, x, z);  // 把1 ~ n - 1个盘从y移动到z，用x作为中转
    }
}

//杨辉三角问题
static long GetElement(const long row, const long col)
{
    // 每行的外围两个元素为1
    if ((1 == col) || (row == col))
        return 1;
    else
        // 其余的部分为上一行的(col - 1)和(col)元素之和
        return GetElement(row - 1, col - 1) + GetElement(row - 1, col);
}

static void PascalTriangle(const long n)
{
    int row;
    int col;

    for (row = 1; row <= n; ++row)
    {
        for (col = 1; col <= row; ++col)
			cout<<GetElement(row,col)<<'\t';
		cout<<endl;
    }
}

int main()
{
	cout<<"求n的阶乘"<<endl;
	long result=Factorial(10);
	cout<<"n!="<<10<<"!="<<result<<endl;

	cout<<endl<<"求斐波那契数"<<endl;
	result=Fib(10);
	cout<<"Fib("<<10<<")="<<result<<endl;

	cout<<endl<<"打印斐波那契数列"<<endl;
	PrintFibArray(10);

	cout<<endl<<"求解汉诺塔问题"<<endl;
	Hanoi(3,'X','Y','Z');

	cout<<endl<<"打印杨辉三角"<<endl;
	PascalTriangle(5);

	return 0;
}