首页 > 试题广场 >

跳格子游戏

[编程题]跳格子游戏

热度指数：8850 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

假设你正在玩跳格子（所有格子排成一个纵列）游戏。需要跳完n 个格子你才能抵达终点。
每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢？
注意：给定 n 是一个正整数。

输入描述:

格子数n

输出描述:

跳完n个格子到达终点的方法

示例1

输入

输出

算法知识视频讲解

无心2019

#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
    if(n<3)
        return n;
    return f(n-1)+f(n-2);
}
int main()
{
    int n;
    cin>>n;
    cout<<f(n);
    return 0;
}

发表于 2019-07-02 19:26:50 回复(0)

LHC0512

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int i = scanner.nextInt();
        int[] record = new int[i+1];
        record[1]=1;
        record[2]=2;
        for (int j = 3; j <= i; j++) {
            record[j]=record[j-1]+record[j-2];
        }
        System.out.println(record[i]);
    }
}

发表于 2020-02-28 21:46:49 回复(0)

混子精


	Leetcode上有爬楼梯的原题。思路是找到到达 n-1 和 n-2 的方法个数然后相加。



	



	importjava.util.*;



	publicclassMain{



	    publicstaticvoidmain(String[] args){



	        Scanner sc = newScanner(System.in);



	        while(sc.hasNext()){



	            intn = sc.nextInt();



	            if(n == 1){



	                System.out.println(1);



	                continue;



	            }



	            if(n == 2){



	                System.out.println(2);



	                continue;



	            }



	            int[] dp = newint[n + 1];



	            dp[1] = 1;



	            dp[2] = 2;



	            for(inti = 3; i <= n; i++){



	                dp[i] = dp[i - 1] + dp[i - 2];



	            }



	            System.out.println(dp[n]);



	        }



	        sc.close();



	    }



	}

发表于 2019-04-09 10:45:40 回复(0)

Java

lmz9509

/*
动态规划：dp[i]表示跳上i格的所有方法数
其中dp[i] = dp[i-1]+dp[i-2];
*/
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] dp = new int[n+1];
        dp[0] = 1;dp[1] = 1;
        for(int i =2;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        System.out.println(dp[n]);
    }
}

发表于 2020-04-21 10:52:37 回复(0)

亚洲舞王智海

n=int(input())
dp=[0]*n
dp[0]=1
dp[1]=2
for i in range(2,n ):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n-1])

发表于 2019-12-26 14:48:15 回复(0)

包子山

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int x = 1, y =1;
    int temp = 0;
    for(int i = 2;i<=n;i++)
    {
        temp = x+y;
        x = y;
        y = temp;
    }
    cout << y << endl;
    return 0;
}

发表于 2019-11-01 17:43:17 回复(0)

dragonlogin

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n = 0;
	
	cin >> n;
    vector<int> f(n+1, 1);    
	for (int i=2; i<=n; ++i) {
        f[i] = 0;
		f[i] = f[i-1] + f[i-2];
	}
	cout << f[n] << endl;
	return 0;
}

发表于 2019-10-19 14:32:32 回复(0)

Python

林林七__

def ways(n):
    dp = [0] * n
    dp[0] = 1
    dp[1] = 2
    for i in range(2, n):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[-1]

n = int(input())
print(ways(n))

发表于 2019-08-24 09:54:26 回复(0)

C/C++

摆码王子星

简单的状态记录

#include<iostream>

using namespace std;
int main()
{
int n;
while(cin>>n)
{
int * p=new int [n+1];
p[0]=1;
p[1]=1;
for(int i=2;i<=n;i++)
{
p[i]=p[i-2]+p[i-1];
}
cout<<p[n]<<endl;
}
return 0;
}

发表于 2019-08-22 21:14:37 回复(0)

C/C++

nbgao


	
	
		#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n+1];
    a[0] = a[1] = 1;
    for(int i=2;i<=n;i++)
        a[i] = a[i-1] + a[i-2];
    cout<<a[n]<<endl;
    return 0;
}

发表于 2019-07-17 00:27:17 回复(0)

谁的电脑

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i <= 2) {
                list.add(i);
            } else {
                list.add(list.get(i - 3) + list.get(i - 2));
            }
        }
        System.out.println(list.get(list.size() - 1));
    }
}

发表于 2019-07-02 16:07:26 回复(0)

KujoJotaro

利用递归，给定 n 是一个正整数，n = 1，2，3，4,...,n

不同的方法数量很明显是个斐波那契数列f(n) = f(n-1) + f(n-2)

import java.util.Scanner;
 
public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(Jump(n));
    }
    public static int Jump(int conclusion){
        if(conclusion == 1) return 1;
        else if(conclusion == 2) return 2;
        else return Jump(conclusion-1)+Jump(conclusion-2);
    }
}

发表于 2019-12-12 15:01:08 回复(0)

Python

小吖201908021331253

n = int(input())
dp = [0 for i in range(n)]
dp[0]=1
dp[1]=2
for i in range(2,len(dp)):
    dp[i] = dp[i-1]+dp[i-2]
count = dp[n-1]
print(count)

解析：每次只用考虑之后一种情况，第i个台阶有两种方法：从前一个台阶跳过来或是从前两个台阶跳过来，将每个台阶的方法的存入dp中，那么第i个台阶的方法则是dp[i-1]+dp[i-2]。最后的递归出口：1个台阶是一种方法，两个台阶是两种方法。

发表于 2019-09-22 14:30:01 回复(0)

keashem

斐波那契，dp来做，可以状态压缩

1. import java.util.Scanner;
2. import static java.lang.System.in;
3. public class Main {
4.     public static void main(String[] args) {
5.         Scanner sc = new Scanner(in);
6.         int n = sc.nextInt();
7.         int f1 = 1, f2 = 1;
8.         int temp = 0;
9.         for (int i = 2; i <=n; i++) {
10.             temp = f1 + f2;
11.             f1 = f2;
12.             f2 = temp;
13.         }
14.         System.out.println(f2);
15.     }
16. }

发表于 2019-08-02 18:37:33 回复(0)

pein531

其实就是斐波那契数列

python迭代解法

n = int(input())
p, q = 1, 2
r = 1 if n == 1 else 2
for _ in range(2, n):
    r = p + q
    p = q
    q = r
print(r)

java递归解法

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        System.out.println(fibonacci(n));
    }
    
    private static int fibonacci(int n){
        if(n == 1)
            return 1;
        else if(n == 2)
            return 2;
        else
            return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

发表于 2021-05-01 18:03:12 回复(0)

Python3

牛客446403687号

n = int(input())
if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    a = 1
    b = 2
    t = 2
    while t < n:
        a,b = b,a+b
        t += 1
    print(b)

发表于 2022-11-04 13:55:11 回复(0)

Java

真的能找到工作

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
System.out.print(dp[n]);

}
}

发表于 2023-08-05 01:40:35 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scan(&n)
    a,b,c:=1,2,3
    for i:=4;i<=n;i++{
        a=b
        b=c
        c=a+b
    }
    if n<=3{
        fmt.Print(n)
    }else{
        fmt.Print(c)
    }
}

发表于 2023-03-18 22:32:00 回复(0)

如我一粒尘埃

一次过

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int in = sc.nextInt();
        System.out.println(tiaogezi(in));
        sc.close();
    }
    
    public static int tiaogezi(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return tiaogezi(n - 1) + tiaogezi(n - 2);
    }
}

发表于 2022-09-03 18:42:40 回复(0)

牛客875188800号

如果第一次跳的是1阶，那么剩下的n-1个台阶，跳法是f(n-1)
如果第一次跳的是2阶，那么剩下的n-2个台阶，跳法是f(n-2)

由此可得：f(n) = f(n-1) + f(n-2)

当n=0时，f(0) = 1

当n=1时，f(1) = 1

当n=2时，f(2) = 2

import java.util.Scanner;

public class Dump {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int num=sc.nextInt();
        int a=1,b=1,sum=0;
        if(num==1)
            System.out.println(1);
        for(int i=2;i<=num;i++){
              sum=a+b;//f(n)=f(n-1)+f(n-2)
              a=b;
              b=sum;
        }
        System.out.println(sum);
    }
}

发表于 2022-04-03 00:51:45 回复(0)