欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JavaScript實(shí)現(xiàn)的一個(gè)計(jì)算數(shù)字步數(shù)的算法分享

 更新時(shí)間：2014年12月06日 11:02:50   投稿：junjie  
這篇文章主要介紹了JavaScript實(shí)現(xiàn)的一個(gè)計(jì)算數(shù)字步數(shù)的算法分享,本文先是講解了算法描述與實(shí)現(xiàn)原理,然后給出實(shí)現(xiàn)代碼,需要的朋友可以參考下

這兩天看了下某位大神的github,知道他對(duì)算法比較感興趣,看了其中的一個(gè)計(jì)算數(shù)字的步數(shù)算法,感覺(jué)這個(gè)有點(diǎn)意思,所以就自己實(shí)現(xiàn)了一個(gè)。

算法描述與實(shí)現(xiàn)原理

給出一個(gè)整型數(shù)字,統(tǒng)計(jì)出有多少種走法可以到達(dá)目標(biāo),比如一個(gè)數(shù)字4,可以有下面幾種走法

復(fù)制代碼 代碼如下:

    [ 1, 3 ]
        [ 4 ]
    [ 1, 1, 2 ]
        [ 2, 2 ]
    [ 1, 1, 1, 1 ]

其實(shí)通過(guò)上面的組合可以得出下面的結(jié)論。

1.先列出所有項(xiàng)是1的組合
2.依次從左到右項(xiàng)為1的組合
3.遞歸上面的集合,找出項(xiàng)里1的索引,然后計(jì)算左起2項(xiàng)的值,結(jié)果遞歸此操作
4.排除1和2的情況

下面先提供三個(gè)工具函數(shù)：

復(fù)制代碼 代碼如下:

// 計(jì)算數(shù)組內(nèi)的值
function calculate(arg){
    return eval(arg.join('+'));
}

// 輸出數(shù)組的值
function print(arg){
    for(var i = 0; i < arg.length; i++){
        console.log(arg[i]);
    }
}

// 檢查是否是正反的走法
function hasRepeat(src, dist){
    if (dist.length != 2) return false;
    for(var i = 0, len = src.length; i < len ; i++){
        if(dist.length == src[i].length){
            if(dist[0] == src[i][1]){
                return true;
            }
        }
    }
    return false;
}

下面貼出算法的實(shí)現(xiàn)：

復(fù)制代碼 代碼如下:

function countSteps(n){
    var counts = 0,i,j = 0;
    var result = [];
    var newresult = [];
    var source = [];
    var temparg = [];
    // 生成項(xiàng)全為1的數(shù)組
    for(i = 1; i <= n ; i++){
        source.push(1);
    }
    if(n > 2){
        for(j = 1; j < n - 1; j++){
            temparg.length = 0;
            if(j < n - 1){
                // 生成從左到右項(xiàng)為1遞增的數(shù)組
                // 1.. 11.. 111..
                Array.prototype.push.apply(temparg, source.slice(0, j));
                temparg.push(calculate(source.slice(j,n)));
                result.push(temparg.slice(0));
                // 遞歸數(shù)組里的內(nèi)容,直到項(xiàng)里沒(méi)有1為止
                combine(temparg.slice(0));
            }
        }
    }
    // 組合包含1的數(shù)組項(xiàng)
    // 111->21->3
    function combine(arg){
        var linearg = [];
        for(var i = 0; i < arg.length; i++){
            if(arg[i] == 1){
                if(i ==0 || i == 1){
                    linearg.push(calculate(arg.slice(0,2)));
                    Array.prototype.push.apply(linearg, arg.slice(2, arg.length));
                    if(!hasRepeat(result, linearg)){
                        result.push(linearg);
                        combine(linearg.slice(0));
                    }
                    return;
                }
            }
        }
    }
    //為2的時(shí)候比1要多一項(xiàng)
    if(n == 2){
        result.push([2]);
    }
    // 添加全為1的情況
    result.push(source);
    // 輸出所有步
    print(result);
    console.log('總共有:' + result.length + '種走法');
}

// 運(yùn)行
countSteps(4);

// 輸出下面內(nèi)容
/*
    [ 1, 3 ]
    [ 4 ]
    [ 1, 1, 2 ]
    [ 2, 2 ]
    [ 1, 1, 1, 1 ]
    總共有:5種走
*/

總結(jié)

這個(gè)算法其實(shí)可以應(yīng)用到某類(lèi)游戲中去,當(dāng)兩個(gè)物體之前的距離一定的話(huà),對(duì)所有的可能進(jìn)行業(yè)務(wù)處理,當(dāng)然也可以應(yīng)用到別的地方,雖然大部分前端工程師對(duì)算法的實(shí)踐比較少,不過(guò)它還是有存在的價(jià)值的,很多UI細(xì)節(jié)方面其實(shí)都運(yùn)用了算法,以后有空還會(huì)貼更多關(guān)于算法相關(guān)的文章,歡迎大家多提些寶貴意見(jiàn).

相關(guān)文章

最新評(píng)論