Лучший способ сгенерировать треугольник Паскаля (из двух упомянутых способов)

Question

У меня есть задание на программирование на Java.

Я реализовал это, создав функцию nCr (http://en.wikipedia.org/wiki/Combination), а затем с помощью двойного цикла for создавая треугольник, распечатывая его.

Однако, назначение требует создания неравномерного 2d-массива, а затем его заполнения, добавив два числа из предыдущих строк и затем распечатав массив.

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

Какой подход лучше?

Answer 1

Если я понимаю ваш вопрос, вы пытаетесь сравнить два подхода к генерации треугольника Паскаля:

1. Запустив функцию nCr для заполнения каждой ячейки треугольника.
2. Генерируя треугольник за один проход, заполняя каждую ячейку простым сложением.

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

Answer 2

Я думаю, что метод, вызванный назначением, будет лучше.Ваш метод требует нескольких умножений для вычисления каждого из элементов треугольника.Это число будет увеличиваться для каждой строки треугольника, который нужно вычислить.

Однако метод назначения требует отдельного сложения для каждого элемента треугольника.

Answer 3

1. По рекурсии

/*By using recursion*/
class RecursivePascal
{
    public static void main(String args[])
    {   int n=100;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                //System.out.print(i+","+j+" ");
                System.out.print(pascal(i,j)+" ");
            }
            System.out.println();
        }
    }
    static int pascal(int i,int j)
    {
        if(j==0)
        return 1;
        else if(j==i)
        return 1;
        else
        {
            return pascal(i-1,j-1)+pascal(i-1,j);
        }   
    }
}

2. По простой логике

/*By using logic*/
class p
{
    public static void main(String args[])
    {
        int one[]={1};
        int n=13;
        System.out.println("1");
        for(int j=0;j<n;j++)
        {
            int two[]=new int[one.length+1];
            int twoCounter=0;
                for(int i=0;i<one.length;i++)
                {
                    if(i==0 )
                    {
                        two[twoCounter++]=one[i];
                        System.out.print(one[i]+" ");
                        }
                    if(i!=0)
                    {   
                        two[twoCounter++]=one[i]+one[i-1];
                        System.out.print( (one[i]+one[i-1]) +" ");
                    }
                    if(i==one.length-1 )
                    {           
                        two[twoCounter++]=one[i];
                        System.out.print(one[i]+" ");
                        }
                }
        System.out.println();
        one=two;
        }
    }
}