|
锁定老帖子 主题：google的一道面试题。
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2007-04-16
对于f(n)=？的计算。。
以上讨论的以f(9),f(99),f(999)。。。。。这种方法最快。。。 但是数值很大的话如123456789要分解好多次。。。 还是慢了一点哦。。。。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
你的那样会快？把证明或算法，或程序给出来，瞧瞧。
你可以运行下我给的那个程序，看看他的时间是多少. PS;我还是觉得这个题的算法好不好，关键在剪枝. |
| 返回顶楼 | |
|
发表时间：2007-04-16
我还没有说我的思路。。。。
我只是说上面众多讨论中我觉得f(9),f(99).. 这种思路还算快，但是我还是觉得他慢。。。 剪枝，我觉得还要看怎剪，不相信我先给结果。。。 程序以后再给。。。 结果。。后面还有1111111110 和10000000000由于溢出所以没算。。 1,0ms used! 199981,0ms used! 199982,0ms used! 199983,0ms used! 199984,0ms used! 199985,0ms used! 199986,0ms used! 199987,0ms used! 199988,0ms used! 199989,0ms used! 199990,0ms used! 200000,0ms used! 200001,0ms used! 1599981,16ms used! 1599982,16ms used! 1599983,16ms used! 1599984,16ms used! 1599985,16ms used! 1599986,16ms used! 1599987,16ms used! 1599988,16ms used! 1599989,16ms used! 1599990,16ms used! 2600000,16ms used! 2600001,16ms used! 35000000,16ms used! 35000001,16ms used! 35199981,31ms used! 35199982,47ms used! 35199983,47ms used! 35199984,47ms used! 35199985,47ms used! 35199986,47ms used! 35199987,47ms used! 35199988,47ms used! 35199989,47ms used! 35199990,47ms used! 35200000,47ms used! 35200001,47ms used! 500000000,47ms used! 500000001,47ms used! 500199981,47ms used! 500199982,47ms used! 500199983,47ms used! 500199984,47ms used! 500199985,47ms used! 500199986,47ms used! 500199987,47ms used! 500199988,62ms used! 500199989,62ms used! 500199990,62ms used! 500200000,62ms used! 500200001,62ms used! 501599981,62ms used! 501599982,62ms used! 501599983,62ms used! 501599984,62ms used! 501599985,62ms used! 501599986,62ms used! 501599987,62ms used! 501599988,62ms used! 501599989,62ms used! 501599990,62ms used! 502600000,62ms used! 502600001,62ms used! 535000000,62ms used! 535000001,62ms used! 535199981,62ms used! 535199982,62ms used! 535199983,62ms used! 535199984,62ms used! 535199985,62ms used! 535199986,62ms used! 535199987,62ms used! 535199988,62ms used! 535199989,62ms used! 535199990,62ms used! 535200000,62ms used! 535200001,62ms used! |
| 返回顶楼 | |
|
发表时间：2007-04-16
我说的分治是：
f(10^m)=? m=1 f(10)=1 m=2 f(100)=10*f(10)+K m=3 f(1000)=10*f(100)+K 当f(10^m)>10^m>10^(m-1)>f(10^(m-1))时命 中 |
| 返回顶楼 | |
|
发表时间：2007-04-16
哦！！
很好。。 阳光的解答和我看到题目的第一思路一样。。。 但是我随后就觉得还是较慢。 就算命中区间，也还是要在区间内搜索。。 想请教阳光的用时时多少？ 还有你既然想出这么好的思路为什么不再深入想想呢？ 你在算f(n)=?时用的是什么方法？ 只是求f(n)的方法，还有你下一步贪心怎样贪心 |
| 返回顶楼 | |
|
发表时间：2007-04-16
to mjy304122
我给的那个 c程序， f(1111111110) = 1111111110 花费 0ms. |
| 返回顶楼 | |
|
发表时间：2007-04-16
哦。。是吗。。
哈哈。。先说明讨论一下。。 楼主能帮助说明一下具体思路吗？ 你看到有那么多的计算用了30000ms的同志可辛苦了。。。 希望楼主帮忙说明思路。。。 我想说的是：如果题目算的不是“1”是“2”或“9” 有什么不一样？用2进制答案会是多少？3进制呢？ 16进制呢？ 你对题目理解多少？ 题目目的就更本不是要人们编程来解决问题。。。 题目就是问最大的f(n)=n是多少。。。 以上所有讨论就算算到1111111110也不是他的答案。。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
还有楼主给的c程序，我没细看只是大概看了看
看到人都晕了。。 速度究竟是否真那么快不知道。。 但我觉得内存用的较多了吧？ 简单的问题复杂化了。 楼主的c程序是自己写的吗？ 剪枝也是多次剪吧？ 我只用了一种很简单的思路，编的程序也很易懂。 道理很简单。。。速度也快。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
还有我用的是java
在计算时间上会与c不一样。。 但我能说我的思路绝对快。。。 从 35199981,31ms used! 35199982,47ms used! 与 500199987,47ms used! 500199988,62ms used! 可以看出不是编程上的时间差。。 和系统有关。 我觉得真正运算时间也是接近0ms的。 |
| 返回顶楼 | |
|
发表时间：2007-04-16
哦。。是吗。。
哈哈。。先说明讨论一下。。 楼主能帮助说明一下具体思路吗？ 你看到有那么多的计算用了30000ms的同志可辛苦了。。。 希望楼主帮忙说明思路。。。 我想说的是：如果题目算的不是“1”是“2”或“9” 有什么不一样？用2进制答案会是多少？3进制呢？ 16进制呢？ 你对题目理解多少？ 题目目的就更本不是要人们编程来解决问题。。。 题目就是问最大的f(n)=n是多少。。。 以上所有讨论就算算到1111111110也不是他的答案。。 还有楼主给的c程序，我没细看只是大概看了看 看到人都晕了。。 速度究竟是否真那么快不知道。。 但我觉得内存用的较多了吧？ 简单的问题复杂化了。 楼主的c程序是自己写的吗？ 剪枝也是多次剪吧？ 我只用了一种很简单的思路，编的程序也很易懂。 道理很简单。。。速度也快。 还有我用的是java 在计算时间上会与c不一样。。 但我能说我的思路绝对快。。。 从 35199981,31ms used! 35199982,47ms used! 与 500199987,47ms used! 500199988,62ms used! 可以看出不是编程上的时间差。。 和系统有关。 我觉得真正运算时间也是接近0ms的。 |
| 返回顶楼 | |
