Почему алгоритм дает разные ответы для C и Python?

#python #c #algorithm

#python #c #алгоритм

Вопрос:

Сегодня я выполняю упражнение по алгоритму. В руководстве по этому вопросу приведен пример ответа, написанного на C :

 int dp[21][200];
int i, j, k;
 
void main()
{
    int bucketN, fishN;
    scanf("%d %d", amp;bucketN, amp;fishN);
 
    dp[0][0] = 1;  
 
    for(int i = 1; i <= bucketN;   i) 
    {
        for(int j = 0; j <= fishN;   j)
        {
            for(int k = 0; k <= 10 amp;amp; j-k >= 0;   k)
            {
                dp[i][j]  = dp[i-1][j-k];
            }
        }
    }
    printf("%dn",dp[bucketN][fishN]);
}

Если bucketN и fishN оба равны 20, результат будет 65649764 .

Я перевел реализацию C на Python, и мой код показан следующим образом.

 import numpy as np
arr = np.zeros((21, 200))

def main(bucket, fish):

    b, f = bucket, fish
    arr[0, 0] = 1

    for i in range(1, b 1):
        for j in range(f 1):
            for k in range(11):
                if j-k < 0:
                    break
                else:
                    arr[i, j]  = arr[i-1, j-k]
    
    print(arr[b, f])
    return arr[b, f]

if __name__ == '__main__':
    main(20, 20)

Оба bucket и fish по-прежнему равны 20, но результат 68785126410.0 .

Я чувствую себя очень смущенным, и я думаю, что мой код такой же, как и исходный C . Надеюсь, что кто-нибудь из экспертов по C или Python сможет это объяснить.

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

2. Код Python дает точный ответ, но код C переполняет тип данных.

3. Измените объявление массива в коде C на long long вместо int , затем %lld вместо %d , чтобы вывести правильное значение. Кроме того, не уверен, почему вы думаете, что это C .

4. @ggorlen » Код Python дает точный ответ » — Он дает ответ. «точный» не играет роли.

5. @TedLyngmo Что вы имеете в виду?

Ответ №1:

В коде C типом данных для dp массива является int, который может содержать до числа 2147483647. Истинный ответ без переполнения, который вы ищете, возвращается вашим кодом python 68785126410. Измените первую строку в вашем коде C с: int dp[21][200]; на long long int dp[21][200]; и спецификатор формата printf с "%d на %lld , чтобы увидеть совпадающие (и правильные) ответы в C и Python

1. Интересный забавный факт: на самом деле это хуже и страннее, чем вы описываете. int может содержать максимум 32767. И может ли он содержать миллиарды. Указан только минимальный размер int , и это 16 бит. Разработчики могут сделать его чем угодно большим, если он не больше, чем long . Он может быть даже того же размера, что и long . Я видел системы, в которых все целочисленные типы имели одинаковый размер.

2. Не забывайте int main , return 0; и #include <cstdio> ! Мы говорим о C . (Хотя я не уверен, почему cstdio был выбран iostream .)

3. int64_t в целом это лучший выбор, чем long long потому что это известный размер, и поэтому вам легче определить, достаточно ли он велик для ваших вычислений. Хотя на практике long long составляет 64 бита во всех современных компиляторах. Если вам не нужны отрицательные числа (что, похоже, относится к вашей проблеме), uint64_t дает вам дополнительный бит.

4. Запуск вашего кода C / C с помощью ubsan также может значительно помочь в поиске проблем, включая переполнение целых чисел со знаком.