1

这个想法是，给定 n 个空格、空字段或你有什么，我可以放置一个从 0 到 m 的数字。因此，如果我有两个空格并且只有 01 ，则结果将是： (0 1) (1 0) (0 0) (1 1)

如果我有两个空格和三个数字（0 1 2），结果将是

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

依此类推，直到我得到所有 9 (3^2) 个可能的结果。

因此，我正在尝试编写一个程序，如果我有 n 个空格并且可以在其中任何一个空格中放置从 0 到 m 的任意数字，它将给我所有可能的结果。

最初我想使用 for 循环，但是当我意识到我必须为 n 之前的每个数字制作一个时，这很快就被击落了，而且它不适用于 n 更大的情况。

我的想法是使用随机数生成器并生成一个从 0 到 m 的数字，但这并不能保证我实际上会得到所有可能的结果。

我被卡住了:(

想法？

任何帮助深表感谢 ：）

4

4 回答 4

4

每当一项任务需要找到“全部”某物时，您应该首先尝试按以下三个步骤完成：我可以将它们按某种顺序排列吗？我可以找到下一个给定的吗？我能找到第一个吗？

所以如果我让你给我从 1 到 10 的所有数字，你会怎么做？嗯，这很容易，因为：您知道一种简单的方法来整理它们。你可以给我下一个给他们任何一个。你知道哪个是第一个。所以你从第一个开始，然后继续下一个，直到你完成。

同样的方法也适用于这个问题。你需要三种算法：

  1. 一种对输出进行排序的算法，使得每个输出都大于或小于其他所有可能的输出。（您无需编写代码，只需了解即可。）

  2. 一种将任何输出转换为下一个输出的算法，如果给出最后一个输出则失败。（您确实需要对此进行编码。）

  3. 一种生成第一个输出的算法，比其他所有可能的输出少一个（根据第一个算法）。（您确实需要对此进行编码。）

然后很简单：

  1. 生成第一个输出（使用算法 3）。输出它。

  2. 使用增量算法（算法 2）生成下一个输出。如果没有下一个输出，则停止。否则，输出它。

  3. 重复步骤 2。

更新：以下是一些可能的算法：

算法1：

  1. 比较两个输出的第一个数字。如果一个大于另一个，则该输出更大。如果相等，继续

  2. 重复移动到连续数字的步骤，直到我们发现不匹配。

算法2：

  1. 从最右边的数字开始。

  2. 如果这个数字不是它可以达到的最大值，增加它并停止。

  3. 我们在最左边的数字吗？如果是这样，请停止错误。

  4. 将数字指针左移一位。

算法3：

  1. 将所有数字设置为零。
于 2012-12-07T19:36:23.983 回答
4

基本上，您需要的是起点、终点以及从每个状态转换到下一个状态的方法。例如，递归函数能够将一个数字添加到您需要的最小步速值，当它大于最大值时，增加下一个更大的数字并将当前的数字设置回零。

以此为例： 

#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范围内的每个数字是同构的。

这意味着要计算一个外部循环（为此，您可以使用 C++++增量运算符），以及一个用于提取和显示数字的内部循环。对于内部循环，您可以使用 C++ 的/除法运算符，并且根据您发现最清楚的内容，还可以使用%余数运算符。除非您将自己限制为 C++ 标准库直接支持的三种 R 选择，在这种情况下使用标准格式化程序。

请注意，R n可以快速变大。

所以不要将输出重定向到您的打印机，并准备等待一段时间让程序完成。

于 2012-12-07T19:58:25.650 回答
1

我认为您需要查找递归。http://www.danzig.us/cpp/recursion.html

基本上它是一个调用自身的函数。这允许您执行 N 次嵌套的 for 循环。

于 2012-12-07T19:36:34.763 回答