欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

(算法设计与分析)实验二 熟悉递归算法

程序员文章站 2022-06-03 13:18:15
...

一、实验目的

利用递归知识和C/C++语言,提升自己的编程能力,实现递归代码。

二、 实验要求

实现若干个递归描述的算法。
1) 汉诺塔问题的递归算法
2) 棋盘覆盖问题的递归算法
3) 其它:任意设计一个递归问题,写出递推关系并实现它。

三、实验步骤与内容

1) 汉诺塔递归算法

#include <iostream>

using namespace std;

int i = 1 ;

void hanoi(int N ,char source , char relay ,char destination)
{
    if(N == 1)
    {
        cout << "第" << i << "步:" << source << "-->" << destination << endl ;
        i++ ;
    }
    else
    {
        hanoi(N-1 , source , destination , relay) ;
        cout << "第" << i << "步:" << source << "-->" << destination << endl ;
        i++ ;
        hanoi(N-1 , relay , source , destination) ;
    }
}

int main()
{
    int n ;
    cout << "请输入汉诺塔数量:" ;
    cin >> n ;
    hanoi(n, 'A' , 'B' , 'C') ;

    return 0;
}


结果:
(算法设计与分析)实验二 熟悉递归算法

2) 棋盘覆盖递归算法

#include<iostream>

using namespace std;

int tile=1;
int Board[100][100];

void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
    if(size==1)
        return;
    int t=tile++,s=size/2;

    if(dr<tr+s && dc<tc+s)
        ChessBoard(tr,tc,dr,dc,s);
    else
    {
        Board[tr+s-1][tc+s-1]=t;
        ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
    }

    if(dr<tr+s && dc>=tc+s)
        ChessBoard(tr,tc+s,dr,dc,s);
    else
    {
        Board[tr+s-1][tc+s]=t;
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }

    if(dr>=tr+s && dc<tc+s)
        ChessBoard(tr+s,tc,dr,dc,s);
    else
    {
        Board[tr+s][tc+s-1]=t;
        ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }

    if(dr>=tr+s && dc>=tc+s)
        ChessBoard(tr+s,tc+s,dr,dc,s);
    else
    {
        Board[tr+s][tc+s]=t;
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}

int main()
{
    int size;
    cout<<"输入棋盘的size(大小必须是2的n次幂): ";
    cin>>size;
    int index_x,index_y;
    cout<<"输入特殊方格位置的坐标: ";
    cin>>index_x>>index_y;
    ChessBoard ( 0,0,index_x-1,index_y-1,size );
    for ( int i=0; i<size; i++ )
    {
        for ( int j=0; j<size; j++ )
            cout<<Board[i][j]<<'\t';
        cout<<endl;
    }
}

结果:
(算法设计与分析)实验二 熟悉递归算法
3) 快速排序的递归算法

在快速排序中,记录的比较和交换是从两端向中间进行的,关键字较大的记录一次就能交换到后面单元,关键字较小的记录一次就能交换到前面单元,记录每次移动的距离较大,因而总的比较和移动次数较少。

#include <iostream>

using namespace std;

void quicksort(int[], int, int);

int main()
{
	int num[] = {11,12,7,22,3,16,14,19,30,23};

	cout << "排序前:" ;
	for (int i = 0; i < 10; i++)
	{
		cout << num[i] << '\t';
	}

	cout << endl;
	quicksort(num, 0, 9);

	cout << "排序后:" ;
	for (int i = 0; i < 10; i++)
	{
		cout << num[i] << '\t';
	}
}

void quicksort(int a[], int left, int right)
{
	if (left > right)
        return;
	int i = left;
	int j = right;
	int temp = a[left];
	while (i != j)
	{
		while (a[j] >= temp && i < j) j--;
		while (a[i] <= temp && i < j) i++;

		if (i < j)
		{
			int t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}

	a[left] = a[i];
	a[i] = temp;

	quicksort(a, left, i-1);
	quicksort(a, i+1, right);
}


结果:
(算法设计与分析)实验二 熟悉递归算法