w*****e
发帖数: 158 | 1 1) given the whole range of 6 digit numbers, design an algorithm which
prints out numbers which have the sum of the right 3 digits equal the left
3 digits? like 123600, 345435 etc.
2）design an algorithm to find square_root of a float? how do you make the
algorithm efficient?
第一题：除了每个数检验之外，还有什么更快得方法吗？
第二题：貌似可以用bisection method 或者 Newton method， Newton method 收敛的
更快
一些。有什么地方需要注意或者可以改进，使得算法更有效？
希望大家指正，先谢谢了。 | t****a
发帖数: 1212 | 2 1. some ideas here:
a. the sum should be within [1, 27], for each number n we can decompose it
as:
n = i1 + i2 + i3, in which 0<=i<=9, so for n we should have a series of [i1,
i2, i3]
b. the left three digits shouldn't start with 0, so for the left three
digits the i1!=0
c. for each n, any combination of [[i1_1, i2_1, i3_1], [i2_1, i2_2, i3_2]]
fit your requirement. | A*********r
发帖数: 564 | 3 前几天有一道跟第一题类似的题，不过是求概率的，作为ｂｒａｉｎ ｔｅａｓｅｒ．
【在 w*****e 的大作中提到】
: 1) given the whole range of 6 digit numbers, design an algorithm which
: prints out numbers which have the sum of the right 3 digits equal the left
: 3 digits? like 123600, 345435 etc.
: 2）design an algorithm to find square_root of a float? how do you make the
: algorithm efficient?
: 第一题：除了每个数检验之外，还有什么更快得方法吗？
: 第二题：貌似可以用bisection method 或者 Newton method， Newton method 收敛的
: 更快
: 一些。有什么地方需要注意或者可以改进，使得算法更有效？
: 希望大家指正，先谢谢了。
| y*********e
发帖数: 518 | 4 第一题，假设输入是一个 set of 6 digits，要求输出的数字可以有重复的 digit。
比如，输入是 { 0, 1, 2, 3, 4, 5 }，一个输出可以是 123600
这个问题可以划分为2个问题：
问题一：从 set of 6 digits 里面，取出 2 组，每组各 3 个 digit，（允许有重复
的取），使得和相等。
问题二：对2个组的数字各自进行全排列。
因为考虑到重复的digit的存在，用上面的办法不是很方便阿。
觉得还是 naive 的办法最好，6个digit的数字最多有1,000,000个。直接扫描一遍即可。
但是还是可以加快的。这1,000,000个数字是对称的，比如我们检查了A1A2A3B1B2B3，
那么就可以知道B1B2B3A1A2A3了。这样可以把扫描的数量从1,000,000降低到
500,000。
第二题可以用2分法的思路解决。要注意float数字比较。
// assume num > 0
const float PRECISION = 0.00001;
float low = 0, high = num;
float middle, num
【在 w*****e 的大作中提到】
: 1) given the whole range of 6 digit numbers, design an algorithm which
: prints out numbers which have the sum of the right 3 digits equal the left
: 3 digits? like 123600, 345435 etc.
: 2）design an algorithm to find square_root of a float? how do you make the
: algorithm efficient?
: 第一题：除了每个数检验之外，还有什么更快得方法吗？
: 第二题：貌似可以用bisection method 或者 Newton method， Newton method 收敛的
: 更快
: 一些。有什么地方需要注意或者可以改进，使得算法更有效？
: 希望大家指正，先谢谢了。
| f***g
发帖数: 214 | 5 第一题:
当把6位数分为两组后。每组3位。
建立Array[1000], 记录三位数的和。
每次6位数分2组后查表。
可以节省一点时间 | a*******8
发帖数: 2299 | 6 把0-999处理一下,build 28个list
(0, (0))
(1, (001, 010, 100))
(2, (011, 110, 101, 002, 020, 200))
...
(27, (999))
对每个list中任意两个数(可以重复),两两combine直接输出,感觉还是罗嗦.
【在 f***g 的大作中提到】
: 第一题:
: 当把6位数分为两组后。每组3位。
: 建立Array[1000], 记录三位数的和。
: 每次6位数分2组后查表。
: 可以节省一点时间
| f***g
发帖数: 214 | 7 牛。
就是写起来麻烦。
1. 前三位不能是0开头的
2. 每一个combine，两个输出， 102201 和 201102
3. 如果是自己和自己combine，只有一个输出 |
|
