一道C＋＋面试编程题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Programming - 葵花宝典

一道C＋＋面试编程题

一道C＋＋面试编程题# Programming - 葵花宝典

s*d2007-01-09 08:01

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*t2007-01-09 08:01

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*r2007-01-09 08:01

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*t2007-01-09 08:01

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*r2007-01-09 08:01

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*d2007-01-09 08:01

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*d2007-01-09 08:01

7 楼

不过，不是最优解