1. <dd id="qfst8"><pre id="qfst8"></pre></dd>
      <nav id="qfst8"><sub id="qfst8"><noframes id="qfst8"></noframes></sub></nav>
      <tbody id="qfst8"><pre id="qfst8"></pre></tbody>

      <dd id="qfst8"><track id="qfst8"></track></dd>
        1. 首頁 > 試題廣場 > 變態跳臺階
          [編程題]變態跳臺階
          一只青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
          function jumpFloorII(number)
          {
          ? ? if (number==1){
          ? ? ? ? return 1;
          ? ? }
          ? ? return Math.pow(2,number-1);
          }
          發表于 2019-08-06 03:17:08 回復(0)
          更多回答
          推薦

          關于本題,前提是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)
          微拍福利