我正在尝试解决 JanuszInTheCasino problem其中一个测试用例 (test_one) 失败。我无法弄清楚问题所在。有什么想法吗?
代码如下:
import java.util.Map;
import static com.google.common.collect.Maps.newHashMap;
/**
* Created by Orestis on 09/07/2015
* topcoder problem statement: http://community.topcoder.com/stat?c=problem_statement&pm=13349
*/
public class JanuszInTheCasino {
private final Map<Long, Double> results = newHashMap();
/**
* @param n number of players
* @param m fields
* @param k rounds
* @return double probabilities
*/
public double findProbability(long n, int m, int k) {
double result;
if (results.containsKey(k + n)) {
return results.get(k + n);
} else {
if (k == 0) {
if (n >= 1) {
result = 1.0;
} else {
result = 0.0;
}
} else {
double p = ((double) n % m) / m;
result = (p * findProbability((n - (n / m + 1)), m, k - 1)) +
((1 - p) * findProbability((n - (n / m)), m, k - 1));
}
}
results.put(k + n, result);
return result;
}
}
和测试:
import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
import static org.testng.Assert.assertTrue;
/**
* Created by Orestis on 09/07/2015
*/
public class JanuszInTheCasinoTest {
private JanuszInTheCasino j;
@BeforeMethod
public void setup() {
j = new JanuszInTheCasino();
}
@Test
public void test_zero() {
double expected = 1.0;
double actual = j.findProbability(1000000000000L, 3, 50);
System.out.println(actual);
assertTrue(Math.abs(actual - expected) <= 0.001);
}
@Test
public void test_one() {
double expected = 0.012293671817445784;
double actual = j.findProbability(432545123543L, 2, 45);
System.out.println(actual);
assertTrue(Math.abs(actual - expected) <= 0.001);
}
@Test
public void test_two() {
double expected = 1.0;
double actual = j.findProbability(4, 3, 2);
System.out.println(actual);
assertTrue(Math.abs(actual - expected) <= 0.001);
}
@Test
public void test_three() {
double expected = 0.75;
double actual = j.findProbability(3, 2, 2);
assertTrue(Math.abs(actual - expected) <= 0.001);
}
@Test
public void test_four() {
double expected = 0.9999999999999996;
double actual = j.findProbability(786342534673L, 7, 48);
assertTrue(Math.abs(actual - expected) <= 0.001);
}
@Test
public void test_five() {
double expected = 0.9999999999999987;
double actual = j.findProbability(1000000000000L, 39, 40);
assertTrue(Math.abs(actual - expected) <= 0.001);
}
}
最佳答案
问题是由我在结果 map 上使用的 key 引起的(有点弱)。所以,而不是 private final Map<Long, Double> results = newHashMap();
我创建了一个 private final Map<Set<Long>, Double> results = newHashMap()
然后在 findProbability
里面我做的方法:
Set<Long> vals = newHashSet(n, (long)k << 1);
if (results.containsKey(vals)) {
return results.get(vals);
} else { // rest of the code }
关于java - TopCoder SRM 645 - 一个测试用例中的错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31442596/