Рекурсия запоминание таблицы


Следующий код для этой проблемы.

Вход

Входные данные состоят из одной строки, содержащей три целых числа Н , с и к (1 ≤ н ≤ 10,000, 1≤ КС ≤ 500 ). Н это количество бросков, к количество различных чисел, которые нужны для победы и с число сторон кости.

Выход

В одной строке вывести вероятность того, что игрок кидает, по крайней мере, к разные номера в Н кидает с з -гранник. Ваш ответ должен быть в абсолютной или относительной погрешностью не более 10-7 .

Пример Ввод 1

3 3 2

Пример Выходных Данных 1

0.888888889

Пример Ввод 2

3 3 3

Пример Выходных Данных 2

0.222222222

Эта программа используется 0.89 s, чтобы пройти все тесты. Но я нахожу другие люди используют Java может достигнуть ~0.20 С. Как я могу улучшить мой код?

Идея заключается в создании таблицы для рекурсивного вызова, чтобы посмотреть ранее вычисленное значение.

import java.util.*;

public class Dice
{
  static double table[][];

  public static double game(int s, int r, int d)
  {
    if(table[r][d] != -1) return table[r][d];
    double a = (1 - (double)d/(double)s) * game(s, r - 1, d + 1);
    double b = ((double)d/(double)s) * game(s, r - 1, d);
    double sum = a + b;
    table[r][d] = sum;
    return sum;
  }

  public static void main(String[] args)
  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int s = in.nextInt();
    int k = in.nextInt();
    table = new double[n+1][n+1];

    for(int i = 0; i < n+1; i++)
     for(int j = 0; j < n+1; j++)
       table[i][j] = (double)-1;

    for(int i = 0; i < n+1; i++)
     for(int j = 0; j < n+1; j++)
      if(i + j < k)
        table[i][j] = (double)0;

    for(int j = 0; j < n+1; j++)
     for(int i = k; i < n+1; i++)
       table[j][i] = (double)1;

    System.out.println(game(s, n, 0));
   }
 }


129
3
задан 9 февраля 2018 в 02:02 Источник Поделиться
Комментарии
1 ответ

Не повторяйся

Ваш main() функция начинается с 3 петель для инициализации table массив. Здесь несколько проблем. Во-первых, он пишет мимо конца массива. Если Ваш массив имеет n + 1 элементы, то вы можете только написать от 0 до n. Элемент n + 1 это вне границ. Так что каждый из ваших циклов записи на один элемент следующей строки, а затем одну дополнительную строку в конце, и один элемент прошлом, что слишком. Петли должны идти только от 0 до n. Это происходит, потому что позже вы читать мимо конца массива, тоже. Если вы собираетесь сделать это, нужно выделить n + 2 строки и столбцы.

Далее, вы пишете несколько элементов в 3 раза. Вы можете комбинировать эти 3 петли в 1 и сделать меньше инициализации. Кроме того, вы должны использовать скобки вокруг всех петель и условные органы, потому что есть потенциал для создания ошибок в будущем, если вы не.

Также, вы перешли i и j на последнем круге, который является весьма запутанным и могут легко быть пропущены читателем.

Вот как я хотел бы написать код инициализации:

table = new double [ n + 2 ][ n + 2 ]
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < k; j++)
{
if (i + j < k)
{
table [ i ][ j ] = 0.0;
}
else
{
table [ i ][ j ] = -1.0;
}
}

for (int j = k; j < n + 1; j++)
{
table [ i ][ j ] = 1.0;
}
}

Теперь ни один элемент не должны быть затронуты более чем один раз, никакие элементы в конец массива должно быть написано, а не индексы массивов переворачиваются.

Вы также расчета (double)d / (double)s дважды. Вы должны вычислить его один раз и повторно использовать это значение.

Именования

Вы должны выбрать имена для ваших переменных. i и j штраф за цикл индексы, так как они обычно используются, таким образом, и никто не будет путать их. Однако, я бы переименовать n, sи k. Я бы назвал n что-то описательное, как numThrows; k должно быть что-то вроде numNeededи s должно быть numSides.

Кроме того, s, rи d не очень удобные имена для аргументов game().

Скорость

Я не профилировали ваш код, который является реальным способом чтобы выяснить, какие части медленно. Я видел много случаев, когда кастинг переменных из одного типа в другой вызывает значительное торможение. Поскольку основная часть вашего game() функция либо, именующая себя или отливки значения, я рекомендую просто аргументов в функцию double начнем с того. Конечно, вы не можете использовать двойника в качестве индекса в массиве. Так что вы можете либо пройти r и d значения как doubleS и intС.

1
ответ дан 9 февраля 2018 в 03:02 Источник Поделиться