java - TopCoder SRM 645 - 一个测试用例中的错误

Question

我正在尝试解决 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);
    }

}

Answer 1

问题是由我在结果 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 }