3

Как написать алгоритм, который выводит в консоль треугольник паскаля, не используя при этом массивы?

p.s. 
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
и т.д.

p.p.s мне никаких идей не приходит :(
1
  • 3
    Если сделайте еще и подсветку четных чисел в этом треугольнике увидите треугольник Серпинского внутри.
    – igumnov
    10 янв 2013 в 12:38

4 ответа 4

17

Давайте немного проанализируем.

Если верить википедии (или школьному маткружку), элементы треугольника паскаля обозначаются C(n, k) и называются биномиальными коэффициентами. Они вычисляются по формуле

C(n, k) = n! / (k! (n-k)!)

Но считать факториалы на каждом шаге не очень эффективно, поэтому давайте найдём рекуррентные соотношения.

1.

C(n, 0) = n! / (0! n!) = 1.

2.

C(n, k) / C(n, k-1) = (n! / (k! (n-k)!)) * (n! / ((k-1)! (n-k+1)!) =
                    = ((k-1)! (n-k+1)!) / (k! (n-k)!) =
                    = ((k-1)! / k!) * ((n-k+1)! / (n-k)!) =
                    = (1/k) * (n-k+1) =
                    = (n-k+1)/k.

Отлично, у нас есть всё, что нужно.

Код:

import static java.lang.System.out;
//...
for (int n = 0; ?; n++)
{
    int Cnk = 1; // согласно (1)
    out.print(Cnk);
    for (int k = 1; k <= n; k++)
    {
        Cnk *= (n - k + 1); // согласно (2)
        Cnk /= k;           // тут обязано делиться нацело
        out.print(" "); out.print(Cnk);
    }
    out.println();
}

Проверка: http://ideone.com/BTObLZ

4
  • @VladD, а что означает for (int n = 0; ?; n++) ?
    – ReinRaus
    10 янв 2013 в 16:44
  • @ReinRaus: ну, туда надо что-нибудь вписать, но у меня не хватило фантазии :-) например, n < N.
    – VladD
    10 янв 2013 в 17:04
  • 2
    @VladD, ну вот, а я минут пять убил гугля что значит вопрос в цикле :)
    – ReinRaus
    10 янв 2013 в 17:06
  • @ReinRaus: сорри :)
    – VladD
    10 янв 2013 в 17:13
6

Каждое значение ячейки вычисляется следующим образом

X(i, j) = X(i - 1, j) + X(i - 1, j - 1)

где i - строка, j - колонка. Причем если j = 0 или i = j, то значение равно 1.

Получаем рекуррентное отношение и решаемую рекурсивно задачу без использования массивов.

public class Pascal {

public static int pascal(int i, int j) {
    return (j == 0 || j == i) ? 1 : pascal(i - 1, j - 1) + pascal(i - 1, j);
}

public static void main(String[] args) {
    for (int i = 0; i <= 10; i++) {
        for (int j = 0; j <= i; j++) {
            System.out.print(pascal(i, j) + " ");
        }
        System.out.println();
    }
}
}
7
  • Вам придётся запоминать предыдущую строку, так что без массивов не обойтись.
    – VladD
    10 янв 2013 в 14:33
  • 1
    Вернее если j==0 или i==j
    – KaZaца
    10 янв 2013 в 14:36
  • 1
    @VladD дополнил ответ примером кода. Никаких массивов.
    – a_gura
    10 янв 2013 в 19:00
  • @a_gura: а, понял, рекурсия. Согласен, не сообразил сразу. ЗЫ: но ваше решение всё же О(2^n).
    – VladD
    10 янв 2013 в 19:16
  • @VladD Вычислительная сложность вашего решения без сомнения меньше.
    – a_gura
    10 янв 2013 в 19:18
5

А в чем проблема просто написать метод, который высчитывает (С из n по k) и прогнать по нужным значениям? Как раз никакого массива использоваться и не будет.

11
  • кароче, проблема сводится лишь к реализации факториала..) Думаю, это не самая большая проблема
    – Stas0n
    10 янв 2013 в 12:42
  • @Stas0n: быстрая реализация факториала не так уж проста. Во-первых, 20! не влезет в long, придётся использовать BigInteger. Во-вторых, придётся сосчитать заранее и закешировать таблицу факториалов.
    – VladD
    10 янв 2013 в 15:30
  • 1
    @VladD Закешировать и "без массивов" -- противоречие.
    – alexlz
    10 янв 2013 в 15:43
  • 1
    @VladD " а BigInteger наверняка внутри тоже массивы использует...". Так ведь и integer внутри -- тоже массив бит. Это уже буквоедство. А вот самопальный кэш или ещё какое динамическое программирование -- уже прямое нарушение правил задачи.
    – alexlz
    10 янв 2013 в 17:25
  • 1
    @alexlz: не совсем буквоедство. Под требованием "не использовать массивы" я понимаю "О(1) по расходу памяти" (иначе массив можно рассовать по переменным). Integer удовлетворяет этому условию, BigInteger -- нет, так как факториал по размеру где-то n^n, а значит, требует O(n log n) разрядов. Убедил?
    – VladD
    10 янв 2013 в 17:38
0
public static void tr(int n){

        for (int i = 0; i < n; i++) {
            int number  = 1;
            System.out.format("%"+(n - i)*2+"s","");
            for (int j = 0; j <= i; j++) {
                System.out.printf("%4d", number);
                number=number * (i - j) / (j + 1); 
            }
            System.out.println("");
        }

    }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.