原文:

找到一棵有给定值的树，打印树的边。如果树不存在，则打印“-1”。

给定三个整数 n，d 和 h。

n -> number of vertices. [1, n]
d -> diameter of the tree (largest 
   distance between two vertices).
h -> height of the tree (longest distance
   between vertex 1 and another vertex)

示例:

input : n = 5, d = 3, h = 2 
output : 1 2
         2 3
         1 4
         1 5
explanation :  

we can see that the height of the tree is 2 (1 -> 
2 --> 5) and diameter is 3 ( 3 -> 2 -> 1 -> 5).
so our conditions are satisfied.
input :  n = 8, d = 4, h = 2
output : 1 2
         2 3
         1 4
         4 5
         1 6
         1 7
         1 8
explanation :
  1. 注意当 d = 1，我们不能构造一棵树(如果树有 2 个以上的顶点)。同样，当 d > 2h* 时，我们不能建造一棵树。
  2. 我们知道，高度是从顶点 1 到另一个顶点的最长路径。所以从顶点 1 开始，通过添加边到 h 来构建路径。现在，如果 d > h ，我们应该添加另一条路径来满足从顶点 1 开始的直径，长度为d–h。
  3. 我们的高度和直径条件得到了满足。但是仍然会留下一些顶点。在端点以外的任何顶点添加剩余顶点。这一步不会改变我们的直径和高度。选择顶点 1 以添加剩余的顶点(您可以选择任何一个)。
  4. 但是当 d == h 时，选择顶点 2 来添加剩余的顶点。

c 

// c   program to construct tree for given count
// width and height.
#include 
using namespace std;
// function to construct the tree
void constructtree(int n, int d, int h)
{
    if (d == 1) {
        // special case when d == 2, only one edge
        if (n == 2 && h == 1) {
            cout << "1 2" << endl;
            return;
        }
        cout << "-1" << endl; // tree is not possible
        return;
    }
    if (d > 2 * h) {
        cout << "-1" << endl;
        return;
    }
    // satisfy the height condition by add
    // edges up to h
    for (int i = 1; i <= h; i  )    
        cout << i << " " << i   1 << endl;
    if (d > h) {
        // add d - h edges from 1 to
        // satisfy diameter condition
        cout << "1"
            << " " << h   2 << endl;
        for (int i = h   2; i <= d; i  ) {
            cout << i << " " << i   1 << endl;
        }
    }
    // remaining edges at vertex 1 or 2(d == h)
    for (int i = d   1; i < n; i  )
    {
        int k = 1;
        if (d == h)
            k = 2;
        cout << k << " " << i   1 << endl;
    }
}
// driver code
int main()
{
    int n = 5, d = 3, h = 2;
    constructtree(n, d, h);
    return 0;
}

java 语言(一种计算机语言，尤用于创建网站)

// java program to construct tree for given count
// width and height.
class gfg {
// function to construct the tree
static void constructtree(int n, int d, int h)
{
    if (d == 1) {
        // special case when d == 2, only one edge
        if (n == 2 && h == 1) {
            system.out.println("1 2");
            return;
        }
        system.out.println("-1"); // tree is not possible
        return;
    }
    if (d > 2 * h) {
        system.out.println("-1");
        return;
    }
    // satisfy the height condition by add
    // edges up to h
    for (int i = 1; i <= h; i  )    
        system.out.println(i   " "   (i   1));
    if (d > h) {
        // add d - h edges from 1 to
        // satisfy diameter condition
        system.out.println("1"   " "   (h   2));
        for (int i = h   2; i <= d; i  ) {
            system.out.println(i   " "   (i   1));
        }
    }
    // remaining edges at vertex 1 or 2(d == h)
    for (int i = d   1; i < n; i  )
    {
        int k = 1;
        if (d == h)
            k = 2;
        system.out.println(k   " "   (i   1));
    }
}
// driver code
public static void main(string[] args)
{
    int n = 5, d = 3, h = 2;
    constructtree(n, d, h);
}
}

python 3

# python3 code to construct tree for given count
# width and height.
# function to construct the tree
def constructtree(n, d, h):
    if d == 1:
        # special case when d == 2, only one edge
        if n == 2 and h == 1:
            print("1 2")
            return 0
        print("-1")    # tree is not possible
        return 0
    if d > 2 * h:
        print("-1")
        return 0
    # satisfy the height condition by add
    # edges up to h
    for i in range(1, h 1):
        print(i," " , i   1)
    if d > h:
        # add d - h edges from 1 to
        # satisfy diameter condition
        print(1,"  ", h   2)
        for i in range(h 2, d 1):
            print(i, " " , i   1)
    # remaining edges at vertex 1 or 2(d == h)
    for i in range(d 1, n):
        k = 1
        if d == h:
            k = 2
        print(k ," " , i   1)
# driver code
n = 5
d = 3
h = 2
constructtree(n, d, h)
# this code is contributed by "sharad_bhardwaj".

c

// c# program to construct tree for 
// given count width and height.
using system;
class gfg
{
    // function to construct the tree
    static void constructtree(int n, int d, int h)
    {
        if (d == 1)
        {
            // special case when d == 2,
            // only one edge
            if (n == 2 && h == 1)
            {
                console.writeline("1 2");
                return;
            }
            // tree is not possible
            console.writeline("-1");
            return;
        }
        if (d > 2 * h)
        {
            console.writeline("-1");
            return;
        }
        // satisfy the height condition
        // by add edges up to h
        for (int i = 1; i <= h; i  )
            console.writeline(i   " "   (i   1));
        if (d > h)
        {
            // add d - h edges from 1 to
            // satisfy diameter condition
            console.writeline("1"   " "   (h   2));
            for (int i = h   2; i <= d; i  )
            {
                console.writeline(i   " "   (i   1));
            }
        }
        // remaining edges at vertex 1 or 2(d == h)
        for (int i = d   1; i < n; i  )
        {
            int k = 1;
            if (d == h)
                k = 2;
            console.writeline(k   " "   (i   1));
        }
    }
    // driver code
    public static void main(string[] args)
    {
        int n = 5, d = 3, h = 2;
        constructtree(n, d, h);
    }
}
// this code is contributed by 29ajaykumar

java 描述语言

输出:

1 2
2 3
1 4
1 5

麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处

本文链接：http://www.moonapi.com/news/38664.html