Рассмотрим стандартный равносторонний треугольник с узлами, помеченными с использованием барицентрических координат :

Мы можем превратить этот треугольник с 3 узлами в треугольник с 6 узлами, добавив новую линию из 3 вершин (на одну больше, чем было на стороне исходного треугольника с 3 узлами), удалив все внутренние ребра (но не внутренние узлы) и повторно нормализовать координаты:

Повторяя процесс, чтобы перейти от треугольника с 6 узлами к треугольнику с 10 узлами, добавить линию из 4 вершин (опять же, на одну больше, чем было на стороне исходного треугольника с 6 узлами), удалить все внутренние ребра (но не внутренние узлы). ) и заново нормализовать координаты:

Этот процесс может повторяться до бесконечности. Целью этой задачи является целое число, Nпредставляющее, сколько раз этот процесс был выполнен, выводить все узлы для соответствующего треугольника в барицентрических координатах.

вход

Ваша программа / функция должна принимать в качестве входных данных одно неотрицательное целое число, Nпредставляющее, сколько раз этот процесс применялся. Обратите внимание, что для N=0, вы должны вывести исходный треугольник с 3 узлами.

Вход может поступать из любого источника (параметр функции, stdio и т. Д.).

Выход

Ваша программа / функция должна выводить все узлы в нормализованных барицентрических координатах. Порядок узлов не имеет значения. Число может быть задано в виде дроби (сокращение дроби не требуется) или числа с плавающей запятой. Вы также можете вывести «масштабированные» векторы, чтобы указать узел. Например, все 3 из следующих выходов эквивалентны и разрешены:

0.5,0.5,0

1/2,2/4,0

[1,1,0]/2

Если вы используете вывод с плавающей запятой, ваш вывод должен быть точным с точностью до 1%. Выход может быть для любого желаемого приемника (stdio, возвращаемого значения, возвращаемого параметра и т. Д.). Обратите внимание, что хотя барицентрические координаты однозначно определяются только 2 числами на узел, вы должны вывести все 3 числа на узел.

Примеры

Примеры случаев отформатированы как:

N
x0,y0,z0
x1,y1,z1
x2,y2,z2
...

где первая строка является входом N, а все последующие строки образуют узел, x,y,zкоторый должен быть на выходе ровно один раз. Все числа даны как приблизительные числа с плавающей точкой.

0
1,0,0
0,1,0
0,0,1

1
1,0,0
0,1,0
0,0,1
0.5,0,0.5
0.5,0.5,0
0,0.5,0.5

2
1,0,0
0,1,0
0,0,1
0.667,0,0.333
0.667,0.333,0
0.333,0,0.667
0.333,0.333,0.333
0.333,0.667,0
0,0.333,0.667
0,0.667,0.333

3
1,0,0
0.75,0,0.25
0.75,0.25,0
0.5,0,0.5
0.5,0.25,0.25
0.5,0.5,0
0.25,0,0.75
0.25,0.25,0.5
0.25,0.5,0.25
0.25,0.75,0
0,0,1
0,0.25,0.75
0,0.5,0.5
0,0.75,0.25
0,1,0

счет

Это код гольф; выигрывает самый короткий код в байтах. Применяются стандартные лазейки. Вы можете использовать любые встроенные модули по желанию.

CJam (22 байта)

{):X),3m*{:+X=},Xdff/}

Это анонимный блок (функция), который берет Nстек и оставляет массив массивов двойников в стеке. Онлайн демо

рассечение

{         e# Define a block
  ):X     e# Let X=N+1 be the number of segments per edge
  ),3m*   e# Generate all triplets of integers in [0, X] (inclusive)
  {:+X=}, e# Filter to those triplets which sum to X
  Xdff/   e# Normalise
}

Haskell, 53 байта

f n|m<-n+1=[map(/m)[x,y,m-x-y]|x<-[0..m],y<-[0..m-x]]

Python 3, 87 байт

На самом деле это должен быть комментарий к решению TheBikingViking, но у меня недостаточно репутации для комментариев.

Можно сохранить несколько байтов, только перебирая переменные i,jи используя тот факт, что с третьим они складываются n+1.

def f(n):d=n+1;r=range(n+2);print([[i/d,j/d,(d-i-j)/d]for i in r for j in r if d>=i+j])

Mathematica,  44  43 байта

Select[Range[0,x=#+1]~Tuples~3/x,Tr@#==1&]&

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

Создает все три набора кратных от 1/(N+1)0 до 1 включительно, а затем выбирает те, чья сумма равна 1 (в соответствии с барицентрическими координатами).

05AB1E , 10 байтов

ÌL<¤/3ãDOÏ

объяснение

ÌL<          # range(1,n+2)-1
   ¤/        # divide all by last element (n+1)
     3ã      # cartesian product repeat (generate all possible triples)
       DO    # make a copy and sum the triples
         Ï   # keep triples with sum 1

Попробуйте онлайн

MATL , 17 байт

2+:qGQ/3Z^t!s1=Y)

Попробуйте онлайн!

объяснение

Подход такой же, как и в других ответах:

1. Сгенерируйте массив [0, 1/(n+1), 2/(n+1), ..., 1], где nнаходится вход;
2. Генерация всех 3-х кортежей с этими значениями;
3. Оставьте только тех, чья сумма равна 1.

Более конкретно:

2+     % Take input and add 2: produces n+2
:q     % Range [0 1 ... n+1]
GQ/    % Divide by n+1 element-wise: gives [0, 1/(n+1), 2/(n+1)..., 1]
3Z^    % Cartesian power with exponent 3. Gives (n+1)^3 × 3 array. Each row is a 3-tuple
t      % Duplicate
!s     % Sum of each row
1=     % Logical index of entries that equal 1
Y)     % Use that index to select rows of the 2D array of 3-tuples

Медуза , 37 33 байта

Спасибо Zgarb за сохранение 4 байта.

p
*%
# S
`
=E   S
`/
1+r#>>i
   3

Попробуйте онлайн!

Как и в моих ответах Mathematica и Peter CJam, здесь генерируется набор подходящих кортежей, а затем выбираются только те, которые суммируются с 1. но я должен рассмотреть это позже.

Perl 6: 50 40 байт

{grep *.sum==1,[X] (0,1/($_+1)...1)xx 3}

Возвращает последовательность 3-элементных списков (точных) рациональных чисел.

Объяснение:

• $_
  Неявно объявленный параметр лямбды.
• 0, 1/($_ + 1) ... 1
  Использует оператор последовательности ...для построения арифметической последовательности, которая соответствует возможным значениям координат.
• [X] EXPR xx 3
  Принимает декартово произведение трех копий EXPR, т.е. генерирует все возможные 3-кортежи.
• grep *.sum == 1, EXPR
  Фильтр кортежей с суммой 1.

Руби, 62

Я был бы удивлен, если это не может быть улучшено:

->x{0.step(1,i=1.0/(x+1)){|a|0.step(1-a,i){|b|p [a,b,1-a-b]}}}

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

Брахилог , 24 байта

+:1f
yg:2j:eaL+?/g:Lz:*a

Попробуйте онлайн!

Python 3, 106 байт

def f(n):r=range(n+2);print([x for x in[[i/-~n,j/-~n,k/-~n]for i in r for j in r for k in r]if sum(x)==1])

Функция, которая принимает входные данные через аргумент и печатает список списков с плавающей точкой в ​​STDOUT.

Python не хорош в декартовых произведениях ...

Как это устроено

def f(n):                         Function with input iteration number n
r=range(n+2)                      Define r as the range [0, n+1]
for i in r for j in r for k in r  Length 3 Cartesian product of r
[i/-~n,j/-~n,k/-~n]               Divide each element of each list in the product
                                  by n+1
[x for x in ... if sum(x)==1]     Filter by summation to 1
print(...)                           Print to STDOUT

Попробуйте это на Ideone

На самом деле 15 байтов

При этом используется алгоритм, аналогичный алгоритму в ответе TheBikingViking на Python . Предложения по игре в гольф приветствуются. Попробуйте онлайн!

u;ur♀/3@∙`Σ1=`░

Ungolfed:

u;                Increment implicit input and duplicate.
  ur              Range [0..n+1]
    ♀/            Divide everything in range by (input+1).
      3@∙         Take the Cartesian product of 3 copies of [range divided by input+1]
         `Σ1=`    Create function that takes a list checks if sum(list) == 1.
              ░   Push values of the Cartesian product where f returns a truthy value.

Рубин, 77 74 байта

Другой ответ с использованием алгоритма в ответе TheBikingViking's Python . Предложения по игре в гольф приветствуются.

->n{a=[*0.step(1,i=1.0/(n+1))];a.product(a,a).reject{|j|j.reduce(&:+)!=1}}

Еще один 74-байтовый алгоритм, основанный на ответе Руби Че .

->x{y=x+1;z=1.0/y;[*0..y].map{|a|[*0..y-a].map{|b|p [a*z,b*z,(y-a-b)*z]}}}

JavaScript (Firefox 30-57), 88 81 байт

n=>[for(x of a=[...Array(++n+1).keys()])for(y of a)if(x+y<=n)[x/n,y/n,(n-x-y)/n]]

Возвращает массив массивов чисел с плавающей точкой. Изменить: 7 байтов сохранены путем непосредственного вычисления третьей координаты. Я попытался исключить if, вычислив диапазон yнапрямую, но это стоило дополнительного байта:

n=>[for(x of a=[...Array(++n+1).keys()])for(y of a.slice(x))[x/n,(y-x)/n,(n-y)/n]]