algorithm - 与えられた数値から一意の値を計算する

Question

たとえば、6つの乱数があり、これらの数値から一意の値を計算したいとします。

編集： 許可される操作は+、-、*、および/です。すべての番号は1回しか使用できませんでした。すべての数字を使用する必要はありません。

例：

Given numbers: 3, 6, 100, 50, 25, 75
Requested result: 953

3 + 6 = 9
9 * 100 = 900
900 + 50 = 950
75 / 25 = 3
3 + 950 = 953

この問題を解決するプログラムを作成するための最も簡単なアルゴリズムアプローチは何でしょうか？

Answer 1

最も簡単なアプローチは、それらすべてを試すことです。6つの数値があります。つまり、演算子を配置できる場所は最大5つで、6!順列は最大です。オペレーターが4つしかないことを考えると6!*4^5、または737280の可能性を検討する必要があります。これは、再帰関数を使用して、またはネストされたループを使用して簡単に実行できます。言語によっては、ライブラリ関数を使用して順列を処理できます。

言語に依存しない再帰的アプローチでは、次の3つの関数を定義する必要があります。

int calc(int nums[6], int ops[5], int countNums) {
    // Calculate the results for a given sequence of numbers
    // with the specified operators.
    // nums are your numbers; only countNums need to be used
    // ops are your operators; only countNums-1 need to be used
    // countNums is the number of items to use; it must be from 1 to 6
}

void permutations(int nums[6], int perm[6], int pos) {
    // Produces all permutations of the original numbers
    // nums are the original numbers
    // perm, 0 through pos, is the indexes of nums used in the permutation so far
    // pos, is the number of perm items filled so far
}

void solveRecursive(int numPerm[6], int permLen, int ops[5], int pos) {
    // Tries all combinations of operations on the given permutation.
    // numPermis the permutation of the original numbers
    // permLen is the number of items used in the permutation
    // ops 0 through pos are operators to be placed between elements
    // of the permutation
    // pos is the number of operators provided so far.
}

Answer 2

最も簡単なアルゴリズムのアプローチは、バックトラックだと思います。実装はかなり簡単で、解決策があればいつでも見つけることができます。基本的な考え方は再帰的です。ソリューションを構築する各ステップで任意の選択を行い、そこから先に進みます。それがうまくいかない場合は、別の選択を試してください。選択肢がなくなった場合は、前の選択ポイントに失敗を報告します（または、前の選択ポイントがない場合は、解決策を見つけられなかったことを報告します）。

選択できるのは、関係する番号の数、各番号の数（各番号の位置の選択）、およびオペレーターによる接続方法（各オペレーターの位置の選択）です。

Answer 3

「一意の数」について言及するときは、手元にあるすべての数を使用して生成された結果の可能な宇宙の結果を意味すると仮定します。

もしそうなら、最初にすべての演算子と利用可能な数の順列を試してみませんか？

Answer 4

異なる数値のセットから同じ数値を取得する可能性がなく、それらの数値から一意の数値を生成することを保証したい場合は、10進数、16進数などと同様の基数演算を使用する必要があります。

ただし、数値の最大値を知る必要があります。

基本的にはA + B * MAX_A + C * MAX_A * MAX_B + D * MAX_A * MAX_B * MAX_C + E * MAX_A * MAX_B * MAX_C * MAX_D + F * MAX_A * ... * MAX_E

Answer 5

再帰を使用して、数値と演算子を並べ替えます。O（6！* 4 ^ 5）です