用火柴棒生成数字的算法
我编写了一个程序来解决 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 尝试过,但我正在摆弄二维状态数组。这里的解决方案要好得多。谢谢!
I made a program to solve this problem from the ACM.
Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:
This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.
Input
On the first line one positive number: the number of testcases, at most 100. After that per testcase:
One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have.
OutputPer testcase:
One line with the smallest and largest numbers you can create, separated by a single space. Both numbers should be positive and contain no leading zeroes.
Sample Input4
3
6
7
15
Sample Output7 7
6 111
8 711
108 7111111
The problem is that it's way too slow to solve it for 100 matchsticks. The search tree is too big to bruteforce it.
Here are the results for the first 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
The pattern for the maximums is easy but I don't see a shortcut for the minimums. Can someone suggest a better way to solve this problem? Here is the code I used:
#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;
}
EDIT : I ended up using the dynamic programming solution. I tried it with dp before but I was messing around with a two-dimensional state array. The solutions here are much better. Thanks!
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(6)
您可以使用动态规划解决方案。
假设您有 n 个匹配项,并且您知道如何解决所有
nk
匹配项的问题(最小数量),其中k
取与该数字对应的所有值每个数字使用的匹配数(2 对应 1,5 对应 3,等等)然后递归导出解决方案。假设您的数字以 1 结尾(在最不重要的位置),则通过编写
(n-2 个匹配的最佳解决方案)1
即可获得最佳解决方案。假设您以 2 结束,则最佳解决方案是(n-5 个匹配的最佳解决方案)2
。等等 ;最终你可以比较这十个数字,并选出最好的一个。所以现在,您所要做的就是递归地为所有小于您的输入的
n
设计最佳解决方案。编辑:如果您以简单的方式实现此算法,您最终会得到指数级的复杂性。这里的技巧是要注意,如果您的核心函数
MinimumGivenNMatches
仅采用一个参数n
。因此,您最终将使用相同的值多次调用它。为了使复杂度呈线性,您只需使用辅助数组记住(即记住)每个
n
的解决方案。You can use a dynamic programming solution.
Suppose that you have n matches, and you know how to solve the problem (minimum number) for all set of
n-k
matches, wherek
takes all the values corresponding to the number of matches that each number uses (2 for 1, 5 for 3, etc.)The solution is then derived recursively. Supposing that you end your number with a one (in the least significant position), then the best solution is obtained by writing
(best solution with n-2 matches) 1
. Supposing you end it with a two, the best solution is(best solution with n-5 matches) 2
. And so on ; eventually you can compare these ten numbers, and pick the best one.So now, all you have to do is devise the best solution for all
n
smaller than your input, recursively.EDIT: If you implement this algorithm in a straightforward way, you'll end up with an exponential complexity. The trick here is to notice that if your core function
MinimumGivenNMatches
, only takes one parameter,n
. Hence you'll end up calling it with the same values a huge number of times.To make the complexity linear, you just need to memoize (ie. remember) the solution for each
n
, using an auxiliary array.为了找到结果:
应选择每个数字,以便存在剩余数字的解决方案。
每个数字需要 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。
此问题的编辑代码
In order to find the result :
Every digit should be chosen so that there exists a solution for remaining digits.
Each digit requires between 2 and 7 matches. So you must choose the smallest Nth "top" digit that leaves the number of remaining matches between 2*(N-1) and 7*(N-1).
Do not forget that 0 has to be excluded from the search for the most significant digit of the result.
As a sidenote, one reason which makes this algorithm work is the fact that there is at least one corresponding digit for every value (of matches) between 2 and 7.
EDIT : example for 10 matches
10 matches --> 2 digits
Acceptable number of matches for top digit = between 3 and 7.
Smallest digit which requires between 3 and 7 matches -> 2 (which takes 5 matches), 0 being excluded.
Chosen first digit = 2
5 remaining matches -->
Acceptable number of matches for second (and in this case last) digit = exactly 5
Smallest digit which requires 5 matches -> 2
Chosen second digit = 2
Result = 22.
EDIT code for this problem
使用动态编程而不是递归。存储计算值并重复使用它们的速度要快得多。事实上,它将指数运行时间变成了多项式运行时间。
基本思想是有一个数组
min
来跟踪使用n
根火柴棍可以制作的最小数量。所以Use dynamic programming instead of recursion. It's significantly faster to store calculated values and re-use them. In fact, it turns an exponential running time into a polynomial one.
The basic idea is to have an array
min
which keeps track of the minimum number that can be made using exactlyn
matchsticks. So对于最小值,请注意,由于不允许使用前导零,因此您需要最小化位数。最小位数为
ceil(n/7)
。然后很容易计算出前导数字中必须使用的最小火柴棒数量,从中您可以获得前导数字的最小可能值。
For the minima, note that because no leading zeros are allowed, you want to minimize the number of digits. The minimal number of digits is
ceil(n/7)
.Then it's quite easy to calculate the minimum number of matchsticks which MUST be used in the leading digit, from that you get the smallest possible value of the leading digit.
我能够用
O(d)
解决问题,其中 d 是位数。这个想法是,首先我们计算所需最小数字的最小位数。这可以通过int nofDigits = n/7+ ((0 == n%7) ? 0 : 1)
计算,其中n
是火柴棒的数量。现在创建一个nofDigits
数组。现在我们开始从最低有效数字到最大有效数字(MSD)之前的一位数字填充最大可能的火柴棒(7),最后将所有剩余的火柴棒分配给最高有效数字(MSD)。现在根据 MSD 的火柴棒数量有 3 种改进的可能性:第一,如果 MSD 的火柴棒数量为 1,那么我们可以通过从其相邻数字借一根火柴棒将其变为 2。 相当于 0
这将使相邻数字的火柴数量为 6,如果 MSD 的火柴数量为 4,则 2d,那么与之前的情况相同,我们可以将 MSD 的火柴数量增加到 5,这相当于到 2
3rd 如果 MSD 的火柴数量是 3,那么我们必须看看总位数是否大于 2,然后我们可以从 MSD 的两个相邻数字减 1,否则我们将相邻的一位数字递减两次,并将 MSD 的火柴数量增加 2
最后通过遍历数组并将火柴数量替换为相应的数字。
完整的程序:
I am able to solve the problem with
O(d)
, where d is the number of digits. The idea is, first we calculate the minimum number of digits for the desired minimum number. This can be calculated byint nofDigits = n/7+ ((0 == n%7) ? 0 : 1)
, wheren
is the number of matchsticks. Now create an array ofnofDigits
. Now we start filling maximum possible matchsticks (7) from least significant digit till one digit before max significant digit (MSD) and in the end assign all remaining matchsticks to the most significant digit (MSD). Now there are 3 possibilities of improvement depending on the number of matchsticks for MSD:1st if the number of matchsticks for MSD is 1, then we can make it 2 by borrowing one matchstick from its adjacent digit. That will make the number of matchsticks for the adjacent digit 6, which is equivalent to 0
2d if the number of matchsticks for MSD is 4, then also same as previous case we can increment the number of matchsticks for MSD to 5, which is equivalent to 2
3rd if the number of matchsticks for MSD is 3, then we have to see if total number of digit is more than 2 then we can decrement 1 from two adjacent digits of MSD or else we will decrement one adjacent digit twice and increment number of matchsticks for MSD by 2
In the end by traversing through the array and replace number of matchsticks with the corresponding digit.
The complete program:
这就是我的回答,希望对你有帮助
This is my answer, wish it be helpful