s***d
发帖数: 2 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: saiad (happy), 信区: JobHunting
标 题: 一道C＋＋面试编程题
发信站: BBS 未名空间站 (Mon Jan 8 21:06:55 2007), 转信
We have a string of digits, find the minimum number of additions required
for the string to equal some target number. Each addition is the equivalent
of inserting a plus sign somewhere into the string of digits. After all plus
signs are inserted, evaluate the sum as usual. For example, consider the
string "12" . With zero additions, we can achieve the number 12. If we
inse | m***t
发帖数: 254 | 2 this looks a lot like a top coder question, but anyway, the way to add is
only 2^10, you can use dynamic
programming or just exhaust the space with bruteforce.
equivalent
plus
So
【在 s***d 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: saiad (happy), 信区: JobHunting
: 标 题: 一道C＋＋面试编程题
: 发信站: BBS 未名空间站 (Mon Jan 8 21:06:55 2007), 转信
: We have a string of digits, find the minimum number of additions required
: for the string to equal some target number. Each addition is the equivalent
: of inserting a plus sign somewhere into the string of digits. After all plus
: signs are inserted, evaluate the sum as usual. For example, consider the
: string "12" . With zero additions, we can achieve the number 12. If we
: inse
| f********r
发帖数: 50 | 3 it is a topcoder problem
i saw that before
brute force will do it
【在 m***t 的大作中提到】
: this looks a lot like a top coder question, but anyway, the way to add is
: only 2^10, you can use dynamic
: programming or just exhaust the space with bruteforce.
:
: equivalent
: plus
: So
| m***t
发帖数: 254 | 4 i thought about it a bit, and having doubt on my original answer. Since we
are going for a specific target
number, not a minimal, i doubt dynamic programming can be applied here. I
donot have a good dynamic
programming solution to this problem.
also the 2^10 should be 2^9.
【在 f********r 的大作中提到】
: it is a topcoder problem
: i saw that before
: brute force will do it
| f********r
发帖数: 50 | 5 here is the link to the problem
http://www.topcoder.com/tc?module=ProblemDetail&rd=5072&pm=2829
you may need to register an id to view it
【在 f********r 的大作中提到】
: it is a topcoder problem
: i saw that before
: brute force will do it
| s*******d
发帖数: 59 | 6 strings find_solution(string, N)
{
for (i=0; i < string.length; i++)
{
head = string.substring(0, i);
rest = find_solution(string+i，N - int.parse(part1));
if (rest != null)
{
return head + rest;
}
}
return null;
} | s*******d
发帖数: 59 | |
|
