質問のカエルのジャンプの問題をJavaで解いてみた。

　質問のカエルのジャンプの問題をJavaで解いてみました。
　ジャンプの回数は、0〜int[({葉っぱの数}+1)/2]なので、ジャンプの回数でそれぞれ場合分けしました。数字を'o'、ジャンプを'j'として、同じものを含む順列を生成して、'j'が隣り合うもの("jj")をスキップしてカウントしました。
　数学的には、「階段上りの問題」の類題でフィボナチ数列を使って解くようですが、あまり効率は良くありませんが敢えて順列を生成して解く方法を使ってみました。(^_^;

※参考URL
●［PDF］フィボナチ数列
http://soroban.ptu.jp/math/fibonacci.pdf

● JumpingFrog1.java

/* 
 * JumpingFrog1.java
 */

class JumpingFrog1 {
    // 順列生成
    static boolean nextPerm(char[] p, int n, int r) {
        int  i, j;
        char t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j = n - 1; i < j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    
    public static void main(String[] args) {
        int N = 20;
        char[] p = new char[N];         // 順列生成用
        int Count = 0;
        
        long tm=System.nanoTime();      // Timer Start
        N = 8;
        for(int i = 0; i<=(N+1)/2; i++){
            for(int j = 0; j< N ; j++)
                p[j] = (j< i) ? 'j' : 'o';
            //System.out.println(new String(p));
            do{
                String s = new String(p);
                if(s.contains("jj")) continue;  // 'j'が隣り合うものをスキップ
                Count+=1;
                //for(int j = 0; j< N ; j++)
                //  System.out.print((p[j]=='j') ? "j" : j+1);
                //System.out.println();
            }while(nextPerm(p,N,N));
        }
        System.out.println("(1) "+Count);
        
        Count = 0;
        N = 20;
        for(int i = 0; i<=(N+1)/2; i++){
            for(int j = 0; j< N ; j++)
                p[j] = (j< i) ? 'j' : 'o';
            do{
                String s = new String(p);
                if(s.contains("jj")) continue;  // 'j'が隣り合うものをスキップ
                Count+=1;
                //System.out.println(s);
            }while(nextPerm(p,N,N));
        }
        System.out.println("(2) "+Count);
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}