すべてのスタックの順序とカタラン数を再帰的に出力するアプリケーション

2969 ワード

Java-ARrayListシミュレーションスタックの動作は,再帰アルゴリズムを用いる.コードは次のとおりです.
import java.util.ArrayList;
import java.util.Scanner;

public class stackAll {
    static int num=0;
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();//      
        ArrayList stackIn=new ArrayList();
        for(int i=n;i>0;i--)//       
            stackIn.add(i);
        
        long start=System.currentTimeMillis();
        stackOut(stackIn,new ArrayList(),new ArrayList());//    
        System.out.println(num);//         
        System.out.println((System.currentTimeMillis()-start)/1000f);//      
    }
    
    public static void stackOut(ArrayList stackIn,ArrayList stack,ArrayList stackOut){
        if(stackIn.size()==0){//       
            if(stack.size()==0){//    
                for(int x : stackOut)//         ,       ,      
                    System.out.print(x+" ");
                System.out.println();
                num++;//    
            }else{
                stackOut.add(stack.get(stack.size()-1));//     ,   ,     
                stack.remove(stack.size()-1);
                stackOut(stackIn,stack,new ArrayList(stackOut));
            }
        }else{
            if(stack.size()==0){//      ,  ,   
                stack.add(stackIn.get(stackIn.size()-1));
                stackIn.remove(stackIn.size()-1);
                stackOut(stackIn,stack,new ArrayList(stackOut));
            }else{
                ArrayList stack_copy=new ArrayList(stack);//               ,           
                ArrayList stackIn_copy=new ArrayList(stackIn);

                stack_copy.add(stackIn_copy.get(stackIn_copy.size()-1));//   
                stackIn_copy.remove(stackIn_copy.size()-1);
                stackOut(stackIn_copy,stack_copy,new ArrayList(stackOut));
                
                stackOut.add(stack.get(stack.size()-1));//   
                stack.remove(stack.size()-1);
                stackOut(stackIn,stack,new ArrayList(stackOut));
            }
        }
    }
}

14要素を超えるスタックのスタックのスタック出順を計算すると,時間が長くなり,1増加するごとに時間幾何級数が増加する.
実際には、スタック順序のすべての可能な総数は、カードタラン数であり、カードタラン数を求めるにはほとんど時間がかからず、非常に速いが、カードタラン数は最終結果の総数しか出力できず、各スタック順序の具体的なデータは出力できないため、状況に応じて使用される.
以下にカードタラン数の解コードを添付します.
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        System.out.println(h(new Scanner(System.in).nextLong()));    
    }
    public static long h(long n){
        if(n==1)
            return 1;
        else if(n==2)
            return 2;
        else
            return h(n-1)*(4*n-2)/(n+1);
    }
}