Interviewstreet 题目一枚

今天在interview Street上面看到一个题目。有了灵感，特记录下来。

 

题目是这样的：

 

Connect the country (20 Points)

We have a country containing N cities. Each day we choose 2 cities such that there is no road between them and build a road between them. We choose each pair of nonadjacent cities with equal probability. Let X be the number of days before we obtain a connected country. What is the expected value of X? Output the integer part of answer.

Input format:
First line of input as an integer N. N <= 30

Output format:
Print an integer being the result of the test.

Sample Testcases:

Input #00:
3

Output #00:
2 

Input #01:
4

Output #01:
3

In the first example, first two roads are sufficient for connecting the cities so the answer would be 2.

In the second example if the first three roads of the country are edges of a triangle, then we need a fourth road to make the country connected, otherwise the country would be connected with first three roads. The probability of the former situation is 4/20 (number of triple of roads that make a triangle divided by number of ways we can choose 3 different roads), and the probability of former situation is 16/20. So the result would be 4/20*4 + 16/20*3 = 3.2 and since you have to print only the integer part as output, print 3

 

翻译一下，就是：

相连的国家：有个国家有n个城市，有一群小鼹鼠，每天可以在两个城市之间挖沟，每天只挖一条沟，它们看不见，就知道从这个城市挖到那个城市。问：需要挖几天，才可以把这个国家所有的城市挖联通？

内涵：n个点中，每天随机选两个点，画两个点之间的连线，x天后，这所有的点联通了？

 

例子：3个点，a, b,c 第一天，a,b连接，第二天，b,c或者ac连接，这三个点就联通了。

             或者，          第一天 ，ac连接，第二天，ab,或者bc连接，这三个点也就联通了。

             或者，           第三天，bc连接，第二天，ab,或者ac连接， 这三个点也就联通了。

  所以E（x)= (1/3)*2+(1/3)*2+(1/3)*2=6/3=2,期望是2天。

 

再比如4个点，

    有几种形态，一种是一个三角形，外加一个点，然后这个点，任意连到三角形一个顶点，必然就成了一个连通图。第二种，就是3条直线连接 4个点。

 

 

 

 

 

但是这种形态是不允许的，

 

已经4个点联通了，再多一条线，完全多余没必要。

 

所以最后是E(x)=(4/20)*4+(16/20)*3=3.2,所以傻乎乎的小鼹鼠，需要3.2天才能把这个国家挖联通。

 

再复杂一些的：6个点，10条线，但是这个图还未联通。

 

开始，我想了好多方法什么，组合，递归，发现都他妈的，不好使啊。最后，百无聊赖，灵感一来，这个问题解决了。

我们用矩阵的方式来重新表示图的联通。

 

那这个图就表示

 

 

再比如下图：

 

这个表格表示的是

 

可以看到，第一个是非连通图，第二个是连通图。

 

有什么规律可言，那就是对号在x,y方向上的投影，只有有一个方向上是满的，即这个图是联通的。

那么我们就需要遍历出，在有最后一行或者最后一列未填满的时候，所有可能的对号组合，是回溯吗？

我基本是真么考虑的，这就是这题的思路。有时间编程实现一下吧！ :-)