Preparing NOJ

最短加法链问题

1000ms 65536K

Description:

   最优求幂问题:给定一个正整数n和一个实数x,如何用最少的乘法次数计算出xn 。例如,可以用6 次乘法逐步计算x23如下:xx 2x3x5x10x 20x23。可以证明计算x23最少需要6 次乘法。计算x23的幂序列中各幂次1235102023 组成了一个关于整数23的加法链。在一般情况下,计算xn 的幂序列中各幂次组成正整数n的一个加法链

                                

上述最优求幂问题相应于正整数n的最短加法链问题,即求n的一个加法链使其长度r达到最小。正整数n的最短加法链长度记为l(n)

对于给定的正整数n,编程计算相应于正整数n的最短加法链。

Input:

 

1 行有1 个正整数n

Output:

计算出最短加法链长度l(n)和相应的最短加法链

Sample Input:

23

Sample Output:

6
1 2 3 5 10 20 23

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1311

Tags

Submitted 11

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet