1

アイデアは、n 個のスペース、空のフィールド、またはあなたが持っているものが与えられた場合、0 から m までの数字のいずれかに配置できるということです。したがって、2 つのスペースと 01 だけがある場合、結果は (0 1) (1 0) (0 0) (1 1) になります。

2 つのスペースと 3 つの数字 (0 1 2) がある場合、結果は次のようになります。

(0 1) (1 1) (0 2) (2 0) (2 2) (2 1)

9 (3^2) 通りの結果が得られるまで続けます。

したがって、n個のスペースがあり、それらのスペースのいずれかに0からmまでの任意の数を配置できる場合に、考えられるすべての結果が得られるプログラムを作成しようとしています。

もともと for ループを使用することを考えていましたが、n までのすべての数値に対して 1 つを作成する必要があり、n が大きい場合には機能しないことに気付いたとき、それはすぐに失敗しました。

乱数ジェネレーターを使用して 0 から m までの数値を生成するというアイデアがありましたが、実際にすべての可能な結果が得られるとは限りません。

ハマった ：（

アイデア？

どんな助けでも大歓迎です:)

4

4 に答える 4

4

タスクで何かの「すべて」を見つける必要がある場合はいつでも、まず次の 3 つの手順を実行してみてください。与えられた次のものを見つけることができますか？最初に見つけることはできますか？

では、1 から 10 までのすべての数字を教えてくださいと言われたら、どのように答えますか? 理由は簡単です: それらを整理する簡単な方法を知っているからです。それらのいずれかが与えられた場合、次のものを私に与えることができます。どちらが最初かはわかります。したがって、最初から始めて、完了するまで次の作業に進みます。

これと同じ方法がこの問題にも当てはまります。次の 3 つのアルゴリズムが必要です。

  1. 各出力が他のすべての可能な出力よりも大きくなるか小さくなるように出力を並べ替えるアルゴリズム。(これをコーディングする必要はありません。理解するだけです。)

  2. 出力を次の出力に変換し、最後の出力が与えられた場合に失敗するアルゴリズム。(これをコーディングする必要があります。)

  3. 最初の出力を生成するアルゴリズム。(最初のアルゴリズムによると) 他のすべての可能な出力よりも 1 つ少なくなります。(これをコーディングする必要があります。)

それは簡単です：

  1. 最初の出力を生成します (アルゴリズム 3 を使用)。出力します。

  2. インクリメント アルゴリズム (アルゴリズム 2) を使用して、次の出力を生成します。次の出力がない場合は停止します。それ以外の場合は出力します。

  3. 手順 2 を繰り返します。

更新：可能なアルゴリズムは次のとおりです。

アルゴリズム 1:

  1. 2 つの出力の最初の桁を比較します。一方が他方よりも大きい場合、その出力は大きくなります。等しい場合は続行

  2. 不一致が見つかるまで、連続する桁に移動する手順を繰り返します。

アルゴリズム 2:

  1. 一番右の数字から始めます。

  2. この桁が可能な最大値でない場合は、増分して停止します。

  3. 一番左の桁ですか？その場合は、エラーで停止します。

  4. 桁ポインタを 1 桁左に移動します。

アルゴリズム 3:

  1. すべての桁をゼロに設定します。
于 2012-12-07T19:36:23.983 に答える
4

基本的に必要なのは、開始点、終了点、および各状態から次の状態に変換する方法です。たとえば、必要な最小のペース値に 1 つの数値を追加し、最大値よりも大きい場合は、次に大きい数値をインクリメントして現在の数値をゼロに戻すことができる再帰関数です。

たとえば、次のようにします。 

#include <iostream>
#include <vector>

using namespace std;

// This is just a function to print out a vector.
template<typename T>
inline ostream &operator<< (ostream &os, const vector<T> &v) {
    bool first = true;
    os << "(";
    for (int i = 0; i < v.size (); i++) {
        if (first) first = false;
        else os << " ";
        os << v[i];
    }
    return os << ")";
}

bool addOne (vector<int> &nums, int pos, int maxNum) {
    // If our position has moved off of bounds, so we're done
    if (pos < 0)
        return false;

    // If we have reached the maximum number in one column, we will
    // set it back to the base number and increment the next smallest number.
    if (nums[pos] == maxNum) {
        nums[pos] = 0;
        return addOne (nums, pos-1, maxNum);
    }

    // Otherwise we simply increment this numbers.
    else {
        nums[pos]++;
        return true;
    }
}

int main () {
    vector<int> nums;
    int spaces = 3;
    int numbers = 3;

    // populate all spaces with 0
    nums.resize (spaces, 0);

    // Continue looping until the recursive addOne() function returns false (which means we
    // have reached the end up all of the numbers)
    do {
        cout << nums << endl;    
    } while (addOne (nums, nums.size()-1, numbers));

    return 0;
}
于 2012-12-07T19:50:14.647 に答える
2

「n 個のスペースがあり、それらのスペースのいずれかに 0 から m までの任意の数を配置できる場合に、考えられるすべての結果が得られるプログラムを作成しようとしています。」

包括的な「to」を想定して、R = m + 1 とします。

次に、これは、ベース R 数値システムで示される0 から R n -1の範囲のすべての数値を出力することと同形です。

つまり、カウントする外側のループが 1 つ (このために C++ の++インクリメント演算子を使用できます)、数字を抽出して表示する内側のループがあります。内側のループには、C++ の/除算演算子を使用できます。最も明確なものに応じて、%剰余演算子も使用できます。C++ 標準ライブラリで直接サポートされている R の 3 つの選択肢に制限しない限り、その場合は標準のフォーマッタを使用します。

R nは急速に大きくなる可能性があることに注意してください。

そのため、出力をプリンターにリダイレクトせず、プログラムが完了するまでしばらく待つようにしてください。

于 2012-12-07T19:58:25.650 に答える
1

再帰を調べる必要があると思います。http://www.danzig.us/cpp/recursion.html

基本的には自分自身を呼び出す関数です。これにより、ネストされた for ループを N 回実行できます。

于 2012-12-07T19:36:34.763 に答える