HJ37 统计每个月兔子的总数

题目描述

示例

代码

代码1 非递归解法

// 是一道找规律的题，实际就是斐波那契数列
// 1只兔子，第三个月起，每个月都会生一只兔子
// 1 1 2 3 5
// 斐波那契数列就有两种解法，递归与非递归
// 先用非递归解一下

let readline = require('readline')
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
})

rl.on('line', line=>{
    
    let num = parseInt(line)
    // 非递归的解法
    if( num < 3){ // 前两个月 都返回1
        console.log(1)
    }else {
        let pre = 1
        let current = 1
        // 从第三个数开始 索引从0开始，第三个数的索引为2
        // 1<=num<=31
        for(let i = 2; i< num; i++ ){
            let sum = pre + current
            pre = current
            current = sum
        }
        
        console.log(current)
    }
})

代码2 递归解法

// 是一道找规律的题，实际就是斐波那契数列
// 1只兔子，第三个月起，每个月都会生一只兔子
// 1 1 2 3 5
// 斐波那契数列就有两种解法，递归与非递归
// 递归解法

let readline = require('readline')
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
})

rl.on('line', line=>{
    
    let num = parseInt(line)
    let result = fn(num)
    console.log(result)
    
    // 递归的解法
    // 1<=num<=31
    // 1 1 2
    function fn(num) {
        if(num < 3){ // 出口
            return 1
        }else {
            // fn(3) = fn(2) + fn(1) 
            // fn(3) =  1 + 1 = 2
            return fn(num-1) + fn(num-2)
        }
    }
})

题目来源

HJ37 统计每个月兔子的总数