首页 > 试题广场 >

童年生活二三事

[编程题]童年生活二三事

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

NowCoder小时候走路喜欢蹦蹦跳跳，他最喜欢在楼梯上跳来跳去。
但年幼的他一次只能走上一阶或者一下子蹦上两阶。
现在一共有N阶台阶，请你计算一下NowCoder从第0阶到第N阶共有几种走法。

输入描述:

输入包括多组数据。每组数据包括一个整数n, (1≤n≤90)。

输出描述:

对应每个输入包括一个输出。
为redraiment到达第n阶不同走法的数量。

示例1

输入

1<br/>2

输出

1<br/>2

算法知识视频讲解

菜鸟葫芦娃

这是典型的青蛙跳台阶的问题即 斐波那契数列这样就知道如何解答了

importjava.util.Scanner;

  publicclassMain {    /*     * 青蛙跳台阶 斐波那契数列     * 规律：1 2 3 5 8 ...     */    publicstaticvoidmain(String[] args) {        long[] lArr = newlong[91];        lArr[1] = 1;        lArr[2] = 2;        for(inti = 3; i < lArr.length; i++)            lArr[i] = lArr[i - 1] + lArr[i - 2];        Scanner in = newScanner(System.in);        while(in.hasNextInt()) {            intn = in.nextInt();            System.out.println(lArr[n]);        }    }}

发表于 2015-07-09 21:27:34 回复(0)

更多回答

Python

华科平凡

python解法。一个跳台阶的问题起成这样的名字也是醉了。

while True:
    try:
        n=int(input())
        arr=[1,2]
        while len(arr)<n:
            arr.append(arr[-1]+arr[-2])
        print(arr[n-1])
    except:
        break

发表于 2017-10-17 11:23:02 回复(2)

C/C++

hanjiangxue

详细解释

https://blog.csdn.net/qq_33375598/article/details/104608324

2 解析

设f(n)为青蛙从0到n台阶的方案数，
当f(1) = 1,f(2) = 2;
当n为3时，
在这里插入图片描述
当n为4时，

于是发现递推式为f(n) = f(n-1)+f(n-2)。也就是斐波那契数列。

用递归（深度搜索）的化，会超时。所以考虑用动态规划，找出递推式，打表，然后查询。
由于递推式最后的值会超过int，采用longlong存储。
3 参考代码

/*
 * 详解：https://blog.csdn.net/qq_33375598/article/details/104608324
 */
#include <cstdio>

typedef long long ll;
const int MAXN = 91;
ll f[MAXN] = {1,1,2};

int main(int argc, char const *argv[]){
    int n;
    for (int i = 3; i <= 90; ++i) {
        f[i] = f[i -1] + f[i -2];
    }
    while(scanf("%d", &n) != EOF){
        printf("%lld\n", f[n]);
    }
    return 0;
}

发表于 2020-03-02 11:45:54 回复(0)

kestars

import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        BigInteger[] steps=new BigInteger[95];
        steps[1]=new BigInteger("1");
        steps[2]=new BigInteger("2");
        for(int i=3;i<95;i++){
            steps[i]=steps[i-1].add(steps[i-2]);
        }
        while(sc.hasNext()){
            int n=sc.nextInt();
            System.out.println(steps[n]);
        }
    }
}

发表于 2018-09-30 00:12:37 回复(0)

C/C++

Caffeine

思路看见这种题目头疼  母牛题目改编。
#include <iostream>
#include <vector>
using namespace std;
/*
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
*/
int main()
{
    vector<long long> v(90);
    long long temp;
    v[0] = 1;// D
    v[1] = 2;// D A
    v[2] = 3;// D A B 
    v[3] = 5;// D A B C
    
    for (int i = 4; i < 90; i++)
    {
        v[i] = v[i - 1] + v[i - 2];
    }
    int n;
    while (cin >> n)
    {
        cout << v[n - 1] << endl;
    }
}

发表于 2018-08-11 21:25:26 回复(0)

Python

shangyit

def redra(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        if ***.get(n)!=None:
            return ***[n]
        else:
            newSum = redra(n-1) + redra(n-2)
            ***[n] = newSum
            return newSum
            
*** = {1:1, 2:2}
while True:
    try:
        n = int(input())
    except:
        break
    print(redra(n))

Python using memoization and recursion

发表于 2017-11-08 21:23:31 回复(0)

C/C++

德芙纵享丝滑

#include <iostream>
using namespace std;
int main()
{	
	long long data[91] = { 0 };
	data[1] = 1;
	data[2] = 2;
	for (int i = 3; i <= 90; i++)
		data[i] = data[i - 1] + data[i - 2];
	int num;
	while (cin >> num)
		cout << data[num] << endl;
	return 0;
}

发表于 2017-04-19 13:23:12 回复(0)

流浪的美味

#include <iostream>

using namespace std ;

int main()

{

int i,n;

long long unsigned int m[ 90 ];

m[ 0 ]= 1 ,m[ 1 ]= 2 ;

for (i= 2 ; i< 90 ; i++){

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

}

while ( cin >>n){

cout <<m[n- 1 ]<< endl ;

}

return 0 ;

}

发表于 2015-05-18 20:05:57 回复(0)

牛客751949234号

为什么超时啊！JAVA提交总是超时😓

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			System.out.println(work(n));
			
		}
	}

	/*
	 * 递归实现
	 * */
	public static int work(int n) {
		if(n == 1) return 1;
		if(n == 2) return 2;
		return work(n-1)+work(n-2);
	}
}

发表于 2020-03-30 10:55:07 回复(0)

hestyle

解题思路： 这题比较经典，是斐波拉契尔数列的包装。 由于只能一次上1阶台阶或者一次2阶台阶，
因此可以从第n - 2阶台阶直接上2阶到达第n阶，也可以从
第n - 1阶台阶上1阶台阶到达第n阶， 因此可得出结论f(n) = f(n - 1) + f(n - 2)(n ≥ 2) 代码实现：\color{blue}代码实现：代码实现： #include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    //建立一张表，用于记录f(n)各项值，注意数据溢出，使用long long型
    long long fTable[91] = {0, 1, 2};
    for (int i = 3; i < 91; ++i) {
        fTable[i] = fTable[i - 1] + fTable[i - 2];
    }
    int number = 0;
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &number) != - 1) {
        printf("%lld\n", fTable[number]);
    }
    return 0;
}

————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104627580

编辑于 2020-03-03 11:03:30 回复(0)

C/C++

不偷不抢安度因_

//又是斐波那契数列...
#include <stdio.h>
#include <stdlib.h>
 
long long int fib[90] = {1, 2, 3, 5, 8};
 
int main()
{
    int n;
    int start = 5;
    while(~scanf("%d", &n))
    {
        if(n > start)
        {
            for(int i = start; i < n; i++)
                fib[i] = fib[i-1] + fib[i-2];
            start = n;
        }
        printf("%ld\n", fib[n-1]);
    }
}

编辑于 2020-03-02 18:22:10 回复(0)

C/C++

JediMaster

#include<iostream>
#include<vector>
using namespace std;
//典型fb数列
int main() {
    int n;
    vector<long long> dp(91,0);
    dp[0]=1;
    dp[1]=1;
    for (int i = 2; i < 91; i++) {
        dp[i]=dp[i-1]+dp[i-2];
    }
    while (cin >> n) {
        cout << dp[n] << endl;
    }
 
}

编辑于 2020-02-25 19:08:33 回复(0)

勇敢牛牛额

怎么又是斐波那契数列数列，没意思

#include <stdio.h>

int main()
{
    int i,n;
    long long dp[91];
    dp[1]=1;
    dp[2]=2;
    for(i=3;i<=90;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld\n",dp[n]);
    }
}

发表于 2019-12-07 22:06:02 回复(0)

双笙20180911074448

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        long[] a=new long[92];
        a[1]=1;
        a[2]=2;
        for(int i=3;i<a.length;i++)
            a[i]=a[i-1]+a[i-2];
        while(sc.hasNext()){
            int c=sc.nextInt();
            System.out.println(a[c]);
        }
    }
}

发表于 2019-07-27 21:47:31 回复(0)

forget12345

<?php
while(fscanf(STDIN, "%d", $a))  
   echo (fib($a))."\n";
function fib($n){
    $data=array();
    $data[0]=1;
    $data[1]=2;
    for ($i=3;$i<=$n;$i++){
        $data[$i-1]=$data[$i-2]+$data[$i-3];
    }
    return $data[$n-1];
}

发表于 2019-03-28 15:37:00 回复(0)

Disconnect

def c(m,n):
    con1,con2,re=1,1,0
    for i in range(n,n-m,-1):
        con1 = con1*i
    for i in range(1,m+1):
        con2 = con2*i
    re = con1//con2
    return re
try:
    while True:
        n = input()
        n = int(n)
        res = 0
        num2 = []
        for i in range(1,n//2+1):
            num2.append(i)
        num1 = []
        for i in num2:
            num1.append(n-i*2)
        for i in range(0,len(num2)):
            res = res + c(num2[i],num1[i]+num2[i])
        res+=1
        print(res)
except:
    pass

发表于 2018-11-29 15:38:06 回复(0)

梦里逆天

#include<stdio.h>
int main() {
int n,i;
    long long int a[91]={1,2};
    for(i=2;i<91;i++)
        a[i] = a[i-1] + a[i-2];
while(scanf("%d",&n)!=EOF) {
printf("%lld\n",a[n-1]);
}
return 0;
}

发表于 2018-11-24 11:07:21 回复(0)

SupritYoung

https://blog.csdn.net/a1097304791/article/details/83993145

题解

发表于 2018-11-12 15:50:15 回复(0)

ShouldBeOk

/*
* =====================================================================================
*
* Filename: 08童年生活二三事.cpp
*
* Version: 1.0
* Created: 2018/09/24 11:23:51
* Revision: none
* Compiler: gcc
*
* Author: Covfefe
* Organization:    Fs-studio
*
*      idea: 方法数为斐波那契数列 1 2 3 5 8 ……
*
* =====================================================================================
*/
#include <stdio.h>
#include <iostream>
using namespace std;
#define FOR(i,n) for(i = 2; i < n; i++)
int main()
{
    int n, i;
    long long F[91];
    F[0] = 1;
    F[1] = 2;
    FOR(i, 90)
        F[i] = F[i - 1] + F[i - 2];
    while (cin >> n)
        cout << F[n - 1] << endl;
}

发表于 2018-09-24 11:47:29 回复(0)

这菜都齐了怎么还不吃啊

#include <bits/stdc++.h>
#define PI 3.1415927
using namespace std; 
typedef unsigned long long ll;
ll arr[1000005];
void init()
{
    arr[1]=1;
    arr[2]=2;
    for(int i=3;i<=90;i++)
        arr[i]=arr[i-1]+arr[i-2];
}
int main(void)  
{   
    init();    
    int n;
    while(cin>>n)
        cout<<arr[n]<<endl;
    return 0;
}

发表于 2018-08-01 15:08:45 回复(0)