Задача: Учитывая площадь треугольника, найдите героновский треугольник с этой областью. Разрешен любой героновский треугольник с указанной площадью.

Героновский треугольник - это треугольник с целочисленными сторонами и целочисленной областью . По формуле Герона треугольник с длинами сторон a,b,cимеет площадь

sqrt(s*(s-a)*(s-b)*(s-c))

где s=(a+b+c)/2половина периметра треугольника. Это также можно записать как

sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)) / 4

Если такого треугольника не существует, выведите с постоянным значением Фэлси.

Входные данные: единственное положительное целое число, представляющее площадь треугольника.

Вывод: любые три длины сторон для такого треугольника ИЛИ ложное значение.

Примеры:

Input -> Output
6 -> 3 4 5
24 -> 4 15 13
114 -> 37 20 19
7 -> error

Применяются стандартные лазейки

Это код гольф, самый короткий ответ в байтах выигрывает.

Желе , 17 16 байт

-1 байт благодаря Эрику-аутголферу (воспользуйтесь быстрым, ¥)

SHð;_P
ṗ3Ç⁼¥Ðf²Ḣ

Применение грубой силы формулы Герона.

Попробуйте онлайн! (истекает тайм-аут 60-х для 114 тестовых случаев. Локально занимает 3 м 30 с - проверяет 114 ³ = 1 481 544 тройки)

Как?

Истинное решение для гольфа - с учетом области aон находит все кортежи из трех целых чисел между 1и a(даже с повторяющимися треугольниками и без области), получает их площадь и фильтрует для тех с нужной областью (он даже не останавливается, как только один найден, он пропускает их все и выдает первый результат потом). Дает, 0если ничего не существует.

SHð;_P - Link 1, get the square of the area of a triangle: list of sides
S      - sum the sides (get the perimeter)
 H     - halve
  ð    - dyadic chain separation (call that p)
    _  - subtraction (vectorises) =    [p-side1,  p-side2,  p-side3]
   ;   - concatenate              = [p, p-side1,  p-side2,  p-side3]
     P - product                  =  p*(p-side1)*(p-side2)*(p-side3)
                                  = the square of Heron's formula = area squared

ṗ3Ç⁼¥Ðf²Ḣ - Main link: number a (area)
ṗ3        - third Cartesian power (all triples of [1,area] : [[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2], ... ,[a,a,a]]
       ²  - square a
     Ðf   - filter keep if:
    ¥     -   last two links as a dyad:
  Ç       -     call last link (1) as a monad f(list of sides)
   ⁼      -     left (that result) equals right (square of a)?
        Ḣ - head - get the first one (an empty list yields 0, perfect for the falsey case)

JavaScript (ES7), 109 102 100 98 байт

Возвращает либо массив из 3 целых чисел, либо false. Как и ответ Jelly , это грубое форсирование формулы Герона.

A=>[...Array(A**3)].some((_,a)=>A*A/(r=[b=a/A%A|0,c=a/A/A|0,a%=A],p=a+b+c>>1)/(p-a)/(p-b)==p-c)&&r

Контрольные примеры

let f =

A=>[...Array(A**3)].some((_,a)=>A*A/(r=[b=a/A%A|0,c=a/A/A|0,a%=A],p=a+b+c>>1)/(p-a)/(p-b)==p-c)&&r

console.log(JSON.stringify(f(6)))
console.log(JSON.stringify(f(24)))
console.log(JSON.stringify(f(114)))
console.log(JSON.stringify(f(7)))

Рекурсивная версия, 83 байта

Возвращает массив из 3 целых чисел или выдает ошибку рекурсии. К сожалению, это работает только для небольших входов.

f=(A,n)=>A*A/(r=[a=n%A,b=n/A%A|0,c=n/A/A|0],p=a+b+c>>1)/(p-a)/(p-b)==p-c?r:f(A,-~n)

демонстрация

f=(A,n)=>A*A/(r=[a=n%A,b=n/A%A|0,c=n/A/A|0],p=a+b+c>>1)/(p-a)/(p-b)==p-c?r:f(A,-~n)

console.log(JSON.stringify(f(6)))
console.log(JSON.stringify(f(24)))

Haskell , 69 байт

f a=take 1[t|t<-mapM(\_->[1..a])":-)",a*a==product[sum t/2-x|x<-0:t]]

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

Выводит один список из трех сторон треугольника, например [[3.0,4.0,5.0]]. Невозможные входы дают []. Технически это только FalseFalsey для Haskell, но поскольку Haskell требует, чтобы все возможные выходы были одного типа, его нельзя использовать. Если ошибка может быть использована как Falsey, [...]!!0сэкономит 3 байта take 1[..].

Пытается все тройки tвозможных длин сторон, начиная от 1области a. Формула Герона используется, чтобы проверить, соответствует ли область через, (s-0)(s-x)(s-y)(s-z)==a*aгде s=(x+y+z)/2есть sum t/2. Продукт (s-0)(s-x)(s-y)(s-z)выражается в виде productэлементов, взятых из 0:t, то есть тройной, а также 0.

F #, 170 156 152 байта

let f(a,b,c)=
 let s=(a+b+c)/2.0
 s*(s-a)*(s-b)*(s-c)
let g A=[for a in 1.0..A do for b in a..A do for c in b..A do yield a,b,c]|>List.find(f>>(=)(A*A))

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

"Ungolfed"

let calculateArea (a, b, c) =
    let s = (a+b+c)/2.0
    s*(s-a)*(s-b)*(s-c)

let getTriangle A =
    [  for a in 1.0..A do
       for b in a..A do
       for c in b..A do yield a,b,c
    ]
    |> List.find(calculateArea>>(=)(A * A))

Если результаты не найдены, программа выдаст ошибку. Если это нежелательно, я должен заменить List.findлибо List.filter(+2 байта), что приведет к созданию пустого списка в случае, если ничего не найдено, либо List.tryFind(+3 байта), возвращая None, если треугольник не был найден.

Я всегда нахожу, что версия F # в гольфе все еще разумно читаема.

Python 2 (PyPy) , 131 123 118 байт

n=input()
t=n*3;r=i=c=0
while c<t:
 i+=1;a,b,c=i%t,i/t%t,i/t/t;s=a+b+c>>1
 if(s-a)*s*(s-b)*(s-c)==n**2:r=a,b,c
print r

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

Хотя это также работает на CPython, PyPy работает намного быстрее и способен вычислять треугольник для 114 за ограничение времени на TIO.

Сроки от моей машины:

$ echo 114 | time pypy2 d.py
        0.55 real         0.52 user         0.02 sys
$ echo 114 | time python2 d.py
       52.46 real        51.76 user         0.27 sys

Pyth - 23 байта

/mu*G-/sd2Hd/sd2^UQ3^Q2

Который печатает истинное / ложное значение, или

fq^Q2u*G-/sT2HT/sT2^UQ3

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

Объяснение:

fq^Q2u*G-/sT2HT/sT2^UQ3
                    UQ    # List of numbers from 0 to input-1
                   ^  3   # All triples of these numbers
f                         # Filter this by the following test (on variable T, based on Hero's formula)
     u*G-/sT2HT/sT2       # s*(s-a)*(s-b)*(s-c), where s is the sum of the triple over 2 (calclated as /sT2 )
 q^Q2                     # Test if equal to input ^2

Попытайся

Perl 6 , 54 байта

->\a{first {a*a==[*] .sum/2 «-«(0,|$_)},[X] ^a xx 3}

Перебор всех возможных сторон на одну единицу меньше, чем aобласть ввода.

• ^aэто диапазон чисел от 0 до a - 1.
• [X] ^a xx 3сокращает по кросс-продукту три копии этого диапазона, производя все тройки от (0, 0, 0)до (a - 1, a - 1, a - 1).
• Мы ищем firstтриплет так, чтобы площадь треугольника с этими сторонами была равна a, используя формулу Герона .

Внутри блока кода, данного first:

• $_это триплет Позвони (x, y, z)здесь.
• (0,|$_)одно и то же триплет , но с 0префиксом: (0, x, y, z).
• .sum / 2составляет половину периметра (количество, которое названо sв обычном выражении формулы Герона).
• .sum / 2 «-« (0, |$_)является гипераоператором вычитания с sлевой и (0, x, y, z)правой стороны (s - 0, s - x, s - y, s - z).
• [*] затем уменьшает эту четверку с умножением, давая квадрат площади.
• a * a == ищет площадь в квадрате, равную квадрату данной области.

Если триплет не найден, Nil(который является ложным) возвращается.

Haskell , 76 байт

f s=[[a,b,c]|a<-[1..s],b<-[1..a],c<-[1..b],a*a*c*c-(a*a+c*c-b*b)^2/4==4*s*s]

Это выводит список списков, содержащих все возможные интегральные размеры, которые генерируют правильную область с помощью грубой силы (выводит пустой список, если таковых нет). Предостережение состоит в том, что он выводит их как двойные из-за этого деления в середине, но их дробная часть всегда равна 0.

Если вы по какой-то причине не можете принять это,

f s=[[a,b,c]|a<-[1..s],b<-[1..a],c<-[1..b],4*a*a*c*c-(a*a+c*c-b*b)^2==16*s*s]

Это выведет ответы в виде списка целочисленных списков для 89 всего 77 байт или 13 1 дополнительных байтов. (Спасибо Нейлу)

Если вам нужно / нужно, чтобы только первый элемент, помещенный !!0в конец, даст вам только первый элемент, если есть числа, которые применяются, и ошибку, если ее нет для еще 3 байтов, и take 1в начале примет первый элемент без ошибок для Еще 6 байтов.

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

TI-Basic, 70 69 байт

Prompt A
For(B,1,A
For(C,1,B
For(D,1,C
(B+C+D)/2
If A2=Ansprod(Ans-{B,C,D
Then
Disp B,C,D
Return
End
End
End
End
/

Отображает три длины стороны, если есть треугольник, выдает синтаксическую ошибку, если ее нет (спасибо /в конце).

-1 байт благодаря комментарию Шона к другому ответу

Mathematica, 77 байтов

с Решением математики

s=(a+b+c)/2;d=Sqrt[s(s-a)(s-b)(s-c)];Solve[d==#&&0<a<b<c<#,{a,b,c},Integers]&

Mathematica, 117 байт

грубая сила

s=(a+b+c)/2;l="error";(For[a=1,a<#,a++,For[b=1,b<a,b++,For[c=1,c<b,c++,If[Sqrt[s(s-a)(s-b)(s-c)]==#,l={a,b,c}]]]];l)&

На самом деле , 22 байта

;╗R3@∙⌠;Σ½;)♀-π*╜²=⌡░F

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

Объяснение:

;╗R3@∙⌠;Σ½;)♀-π*╜²=⌡░F  (implicit input: A)
;╗                      store a copy of A in register 0
  R                     range(1, A+1)
   3@∙                  ternary Cartesian product (all triples with values in [1, A])
      ⌠;Σ½;)♀-π*╜²=⌡░   filter: take triples where function returns truthy
       ;Σ½                make a copy of the triple, compute s = (a+b+c)/2
          ;)              make a copy of s, move it to the bottom of the stack
            ♀-            subtract each value in the triple from s
              π*          product of those values and s (s*(s-a)*(s-b)*(s-c))
                ╜²        A*A
                  =       compare equality (does area of triangle with given dimensions equal input?)
                     F  take first triple that satisfies the filter (or empty list if none)

Casio Basic, 123 байта

For 1⇒a To n
For 1⇒b To n
For 1⇒c To n
If(s*(s-a)*(s-b)*(s-c)|s=(a+b+c)/2)=n^2
Then
Print{a,b,c}
Stop
IfEnd
Next:Next:Next

Стандартное решение для перебора. 122 байта для кода, 1 байт для указания nв качестве параметра.

Wolfram Language (Mathematica) , 59 байт

Solve[Area@SSSTriangle[a,b,c]==#>c>b>a>0,{a,b,c},Integers]&

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