Re: [cpp] 一道题目

[analyst]

先把数组排个序，然后把正负分成两个过程开始找解，找解过程用试探回溯就可以了。


在06-9-20，DarkSpy <coneos at 21cn.com> 写道：
>
> 云风,您好！
>
> 不知道大家对我出的题目感不感兴趣, 其实看起来好像蛮无聊的.
>
>     一组数字, 允许 float, 带符号,
>     输入一个结果 X, 要求
>
>     所有这组数字相加, 每个数字只能在表达式里面用一次, 计算和, 等于这个结果 X,
> 如果没有匹配的, 就输出所有可能最接近的 和 以及该表达式, 正负最接近结果都需要
>
> 例如
> 1
> 2
> 3
> 4
> 5
> 要求结果是 10.2
>
> 结果为正的最接近表达式:
> 1 + 2 + 3 + 5 = 11, 相差 0.8
>
> 结果为负的最接近表达式
> 1 + 2 + 3 + 4 = 10, 相差: -0.2
> 2 + 3 + 5 = 10,     相差: -0.2
>
>
> ======= 2006-09-20 您在来信中写道：=======
>
> >我向广大的数字朋友认个错，如果不是我把数字分了等级，就不会多花这么多时间了。我们应该承认数字人人平等。
> >
> >刚开始看到题还想，如果是 2 进制的，就好算了。只有 0 和 1 大家平等。其实 10 进制里的 0~9 也是平等的兄弟啊。
> >
> >在 06-9-20，卢立璵(bad_fish)<luliyi1024 at gmail.com> 写道：
> >> 晕倒，大家抢楼啊，动作还真快。
> >>
> >> On 9/20/06, 卢立璵(bad_fish) <luliyi1024 at gmail.com> wrote:
> >> > 既然 Google 的面试题目不能用计算机，那就只好用笔算了，如果没有笔的话（汗），我们就凭空YY就好了：
> >> >
> >> > 按照 Cloud 的说法：
> >> >
> >> > f(200000)=f(99999)*2+100000
> >> >
> >> > 没错！
> >> >
> >> > 现在算 f(99999)
> >> > 可以看成 0~99999
> >> > 既 00000~99999
> >> > 一共 100000 个数字，每个数字有 5 位，一共就是 100000*5 = 500000 位
> >> > 0123456789 每个数字出现的概率相同
> >> > 因此 1 出现的次数为 500000/10 = 50000 次
> >> >
> >> > 那么
> >> > f(200000) = 50000*2 + 100000 = 200000
> >> >
> >> > !!!!GOOD和云风的结果一样：）
> >> >
> >> > On 9/20/06, cloud <cloudwu at gmail.com> wrote:
> >> > > 我是来看大腕版 google 面试题的 :)
> >> > >
> >> > > 最近写程序忙，没留意这里，原来这么热闹了。刚才一边吃饭一边想了一下。
> >> > > 既然是面试题，肯定没计算机用了，只能拿笔算。
> >> > >
> >> > > 我想应该是这样的， 0~200000 的数字不太好算，大概可以这样算
> >> > > f(200000)=f(99999)*2+100000
> >> > >
> >> > > 现在来算 f(99999),
> >> > > 0~99999 一共 10万个数字, 这些数字怎么分布的呢
> >> > >
> >> > > 没有 1 的低等数字有 9^5 之多.
> >> > > 有一个 1 的贱民有 9^4 *5
> >> > > 有两个 1 的平民有 9^3 *10
> >> > > 有3个 1 的中产阶级有 9^2 *10
> >> > > 有4个 1 的贵族有 9 *5
> >> > > 有5个 1 的仅有一个。
> >> > >
> >> > > 以上数字加起来 f(99999)=9^4 *5 + 9^3 *10*2 + 9*9 *10*3 + 9*5*4 +1*5
> >> > > 本着不用计算机的原则，我用铅笔算了一下，结果为 615*81+185=50000
> >> > > 那么 f(200000)=200000
> >> > > 寒一个，不太像巧合吧。
> >> > >
> >> > >
> >> > > 在 06-9-19，Chen Shuo<giantchen at gmail.com> 写道：
> >> > > > 最后一句改为"你就用个STL都不好意思跟人打招呼"似乎效果更佳。
> >> > > >
> >> > > > On 9/19/06, 卢立璵(bad_fish) <luliyi1024 at gmail.com> wrote:
> >> > > > > 楼上的握手
> >> > > > > 写个C++程序就得什么库什么技巧都用上，什么 boost stlport loki 范型 CTP Policy
> >> > > > > ，什么晦涩用什么，这年头，你就用个class都不好意思跟人打招呼。
> >> > > > >
> >> > > > > On 9/19/06, cat street <gamcat at gmail.com> wrote:
> >> > > > > > 启发蚂蚁神经遗传退火 :D
> >> > > > > > _______________________________________________
> >> > > > > > Cpp mailing list
> >> > > > > > Cpp at codingnow.com
> >> > > > > > http://codingnow.com/mailman/listinfo/cpp
> >> > > > > >
> >> > > > > >
> >> > > > >
> >> > > > > _______________________________________________
> >> > > > > Cpp mailing list
> >> > > > > Cpp at codingnow.com
> >> > > > > http://codingnow.com/mailman/listinfo/cpp
> >> > > > >
> >> > > >
> >> > > > _______________________________________________
> >> > > > Cpp mailing list
> >> > > > Cpp at codingnow.com
> >> > > > http://codingnow.com/mailman/listinfo/cpp
> >> > > >
> >> > >
> >> > >
> >> > > --
> >> > > http://blog.codingnow.com
> >> > >
> >> > > _______________________________________________
> >> > > Cpp mailing list
> >> > > Cpp at codingnow.com
> >> > > http://codingnow.com/mailman/listinfo/cpp
> >> > >
> >> >
> >>
> >> _______________________________________________
> >> Cpp mailing list
> >> Cpp at codingnow.com
> >> http://codingnow.com/mailman/listinfo/cpp
> >>
> >
> >
> >--
> >http://blog.codingnow.com
> >
> >_______________________________________________
> >Cpp mailing list
> >Cpp at codingnow.com
> >http://codingnow.com/mailman/listinfo/cpp
> >
>
> = = = = = = = = = = = = = = = = = = = =
>
>
>                     致
> 礼！
>
>                DarkSpy
>                coneos at 21cn.com
>                                         2006-09-20
>
> _______________________________________________
> Cpp mailing list
> Cpp at codingnow.com
> http://codingnow.com/mailman/listinfo/cpp
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://codingnow.com/pipermail/cpp/attachments/20060922/3304f39a/attachment-0001.html