f (g (x)) maleje, podczas gdy g (f (x)) wzrasta


42

Aby sprostać temu wyzwaniu, musisz zaimplementować dwie liczby f i g na liczbach całkowitych, tak że f ∘ g jest funkcją ściśle malejącą, podczas gdy g ∘ f jest funkcją ściśle rosnącą. Innymi słowy, jeśli podejmują wszelkie dwóch liczb całkowitych a <b , to f (g (a))> f (g (b)) i g (f (a)) <g (f (b)) . Nie ma ograniczeń dotyczących f i g indywidualnie, z wyjątkiem tego, że muszą one mapować jedną liczbę całkowitą na inną liczbę całkowitą.

Podaj krótki opis f i g oraz argument, dlaczego mają wymaganą właściwość.

Kredyt: To wyzwanie zostało zainspirowane problemem w rumuńskim konkursie Master of Mathematics 2011 (który pyta o to samo, ale o liczby rzeczywiste zamiast liczb całkowitych). Jeśli naprawdę chcesz spoilerów, teraz wiesz, czego szukać.

Zasady

  • Słowo „funkcja” w tym wyzwaniu należy rozumieć matematycznie, odwzorowując jedną liczbę całkowitą na drugą: możesz albo napisać dwa programy lub dwie funkcje i użyć dowolnej ze standardowych metod odbierania danych wejściowych i dostarczania danych wyjściowych, jak zwykle. Możesz użyć ciągów reprezentujących liczby całkowite zamiast rzeczywistych zmiennych całkowitych, ale typy danych wejściowych i wyjściowych powinny być identyczne, aby funkcje można było komponować bez ręcznej konwersji typów pomiędzy nimi. Pamiętaj, że koncepcyjnie, f i g nadal muszą być funkcjami na ℤ, więc nie możesz oszukiwać, używając dwóch różnych reprezentacji ciągów o tej samej liczbie lub czegoś podobnego.

  • Pamiętaj, że funkcje mogą być nienazwane , o ile ich nazwa nie jest potrzebna sama lub inna funkcja, którą zdefiniujesz. Jeśli nazwiesz jedną lub obie funkcje, możesz założyć, że istnieją one w tym samym programie, aby mogły się nawzajem odwoływać w swojej implementacji (np. def f(x): return -g(x)W Pythonie).

  • Obowiązują zwykłe reguły przepełnienia liczb całkowitych: twoje rozwiązanie musi być w stanie pracować dla dowolnie dużych liczb całkowitych w hipotetycznej (lub być może rzeczywistej) wersji twojego języka, w której wszystkie liczby całkowite są domyślnie nieograniczone, ale jeśli twój program zawiedzie w praktyce z powodu implementacji brak obsługi liczb całkowitych tak dużych, co nie unieważnia rozwiązania.

  • Możesz używać dowolnego języka programowania , ale pamiętaj, że te luki są domyślnie zabronione.

  • To jest , więc twój wynik jest sumą liczby bajtów obu funkcji i wygrywa najkrótsza poprawna odpowiedź.


Czy funkcje mogą zwracać ciąg znaków?
Matthew Roh

@SIGSEGV Powiedziałbym „tak”, ale tylko wtedy, gdy przyjmują one również ciąg znaków jako dane wejściowe, dzięki czemu można je komponować bez konieczności wstawiania jakiejkolwiek konwersji typu.
Martin Ender,

Aww darnit, próbowałem konwersji na ciąg znaków, aby inna funkcja nie mogła dalej edytować wyników.
Matthew Roh,

1
@Fatalize Correct. Każda musi być funkcją typu ℤ → ℤ.
Martin Ender,

1
@Bijan zarówno pozytywne, jak i negatywne.
Martin Ender,

Odpowiedzi:


18

Python, 68 znaków

f=lambda x:(1-x%2*2)*(2*x*x+(x<0))
g=lambda x:(1-x%2*2)*(2*x*x+(x>0))

f odwzorowuje liczby ujemne na liczby nieparzyste i liczby dodatnie na liczby parzyste, a liczby parzyste na liczby dodatnie i liczby nieparzyste na liczby ujemne, przy czym wielkość wyjściowa rośnie ściśle wraz z wielkością wejściową.

g robi to samo, z tym że odwzorowuje liczby ujemne na liczby parzyste i liczby dodatnie na liczby nieparzyste.

f ∘ g mapy ujemne → parzyste → dodatnie i dodatnie → nieparzyste → negatywne.
g ∘ f mapy ujemne → nieparzyste → negatywne i dodatnie → parzyste → pozytywne.

Dlatego f i g mają pożądane właściwości.


2
fi gmogą być funkcjami nienazwanymi, więc możesz upuścić cztery bajty.
Martin Ender,

Możesz zdefiniować (1-x%2*2)jako zmienną, aby zapisać kilka bajtów.
OldBunny2800 10.04.17

Oto kompletny kod do zabawy import numpy as np; import matplotlib.pyplot as plt; xrange=np.arange(-3,4); f=lambda x:(1-x%2*2)*(2*x*x+(x<0)); g=lambda x:(1-x%2*2)*(2*x*x+(x>0)); plt.plot(xrange, map(f, xrange), 'ro'); plt.plot(xrange, map(g, xrange), 'go'); plt.plot(xrange, map(f, map(g, xrange)), 'b--'); plt.plot(xrange, map(g, map(f, xrange)), 'y--'); plt.show(); Możesz zastąpić ;go liniami dla czytelności.
Stéphane Gourichon

16

Python , 40 bajtów

f=lambda x:x*(-1)**x
g=lambda x:3*f(x)+1

Wypróbuj online! Niektóre dane wyjściowe są (-1)**(-3)zmiennoprzecinkowe, które są równe liczbom całkowitym, ponieważ dają na przykład zmiennoprzecinkowe.

Na podstawie pomysłów Petera Taylora . Funkcja fneguje liczby nieparzyste i pozostawia parzyste bez zmian. Funkcja grobi to samo, a następnie stosuje monotoniczną mapę z przełączaniem parzystości x -> 3*x + 1.

Od f(f(x)) = xtego czasu g(f(x)) = 3*f(f(x))+1 = 3*x+1rośnie.

Na f(g(x)) = f(3*f(x)+1)pomysł, że dokładnie jedna wewnętrzna i zewnętrzna fodwraca znak, dzięki czemu maleje.

  • Na parzyste x, f(x) = xale f(3*x+1) = -3*x-1dlatego , że 3*x+1jest dziwne.
  • Dla nieparzystych x, f(x) = -xa f(-3*x+1) = -3*x+1ponieważ -3*x+1jest parzysty.

Teraz potrzebujemy tylko parzystych i nieparzystych danych wejściowych przeplatanych w sposób malejący, co utrzymuje się, ponieważ -3*x±1zmniejsza się niezależnie od wyboru znaków. Dlatego 3*jest potrzebny.

Port Haskell ma 25 bajtów:

f x=x*(-1)**x
g x=1+3*f x

Wypróbuj online!


W Haskell (^)jest wykładnikiem liczb całkowitych.
user1502040 7.04.17

1
@ user1502040 Nie radzi sobie z wykładnikami ujemnymi.
xnor

1
Ponieważ nie nazywasz się gsobą, możesz zaoszczędzić dwa bajty, czyniąc go bezimiennym.
Martin Ender,

14

CJam (17 bajtów)

Funkcja f (nazwana, Fponieważ CJam dopuszcza tylko nazwy pisane dużymi literami):

{W1$2b,#*}:F

Funkcja g (anonimowa):

{F2*}

Demo online

Oszczędza to bajt, opierając się na szczegółach implementacji CJam, co jest prawdopodobnie błędem: podczas wykonywania podstawowych konwersji używa wartości bezwzględnej. 2b,dlatego podaje liczbę bitów w wartości bezwzględnej argumentu, więc f neguje dokładnie te liczby, których wartość bezwzględna ma nieparzystą liczbę bitów. g stosuje f, a następnie podwaja (zmieniając parzystość liczby bitów).

Zatem zastosowanie znaku f, a następnie g pozostawia znak niezmieniony i podwaja się, odwzorowując xna 2x. Zastosowanie g, a następnie f zmienia znak dokładnie raz i podwaja się, odwzorowując xna -2x.


Fajnie, to jest dokładnie rozwiązanie referencyjne podane w konkursie, z którego pochodzi. (Zakładam, że sam to wymyśliłeś?)
Martin Ender

@MartinEnder, widziałem już kiedyś ten problem. Prawdopodobnie na matematyce.
Peter Taylor,

2

Pyth, 34 bajtów

To jest tylko bezpośrednie tłumaczenie mojej odpowiedzi w języku Python.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.