Треугольник паскаля в python без использования каких-либо циклов

Итак, я пытаюсь реализовать треугольник Паскаля, который дает в python следующее:

pascal_triangle(5) prints:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Проблема в том, что я пытаюсь сделать это без использования каких-либо циклов, но не могу понять, как это сделать. Любая помощь будет оценена по достоинству. Чем ты.

Вот что у меня есть на данный момент:

   def factorial(x):
            if x == 0:
                    return 1
            else: 
                    x * factorial(x - 1)

    def pascal_triangle(n):`

ОБНОВЛЕНО:

print_pascal_line(r):
    if r == 0:
        return 1
    else:
        R = print_pascal_line(r-1)
        return 1 +

Возможный дубликат Треугольник Паскаля с рекурсией

Mulan 06.11.2018 16:21
0
1
1 976
6

Ответы 6

Сначала создайте функцию, которая печатает N-ю строку треугольника Паскаля, и я советую вам использовать комбинации вместо ручного вычисления значений в каждой строке с использованием факториалов, это было бы намного эффективнее. Допустим, эта функция называется print_pascal_line и получает целое число - номер строки.

Тогда у вас просто есть:

def pascal_triangle(n):
    aux(0, n)

def aux(current_line, n):
    if current_line < n:
        print_pascal_line(current_line)
        aux(current_line + 1, n)

Или вы можете использовать аргументы по умолчанию, чтобы иметь это только в одной функции:

def pascal_triangle(n, current_line = 0):
    if current_line < n:
        print_pascal_line(current_line)
        pascal_triangle(n, current_line + 1)

Спасибо за ваш ответ. вот мой снимок для print_pascal_line: (и, основываясь на вашем объяснении, я считаю, что он должен печатать только эту N-ю строку, поэтому, например, если n = 6, он печатает 6-ю строку).

Cutie Pie 26.10.2018 06:02

Да, именно это я имел в виду. И, кстати, вот кое-что, что поможет вам с вашей функцией print_pascal_line: scipy.special.comb

eat chocolate 26.10.2018 06:10

Как насчет этого?

def pascal_triangle(n, line=None):
    if n == 0: return
    if line is None: 
        line = [1]
    print(" ".join(map(str, line)))
    pascal_line(line)
    pascal_triangle(n-1, line)

def pascal_line(line, i=0, add=0):
    if i >= len(line):
        line.append(add)
        return
    add, line[i] = line[i], line[i] + add
    pascal_line(line, i+1, add)

это работает также, однако есть альтернативный способ определения параметров, таких как line = None, i = 0 и add = 0, потому что я лично никогда не учился делать это таким образом.

Cutie Pie 26.10.2018 07:20

Каждый элемент треугольника Паскаля оценивается с помощью биномиальный коэффициент. Это значение, часто обозначаемое как nCr, спрашивает: «С учетом элементов n, сколькими способами вы можете выбрать элементы C

Возьмем, к примеру, элементы r, a и b. Сколько способов мы можем создать комбинации следующих размеров?

  1. Есть только 1 способ выбрать 0 элементов: c
  2. Возможны 3 комбинации: {}, {a} или {b}.
  3. Опять же, 3 способа: {c}, {a, b} или {a, c}
  4. Только {b, c}

И что бы вы знали, это как раз уровень 3 * треугольника Паскаля: {a, b, c}! Как оказалось, мы можем использовать это на любом уровне.

0: nCr(0, 0)
1: nCr(1, 0) nCr(1, 1)
2: nCr(2, 0) nCr(2, 1) nCr(2, 2)
3: nCr(3, 0) nCr(3, 1) nCr(3, 2) nCr(3, 3)
etc
etc

Итак, как мы можем для этого кодировать? Глядя на этот ответ, мы получаем нашу функцию 1 3 3 1

In [454]: import functools as ft

In [455]: import operator as op

In [456]: def nCr(n, r):
     ...:     r = min(r, n-r)
     ...:     numer = ft.reduce(op.mul, range(n, n - r, -1), 1)
     ...:     denom = ft.reduce(op.mul, range(1, r + 1), 1)
     ...:     return numer // denom
     ...:

Наконец, давайте создадим рекурсивную функцию, чтобы связать все это воедино.

In [457]: def pascal(n):
     ...:     if n >= 1:
     ...:         pascal(n - 1)
     ...:         print(' '.join(str(nCr(n - 1, r)) for r in range(n)))
     ...:

In [463]: pascal(5)
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

Технически это должен быть nCr, поскольку треугольник Паскаля имеет нулевой индекс *, но я просто следую запросу OP. Если бы мы хотели изменить это, мы бы изменили нашу функцию pascal(4) на

In [468]: def pascal(n):
     ...:     if n >= 0:
     ...:         pascal(n - 1)
     ...:         print(' '.join(str(nCr(n, r)) for r in range(n + 1)))
     ...:

Очень хороший ответ. Я узнал кое-что новое о Паскале. Однако подсказки In [###]: отвлекают и затрудняют копирование / вставку кода.

Mulan 06.11.2018 16:31

ОП явно указано несколько раз, «без использования каких-либо циклов». Выражение (str(nCr(n, r)) for r in range(n + 1)) - это петля!

cdlane 31.10.2019 23:25

Чисто рекурсивное решение (без цикла, без присваивания, без внешних модулей, используется только функция Python - sum, чего также можно избежать). Этот код можно легко перевести на семейный язык LISP.

def pascal_line(n):
    def nextline(thisline):
        if thisline == []:
            return []
        else:
            return [sum(thisline[:2])] + nextline(thisline[1:])
    if n == 1:
        return [1]
    elif n == 2:
        return [1, 1]
    else:
        return [1]+nextline(pascal_line(n-1))

def pascal_triangle(n):
    def printline(m):
        if m <= n:
            print(*pascal_line(m))
            printline(m+1)
    return printline(1)

pascal_triangle(6)
# output =>
# 1
# 1 1
# 1 2 1
# 1 3 3 1
# 1 4 6 4 1
# 1 5 10 10 5 1

Внутренняя функция nextline рекурсивно выводит следующую строку (без ведущей 1) в треугольнике паскаля на основе текущей строки.

Функция pascal_line выводит строку nth в треугольнике паскаля, рекурсивно вызывая nextline с строкой (n-1) th (ее собственное предыдущее решение).

Функция pascal_triangle выводит строки в виде треугольника Паскаля, рекурсивно вызывая pascal_line.

Все вместе три рекурсивные функции прекрасно иллюстрируют типичную природу рекурсивного подхода «разделяй и властвуй».

Я отвечал на этот вопрос один раз перед здесь. Перейдите по ссылке, чтобы узнать, как создавать рекурсивные функции, подобные этой.

def pairs (xs):
  if 2 > len(xs):
    return []
  else:
    return [xs[0:2]] + pairs(xs[1:])

def pascal (n):
  def compute (prev):
    return [1] + [x + y for (x,y) in pairs(prev)] + [1]
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, compute(prev))
  return aux(1, [1])

for line in pascal(5):
  print(line)
# [1]
# [1, 1]
# [1, 2, 1]
# [1, 3, 3, 1]
# [1, 4, 6, 4, 1]

Выше мы создаем новый синглтон [1] в трех местах; два из которых являются частью цикла compute. Мы должны создать его один раз и вместо этого использовать повторно.

def pascal (n):
  one = [1]
  def compute (prev):
    return one + [x + y for (x,y) in pairs(prev)] + one
  def aux (m, prev):
    if (m > n):
      return []
    else:
      return [prev] + aux(m + 1, compute(prev))
  return aux(1, one)

Последнее улучшение, которое я мог бы предложить, - это использовать генератор вместо быстрого возврата всех строк.

def pascal (n):
  one = [1]
  def compute (prev):
    return one + [x + y for (x,y) in pairs(prev)] + one
  def aux (m, prev):
    if (m > n):
      return
    else:
      yield prev
      yield from aux(m + 1, compute(prev))
  yield from aux(1, one)

Теперь вы можете лениво вычислять результат по мере его использования. Однако, если вы хотите все сразу, вы можете использовать list.

list(pascal(5))
# [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]

очень красивое решение. мы получаем почти такое же решение. Я предлагаю позволить функции pairs возвращать [sum(xs[0:2])] + pairs(xs[1:]). Затем вы сохраняете понимание списка позже в compute, возвращая one + pairs(prev) + one, что делает всю программу более читаемой и краткой и позволяет избежать любого типа цикла, запрошенного OP.

englealuze 07.11.2018 10:25

ОП явно указано несколько раз, «без использования каких-либо циклов». Выражение [x + y for (x,y) in pairs(prev)] - это петля!

cdlane 31.10.2019 23:24

Более простое рекурсивное решение, использующее математику для построения треугольника без каких-либо скрытых циклов:

def pascal(n, row=0):

    def pascal_row(numerator, denominator=1, number=1):
        if numerator > 0:
            number = number * numerator // denominator
            return [number, *pascal_row(numerator - 1, denominator + 1, number)]

        return []

    if row < n:
        return [[1, *pascal_row(row)], *pascal(n, row + 1)]

    return []

print(*pascal(10), sep='\n')

ВЫХОД

% python3 test.py
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
%

Другие вопросы по теме