y******n
发帖数: 67 | 1 You are given a positive integer A. The goal is to construct the shortest
possible sequence of integers ending with A, using the following rules:
the first element of the sequence is 1,
each of the successive elements is the sum of any two preceding elements (
adding a single element to itself is also permissible),
each element is larger than all the preceding elements; that is, the
sequence is increasing.
For example, for A = 42, a possible solutions is [1, 2, 3, 6, 12, 24, 30, 42
]. Another possible solution is [1, 2, 4, 5, 8, 16, 21, 42].
Is it possible to use dynamic programming here? | e******x
发帖数: 184 | 2 Mark! 没想法。。
我猜是偶数，f(2n) = f(n) + 1； 奇数，f(2n+1) = f(2n) + 1.......
抛砖引玉了。 | c****p
发帖数: 6474 | 3 刚才出去吃饭时候也是这么想的，但是好像不行。
15: 1 2 3 6 9 15
用这个办法的话：
1 2 3 6 7 14 15
【在 e******x 的大作中提到】
: Mark! 没想法。。
: 我猜是偶数，f(2n) = f(n) + 1； 奇数，f(2n+1) = f(2n) + 1.......
: 抛砖引玉了。
| e******x
发帖数: 184 | | h****e
发帖数: 928 | 5 是不是这样：
如果N是奇数的话，
N=3 => 1, 2, 3 (size = 3)
N>3 => 1, (N-1)/2, (N+1)/2, N (size=4)
如果N是偶数的话，N=2^k*M，M是奇数，那么
M=3, size = k+3
M>3, size = k+4
例如 100 -> 1, 12, 13, 25, 50, 100 (size = 6)
42 -> 1, 10, 11, 21, 42 (size = 5)
12 -> 1, 2, 3, 6, 12 (size = 5) | c****p
发帖数: 6474 | 6 设steps(i)为实现i需要的最小步数
steps(2)=2;
对于i>2
若i为偶:
steps(i) = steps(i/2)+1
若i为奇:
a)若i为质数，steps(i) = steps(i-1) + 1
b)若i为合数，且i = k1*k2*...kn（k1....kn均为质数），
则steps(i) = (sum(steps(kj)-1))+1（j=1....n）。
生成数列有点麻烦【 在 yangchan (yangchan) 的大作中提到: 】
42 | e******x
发帖数: 184 | 7 LS牛逼！虽然不懂怎么严格证明，应该是对的吧~~ | c****p
发帖数: 6474 | 8 解释一下：
对于一个奇合数（简单起见）n=k1*k2，且k1
那么我们可以这样生成数列，
1.先生成k1。
2.以k1为起点，生成k1*k2，这个过程其实就是以1为起点，生成k2的过程。
举例：
15 = 3 * 5
先生成3: 1 2 3，再以3为起点，生成3*5：3*(1, 2, 3, 5)
所以最后的数列就是：(1 2 [3) 6 9 15]
再举例：
105 = 3 * 5 * 7
先生成3（其实先生成7也一样）： 1 2 3，
再生成5： 1 2 3 5
最后生成7: 1 2 3 5 7
最后的序列是：
( 1 2 [3) 6 9 {15] 30 45 75 105}
总步数就是生成每个质因数的步数-1的和再加1。【 在 chenpp (chenpp) 的大作中提
到: 】 | e******x
发帖数: 184 | | h****e
发帖数: 928 | 10 不太明白这道题的意思了：对于15来说，(1,7,8,15)算是满足
条件的序列吗？ | | | c****p
发帖数: 6474 | 11 是的，刚才蹲厕的时候想到这个了。。。
说白了就是先分解质因数，然后一个质因数一个质因数地生成就行了。
生成序列的代码倒是有点不太好写。。。
【在 e******x 的大作中提到】
: 其实i为偶数也包括在合数那个情况里面
| c****p
发帖数: 6474 | 12 序列中每一个数都得是它前面两个元素的和。
【在 h****e 的大作中提到】
: 不太明白这道题的意思了：对于15来说，(1,7,8,15)算是满足
: 条件的序列吗？
| e******x
发帖数: 184 | 13 应该还好吧，明天有空写个~
【在 c****p 的大作中提到】
: 是的，刚才蹲厕的时候想到这个了。。。
: 说白了就是先分解质因数，然后一个质因数一个质因数地生成就行了。
: 生成序列的代码倒是有点不太好写。。。
| c****p
发帖数: 6474 | 14 需要储存已经计算过的质因数的生成方式，
不然代价太大。
【在 e******x 的大作中提到】
: 应该还好吧，明天有空写个~
| h****e
发帖数: 928 | 15 明白了，漏看了第二个数。
【在 c****p 的大作中提到】
: 序列中每一个数都得是它前面两个元素的和。
| l*********8
发帖数: 4642 | 16 zan!
【在 c****p 的大作中提到】
: 解释一下：
: 对于一个奇合数（简单起见）n=k1*k2，且k1: 那么我们可以这样生成数列，
: 1.先生成k1。
: 2.以k1为起点，生成k1*k2，这个过程其实就是以1为起点，生成k2的过程。
: 举例：
: 15 = 3 * 5
: 先生成3: 1 2 3，再以3为起点，生成3*5：3*(1, 2, 3, 5)
: 所以最后的数列就是：(1 2 [3) 6 9 15]
: 再举例：
|
|
