ошибка сегментации (сбрасывается ядро) в программе c для комбинированной функции

Question

#include <stdio.h>
#include <stdlib.h>

int factorial(int i) {
    if(i == 1) {
        return 1;
    }
    else {
        return i*factorial(i - 1);
    }
}

int combination(int l, int m) {
    return factorial(l)/(factorial(l-m)*factorial(m));
}

int main() {
    int n,r;
    printf("Input taken in form of nCr\n");
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Enter r: ");
    scanf("%d", &r);
    int y = combination(n, r);
    printf("Result: %d", y);

    return 0;
}

Попытка сделать простой код для вычисления функции комбинации в математике. Он работал для небольших значений и в основном работает до n = 12, и дает неправильные значения от n = 13 и далее. Также для n = 15 и r = 2 он возвращает результат -4. И это дает ошибку

ошибка сегментации (ядро сброшено)

для n = 40 и r = 20. Я хотел бы знать, как решить эту проблему и почему именно это и происходит.

Answer 1

значение 13! 6227020800, который слишком велик, чтобы поместиться в 32-битное целое число. Попытка вычислить этот факториал или больше приводит к переполнению 32-битного int. Целочисленное переполнение со знаком вызывает неопределенное поведение .

В некоторых случаях это неопределенное поведение проявляется как вывод неправильного значения, в то время как в других оно проявляется как cra sh. В случаях, когда происходит сбой функции factorial, наиболее вероятно, что ей передается значение меньше 1, что означает, что рекурсивные вызовы будут пытаться до go вплоть до INT_MIN, но заполняют стек до того, как это может произойти.

Даже изменения на long long недостаточно, чтобы это исправить, поскольку промежуточные результаты будут переполнены. Так как же это исправить? Если вы вычисляете эти значения вручную, вы не умножите все числа вместе, а разделите два огромных числа. Вы выписали бы факторы и отменили бы термины сверху и снизу уравнения. Например, предположим, что вы хотите вычислить ₁₂ C ₇ . Вы бы написали это так:

12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
------------------------------------------------
( 5 * 4 * 3 * 2 * 1 ) * (7 * 6 * 5 * 4 * 3 * 2 * 1)

Тогда отмените 7! сверху и снизу:

12 * 11 * 10 * 9 * 8 
---------------------
 5 * 4 * 3 * 2       

Затем отмените другие термины:

12 * 11 * 10 * 9 * 8     12 * 11 * 2 * 9 * 8    12 * 11 * 2 * 9 
---------------------  = -------------------- = --------------- =  4 * 11 * 2 * 9
 5 * 4 * 3 * 2              4 * 3 * 2                 3

Затем умножьте то, что осталось:

4 * 11 * 2 * 9 = 792

Теперь сделайте это в коде. :) Обязательно измените все типы данных на long long, в результате ₄₀ C ₂₀ все еще немного больше, чем 32-битный int может держать. Этот тип гарантированно должен быть не менее 64 бит.

Answer 2

Это проблема переполнения. Ваш результат выше максимального значения int.

13! = 6227020800

Который больше INT_MAX (2147483647). Если вы хотите обрабатывать большие числа, вы должны либо использовать другие типы переменных (например, unsigned long long), либо обработать переполнение в вашей функции, чтобы избежать сбоев памяти.

Вот топи c, которая может быть интересно проверить переполнение в c здесь .

Также при n = 15 и r = 2 возвращается результат -4

Переполнение переменной может привести к переполнению циклов и . Вот почему вы получаете отрицательные значения. Я не уверен, но я думаю, что это связано. Если кто-то может это подтвердить, было бы здорово.

Answer 3

Я предполагаю, что есть 2 взаимодействующих эффекта:

1. Ваше переполнение целых чисел, то есть значение factorial(i) станет отрицательным для достаточно большого i, ведущего к
2. Ваш рекурсия (при наличии factorial самого вызова) занимает все пространство стека.

Попробуйте изменить условие в factorial с if(i == 1):

int factorial(int i) {
   if(1 == i) {
      return 1;
   } else if(1 > i) {
      return -1;
   }

   return i * factorial(i - 1);

}

Это должно иметь вы избавляетесь от SEGFAULT.

Для целочисленного переполнения единственным возможным решением будет не полагаться на C integer arithmethi c, а использовать некоторую библиотеку bignum (или написать код самостоятельно) .

Некоторое объяснение того, что, вероятно, происходит:

Как указывало @WhozCraig, целые числа могут сохранять диапазон чисел только до INT_MAX. Однако factorial(i) просто взрывается даже для относительно небольших чисел. C однако не фиксирует это исключение, и ваши целые числа будут молча переполняться до отрицательных чисел. Это означает, что в какой-то момент вы начинаете вводить factorial с отрицательными числами.

Однако для каждого вызова функции некоторые данные должны быть помещены в стек (обычно это адрес возврата и локальные переменные, возможно, включая функцию аргументы). Эта память будет освобождена только после возврата функции. Это означает, что если вы позвоните по номеру factorial(40), если все работает целочисленно, вы будете в 40 раз превышать объем памяти на 1 звонок на factorial.

, поскольку ваш factorial не обрабатывает отрицательные числа правильно, он будет вызывать себя бесконечно, время от времени переполняться, пока условие i == 1 в какой-то момент не будет случайно выполнено. Якобы в большинстве случаев этого не происходит до того, как ваш стек исчерпан.

Answer 4

Когда я запускаю вашу программу в отладчике с n = 40 и r = 20 в 32-разрядном двоичном файле, скомпилированном с Microsoft Visual Studio, я не получаю ошибку сегментации, но я получаю ошибку деления на ноль в следующая строка:

return factorial(l)/(factorial(l-m)*factorial(m));

factorial(l-m) и factorial(m) оба оценивают как factorial(20), что составляет 2,192,834,560.

Предполагая, что sizeof(int) == 4 (32-разрядный), это число не может быть представлено знаком int. Поэтому переполнение int, которое, согласно официальному стандарту C, вызывает неопределенное поведение .

Однако, даже если поведение не определено, я могу разумно предположить, что происходит следующее:

Из-за переполнения число 2,192,834,560 станет -2,102,132,736. Это связано с тем, что второе число соответствует первому числу в двоичном представлении двоичного дополнения .

Поскольку это число умножается на себя в вашем коде (при условии n = 40 и r = 20), тогда результат умножения будет 4,418,962,039,762,845,696. Это число, конечно, не вписывается в int со знаком, так что переполнение происходит снова.

Шестнадцатеричное представление этого числа 0x3D534E9000000000.

, так как это большое число не подходит в 32-разрядное целое число все лишние биты удаляются, что эквивалентно обработке результата по модулю UINT_MAX + 1 (4,294,967,296). Результат этой операции по модулю 0.

Следовательно, выражение

factorial(l-m)*factorial(m)

оценивается как 0.

Это означает что строка

return factorial(l)/(factorial(l-m)*factorial(m));

приведет к исключению деления на ноль.

Одним из способов решения проблемы обработки больших чисел является использование чисел с плавающей запятой вместо целые числа. Они могут обрабатывать очень большие числа без переполнения, но вы можете потерять точность. Если вы используете double вместо float, вы не так легко потеряете точность, и, даже если вы это сделаете, потеря точности будет меньше.