该代码的目标:具有N个标记顶点和K个未标记边的简单连接图的数量。
注意:这可能被认为是代码审查问题,但是在反复尝试之后,我认为python和java代码具有相同的功能。我不确定代码是否有问题,或与语言错综复杂有关,还是我在忽略某些内容时出错。
这是针对Google Foobar的挑战。我用上面的方法完成了它。我已经发布了指向所有源代码的链接,这些链接可以测试所有可能的情况。
第一种方法完全有效。唯一的问题-它使O(NK)递归调用和K是平均二次在N. [完整的源]
一个朋友想出了一种算法,该算法可以使用自下而上的方法来完成相同的任务。主要功能:
def answerHelper(n,k):
totalGraphs = 0
for s in range(1,n):
graphs = 0
for t in range(0,k+1):
graphs += answer(s, t) * answer(n - s, k - t)
graphs = choose(n, s)*s*(n - s) * graphs
totalGraphs+= graphs
return totalGraphs/2
F = {}
def answer(n, k):
if (n, k) in F:
return F[n, k]
N = n * (n - 1)/2
if k is n - 1:
return int(n ** (n-2))
if k < n or k > N:
return 0
if k == N:
return 1
result = ((N - k + 1) * answer(n, k - 1) + answerHelper(n, k - 1)) / k
F[n, k] = result
return result
与原始工作的Java代码[diffchecker]相比,python在4种情况下失败。我认为这是由于某种溢出(?)造成的。[完整的python来源]
我正在尝试将此python代码转换为Java。这就是我想出的。
static Map<List<Integer>, String> resultMap = new HashMap<List<Integer>, String>();
public static String answer(int N, int K) {
/* for the case where K > N-1 */
// check if key is present in the map
List<Integer> tuple = Arrays.asList(N, K);
if( resultMap.containsKey(tuple) )
return resultMap.get(tuple);
// maximum number of edges in a simply
// connected undirected unweighted graph
// with n nodes = |N| * |N-1| / 2
int maxEdges = N * (N-1) / 2;
/* for the case where K < N-1 or K > N(N-1)/2 */
if(K < N-1 || K > maxEdges)
return BigInteger.ZERO.toString();
/* for the case where K = N-1 */
// Cayley's formula applies [https://en.wikipedia.org/wiki/Cayley's_formula].
// number of trees on n labeled vertices is n^{n-2}.
if(K == N-1)
return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();
/* for the case where K = N(N-1)/2 */
// if K is the maximum possible
// number of edges for the number of
// nodes, then there is only one way is
// to make a graph (connect each node
// to all other nodes)
if(K == maxEdges)
return BigInteger.ONE.toString();
// number of edges left from maxEdges if I take away K-1 edges
BigInteger numWays = BigInteger.valueOf(maxEdges - K + 1);
// number of graphs possible for each of the numWays edges for a graph that has 1 less edge
BigInteger numGraphsWithOneLessEdge = new BigInteger( answer(N, K-1) );
// number of all possible subgraphs with K-1 edges
BigInteger subGraphs = answerHelper(N, K-1);
// numWays*numGraphsWithOneLessEdge + subGraphs
BigInteger result = subGraphs.add(numWays.multiply(numGraphsWithOneLessEdge));
// this contains repeats for each of the K edges
result = result.divide(BigInteger.valueOf(K));
// add to cache
resultMap.put(Collections.unmodifiableList(Arrays.asList(N, K)), result.toString());
return resultMap.get(tuple);
}
private static BigInteger answerHelper(int N, int K) {
BigInteger totalGraphs = BigInteger.ZERO;
for(int n = 1 ; n < N ; n++) {
BigInteger graphs = BigInteger.ZERO;
for(int k = 0 ; k <= K ; k++) {
// number of graphs with n nodes and k edges
BigInteger num = new BigInteger( answer(n, k) );
// number of graphs with N-n nodes and K-k edges
BigInteger num2 = new BigInteger( answer(N-n, K-k) );
graphs = graphs.add( num.multiply(num2) );
}
// number of ways to choose n nodes from N nodes
BigInteger choose = choose(N, n);
// this is repeated for each of the n chosen nodes
// and the N-n unchosen nodes
choose = choose.multiply(BigInteger.valueOf(n)).multiply(BigInteger.valueOf(N-n));
totalGraphs = totalGraphs.add( choose.multiply(graphs) );
}
// now, consider the case where N = 20
// when n = 2, we compute for N-n = 18
// when n = 18, we do the same thing again
// hence, contents of totalGraphs is 2 times
// of what it should be
return totalGraphs.divide(BigInteger.valueOf(2));
}
此代码(我打算与Python发挥相同的功能)针对有效的Java代码[diffchecker]在多种情况下均未通过
如果能得到一些指导,我将不胜感激。
问题出在Java代码,而不是Python代码(我怀疑是溢出;否则,经过了一些精心的调试,事实证明。这不是最简单的比较20位奇数的数字)。
错误代码:
/* for the case where K = N-1 */
// Cayley's formula applies [https://en.wikipedia.org/wiki/Cayley's_formula].
// number of trees on n labeled vertices is n^{n-2}.
if(K == N-1)
return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();
对于N> = 17,(long)Math.pow(N, N-2)
是不准确的。之所以发生这种情况,是因为使用更大的double值,连续值之间的差距会增加。双精度不能代表其范围内的每个整数值,这就是这里的问题所在。它会将最接近的double值返回到精确结果。此外,对于双精度值,尾数为52位,大约等于小数点的16(?)位。因此,泛滥(不是一个字)。因此,返回的值小于应该的值。不得不用下面的代码块替换它。
if(K == N-1) {
if(N < 2)
return BigInteger.valueOf((long)Math.pow(N, N-2)).toString();
// multiply N to itself N-2 times
BigInteger val = BigInteger.ONE;
int count = 0;
while(count++ != N-2)
val = val.multiply( BigInteger.valueOf( (long)N ) );
return val.toString();
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句