JavaScript_javascript スキルに実装されたデジタル ステップ数を計算するアルゴリズムを共有する

この2日間、ある師匠のgithubを見ていたら、アルゴリズムに興味があるということで、歩数計算のアルゴリズムが面白いと思ったので実装してみました。私自身も1つ。

アルゴリズムの説明と実装原理

整数が与えられた場合、ゴールに到達できる手数を数えます。たとえば、数字 4 には次のような手があります
。

コードをコピー コードは次のとおりです:

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

実際、上記の組み合わせから次の結論が導き出されます。

1. まず、項目が 1 であるすべての組み合わせをリストします
2. 左から右へ、アイテムが 1
である組み合わせ 3. 上記のセットを再帰し、項目内の 1 のインデックスを見つけて、左から 2 つの項目の値を計算します。結果は再帰演算
です。 4. 状況 1 と 2 を除外します

次の 3 つのツール機能が提供されます。

コードをコピーします コードは次のとおりです:

// 配列内の値を計算します
関数計算(引数){
Return eval(arg.join(' '));
}

//配列の値を出力します
関数 print(arg){
for(var i = 0; i console.log(arg[i]);
}
}

// 前進か後退かを確認します
関数 hasRepeat(src, dist){
(dist.length != 2) の場合は false を返します;
for(var i = 0, len = src.length; i If(dist.length == src[i].length){
If(dist[0] == src[i][1]){
return true;
}
}
}
false を返します;
}

アルゴリズムの実装は以下に掲載されています:

コードをコピー コードは次のとおりです:

関数 countSteps(n){
var カウント = 0,i,j = 0;
var result = [];
var newresult = [];
var ソース = [];
var temparg = [];
// すべての項目が 1
である配列を生成します for(i = 1; i source.push(1);
}
If(n > 2){
for(j = 1; j Temparg.length = 0;
if(j // 左から右に 1 ずつ増加する項目を含む配列を生成します
// 1.. 11.. 111..
Array.prototype.push.apply(temparg,source.slice(0, j));
temparg.push(calculate(source.slice(j,n)));
result.push(temparg.slice(0));
// 項目
に 1 がなくなるまで配列の内容を再帰します。 combine(temparg.slice(0));
}
}
}
// 1
を含む配列項目を結合します // 111->21->3
関数結合(arg){
var Linearg = [];
for(var i = 0; 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の場合は1より項目が1つ多くなります
If(n == 2){
result.push([2]);
}
// すべてが 1 の場合を追加
result.push(ソース);
// すべてのステップを出力します
印刷(結果);
console.log('合計:' result.length '移動数');
}

//実行
countSteps(4);

// 以下の内容を出力します
/*
[ 1, 3 ]
[ 4 ]
[ 1、1、2 ]
[ 2, 2 ]
[ 1、1、1、1 ]
ウォーキングの種類は全部で5種類
*/

概要

このアルゴリズムは、実際には、2 つのオブジェクト間の距離が一定である場合には、他の場所にも適用できますが、ほとんどのフロントエンド エンジニアは適用できません。アルゴリズムについてはあまり実践されていませんが、実際には多くの UI で使用されています。今後、時間があるときにアルゴリズムに関する記事を投稿します。