f (g (x)) nimmt ab, während g (f (x)) zunimmt

42

Für diese Herausforderung müssen Sie zwei Funktionen, f und g , in die Ganzzahlen implementieren , sodass f f g eine streng abnehmende Funktion ist, während g ∘ f eine streng zunehmende Funktion ist. Mit anderen Worten, wenn Sie zwei ganze Zahlen a <b nehmen , dann gilt f (g (a))> f (g (b)) und g (f (a)) <g (f (b)) . Es gibt keine Einschränkungen für f und g , außer dass sie jeweils eine ganze Zahl einer anderen ganzen Zahl zuordnen müssen.

Bitte geben Sie eine kurze Beschreibung von f und g sowie ein Argument an, warum sie die erforderliche Eigenschaft haben.

Kredit: Diese Herausforderung wurde durch ein Problem im rumänischen Master of Mathematics-Wettbewerb 2011 inspiriert (bei dem das Gleiche gefragt wird, aber die reellen Zahlen anstelle von ganzen Zahlen). Wenn Sie wirklich Spoiler wollen, wissen Sie jetzt, wonach Sie suchen müssen.

Regeln

  • Das Wort "Funktion" in dieser Herausforderung sollte im mathematischen Sinne der Abbildung einer Ganzzahl auf eine andere verstanden werden: Sie können entweder zwei Programme oder zwei Funktionen schreiben und wie üblich eine der Standardmethoden zum Empfangen von Eingaben und zum Bereitstellen von Ausgaben verwenden. Sie können Zeichenfolgendarstellungen von Ganzzahlen anstelle von tatsächlichen Ganzzahlvariablen verwenden, die Eingabe- und Ausgabetypen sollten jedoch identisch sein, damit die Funktionen zusammengesetzt werden können, ohne dass Typen dazwischen manuell konvertiert werden müssen. Denken Sie daran, dass f und g konzeptionell immer noch Funktionen für ℤ sein müssen, sodass Sie nicht schummeln können, wenn Sie zwei verschiedene Zeichenfolgendarstellungen mit derselben Nummer oder Ähnlichem verwenden.

  • Denken Sie daran, dass Funktionen möglicherweise nicht benannt sind , solange ihr Name nicht von sich aus oder von einer anderen von Ihnen definierten Funktion benötigt wird. Wenn Sie eine oder beide Funktionen benennen, können Sie davon ausgehen, dass sie im selben Programm vorhanden sind, sodass sie in ihrer Implementierung aufeinander verweisen können (z def f(x): return -g(x). B. in Python).

  • Es gelten die üblichen Überlaufregeln für Ganzzahlen: Ihre Lösung muss in der Lage sein, für beliebig große Ganzzahlen in einer hypothetischen (oder möglicherweise realen) Version Ihrer Sprache zu arbeiten, in der standardmäßig alle Ganzzahlen unbegrenzt sind, Ihr Programm jedoch aufgrund der Implementierung in der Praxis fehlschlägt Ganzzahlen, die so groß sind, werden nicht unterstützt, was die Lösung nicht ungültig macht.

  • Sie können jede Programmiersprache verwenden , beachten Sie jedoch, dass diese Lücken standardmäßig verboten sind.

  • Dies ist , also ist Ihre Punktzahl die Summe der Anzahl der Bytes beider Funktionen und der kürzesten gültigen Antwortgewinne.

Martin Ender
quelle
Dürfen die Funktionen einen String zurückgeben?
Matthew Roh
@SIGSEGV Ich würde ja sagen, aber nur, wenn sie auch eine Zeichenfolge als Eingabe verwenden, sodass sie zusammengesetzt werden können, ohne dass eine Typkonvertierung eingefügt werden muss.
Martin Ender
Oh, verdammt, ich habe versucht, in einen String zu konvertieren, damit die andere Funktion die Ergebnisse nicht weiter bearbeiten kann.
Matthew Roh
1
@Fatalize Richtig. Jedes muss eine Funktion vom Typ ℤ → ℤ sein.
Martin Ender
1
@ Bijan sowohl positiv als auch negativ.
Martin Ender

Antworten:

18

Python, 68 Zeichen

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 ordnet negative Zahlen ungeraden Zahlen und positive Zahlen geraden Zahlen und gerade Zahlen positiven Zahlen und ungeraden Zahlen negativen Zahlen zu, wobei die Ausgabegröße streng mit der Eingabegröße zunimmt.

g macht dasselbe, außer dass es negative Zahlen auf gerade Zahlen und positive Zahlen auf ungerade Zahlen abbildet.

f ∘ g bildet negativ → gerade → positiv und positiv → ungerade → negativ ab.
g ∘ f bildet negativ → ungerade → negativ und positiv → gerade → positiv ab.

Daher haben f und g die gewünschten Eigenschaften.

user1502040
quelle
2
fund gkönnen unbenannte Funktionen sein, sodass Sie vier Bytes löschen können.
Martin Ender
Sie können (1-x%2*2)als Variable definieren , um einige Bytes zu sparen.
OldBunny2800
Hier ist ein vollständiger Code zum Spielen. 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(); Sie können ihn ;zur besseren Lesbarkeit durch Zeilenvorschübe ersetzen .
Stéphane Gourichon
16

Python , 40 Bytes

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

Probieren Sie es online! Einige Ausgaben sind Floats mit gleichen ganzen Zahlen, weil sie beispielsweise (-1)**(-3)ein Float ergeben.

Basierend auf Ideen von Peter Taylor . Die Funktion fnegiert ungerade Zahlen und lässt gerade unverändert. Die Funktion gmacht dasselbe und wendet dann die monotone Paritätsumschaltkarte an x -> 3*x + 1.

Seitdem f(f(x)) = xhaben wir g(f(x)) = 3*f(f(x))+1 = 3*x+1zugenommen.

Denn f(g(x)) = f(3*f(x)+1)die Idee ist, dass genau eines der inneren und äußeren fKippzeichen, wodurch es abnimmt.

  • Für gerade x, f(x) = xaber f(3*x+1) = -3*x-1da 3*x+1ist seltsam.
  • Für ungerade x, f(x) = -xund f(-3*x+1) = -3*x+1weil gerade -3*x+1ist.

Wir brauchen jetzt nur noch die geraden und ungeraden Eingaben, die sich in abnehmender Weise verschachteln, was gilt, weil -3*x±1sich die Verschachtelung verringert, unabhängig davon, wie die Vorzeichen gewählt werden. Deshalb wird das 3*benötigt.

Ein Haskell-Port hat 25 Bytes:

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

Probieren Sie es online!

xnor
quelle
In Haskell (^)ist Integer-Exponentiation.
user1502040
1
@ user1502040 Negative Exponenten können nicht verarbeitet werden.
Xnor
1
Da Sie sich nicht gselbst anrufen, können Sie zwei Bytes sparen, indem Sie die Bezeichnung aufheben.
Martin Ender
14

CJam (17 Bytes)

Funktion f (benannt, Fweil CJam nur Namen in Großbuchstaben zulässt):

{W1$2b,#*}:F

Funktion g (anonym):

{F2*}

Online-Demo

Dies spart ein Byte, indem auf ein Implementierungsdetail von CJam zurückgegriffen wird, bei dem es sich wahrscheinlich um einen Fehler handelt: Bei der Ausführung von Basiskonvertierungen wird der absolute Wert verwendet. 2b,gibt also die Anzahl der Bits im Absolutwert seines Arguments an, also negiert f genau die Zahlen, deren Absolutwert eine ungerade Anzahl von Bits hat. g wendet f an und verdoppelt sich dann (Ändern der Parität der Anzahl von Bits).

Wenn Sie also f und dann g anwenden, bleibt das Vorzeichen unverändert und verdoppelt xsich 2x. Durch Anwenden von g und dann f wird das Vorzeichen genau einmal geändert und verdoppelt, wobei eine Zuordnung xzu erfolgt -2x.

Peter Taylor
quelle
Schön, das ist genau die Referenzlösung, die der Wettbewerb hergibt. (Ich nehme an, Sie haben es sich selbst ausgedacht?)
Martin Ender
@MartinEnder, ich habe dieses Problem schon einmal gesehen. Möglicherweise auf math.SE.
Peter Taylor
2

Pyth, 34 Bytes

Dies ist nur eine direkte Übersetzung meiner Python-Antwort.

*-1*2%Q2+*2*QQ<Q0
*-1*2%Q2+*2*QQ>Q0
user1502040
quelle