从匹配棒中制作数字的算法

Question

我制作了一个程序来解决ACM中的这个问题.

火柴棍是表示数字的理想工具.使用火柴棍表示十位小数的常用方法如下:

这与普通闹钟上的数字显示方式相同.使用给定数量的火柴棍,您可以生成多种数字.我们想知道使用所有火柴棍可以创建的最小和最大数字是多少.

输入

在第一行上有一个正数:测试用例的数量,最多为100.在每个测试用例之后:

一行整数n(2≤n≤100):你有的火柴数.产量

每个测试用例:

可以创建的最小和最大数字的一行,由单个空格分隔.两个数字都应该是正数并且不包含前导零.样本输入

4 3 6 7 15样品输出

7 7 6 111 8 711 108 7111111

问题是,要解决100个火柴棍问题太慢了.搜索树太大而无法强制执行.

以下是前10个的结果:

2:1 1

3:7 7

4:4 11

5:2 71

6:6 111

7:8 711

8:10 1111

9:18 7111

10:22 11111

最大值的模式很容易,但我没有看到最小值的快捷方式.有人可以建议一个更好的方法来解决这个问题吗？这是我使用的代码:

    #include <iostream>
    #include <string>
    using namespace std;

    #define MAX 20 //should be 100

    //match[i] contains number of matches needed to form i
    int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    string mi[MAX+1], ma[MAX+1];
    char curr[MAX+1] = "";

    //compare numbers saved as strings
    int mycmp(string s1, string s2)
    {
        int n = (int)s1.length();
        int m = (int)s2.length();
        if (n != m)
            return n - m;
        else
            return s1.compare(s2);
    }

    //i is the current digit, used are the number of matchsticks so far
    void fill(int i, int used)
    {
        //check for smaller and bigger values
        if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
        if (mycmp(curr, ma[used]) > 0) ma[used] = curr;

        //recurse further, don't start numbers with a zero
        for (int a = i ? '0' : '1'; a <= '9'; a++) {
            int next = used + match[a-'0'];
            if (next <= MAX) {
                curr[i] = a;
                curr[i+1] = '\0';
                fill(i + 1, next);
            }
        }
    }

    int main()
    {
        //initialise 
        for (int i = 0; i <= MAX; i++) {
            mi[i] = string(MAX, '9');
            ma[i] = "0";
        }

        //precalculate the values
        fill(0, 0);

        int n;
        cin >> n;

        //print those that were asked
        while (n--) {
            int num;
            cin >> num;
            cout << mi[num] << " " << ma[num] << endl;
        }

        return 0;
    }

编辑:我最终使用动态编程解决方案.我之前用dp尝试了它,但我正在弄乱二维状态数组.这里的解决方案要好得多.谢谢!

Answer 1

为了找到结果：

• 首先找到最小数的最小位数
• 然后从最高有效数字到最低有效数字。

应选择每个数字，以便存在剩余数字的解决方案。每个数字需要 2 到 7 个匹配项。因此，您必须选择最小的第 N 个“顶部”数字，使剩余匹配项的数量介于 2*(N-1) 和 7*(N-1) 之间。

不要忘记，在搜索结果的最高有效位时必须排除 0。

顺便说一句，该算法起作用的一个原因是 2 到 7 之间的每个（匹配）值都至少有一个对应的数字。

编辑： 10 个匹配的示例 10 个匹配 --> 2 位数字
最高数字可接受的匹配数量 = 3 到 7 之间。
需要 3 到 7 个匹配的最小数字 -> 2 （需要 5 个匹配），排除 0。
选择的第一个数字 = 2

剩余 5 个匹配项 -->
第二个（在本例中是最后一个）数字的可接受匹配数 = 恰好 5
需要 5 个匹配的最小数字 -> 2
选择的第二个数字 = 2

结果 = 22。

编辑此问题的代码

#include <iostream>
#include <vector>

std::vector<int> nbMatchesForDigit;

long long minNumberForMatches(unsigned int nbMatches)
{
    int nbMaxMatchesForOneDigit = 7;
    int nbMinMatchesForOneDigit = 2;
    int remainingMatches = nbMatches;
    int nbDigits = 1 + nbMatches / nbMaxMatchesForOneDigit; 
    long long result = 0;
    for (int idDigit = 0 ; idDigit < nbDigits ; ++idDigit )
    {
        int minMatchesToUse = std::max(nbMinMatchesForOneDigit, remainingMatches - nbMaxMatchesForOneDigit * (nbDigits - 1 - idDigit));
        int maxMatchesToUse = std::min(nbMaxMatchesForOneDigit, remainingMatches - nbMinMatchesForOneDigit * (nbDigits - 1 - idDigit));
        for (int digit = idDigit > 0 ? 0 : 1 ; digit <= 9 ; ++digit )
        {
            if( nbMatchesForDigit[digit] >= minMatchesToUse && 
                nbMatchesForDigit[digit] <= maxMatchesToUse )
            {
                result = result * 10 + digit;
                remainingMatches -= nbMatchesForDigit[digit];
                break;
            }
        }
    }
    return result;
}

int main()
{
    nbMatchesForDigit.push_back(6);
    nbMatchesForDigit.push_back(2);
    nbMatchesForDigit.push_back(5);
    nbMatchesForDigit.push_back(5);
    nbMatchesForDigit.push_back(4);
    nbMatchesForDigit.push_back(5);
    nbMatchesForDigit.push_back(6);
    nbMatchesForDigit.push_back(3);
    nbMatchesForDigit.push_back(7);
    nbMatchesForDigit.push_back(6);

    for( int i = 2 ; i <= 100 ; ++i )
    {
        std::cout << i << " " << minNumberForMatches(i) << std::endl;
    }
}