递归求全排列
其实它是没有排序的全排列……
-
#include<iostream>
-
using namespace std;
-
-
#define N 30
-
-
/********************************
-
* 打印数组函数
-
********************************/
-
void printArray(int A[], int n){
-
for(int i=0; i<n; i++){
-
cout<<A[i]<<" ";
-
}
-
cout<<endl;
-
}
-
-
/********************************************
-
* 全排列算法
-
*
-
* 输入：数组A[]，数组的元素个数n，
-
* 当前递归层次已完成排列的元素个数k（0<=k<n)
-
* 输出：数组A[]的全排列
-
********************************************/
-
void perm(int A[], int n, int k){
-
if(k==n-1){ // 已完成排列则打印
-
printArray(A,n);
-
}else{
-
for(int i=k; i<n ;i++){ // 生成后续的一系列排列
-
swap(A[i], A[k]);
-
perm(A, n, k+1);
-
swap(A[i], A[k]);
-
}
-
}
-
}
-
-
int main(){
-
int A[N], n;
-
-
cout<<"请输入数组的元素个数：";
-
cin>>n;
-
-
cout<<"请输入数组的元素：";
-
for(int i=0; i<n; i++){
-
cin>>A[i];
-
}
-
-
cout<<"数组的全排列是："<<endl;
-
perm(A,n,0);
-
-
return 0;
-
}
设计一个递归算法求解汉诺塔问题
算了好久 囧
-
#include<iostream>
-
using namespace std;
-
-
void move(int n, int x, int y){
-
static int t = 1;
-
cout<<"第"<<t++<<"步 "<<char(x+64)<<"(第"<<n<<"号盘子) -> "<<char(y+64)<<endl;
-
}
-
-
void hanoi(int n,int a, int b, int c){
-
if(n==1)
-
move(1,a,c);
-
else{
-
hanoi(n-1,a,c,b);
-
move(n,a,c);
-
hanoi(n-1,b,a,c);
-
}
-
}
-
-
int main(){
-
int n;
-
-
cout<<"请输入第一根柱子上的盘子数：";
-
cin>>n;
-
-
hanoi(n,1,2,3);
-
-
return 0;
-
}
用递归算法重新设计选择排序算法
不知道是不是这样写 囧？
-
#include<iostream>
-
using namespace std;
-
-
#define N 100
-
-
void sort(int A[], int n){
-
if(n==1)return;
-
for(int i=0; i<n-1; i++){
-
if(A[i]>A[n-1]){
-
int t = A[i];
-
A[i] = A[n-1];
-
A[n-1] = t;
-
}
-
}
-
sort(A,n-1);
-
}
-
-
void print(int A[], int n){
-
for(int i=0; i<n; i++){
-
cout<<A[i]<<" ";
-
}
-
cout<<endl;
-
}
-
-
int main(){
-
int A[N], n;
-
-
input:
-
cout<<"请输入数组的长度(<"<<N<<")：";
-
cin>>n;
-
-
if(n<=0){
-
cout<<"n必须大于0！"<<endl;
-
goto input;
-
}
-
if(n>=N){
-
cout<<"n必须小于"<<N<<"！"<<endl;
-
goto input;
-
}
-
-
cout<<"请输入数组的元素：";
-
for(int i=0; i<n; i++){
-
cin>>A[i];
-
}
-
-
cout<<"排序前的数组：";
-
print(A,n);
-
-
sort(A,n);
-
-
cout<<"排序后的数组：";
-
print(A,n);
-
-
return 0;
-
}
用递归算法求解f(x)=x-x^3/3!+x^5/5!-x^7/7!+...
用递归算法求解如下问题，计算到第n项为止：
用递归算法求解f(x)=x/2+x^2/4+...+x^n/2^n
用递归算法求解如下问题：
设计一个递归算法计算Fibonacci数列
囧 好久没写算法了……
-
#include<iostream>
-
using namespace std;
-
-
int getFibonacci(int n){
-
if(n==0||n==1)return 1;
-
return getFibonacci(n-1)+getFibonacci(n-2);
-
}
-
-
int main(){
-
int n;
-
-
while(true){
-
cout<<"请输入要求的Fibonacci数列项数（输入-1退出）：";
-
cin>>n;
-
if(n<0)break;
-
-
cout<<"第"<<n<<"项是：";
-
cout<<getFibonacci(n)<<endl;
-
}
-
-
return 0;
-
}
