S**Y
发帖数: 136 | 1 1。 有一个binary search tree, 现在给每个 Node多两个field (Node*), 可以指向另
一个Node. 要求traverse tree,把同层的Node全部连起来。
2。 一个正整数，可以分成许多正整数的和，比如 8 可以分成 3+4+1, 如何分才能使这
些数的乘积最大？
怎么解决？第二个是经典题么？ | t****t
发帖数: 6806 | 2 第二题是经典(小学)数学题
分成尽可能多的3, 如果剩4就分成2+2
第一题不知道为什么要多两个node*, 多一个就够了啊
第一层是根, 第二层就是左子树指向右子树(if any)
以后每一层都从左向右遍历, 把每个节点的左子树和右子树头尾相连
使这
【在 S**Y 的大作中提到】
: 1。 有一个binary search tree, 现在给每个 Node多两个field (Node*), 可以指向另
: 一个Node. 要求traverse tree,把同层的Node全部连起来。
: 2。 一个正整数，可以分成许多正整数的和，比如 8 可以分成 3+4+1, 如何分才能使这
: 些数的乘积最大？
: 怎么解决？第二个是经典题么？
| m****o
发帖数: 114 | 3 how to prove it using 小学 only knowledge?
【在 t****t 的大作中提到】
: 第二题是经典(小学)数学题
: 分成尽可能多的3, 如果剩4就分成2+2
: 第一题不知道为什么要多两个node*, 多一个就够了啊
: 第一层是根, 第二层就是左子树指向右子树(if any)
: 以后每一层都从左向右遍历, 把每个节点的左子树和右子树头尾相连
:
: 使这
| c*****t
发帖数: 1879 | 4 1. Given N >= 4,
if even, then
(N / 2) * (N / 2) = N^2 / 4 >= N
if odd, then
(N - 1) / 2 * (N + 1) / 2 = (N^2 - 1) / 4 > N
Thus, N can be break into chunks of smaller than 4.
2. Given that 2^3 < 3^2, all fragments should be broken into chunks of
3, until 2,3,4 are left.
【在 m****o 的大作中提到】
: how to prove it using 小学 only knowledge?
| m****o
发帖数: 114 | 5 for the given problem. 8 can be broken into 3 + 5 OR 4 + 4, is every
case covered by your proof?
【在 c*****t 的大作中提到】
: 1. Given N >= 4,
: if even, then
: (N / 2) * (N / 2) = N^2 / 4 >= N
: if odd, then
: (N - 1) / 2 * (N + 1) / 2 = (N^2 - 1) / 4 > N
: Thus, N can be break into chunks of smaller than 4.
: 2. Given that 2^3 < 3^2, all fragments should be broken into chunks of
: 3, until 2,3,4 are left.
| e****d
发帖数: 333 | 6 8=3+3+2?
是这个意思？
【在 m****o 的大作中提到】
: for the given problem. 8 can be broken into 3 + 5 OR 4 + 4, is every
: case covered by your proof?
| e****d
发帖数: 333 | | S**Y
发帖数: 136 | 8 this is a good proof.
one more thing is, when there is 4 left, should be divided into 2+2 because
2*2 > 3*1
【在 c*****t 的大作中提到】
: 1. Given N >= 4,
: if even, then
: (N / 2) * (N / 2) = N^2 / 4 >= N
: if odd, then
: (N - 1) / 2 * (N + 1) / 2 = (N^2 - 1) / 4 > N
: Thus, N can be break into chunks of smaller than 4.
: 2. Given that 2^3 < 3^2, all fragments should be broken into chunks of
: 3, until 2,3,4 are left.
| e****d
发帖数: 333 | 9 这下圆满了。
because
【在 S**Y 的大作中提到】
: this is a good proof.
: one more thing is, when there is 4 left, should be divided into 2+2 because
: 2*2 > 3*1
| e****d
发帖数: 333 | 10 不过coconut 说是untill 2,3,4 are left.
所以也不用再拆开最后的4=2+2了。
because
【在 S**Y 的大作中提到】
: this is a good proof.
: one more thing is, when there is 4 left, should be divided into 2+2 because
: 2*2 > 3*1
| S**Y
发帖数: 136 | 11 yeah. coconut is right..
should be break the number into as many as possible 3s, until the remaining
is either 2, 3, or 4. | c*****t
发帖数: 1879 | 12 Yes. The first part is a non-constructive proof. That shows that any
pieces greater than or equal to 4 will need to be broken into smaller
pieces. The answer should only be consisted of 2's and 3's.
【在 m****o 的大作中提到】
: for the given problem. 8 can be broken into 3 + 5 OR 4 + 4, is every
: case covered by your proof?
|
|
