Liny_@NotePad

沉迷ACG中

递归求全排列

 其实它是没有排序的全排列……

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 30
  5.  
  6. /********************************
  7. * 打印数组函数
  8. ********************************/
  9. void printArray(int A[], int n){
  10.         for(int i=0; i<n; i++){
  11.                         cout<<A[i]<<" ";
  12.                 }
  13.         cout<<endl;
  14. }
  15.  
  16. /********************************************
  17. * 全排列算法
  18. *
  19. * 输入:数组A[],数组的元素个数n,
  20. *       当前递归层次已完成排列的元素个数k(0<=k<n)
  21. * 输出:数组A[]的全排列
  22. ********************************************/
  23. void perm(int A[], int n, int k){
  24.         if(k==n-1){                    //   已完成排列则打印
  25.                 printArray(A,n);
  26.         }else{
  27.                 for(int i=k; i<n ;i++){ //       生成后续的一系列排列
  28.                         swap(A[i], A[k]);
  29.                         perm(A, n, k+1);
  30.                         swap(A[i], A[k]);
  31.                 }
  32.         }
  33. }
  34.  
  35. int main(){
  36.         int A[N], n;
  37.  
  38.         cout<<"请输入数组的元素个数:";
  39.         cin>>n;
  40.  
  41.         cout<<"请输入数组的元素:";
  42.         for(int i=0; i<n; i++){
  43.                 cin>>A[i];
  44.         }
  45.  
  46.         cout<<"数组的全排列是:"<<endl;
  47.         perm(A,n,0);
  48.  
  49.         return 0;
  50. }

设计一个递归算法求解汉诺塔问题

  算了好久 囧

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. void move(int n, int x, int y){
  5.         static int t = 1;
  6.         cout<<"第"<<t++<<"步 "<<char(x+64)<<"(第"<<n<<"号盘子) -> "<<char(y+64)<<endl;
  7. }
  8.  
  9. void hanoi(int n,int a, int b, int c){
  10.         if(n==1)
  11.                 move(1,a,c);
  12.         else{
  13.                 hanoi(n-1,a,c,b);
  14.                 move(n,a,c);
  15.                 hanoi(n-1,b,a,c);
  16.         }
  17. }
  18.  
  19. int main(){
  20.         int n;
  21.  
  22.         cout<<"请输入第一根柱子上的盘子数:";
  23.         cin>>n;
  24.  
  25.         hanoi(n,1,2,3);
  26.  
  27.         return 0;
  28. }

 

用递归算法重新设计选择排序算法

不知道是不是这样写 囧?

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 100
  5.  
  6. void sort(int A[], int n){
  7.         if(n==1)return;
  8.         for(int i=0; i<n-1; i++){
  9.                 if(A[i]>A[n-1]){
  10.                         int t = A[i];
  11.                         A[i] = A[n-1];
  12.                         A[n-1] = t;
  13.                 }
  14.         }
  15.         sort(A,n-1);
  16. }
  17.  
  18. void print(int A[], int n){
  19.         for(int i=0; i<n; i++){
  20.                 cout<<A[i]<<" ";
  21.         }
  22.         cout<<endl;
  23. }
  24.  
  25. int main(){
  26.         int A[N], n;
  27.  
  28. input:
  29.         cout<<"请输入数组的长度(<"<<N<<"):";
  30.         cin>>n;
  31.  
  32.         if(n<=0){
  33.                 cout<<"n必须大于0!"<<endl;
  34.                 goto input;
  35.         }
  36.         if(n>=N){
  37.                 cout<<"n必须小于"<<N<<"!"<<endl;
  38.                 goto input;
  39.         }
  40.  
  41.         cout<<"请输入数组的元素:";
  42.         for(int i=0; i<n; i++){
  43.                 cin>>A[i];
  44.         }
  45.  
  46.         cout<<"排序前的数组:";
  47.         print(A,n);
  48.  
  49.         sort(A,n);
  50.  
  51.         cout<<"排序后的数组:";
  52.         print(A,n);
  53.  
  54.         return 0;
  55. }

用递归算法求解f(x)=x-x^3/3!+x^5/5!-x^7/7!+...

用递归算法求解如下问题,计算到第n项为止:
f(x)=x-$\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+...

用递归算法求解f(x)=x/2+x^2/4+...+x^n/2^n

用递归算法求解如下问题:

f(x)=$\frac{x}{2}$$+\frac{x^2}{4}+...+\frac{x^n}{2^n}

设计一个递归算法计算Fibonacci数列

囧 好久没写算法了……

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int getFibonacci(int n){
  5.         if(n==0||n==1)return 1;
  6.         return getFibonacci(n-1)+getFibonacci(n-2);
  7. }
  8.  
  9. int main(){
  10.         int n;
  11.        
  12.         while(true){
  13.                 cout<<"请输入要求的Fibonacci数列项数(输入-1退出):";
  14.                 cin>>n;
  15.                 if(n<0)break;
  16.  
  17.                 cout<<"第"<<n<<"项是:";
  18.                 cout<<getFibonacci(n)<<endl;
  19.         }
  20.  
  21.         return 0;
  22. }