プログラマ:N表示

(質問リンク)

質問する

以下に示すように、5と4の演算を使用して12を表すことができます.
12 = 5 + 5 + (5/5) + (5/5)
12 = 55/5 + 5/5
12 = (55 + 5)/5
5の使用回数はそれぞれ6,5,4である.その中で一番小さいのは4です.
Nとnumberが与えられた場合、Nと4則演算のみを使用するN使用回数の最高値を返すために、解法関数を作成します.
せいげんじょうけん

Nは1または9未満です.

は32000より大きい番号です.

式では、カッコとスラッシュの演算のみが許可され、除算演算で残りの部分は無視されます.

ピーク

が8より大きい場合は、-1を返します.

I/O例
Nnumberreturn51242113
I/O例説明
例1
問題の例は次のとおりです.
例211 = 22 / 2のような2回しか使用できません.

最初の解

Nと4則演算を用いてnumberを生成する方法では、Nを用いた最小値を見出すべきである.
したがって、Nを1回使用すると、numberが作成可能であれば、1が返される.
2回使用して作成できる場合は、2を返します.
3番を使うときにできることなら、3を8まで返却します.

反復文を使用して、Nおよび4則演算iを使用して生成できるすべての結果値を検索します.

にnumberがある場合、iが返されます.

可能なすべての結果値を保存すると、重複する値が保存される可能性があります.
だからSetを使いました
では、最も重要なNと4則演算iを使用して、すべての結果値を検索するプロセスは?
メソッドを話す前に、Nと4則演算を直接使用して数値を生成します.
Nの個数は、1 N 2 NN、N+N、N*N、N/N 3 NNN、N+(N+N)、N*(N+N)、N*(N+N)、N/(N+N)、N+(N-)、N*(N-)、N*(N-)、N*(N-(N-)、N-(N-)、N-(N-)、N-(N-)、N-(N-)、N-(N-)、N-(N-)、N-(N-)、N-(N-...
多すぎます.ここまでにしましょう.
つまり、試してみると4つの演算結果が重なっていることがわかります.
N個数の数字1 N 2 N+NとNの4則演算3 NN+NとNNの4則演算、Nと(N+N)の4則演算、Nと(N-N)の4則演算、Nと(N*N)の4則演算、1回Nと(N/N)の4則演算4 NNNNN+N、4回結果値の4則演算+N、2回結果値と2回結果値の4則演算+N、3回結果値と1回結果値の4則演算...
繰り返し文を作成し、繰り返しiのNを最初の文(N、NN、NNNなど)に配置します.iに従ってNを用いて四則演算を行う.
上記のN을 1번 사용한 결과값과 4번 사용한 결과값의 사칙연산 + N을 2번 사용한 결과값과 2번 사용한 결과값의 사칙연산 ...等の部分を実現するために、
繰り返し文iは、結果値を保存したSetを全て配列に入れる.(Setは重複除外用)
その配列にはSetが山積みになります[N을 1번만 사용한 결과값 Set, N을 2번만 사용한 결과값 Set, N을 3번만 사용한 결과값 Set, ...]これにより、アレイに順次格納され、Nおよびiを用いた結果が容易に分かる.
では、結果値セット間の4つの演算はどうすればいいのでしょうか.
1番目のSet要素と2番目のSet要素の間ですべての4つの演算を検索する関数が作成されました...(ダブルゲート)😥)
Setで他のSetを1つのSetにマージしようとしたが,適切な基本関数がなかったため,JavaScript Setドキュメントを参照した.(unionは集約の意味)
自分で作ることができますが、確かに正式なドキュメントコードは書きやすいです.😊

Set.prototype.union = function(setB) {
    var union = new Set(this);
    for (var elem of setB) {
        union.add(elem);
    }
    return union;
}

ソースコード

// Set1과 Set2의 사칙연산 결과 Set 반환
function operation(op1, op2) {
    let set = new Set();
    for (let item1 of op1) {
        for (let item2 of op2) {
            set.add(item1 + item2);
            set.add(item1 - item2);
            set.add(item1 * item2);
            set.add(Math.floor(item1 / item2));
        }
    }
    return set;
}

// N을 count만큼 반복한 숫자 반환
function Nrepeat(N, count) {
    let num = '';
    for (let i=0; i<count; i++) num += N;
    return Number(num);
}

//  Set + Set (합집합 함수)
Set.prototype.union = function(setB) {
    var union = new Set(this);
    for (var elem of setB) {
        union.add(elem);
    }
    return union;
}

function solution(N, number) { 
    // 모든 경우의 수 계산
    let calcul = [];
    for (let i=1; i<=8; i++) {
        let set = new Set();
        set.add(Nrepeat(N, i));
        
        for (let j=1; j<i; j++) {
            set = set.union(operation(calcul[j-1], calcul[i-j-1]));
        }
        // number가 있다면 N을 사용한 횟수 반환
        if (set.has(number)) return i;
        else calcul.push(set);
    }
    // 최솟값이 8보다 클 때
    return -1;
}

実行結果

第二の解釈

SetじゃなくArray
数値過大を防止するために,Setによる重複除外のほか,基本演算にはArrayを用いた.
チェックはArray.includes()であり,繰返しでない場合のみプッシュする方法では実行時間がかかりすぎるため,繰返しを解消するためにSetに変換する必要がある.
このようにしたのは,Arrayの基本演算がSetよりも速い文章を見て,時間効率がよくなるかどうか気になったからである.
ソースコード

function operation(op1, op2) {
    let arr = [];
    for (let i=0; i<op1.length; i++) {
        for (let j=0; j<op2.length; j++) {
            arr.push(op1[i]+op2[j], op1[i]-op2[j], op1[i]*op2[j], Math.floor(op1[i]/op2[j]));
        }
    }
    return arr;
}

function Nrepeat(N, count) {
    let num = 0;
    for (let i=0; i<count; i++) num += N * Math.pow(10, i); 
    return num;
}

function solution(N, number) {
    // 모든 경우의 수 계산
    let calcul = [];
    for (let i=1; i<=8; i++) {
        let arr = [];
        arr.push(Nrepeat(N, i));
        for (let j=1; j<i; j++) {
            arr.push(...operation(calcul[j-1], calcul[i-j-1]));
        }
        // 중복 제거
        arr = [...new Set(arr)];
        if (arr.includes(number)) return i;
        else calcul.push(arr);
        
    }
    return -1;
}

実行結果
1番目の解の実行時間が長いテストは、2番目の解の場合より長くなります.
従来の稼働時間が短いテストでも、より短い場合があり、容量が大きいほどSETが有利です.

に感銘を与える

Setを用いた例とArrayを用いた例はそれぞれ3回ずつ実行し,結果はほぼ上図と同様であった.
SetがArrayより運行時間が短い理由は何ですか?
Setは重複値を格納できないデータ構造である.
値入力時に重複の有無をチェックして入れるため,Setの基本演算速度はArrayより遅い.
実際,データの少ないテストではArrayの方が使用速度は速いが,データ量が大きいほどSetの使用速度は速くなる.
これは、データ量が大きいほどarr = [...new Set(arr)];にかかる時間が多くなるためと推測される.
Arrayの基本演算速度は速いが,重複を防止するためにSetに再変換するプロセスに比べて,最初からSetを用いて重複を防止することが正しいようである.