(算法设计与分析)实验二 熟悉递归算法
程序员文章站
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);
}
结果:
下一篇: 独立博客必备:三款PHP类博客管理系统