Margines jest zbyt wąski

30

Około roku 1637 Pierre de Fermat napisał na marginesie swojej kopii Arytmetyki: 

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.

Niestety dla nas margines jest wciąż zbyt wąski, aby pomieścić dowód. Dzisiaj zamierzamy napisać na marginesie prosty program, który potwierdza dowód na arbitralne dane wejściowe.

Wyzwanie

Chcemy programu dla funkcji, który ma moc, dzieli ją na dwie pary dwóch mocy, które są jak najbliżej mocy. Chcemy, aby program, który to robi, był tak mały, jak to możliwe, aby pasował do marginesów.

Wkład

Moc i numer silnika: c,x

Ograniczenia: c > 2ix > 2

Dane wejściowe mogą odbywać się za pomocą argumentów programu, argumentów funkcji lub od użytkownika.

Wydajność

Ten dokładny ciąg: „ a^x + b^x < c^x” o a, b, c, i xzastąpiono ich dosłownych wartości całkowitych. ai bmuszą być tak dobrane, aby a^x + b^x < c^xżadne inne wartości alub bnie zbliżyłyby się do nich c^x. Również:a>=b>0

Dane wyjściowe mogą być przekazywane przez funkcję zwracaną wartość, standardowe wyjście, zapisywane do pliku lub wyświetlane na ekranie.

Przykłady:

> 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

Ze względu na średnie umiejętności pisania Fermata, znaki niedrukowalne nie są dozwolone. Program z najmniejszą liczbą znaków wygrywa.

Liderów

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

## Language Name, N characters

Alternatywnie możesz zacząć od:

## Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie tabeli wyników:

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

Pokaż fragment kodu

code-golf number Numer jeden
źródło
1
Myślę, że tak powinno być a>=b>0lub twój pierwszy przykład byłby nieważny. I dlaczego musimy wyświetlać, <kiedy chcesz <=?
flawr
@flawr Naprawiono :)
TheNumberOne
Czy dobrze byłoby przyjąć argumenty w odwrotnej kolejności? Po pierwsze x, to c?
Reto Koradi,
@RetoKoradi Sure :)
TheNumberOne

Odpowiedzi:

9

Pyth, 38 bajtów

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

Pobiera dane wejściowe w tym formacie:

x
c
orlp
źródło
8

Matlab, 169 153 bajtów

Wynik może wynosić + -1 w zależności od nierozwiązanych problemów w komentarzach =) Wynik pozostaje taki sam. To tylko brutalne poszukiwanie najlepszej (a,b)pary.

Całkiem rozczarowujące: najpierw próbowałem eksperymentować z niektórymi „fantazyjnymi” rzeczami, a potem zdałem sobie sprawę, że dwa proste zagnieżdżone dla pętli są znacznie krótsze ...

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)

Stara wersja:

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])
wada
źródło
Usunąć spacje w m = 0? Jednak to nie zbliży cię do mojej odpowiedzi: -PP
Luis Mendo
Wygląda też na to, że można usunąć q=z definicji funkcji
Luis Mendo
qNigdzie nie widzę tej zmiennej. Możesz ogolić kilka bajtów, wykonując function f(c,x)i usuwając również średnik.
rayryeng - Przywróć Monikę
8

Mathematica, 79 95 80 bajtów

To może pasować na margines.

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

Testowanie

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

wydajność

DavidC
źródło
7

CJam, 51 46 43 bajtów

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

Ten pełny program odczytuje moc, a następnie bazę ze STDIN.

Wypróbuj online w interpretatorze CJam .

Dennis
źródło
6

Matlab, 141 140 bajtów

Jest to zakodowane jako funkcja wyświetlająca wynik w 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])

Przykładowe zastosowanie:

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

Lub wypróbuj online w Octave .

Dzięki @flawr za usunięcie jednego bajtu.

Luis Mendo
źródło
Zawsze unikałem, sprintfponieważ wydawało się to tak skomplikowane, a tak naprawdę nie jest! I bsxfunznowu zapomniałem , więc to bardzo eleganckie rozwiązanie. Szczególnie podoba mi się sposób, w jaki nadużywałeś indeksowania pojedynczego / podwójnego w ostatnim argumencie =) (Możesz też usunąć spację!)
flawr
Dzięki! Zwykle dispteż używam , z wyjątkiem Code Golf :-P
Luis Mendo
Jeśli użyjesz fprintfzamiast sprintf, to nie wyświetli „ans”
Jonas
@Jonas Ale drukuje wynik, a następnie monit >>w tym samym wierszu, co jest nieco dziwne
Luis Mendo
Możesz użyć fprintf, ale musisz wstawić ręczny powrót karetki.
rayryeng - Przywróć Monikę
5

CJam, 53 51 bajtów

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

Wypróbuj online

Format wejściowy to x codwrotność kolejności użytej w przykładach.

Wyjaśnienie:

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.
Reto Koradi
źródło
5

R, 139 znaków

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
źródło
4

Python 2, 182 161 157 bajtów

Zwykle odpowiadam w MATLAB, ale ponieważ istnieją już dwa rozwiązania w tym języku, pomyślałbym, że spróbuję innego języka :)

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]

Nieskluczony kod z objaśnieniami

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])

Przykład działa

Uruchomiłem to w 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

Wypróbuj online!

http://ideone.com/tMjGdh

Jeśli chcesz uruchomić kod, kliknij link edytuj u góry, a następnie zmodyfikuj parametr STDIN za pomocą dwóch liczb całkowitych oddzielonych spacją. Pierwszą liczbą całkowitą jest, ca następną jest x. W tej chwili, c=3a x=3jego wynik jest obecnie wyświetlany.

rayryeng - Przywróć Monikę
źródło
3

Pyth, 53 52 50 bajtów

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

Wypróbuj online.

Bierze jako dane wejściowe c,xgdzie cjest liczbą docelową i xjest bazą.

PurkkaKoodari
źródło
2

C, 175 bajtów

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);}

Aby dopasować kod do marginesu, wstawiłem znaki nowej linii i podzieliłem literał ciągu powyżej - kod do gry w golfa, który należy policzyć / skompilować, to

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);}

Funkcja ftrwa ci xjako argumenty i tworzy wynik na stdout.

Wyjaśnienie

Jest to iteracyjne rozwiązanie, które zygzakuje linię zdefiniowaną przez a^x + b^x = c^x. Zaczynamy od a=ci b=1. Oczywiście stawia nas to po złej stronie linii, ponieważ c^x + 1 > c^x. Zmniejszamy się, adopóki nie przekroczymy linii. Kiedy znajdujemy się poniżej linii, zwiększamy, bdopóki nie przekroczymy jej w innym kierunku. Powtarzaj, aż bspotyka a, pamiętając najlepsze rozwiązanie w Aa Bjak idziemy. Następnie wydrukuj.

pjest prostą rekurencyjną implementacją a^x(for x>0), ponieważ C nie zapewnia operatora potęgowania.

W pseudokodzie: 

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

Ograniczenia

c^xmuszą być reprezentowalne w zakresie int. Jeśli to ograniczenie jest zbyt wąska, podpis pmoże być trywialny zmodyfikowany long p(long,int)i double p(double,int)i mi Mna longlub doubleodpowiednio, bez modyfikacji f().

Program testowy

To akceptuje ci xjako argumenty wiersza polecenia, a następnie drukuje wynik.

#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;
}
Toby Speight
źródło
1

Haskell, 120 bajtów

Myślę, że grałem w golfa tak bardzo, jak potrafię:

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

Nie golfowany:

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]

Stosowanie:

Prelude> 30 % 11
"28^30 + 28^30 < 30^30"
CR Drost
źródło
0

Haskell, 132 128 bajtów

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]

Przykład użycia: 7 # 3zwraca ciąg "6^3 + 5^3 < 7^3".

nimi
źródło
0

Perl 5, 119 bajtów

Podprogram:

{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]}

Użyj jako np .:

print sub{...}->(8,3)
msh210
źródło
0

Rubin, 125 bajtów

Funkcja anonimowa. Tworzy listę awartości, używa jej do konstruowania a,bpar, a następnie znajduje maksimum dla tych, które pasują do kryteriów, i zwraca stamtąd ciąg.

->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}"}
Wartość tuszu
źródło