Маржа слишком узкая

30

Примерно в 1637 году Пьер де Ферма написал на полях своей копии «Арифметики»: 

It is impossible to separate a cube into two cubes, or a fourth power 
into two fourth powers, or in general, any power higher than the 
second, into two like powers. I have discovered a truly marvelous 
proof of this, which this margin is too narrow to contain.

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

Соревнование

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

вход

Мощность и количество энергии: c,x

Ограничения: c > 2иx > 2

Ввод может быть через аргументы программы, аргументы функции или от пользователя.

Выход

Это точная строка: « a^x + b^x < c^x» с a, b, cи xзаменить их буквального целочисленных значений. aи bдолжны быть выбраны так, чтобы a^x + b^x < c^xи никакие другие ценности aили bне приблизили бы их c^x. Также:a>=b>0

Вывод может быть выполнен через возвращаемое значение функции, стандартный вывод, сохранен в файл или отображен на экране.

Примеры:

> 3 3
2^3 + 2^3 < 3^3
> 4 3
3^3 + 3^3 < 4^3
> 5 3
4^3 + 3^3 < 5^3
> 6 3
5^3 + 4^3 < 6^3
> 7 3
6^3 + 5^3 < 7^3
> 8 3
7^3 + 5^3 < 8^3

Из-за средних навыков письма Ферма непечатаемые символы не допускаются. Программа с наименьшим количеством символов выигрывает.

Leaderboards

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

Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:

## Language Name, N characters

Кроме того, вы можете начать с:

## Language Name, N bytes

где Nразмер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:

## Ruby, <s>104</s> <s>101</s> 96 bytes

Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:

## Perl, 43 + 2 (-p flag) = 45 bytes

Вы также можете сделать название языка ссылкой, которая затем будет отображаться во фрагменте списка лидеров:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Показать фрагмент кода

code-golf number Номер один
источник
1
Я думаю, что это должно быть a>=b>0или ваш первый пример будет неверным. И почему мы должны отображать, <когда вы хотите, чтобы это было <=?
Flawr
@flawr Исправлено :)
TheNumberOne
Было бы нормально принять аргументы в обратном порядке? Сначала x, потом c?
Рето Коради
@RetoKoradi Конечно :)
TheNumberOne

Ответы:

9

Pyth, 38 байт

Ls^Rvzbjd.imj\^,dz+eoyNf<yTy]Q^UQ2Q"+<

Принимает участие в этом формате:

x
c
orlp
источник
8

Matlab, 169 153 байта

Оценка может быть + -1 в зависимости от нерешенных проблем в комментариях =) Оценка остается прежней. Это просто грубый поиск лучшей (a,b)пары.

Довольно разочаровывающе: я сначала попробовал поэкспериментировать с некоторыми «причудливыми» вещами, а потом понял, что два простых вложенных цикла for намного короче ...

function f(c,x);
m=0;p=@(x)int2str(x);
X=['^' p(x)];
for b=1:c;for a=b:c;
n=a^x+b^x;
if n<c^x&n>m;m=n;s=[p(a) X ' + ' p(b) X ' < ' p(c) X];end;end;end;
disp(s)

Старая версия:

function q=f(c,x);
[b,a]=meshgrid(1:c);
z=a.^x+b.^x;
k=find(z==max(z(z(:)<c^x & a(:)>=b(:))),1);
p=@(x)int2str(x);x=['^' p(x)];
disp([p(a(k)) x ' + ' p(b(k)) x ' < ' p(c) x])
flawr
источник
Удалить пробелы в m = 0? Тем не менее, это не поможет вам приблизиться к моему ответу: -PP
Луис Мендо
Кроме того, похоже, что вы можете удалить q=из определения функции
Луис Мендо
Я не вижу qнигде используемой переменной. Вы можете сбрить пару байтов, просто сделав function f(c,x)и удалив точку с запятой.
rayryeng - Восстановить Монику
8

Mathematica, 79 95 80 байт

Это может просто соответствовать краю.

c_~f~x_:=Inactivate[a^x+b^x<c^x]/.Last@Solve[a^x+b^x<c^x&&a>=b>0,{a,b},Integers]

тестирование

f[3, 3]
f[4, 3]
f[5, 3]
f[6, 3]
f[7, 3]
f[8, 3]

выход

DavidC
источник
7

CJam, 51 46 43 байта

q~_2m*\f+{W$f#)\:+_@<*}$W='^@s+f+"+<".{S\S}

Эта полная программа считывает мощность, а затем базу от STDIN.

Попробуйте онлайн в интерпретаторе CJam .

Деннис
источник
6

Matlab, 141 140 байт

Это кодируется как функция, которая отображает результат в stdout.

function f(c,x)
b=(1:c).^x;d=bsxfun(@plus,b,b');d(d>c^x)=0;[~,r]=max(d(:));sprintf('%i^%i + %i^%i < %i^%i',[mod(r-1,c)+1 ceil(r/c) c;x x x])

Пример использования:

>> f(8,3)
ans =
7^3 + 5^3 < 8^3

Или попробуйте это онлайн в Октаве .

Спасибо @flawr за удаление одного байта.

Луис Мендо
источник
Я всегда избегал, sprintfпотому что это казалось таким сложным, хотя на самом деле это не так! И я забыл bsxfunеще раз, так что это очень элегантное решение. Мне особенно нравится, как вы злоупотребляли индексированием одинарного / двойного в последнем аргументе =) (Вы также можете удалить пробел там!)
flawr
Благодарность! Я dispтоже обычно пользуюсь , кроме как в Code Golf :-P
Луис Мендо
Если вы используете fprintfвместо него sprintf, он не отображает «ans»
Jonas
@Jonas Но он печатает результат, а затем подсказку >>в той же строке, что немного странно
Луис Мендо
Вы можете использовать fprintf, но вам придется вставить ручной возврат каретки.
rayryeng - Восстановить Монику
5

CJam, 53 51 байт

l~:C\:X#:U;C2m*{Xf#:+_U<*}$W=~"^"X+:T" + "@T" < "CT

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

Формат ввода - x cэто обратный порядок, используемый в примерах.

Объяснение:

l~    Read and interpret input.
:C    Store c in variable C.
\     Swap x to top.
:X    Store it in variable X.
#     Calculate c^x.
:U;   Store it in variable U as the upper limit, and pop it from stack.
C2m*  Generate all pairs of values less than c. These are candidates for a/b.
{     Start of mapping function for sort.
  X     Get value of x.
  f#    Apply power to calculate [a^x b^x] for a/b candidates.
  :+    Sum them to get a^x+b^x.
  _U<   Compare value to upper limit.
  *     Multiply value and comparison result to get 0 for values above limit.
}$    End of sort block.
W=    Last a/b pair in sorted list is the solution.
~     Unpack it.
"^"X+ Build "^x" string with value of x.
:T    Store it in variable T, will use it 2 more times in output.
" + " Constant part of output.
@     Rotate b to top of stack.
T     "^x" again.
" < " Constant part of output.
C     Value of c.
T     And "^x" one more time, to conclude the output.
Рето Коради
источник
5

R, 139 символов

function(c,x)with(expand.grid(a=1:c,b=1:c),{d=a^x+b^x-c^x
d[d>0]=-Inf
i=which.max(d)
sprintf("%i^%4$i + %i^%4$i < %i^%4$i",a[i],b[i],c,x)})
flodel
источник
4

Python 2, 182 161 157 байт

Я обычно отвечаю в MATLAB, но поскольку на этом языке уже есть два решения, я решил бы попробовать другой язык :)

def f(c,x):print max([('%d^%d + %d^%d < %d^%d'%(a,x,b,x,c,x),a**x+b**x) for b in range(1,c+1) for a in range(b,c+1) if a**x+b**x<c**x],key=lambda x:x[1])[0]

Разоблаченный код с пояснениями

def f(c,x): # Function declaration - takes in c and x as inputs

    # This generates a list of tuples where the first element is 
    # the a^x + b^x < c^x string and the second element is a^x + b^x
    # Only values that satisfy the theorem have their strings and their
    # corresponding values here
    # This is a brute force method for searching
    lst = [('%d^%d + %d^%d < %d^%d'%(a,x,b,x,c,x),a**x+b**x) for b in range(1,c+1) for a in range(b,c+1) if a**x+b**x<c**x]

    # Get the tuple that provides the largest a^x + b^x value
    i = max(lst, key=lambda x:x[1])

    # Print out the string for this corresponding tuple
    print(i[0])

Примеры запусков

Я запустил это в IPython:

In [46]: f(3,3)
2^3 + 2^3 < 3^3

In [47]: f(4,3)
3^3 + 3^3 < 4^3

In [48]: f(5,3)
4^3 + 3^3 < 5^3

In [49]: f(6,3)
5^3 + 4^3 < 6^3

In [50]: f(7,3)
6^3 + 5^3 < 7^3

In [51]: f(8,3)
7^3 + 5^3 < 8^3

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

http://ideone.com/tMjGdh

Если вы хотите запустить код, нажмите на ссылку редактирования в верхней части, затем измените параметр STDIN с двумя целыми числами, разделенными пробелом. Первое целое число cи следующее x. Прямо сейчас, c=3а x=3и в данный момент отображается его результат.

rayryeng - Восстановить Монику
источник
3

Pyth, 53 52 50 байт

Ls^ReQbs[j" + "+R+\^eQ_Sh.MyZf<yT^FQ^UhQ2" < "j\^Q

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

Принимает в качестве входных данных , c,xгде cявляется целевым числом и xявляется базой.

PurkkaKoodari
источник
2

C 175 байт

a,b,m,A,B,M;p(
a,x){return--x
?a*p(a,x):a;}f
(c,x){M=p(c,x)
;for(a=c,b=1;a
>=b;)(m=p(c,x)
-p(a,x)-p(b,x
))<0?--a:m<M?
(M=m,B=b++,A=
a):b++;printf
("%d^%d + %d"
"^%d < %d^%d",
A,x,B,x,c,x);}

Чтобы поместить код в поле, я вставил новые строки и разделил строковый литерал выше - код для подсчета / компиляции

a,b,m,A,B,M;p(a,x){return--x?a*p(a,x):a;}f(c,x){M=p(c,x);for(a=c,b=1;a>=b;)(m=p(c,x)-p(a,x)-p(b,x))<0?--a:m<M?(M=m,B=b++,A=a):b++;printf("%d^%d + %d^%d < %d^%d",A,x,B,x,c,x);}

Функция fпринимает cи в xкачестве аргументов, и выдает результат по stdout.

объяснение

Это итеративное решение, которое зигзагами определяет линию, определяемую a^x + b^x = c^x. Начнем с a=cи b=1. Очевидно, это ставит нас не на ту сторону линии, потому что c^x + 1 > c^x. Мы уменьшаем, aпока не пересечем черту. Когда мы ниже линии, мы увеличиваем, bпока не пересечем ее в другом направлении. Повторите до bвстречи a, помня лучшее решение вA и Bпо ходу дела. Тогда напечатайте это.

pпростая рекурсивная реализация a^x(дляx>0 ), так как C не предоставляет оператора для возведения в степень.

В псевдокоде: 

a=c
b=1
M = c^x

while a >= b
do
   m = c^x - a^x - b^x
   if m < 0
      a -= 1
   else // (m > 0, by Fermat's Last Theorem)
      if m < M
         A,B,M = a,b,m
      b += 1
done
return A,B

Ограничения

c^xдолжно быть представимо в пределах диапазона int. Если это ограничение является слишком ограничительным, сигнатура pможет быть тривиально изменена на long p(long,int)или double p(double,int), и mи Mна longили doubleсоответственно, без каких-либо изменений f().

Тестовая программа

Это принимает cи в xкачестве аргументов командной строки, и печатает результат.

#include<stdio.h>
int main(int argc, char**argv) {
    if (argc <= 2) return 1;
    int c = atoi(argv[1]);
    int x = atoi(argv[2]);
    f(c,x);
    puts("");
    return 0;
}
Тоби Спейт
источник
1

Haskell, 120 байт

Я думаю, что я играл в гольф столько, сколько я могу:

c%x=a&" + "++b&" < "++c&""where(_,a,b)=maximum[(a^x+b^x,a,b)|b<-[1..c],a<-[b..c],a^x+b^x<c^x];u&v=show u++"^"++show c++v

Ungolfed:

fn c x = format a " + " ++ format b " < " ++ format c ""
    where format :: Integer -> String -> String
          -- `format u v` converts `u`, appends an exponent string, and appends `v`
          format u v = show u ++ "^" ++ show c ++ v
          -- this defines the variables `a` and `b` above
          (_, a, b) = maximum [(a^x + b^x, a, b) | b <- [1..c], 
                                                   a <- [b..c],
                                                   a^x + b^x < c^x]

Использование:

Prelude> 30 % 11
"28^30 + 28^30 < 30^30"
ЧР Дрост
источник
0

Haskell, 132 128 байтов

x!y=x++show y
c#x=(\[_,a,b]->""!a++"^"!x++" + "!b++"^"!x++" < "!c++"^"!x)$maximum[[a^x+b^x,a,b]|a<-[0..c],b<-[0..a],a^x+b^x<c^x]

Пример использования: 7 # 3возвращает строку "6^3 + 5^3 < 7^3".

Ними
источник
0

Perl 5, 119 байт

Подпрограмма:

{for$b(1..($z=$_[0])){for(1..$b){@c=("$b^$o + $_^$o < $z^$o",$d)if($d=$b**($o=$_[1])+$_**$o)<$z**$o and$d>$c[1]}}$c[0]}

Используйте как например:

print sub{...}->(8,3)
msh210
источник
0

Рубин, 125 байт

Анонимная функция. Создает список aзначений, использует его для построения a,bпар, затем находит максимум для тех, которые соответствуют критериям, и возвращает оттуда строку.

->c,x{r=[];(1..c).map{|a|r+=([a]*a).zip 1..a}
a,b=r.max_by{|a,b|z=a**x+b**x;z<c**x ?z:0}
"#{a}^#{x} + #{b}^#{x} < #{c}^#{x}"}
Значение чернил
источник