Как написать алгоритм, который выводит в консоль треугольник паскаля, не используя при этом массивы?
p.s.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
и т.д.
p.p.s мне никаких идей не приходит :(
Как написать алгоритм, который выводит в консоль треугольник паскаля, не используя при этом массивы?
p.s.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
и т.д.
p.p.s мне никаких идей не приходит :(
Давайте немного проанализируем.
Если верить википедии (или школьному маткружку), элементы треугольника паскаля обозначаются 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
Каждое значение ячейки вычисляется следующим образом
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();
}
}
}
А в чем проблема просто написать метод, который высчитывает (С из n по k) и прогнать по нужным значениям? Как раз никакого массива использоваться и не будет.
20!
не влезет в long, придётся использовать BigInteger. Во-вторых, придётся сосчитать заранее и закешировать таблицу факториалов.
n^n
, а значит, требует O(n log n) разрядов. Убедил?
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("");
}
}