Разница в результатах при реализации алгоритма динамического планирования c C ++ и Python? - PullRequest
Новая
       5

Разница в результатах при реализации алгоритма динамического планирования c C ++ и Python?

0 голосов
/ 27 апреля 2020

В игре «Выживший джедай» есть три уровня брони и бронежилета, каждый из которых обозначен как 1,2,3. Каждый раз, когда вы можете подобрать только то, чего у вас нет, или модернизировать оборудование низкого уровня до высокого уровня, спросите, сколько существует маршрутов улучшения от ничего до «Броня Броня 3 уровня Броня 3 уровня Броня»? Текущее состояние представлено упорядоченным количеством пар (бронежилет, броня), обе из которых имеют значения 0-3, например (0,0) -> (0,1) -> (0,3) -> ( 3,3) в качестве стратегии обновления.

Теория состоит в том, что это массив 4 * 4, мне интересно, почему массив python 4 * 4 может быть реализован, но c ++ должен быть записан как int [4] [4] то есть 5 * 5 массив результата, чтобы быть правильным, int [3] [3] вычислено неправильно? (Результатом является последний элемент, который равен 106)

python: 

dp = [[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]
for i in range(4):
    for j in range(4):
        for m in range(j):
            dp[i][j] += dp[i][m]
        for m in range(i):
            dp[i][j] += dp[m][j]
dp

вывод: 106 (правильный ответ) c ++: 

#include<iostream>
int dp[3][3];
int main (){
    dp[0][0] = 1;
    for (int i = 0; i <= 3; i++){
        for (int j = 0; j <= 3; j++){
            for (int m = 0; m < i; m++)
                dp[i][j] += dp[m][j];
            for (int m = 0; m < j; m++)
                dp[i][j] += dp[i][m];
       }
    }
  std::cout<<dp[3][3]<<std::endl;
}

вывод: 1495 (чёрт! Но я не знаю почему? Почему вывод в с ++ неправильный?)

1 Ответ

0 голосов
/ 27 апреля 2020

Хорошо, нашел это. Ваша проблема в том, что вы используете массив размером 3x3, как если бы он был размером 4x4.
Рабочая версия: 

#include<iostream>

int dp[4][4];
int main ()
{
    dp[0][0] = 1;
    for (int i = 0; i < 4; i++){
        for (int j = 0; j < 4; j++){
            for (int m = 0; m < j; m++)
                dp[i][j] += dp[i][m];
            for (int m = 0; m < i; m++)
                dp[i][j] += dp[m][j];
       }
    }
    std::cout<<dp[3][3]<<std::endl; 
}

Важное изменение: int dp[3][3]; к int dp[4][4];. При этом ваш приведенный выше код работает.
Без этого вы получили доступ к массиву вне границ, что является неопределенным поведением. 1495 был просто результатом того, как компилятор интерпретировал ваш код, но, поскольку это UB, любой результат был бы верным. Это обманчивая вещь UB - он часто выглядит так, как будто он делает что-то разумное, создавая впечатление, что это было ошибкой в ​​вашем алгоритме, а это не так.
Я внес некоторые дополнительные незначительные изменения во время экспериментов. Один из них заключался в переключении двух внутренних петель, но это не является необходимым. Я также изменил <= 3 на < 4, так как это более обычный стиль, но, очевидно, также не требуется.

В будущем ознакомьтесь с использованием отладчика или распечатайте результат между шагами. , Если у вас есть работающий фитон-код, вы можете сделать то же самое там, а затем сравнить поведение обеих программ. Однако обратите внимание, что в вашем случае результат, вероятно, выглядел бы странно - я делал это во время экспериментов, а результат забавный, см. http://www.cpp.sh/8aufco. Переменная i работает с 257, несмотря на то, что l oop ограничивает ее до 3. Я понятия не имею, почему это происходит именно так - просто результат UB.

Возможно, вы захотите изменить необработанный массив на std::vector или std::array, но я оставил это на данный момент.
Ваш основной должен return 0; как хорошая практика, хотя он работает как есть.
Вы не должны использовать глобальные переменные в C ++ как вы делаете с dp. Просто объявите это внутри вашего основного (или там, где вы позже будете его использовать). Глобальные переменные являются легким источником ошибок (обратите внимание, что константы в порядке).

...