經典的遞歸面試題

enali 發布于2019-08-23 16:15 / 3531人閱讀

摘要：遞歸閉包解決也就是存在數組中，再次循環時，如果數組中已經存在，就返回數組中的值，大大減少了遞歸調用函數的次數第位只是占位，從第一位開始算起如果中存在，返回這個值普通普通循環解決這個問題是性能最好的。

細胞分裂

細胞分裂 有一個細胞 每一個小時分裂一次，一次分裂一個子細胞，第三個小時后會死亡。那么n個小時候有多少細胞？
這個問題的核心就是三個小時為一個周期

// 每三個小時為一個周期 ， 第四個小時就 go die 了。
// 方法一
// 第一個小時，只有a態細胞；第二個小時，a態細胞分裂，原來的a態細胞變成了b態細胞，分裂出來的細胞變成了新的a態細胞；第三個小時，a態細胞繼續分裂變成b態細胞和新的a態細胞，b態細胞分裂變成c態細胞和a態細胞；第四個小時，a、b、c態細胞都會分裂，并且按照之前的規律轉變。得出下面的結論
// a 初始態 一個小時 前一個小時的 a+b+c
// b 幼年態 兩個小時 前一個小時的 a
// c 成熟態 三個小時 前一個小時的 b
function allCell(n){
    // a態細胞
    let aCell = function(n){
        if(n==1){
            return 1;
        }else{
            return aCell(n-1)+bCell(n-1)+cCell(n-1);
        }
    }
    // b態細胞
    let bCell = function(n){
        if(n==1){
            return 0;
        }else{
            return aCell(n-1);
        }
    }
    // c態細胞
    let cCell = function(n){
        if(n==1||n==2){
            return 0;
        }else{
            return bCell(n-1);
        }
    }
    return aCell(n)+bCell(n)+cCell(n)
}
console.log(allCell(10))
// 方法二
// 這個方法就是分成了 活著的 和 死亡的
function cell(hour){
    // 活著的細胞
    function livecell(hour){
        if(hour<4){
            // 前三個小時沒有死亡的細胞 成2的n-1次方增長
            return Math.pow(2,hour-1)
        }else{
            // 從第四個小時開始有死亡的細胞 
            // 活著的細胞 = 前一個小時活著的細胞 - 這個小時死去的細胞
            return livecell(hour-1)*2 - diecell(hour)
        }
    }
    // 死亡的細胞
    function diecell(hour){
        if(hour<4){
            // 前三個小時沒有死亡的細胞
            return 0
        }else{
            // 因為三個小時一個周期
            // 也就是每三個小時,(n-3)時的細胞就會死完
            // 那么 這個小時(n)死去的細胞 + 上個小時(n-1)死去的細胞 + 前兩個小時(n-2)死去的細胞 = 前三個小時(n-3)活著的細胞
            return livecell(hour-3) - diecell(hour-1) - diecell(hour-2)
        }
    }
    return livecell(hour)
}
console.log(cell(10))

斐波那契數列

又稱兔子數列，是以兔子繁殖為例，得出這樣一個數列：1,1,2,3,5,8... 指從第三個值開始，每個值都是前兩個值的和。

// 遞歸
    let a = 0;
    function tu(num){
        a++
        if(num==1||num==2){
            return 1
        }
        let nums = tu(num-1)+tu(num-2)
        return nums
    }
    console.log(tu(8),a)
// 閉包解決
    // 也就是存在數組中，再次循環時，如果數組中已經存在，就返回數組中的值，大大減少了遞歸調用函數的次數
    var count2=0;
    var fiba = (function(){
        var arr = [0,1,1];   //第0位只是占位，從第一位開始算起
        return function(n){
            count2++;   
            var res=arr[n]; 
            if(res){// 如果arr中存在，返回這個值
                console.log(res,"----")
                return res;
            }else{
                console.log(arr[n],"+++++")
                arr[n]=fiba(n-1)+fiba(n-2);
                return arr[n];
            }   
        }
    })();
    console.log(fiba(8),count2)
// 普通
    // 普通循環解決這個問題是性能最好的。
    let a = 1;
    let b = 1
    let c;
    function tu(num){
        for(let i=0;i
64格子
有 64 個格子，第一個格子放一粒麥子，第二個放2粒，第三個放4粒...每個格子都是前邊的兩倍。一共有多少粒？
let sum = 0
let start = 1;
let end = 0;
function tow(){
    if(end>=64){
        return false
    }
    sum+=start
    start*=2
    end++
    tow()
}
tow()
console.log(sum)
使用遞歸實現數組快速排序方法
這個問題的核心思想是 取中間值，然大的放一邊，小的放一邊，然后再對兩邊執行一樣的操作，也就是遞歸了。
var mysort = function(arr){
    // 結束條件
    if(arr.length<=1){
        return arr
    }
    // 找基準值 數組中間值
    // 求下標
    var center = Math.floor(arr.length/2)
    var jZ = arr.splice(center,1)[0]
    // 創建兩個空數組
    var left = [] , right = [];
    // 循環數組，并進行比較
    for(var i=0;i
九九乘法表
// 遞歸
function num(nums){
    if(nums==1){
        console.log("1x1=1")
    }else{
        num(nums-1)
        for(var i=1,str="";i<=nums;i++){
            str += `${i}x${nums}=`+i*nums+" "
        }
        console.log(str)
    }
}
num(9)
// 循環
for(var i=1;i<10;i++){
    let str = ""
    for(var j=1;j<10;j++){
        if(i>=j){
            str += `${j}x${i}=`+i*j+" "
        }
    }
    console.log(str)
}

GPU云服務器云服務器 linux的面試題 js的基礎面試題棧面試題筆試面試題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/102825.html

前端經典面試題總結

摘要：接著我之前寫的一篇有關前端面試題的總結，分享幾道比較經典的題目第一題考點作用域，運算符栗子都會進行運算，但是最后之后輸出最后一個也就是那么其實就是而且是個匿名函數，也就是屬于，就輸出第二和第三個都是類似的，而且作用域是都是輸出最后一個其實就接著我之前寫的一篇有關前端面試題的總結，分享幾道比較經典的題目：第一題： showImg(https://segmentfault.com/im...

BlackMass 2019-08-23 16:29 評論0 收藏0
高級函數技巧-函數柯里化

摘要：如果你對函數式編程有一定了解，函數柯里化是不可或缺的，利用函數柯里化，可以在開發中非常優雅的處理復雜邏輯。同樣先看簡單版本的方法，以方法為例，代碼來自高級程序設計加強版實現上面函數，可以換成任何其他函數，經過函數處理，都可以轉成柯里化函數。我們經常說在Javascript語言中，函數是一等公民，它們本質上是十分簡單和過程化的。可以利用函數，進行一些簡單的數據處理，return 結果，...

shixinzhang 2019-08-23 15:25 評論0 收藏0
前端面試題收集，持續更新中

摘要：對于所訪問的每個元素，函數應該將該元素傳遞給所提供的回調函數。 HTML 在線閱讀Github地址題目列表 HTML HTML和XHTML的區別 Html的語義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區別 HTML全局屬性(global attribute)有哪些？常見的瀏覽器內核有哪些？介紹一下你對瀏覽器內核的理解？...

kgbook 2019-08-22 16:49 評論0 收藏0
前端面試題收集，持續更新中

摘要：對于所訪問的每個元素，函數應該將該元素傳遞給所提供的回調函數。 HTML 在線閱讀Github地址題目列表 HTML HTML和XHTML的區別 Html的語義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區別 HTML全局屬性(global attribute)有哪些？常見的瀏覽器內核有哪些？介紹一下你對瀏覽器內核的理解？...

2json 2019-08-29 15:12 評論0 收藏0
前端面試題收集，持續更新中

摘要：對于所訪問的每個元素，函數應該將該元素傳遞給所提供的回調函數。 HTML 在線閱讀Github地址題目列表 HTML HTML和XHTML的區別 Html的語義化 Doctype的文檔類型 cookie、sessionSttorage、localStory區別 HTML全局屬性(global attribute)有哪些？常見的瀏覽器內核有哪些？介紹一下你對瀏覽器內核的理解？...

adam1q84 2019-08-02 10:17 評論0 收藏0