编程介的小学生 2019-01-31 15:14 采纳率: 20.5%
浏览 191

质数分解二叉树的一个问题,数据结构问题怎么采用C语言的实现

Problem Description
Given an integer n, it generates a tree by the following operation.

Initially, there is a node weights n.

If n is not a prime number, the nodes gets a left son and a right son, the left son weights x, where x is a factor of n and x is larger than 1 and smaller than n chosen randomly, and the right son weights n/x. We call this step split.

For each leaf of tree, we do the split operation, until all of the leaves weight a prime number.

For example, suppose n to be 12, and the picture below shows a tree generated.

Now we want to know the expectated height of the tree.

Input
There are multiply test cases.

The first line contains an integer T(T<=50000), which denotes the number of test cases.

For each test case, there is an integer n(2<=n<=10^11), denotes the weight of the root.

The test cases are generated almost randomly.

Output
For each test case, output “Case #k: ”first, k is the case number, from 1 to T , and then output the expectated height. The answer should be rounded after the sixth decimal place.

Sample Input
3
2
4
36

Sample Output
Case #1: 1.000000
Case #2: 2.000000
Case #3: 3.571429

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥50 树莓派安卓APK系统签名
    • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿
    • ¥100 关于使用MATLAB中copularnd函数的问题
    • ¥20 在虚拟机的pycharm上
    • ¥15 jupyterthemes 设置完毕后没有效果
    • ¥15 matlab图像高斯低通滤波
    • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗