<rp id="qpc6k"><optgroup id="qpc6k"><bdo id="qpc6k"></bdo></optgroup></rp>
  • <mark id="qpc6k"><noframes id="qpc6k"><b id="qpc6k"></b></noframes></mark>
    1. <input id="qpc6k"></input>
    <u id="qpc6k"></u>

      <video id="qpc6k"><input id="qpc6k"><p id="qpc6k"></p></input></video>
      <u id="qpc6k"><dl id="qpc6k"></dl></u>
      <b id="qpc6k"><kbd id="qpc6k"></kbd></b>

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

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

         查看全部
      編輯于 2015-06-17 21:30:40 回復(173)
      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 回復(9)
      因為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)
      微拍福利