• <optgroup id="100me"></optgroup>

    
    

  • <track id="100me"></track>
    首頁 > 試題廣場 > 變態跳臺階
    [編程題]變態跳臺階
    一只青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
    推薦

    關于本題,前提是n個臺階會有

       查看全部
    編輯于 2015-06-17 21:30:40 回復(171)
    class Solution {
    public:
    ? ? int jumpFloorII(int number) {
    ????????????????int a=1; return a<<(number-1);
    ? ? }
    };
    2^(n-1)可以用位移操作進行,更快。
    發表于 2015-08-16 00:29:46 回復(25)
    【分析】 每個臺階可以看作一塊木板,讓青蛙跳上去,n個臺階就有n塊木板,最后一塊木板是青蛙到達的位子, 必須存在,其他 (n-1) 塊木板可以任意選擇是否存在,則每個木板有存在和不存在兩種選擇,(n-1) 塊木板 就有 [2^(n-1)] 種跳法,可以直接得到結果。

    其實我們所要求的序列為:0,1,2,4,8,16,……
    所以除了第一位外,其他位的數都是前一位的數去乘以2所得到的積。

    【參考代碼】
    package javaTest;
    
    import java.util.Scanner;
    
    
    public class JavaTest {
    	public static void main(String[] args) {
    		Scanner input = new Scanner(System.in);
    		int target = input.nextInt();
    		System.out.println("跳上一個" + target + "級的臺階總共有"
    				+ jumpFloor(target) + "種跳法");
    	}
    	// 第一種做法
    	public static int jumpFloor(int target) {
    		if (target <= 0) return 0;
    		return (int) Math.pow(2, target - 1);
    	}
    //       第二種做法
    //	public static int jumpFloor(int target) {
    //		if (target <= 0) return 0;
    //		if (target == 1) return 1;
    //		int a = 1;
    //		int b = 2;
    //		for (int i = 2; i <= target; i++) {
    //			b = 2 * a;
    //			a = b;
    //		}
    //		return b;
    //	}
    }

    發表于 2016-10-08 22:30:44 回復(8)
    因為n級臺階,第一步有n種跳法:跳1級、跳2級、到跳n級
    跳1級,剩下n-1級,則剩下跳法是f(n-1)
    跳2級,剩下n-2級,則剩下跳法是f(n-2)
    所以f(n)=f(n-1)+f(n-2)+...+f(1)
    因為f(n-1)=f(n-2)+f(n-3)+...+f(1)
    所以f(n)=2*f(n-1)
    編輯于 2018-03-28 20:41:06 回復(40)
    http://頭像 //

    每個臺階都有跳與不跳兩種情況(除了最后一個臺階),最后一個臺階必須跳。所以共用2^(n-1)中情況

    發表于 2015-06-03 22:36:45 回復(97)
    HXY頭像 HXY
    一行代碼 return ?1<<--number;
    編輯于 2015-04-25 20:40:41 回復(121)
    ? ? ? ? 根據上一個題目:青蛙只跳1或2可以得出是一個斐波那契問題,即a[n]=a[n-1]+a[n-2],那么能跳1,2,3個臺階時a[n]=a[n-1]+a[n-2]+a[n-3],......
    ? ? ? ??依次類推,能推出本題的a[n]=a[n-1]+a[n-2]+......+a[1];由此得出代碼:
    class Solution {
    public:
        int jumpFloorII(int number) {
            int *a=new int[number+1];
            a[0]=1;
            a[1]=1;
            for(int i=2;i<=number;i++){
                a[i]=0;
                for(int j=i-1;j>=0;j--){
                    a[i]+=a[j];
                }
            }
            return a[number];
        }
    };
    
    但是上述代碼時間復雜度達到O(n^2),空間復雜度也達到O(n),重新看一下上述結論:
    a[n]=a[n-1]+a[n-2]+......+a[1];..........................①
    a[n-1]= ? ? ? ?a[n-2]+......+a[1];..........................②
    兩式相減可知:a[n]=2*a[n-1];
    所以代碼進一步簡化:
    class Solution {
    public:
        int jumpFloorII(int number) {
            int f=1,fn=1;
            for(int i=2;i<=number;i++){
                fn=2*f;
                f=fn;
            }
            return fn;
        }
    };
    

    編輯于 2016-06-13 13:14:06 回復(10)

    python solution:

    return 2**(number-1)
    
    發表于 2017-10-14 13:24:19 回復(12)
    拒絕時間開銷,拒絕遞歸調用
    class Solution {
    public:
        int jumpFloorII(int number) {
        	int jumpFlo=1;
            while(--number)
            {
                jumpFlo*=2;
            }
            return jumpFlo;
        }
    };

    編輯于 2016-07-19 17:14:58 回復(8)

    (1)假定第一次跳的是一階,那么剩下的是n-1個臺階,跳法是f(n-1);假定第一次跳的是2階,那么剩下的是n-2個臺階,跳法是f(n-2);假定第一次跳的是3階,那么剩下的是n-3個臺階,跳法是f(n-3)......假定第一次跳的是n-1階,那么剩下的是1個臺階,跳法是f(1); 假定第一次跳的是n階,那么剩下的是0個臺階,跳法是1種;

    (2)總跳法為: f(n) = 1+f(n-1) + f(n-2)+....+f(1) ?(第一個1是跳n階只有一種方法)

    (3)根據(2)可以得出有一階的時候 f(1) = 1 ;有兩階的時候可以有 f(2) = 1+f(1)=2;有三階的時候可以有 f(3) = 1+f(2)+f(1)=4...依次內推,有n階時f(n)=2^(n-1)。

    為了加快運算速度,可以通過向左移移位來完成乘以2的工作:
    class Solution{
    public:
        int jumpFloorII(int number) {
            //通過移位計算2的次方
            return 1<<(number-1);        
        }
    };

    編輯于 2016-09-05 11:40:55 回復(3)
    直接看圖就知道:
    發表于 2015-05-11 14:59:02 回復(11)
    其實是隔板問題,假設n個臺階,有n-1個空隙,可以用0~n-1個隔板分割,c(n-1,0)+c(n-1,1)+...+c(n-1,n-1)=2^(n-1),其中c表示組合。
    有人用移位1<<--number,這是最快的。直接連續乘以2不會慢多少,編譯器會自動優化。不過移位還是最有啟發的!
    發表于 2015-09-05 21:31:40 回復(5)
    數學問題, n個臺階最多有n-1個分段, ?每個分段可以跳也可以不跳,所以有2的n-1次方
    class Solution {
    public:
    ? ? int jumpFloorII(int number) {
    ? ? ? ? return pow(2,number-1);
    ? ? }
    };
    編輯于 2017-08-14 17:35:02 回復(1)
    假設有n級的臺階,其實就是找組合數,將n分成n個0或者1(1,1,0,0,0,1)第一個必須是1,其中1表示未被前面步數包含,0表示被前面步數包含,比如如果是4步,(1,1,1,1)表示一次跳一步,(1,0,0,1)表示3,1(1,1,0,1)表示1,2,1所以組合應該為2的n-1次方
    發表于 2015-10-10 13:20:41 回復(2)
    public class Solution {
        public int JumpFloorII(int target) {
            if(target<=0)
                return 0;
            return 1<<(target-1);
        }
    }

    發表于 2016-04-18 14:03:46 回復(0)
    class Solution {
    public:
    ??? int jumpFloorII(int number) {
    /*??????? //第一種
    ??????? long int sum=0;
    ??????? if(number==0) return 1;
    ??????? else if(number==1) return 1;
    ??????? else if(number==2) return 2;
    ??????? else
    ??????? {
    ?????????????? for(int i=number-1; i>=0; i--)
    ?????????????????? sum += jumpFloorII(i);
    ??????? }
    ?????? ?
    ??????? return sum;
    ??????? */
    ??????? //第二種做法
    ??????? return pow(2, number-1);
    ??? }
    };
    發表于 2015-10-09 16:36:30 回復(0)
    class Solution {
    public:
        int jumpFloorII(int number) {
    			return pow(2,number-1);
        }
    };

    發表于 2016-11-18 20:08:04 回復(0)

    得出規律后,直接使用2的n-1次方公式。

    public class Page79 {
        public int JumpFloorII(int target) {
            if (target == 0) {
                return 0;
            } else{
                return (int) Math.pow(2,target - 1);
            }
        }
    
        public static void main(String[] args) {
            Page79 page79 = new Page79();
            System.out.println(page79.JumpFloorII(3));
        }
    }
    發表于 2019-01-22 11:02:44 回復(0)
    public class Solution {
    ? ? public int JumpFloorII(int target) {
    ? ? ? ? int sum = 1;
    ? ? ? ? while(target > 1){
    ? ? ? ? ? ? sum *= 2;
    ? ? ? ? ? ? target--;
    ? ? ? ? }
    ? ? ? ? return sum;
    ? ? }
    }
    
    或者是使用位運算
    發表于 2018-08-03 11:55:29 回復(0)
    class Solution {
    public:
    ? ? int jumpFloorII(int number) {
    ? ? ? ? return 1<<(number-1);
    ? ? }
    };
    發表于 2017-10-20 22:57:26 回復(0)
    public class Solution {
    ? ? public int JumpFloorII(int target) {
    ? ? ? ? // 假設:f(n)表示:n個臺階第一次1,2,...n階的跳法數;
    ? ? ? ? // 若第一次跳了1階,則還剩n-1階,
    ? ? ? ? // 假設:f(n-1)表示:n-1個臺階第一次1,2,...n-1階的跳法數;
    ? ? ? ? // 若第一次跳了2階,則還剩n-2階,
    ? ? ? ? // 假設:f(n-2)表示:n-1個臺階第一次1,2,...n-2階的跳法數;
    ? ? ? ? // ...
    ? ? ? ? // 把所以可能的情況(第一次可能跳1,2,...,n階)加起來:
    ? ? ? ? // 可以求出:f(n) = f(n-1) + f(n-2) + ... + f(1)
    ? ? ? ? // 遞歸:f(n-1) = f(n-2) + ... + f(1)
    ? ? ? ? // 可以求出:f(n) = 2*f(n-1)?
    ? ? ? ??
    ? ? ? ? /*
    ? ? ? ? if (target <= 0) {
    ? ? ? ? ? ? return 0;
    ? ? ? ? } else if (target == 1) {
    ? ? ? ? ? ? return 1;
    ? ? ? ? } else {
    ? ? ? ? ? ? return 2 * JumpFloorII(target - 1);
    ? ? ? ? }
    ? ? ? ? */?
            // 更實用的解法是:從下往上計算,避免了遞歸的多余計算量
    ? ? ? ? int a = 1, b = 0;
    ? ? ? ? if (target <= 0) {
    ? ? ? ? ? ? return 0;
    ? ? ? ? } else if (target == 1) {
    ? ? ? ? ? ? return 1;
    ? ? ? ? } else {
    ? ? ? ? ? ? for (int i = 2; i <= target; i++) {
    ? ? ? ? ? ? ? ? b = 2 * a;
    ? ? ? ? ? ? ? ? a = b;
    ? ? ? ? ? ? }
    ? ? ? ? ? ? return b;
    ? ? ? ? }
    ? ? }
    }

    編輯于 2017-03-14 01:31:46 回復(0)
    狠狠的撸2019手机看片电影最新版