Треугольник Паскаля в C с комбинациями - PullRequest
Новая
       46

Треугольник Паскаля в C с комбинациями

2 голосов
/ 02 марта 2011 
#include <stdio.h>
long factorial(int num)
{
    int counter;
    int fact = 1;
    for (counter = num; counter > 0; counter--) fact *= counter;
    return fact;
}

float combinations(int n, int k)
{
    int numerator = factorial(n);
    int denominator = factorial(k) * factorial(n-k);
    float fraction = numerator/denominator;
    return fraction;
}
int main()
{
    printf("How many rows of Pascal\'s triangle should I print?\t");
    int rows = GetInteger();
    int counter;
    int counter2;
    for (counter = 1; counter <= rows; counter++)
    {
        int y = rows-counter;
        for (; y > 0; y--) printf("   ");
        for (counter2 = 0; counter2 <= counter; counter2++)
                printf("%6.0lu", (long) combinations(counter, counter2));
        printf("\n");
    }
}

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

И, GetInteger() - это просто scanf() с несколькими подправками.Я на 100% уверен, что все работает отлично.

Ответы [ 3 ]

4 голосов
/ 02 марта 2011

После того, как факторные элементы в 12-й строке и т. Д. Элементы треугольника Паскаля становятся слишком большими, поэтому тип int не может их удерживать - поэтому вы получаете переполнение (наиболее вероятные значения, которые вы получаете, оборачиваются вокруг максимального значения int).

P.S. почему вы используете 3 разных типа в вашем коде (long, int, float)? Как к! * (Н-к)! всегда делит! вам не нужно значение с плавающей запятой (вы все равно используете целочисленное деление и приводите результат к long). Просто используйте самый большой целочисленный тип или какой-либо другой тип BigInt, который может содержать целые числа произвольной длины, чтобы вы могли отображать правильные значения для больших чисел в строке.

3 голосов
/ 02 марта 2011

Не начинайте с факториалов.Начните со следующих фактов о треугольнике Паскаля:

  1. в n-й строке треугольника есть n элементов (если мы начинаем считать с 1)
  2. первый и последний элементы каждой строки1
  3. каждый элемент, кроме первого и последнего, является суммой двух элементов по диагонали над ним (если треугольник написан симметрично)

Вы, конечно,ограничиваться размером типа данных, к которому вы относитесь, но не раньше, чем необходимо (промежуточными результатами, такими как факториалы).

2 голосов
/ 02 марта 2011

INT_MAX обычно составляет 2 147 483 647
12! 479 001 600
13! 6,227,020,800, но ваша функция factorial(13) возвращает 1,932,053,504 (= 6,227,020,800 - 4,294,967,296)

...