Mówi się, że funkcja ma cykl długości n, jeśli istnieje w jej domenie x taki, że f ⁿ (x) = x i f ^m (x) ≠ x dla 0 <m <n , gdzie indeks górny n oznacza n - złóż aplikację f . Zauważ, że cykl o długości 1 jest stałym punktem f (x) = x .

Twoim zadaniem jest zaimplementowanie funkcji bijectywnej od liczb całkowitych do siebie, która ma dokładnie jeden cykl o każdej długości dodatniej n . Funkcja bijectywna to korespondencja jeden do jednego, tzn. Każda liczba całkowita odwzorowana na dokładnie jeden raz. Posiadanie dokładnie jednego cyklu długości n oznacza, że ​​istnieją dokładnie n różnych liczb x, dla których f ⁿ (x) = x i f ^m (x) ≠ x dla 0 <m <n .

Oto przykład, jak mogłaby wyglądać taka funkcja około x = 0 :

x     ... -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7 ...
f(x)  ...  2  4  6 -3 -1  1 -4  0 -2  5  7 -7 -6  3 -5 ...

Ten fragment zawiera cykle o długości od 1 do 5 :

n   cycle
1    0
2   -2  1
3   -4 -3 -1
4   -5  6  3  7
5   -7  2  5 -6  4
...

Zauważ, że powyżej używam „funkcji” tylko w sensie matematycznym. Możesz napisać funkcję lub pełny program w wybranym przez siebie języku, pod warunkiem, że pobiera on jedną (całkowitą) liczbę całkowitą jako wejście i zwraca jedną (całkowitą) liczbę całkowitą. Jak zwykle możesz przyjmować dane wejściowe za pośrednictwem STDIN, argument wiersza poleceń, argument funkcji itp. I dane wyjściowe za pomocą STDOUT, wartości zwracanej funkcji lub argumentu funkcji (wyjściowej) itp.

Oczywiście wiele języków nie obsługuje (łatwo) liczb całkowitych o dowolnej precyzji. W porządku, jeśli twoja implementacja działa tylko w zakresie rodzimego typu liczb całkowitych twojego języka, o ile obejmuje on co najmniej zakres [-127, 127] i działałby dla dowolnych liczb całkowitych, gdyby typ liczb całkowitych języka został zastąpiony przez dowolne- precyzyjne liczby całkowite.

Obowiązują standardowe zasady gry w golfa .

Pyth, 27 18 bajtów

_h?gQ0^2Q*.5@,Q-xh

Objaśnienie (Pyth inicjuje Qsię na wejściową liczbę całkowitą):

_                       negative of (
                          (
  ?gQ0                      if Q >= 0:
      ^2Q                     2**Q
                            else:
         *.5                  half of
            @        Q          element Q (modulo list length) in
             ,                    the two element list [
              Q                     Q,
                 hQ                 ((Q plus 1)
                x  Q                 XOR Q)
               -    Q               minus Q
                                  ]
 h                        ) plus 1
                        )

To ma cykle

(−1)
(0, −2)
(1, −3, −4)
(2, −5, −7, −6)
(3, −9, −13, −11, −8)
(4, - 17, -25, -21, -15, -10)
(5, -33, -49, -41, -29, -19, -12)
(6, -65, -97, -81, -57, -37, -23, -14)
(7, -129, -193, -161, -113, -73, -45, -27, -16)
(8, -257, -385, -321, -225 , −145, −89, −53, −31, −18)
(9, −513, −769, −641, −449, −289, −177, −105, −61, −35, −20)
⋮

Cykl długości n jest określony przez

( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1, 22
^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
-2 ^ 1⋅ (2 · n - 5) - 1,
-2 ^ 0⋅ (2 · n - 3) - 1).

Każda liczba całkowita k ≥ -1 pojawia się jako pierwszy element cyklu ( k + 2). Dla każdej liczby całkowitej k <−1 możemy jednoznacznie zapisać 1 - k = 2 ^ i ⋅ (2⋅ j + 1) dla niektórych i , j ≥ 0; wtedy k pojawia się jako ( j + 2) element elementu ( i + j + 2) -cykl.

MATL , 47 bajtów

E|G0<-QXJ:tQ*2/0hStJ<f0))Q2MQ)&:J6M-)2/ttk>Eq*k

Wypróbuj online!

Ogólne wyjaśnienie

Funkcja 2 poniżej jest taka sama, jak użyta w odpowiedzi @ Sp3000 na powiązane wyzwanie. Dzięki @ Agawa001 za zauważenie.

Funkcja składa się z trzech:

1. Bijection od Z (liczby całkowite) do N (naturals).
2. Bijection od N do N o pożądanej charakterystyce (jeden cykl każdej długości).
3. Odwrotna funkcja 1.

Funkcje 1 i 3 są używane, ponieważ jest to łatwiejsze (chyba) w celu uzyskania pożądanego zachowania w N , niż w Z. .

Funkcja 2 wygląda następująco: górna linia to domena, dolna linia to domena kodowa. Przecinki są używane dla przejrzystości:

1,  2  3,  4  5  6,  7  8  9  10  ...
1,  3  2,  6  4  5, 10  7  8   9  ...

Pierwszy blok (od górnej 1do dolnej 1) to cykl o długości 1. Drugi (od 2 3do 3 2) to cykl o długości 2 itd. W każdym bloku dolna część (obraz funkcji) jest górnie przesunięta kołowo jeden krok w prawo.

Funkcja 1 wygląda następująco:

 -5  -4  -3  -2  -1   0  +1  +2  +3  +4  ...
+10  +8  +6  +4  +2  +1  +3  +5  +7  +9  ...

Funkcja 3 jest taka sama jak 1 z zamienionymi dwoma liniami.

Przykłady

Obraz 3jest -5. Pierwszy 3jest mapowany 7przez funkcję 1; następnie 7jest mapowany 10przez funkcję 2; następnie 10jest mapowany na -5` przez funkcję 3.

Cykl długości 1 wynosi 0. Cykl długości 2 wynosi -1 1. Cykl długości 3 wynosi -3 2 -2itp.

Kod wyjaśniony

Funkcje 1 i 3 są proste.

Funkcja 2 polega na znalezieniu dolnego punktu końcowego odpowiedniego bloku wejściowego. Na przykład, jeśli dane wejściowe do tej funkcji 9znajdują się 7(patrz bloki powyżej). Następnie wybiera górny punkt końcowy, który znajduje się 10w przykładzie. Okrągłe przesunięcie bloku uzyskuje się dzięki modułowej indeksacji MATL 1.

         % FUNCTION 1
         % Implicit input
E|       % Multiply by two. Absolute value
G0<      % 1 if input is negative, 0 otherwise
-        % Subtract
Q        % Add 1
XJ       % Copy to clipboard J. Used as input to the next function

         % FUNCTION 2
:        % Range [1 2 ... J], where J denotes the input to this function
tQ*      % Duplicate, increment by 1, multiply
2/       % Divide by 2
0hS      % Prepend a 0. This is needed in case J is 0
tJ<f     % Duplicate. Find indices that are less than the input J
0)       % Pick the last index.
)        % Apply as index to obtain input value that ends previous block
Q        % Add 1: start of current block
2M       % Push the two arguments to second-to-last function call
Q)       % Add 1 and use as index: end of current block
&:       % Inclusive binary range: generate input block 
J        % Push J (input to function 2)
6M-      % Subtract start of block
)        % Apply as index (1-based, modular). This realizes the shifting

         % FUNCTION 3
2/       % Divide by 2
ttk>     % Duplicate. 1 if decimal part is not 0; 0 otherwise
Eq       % Multiply by 2, add 1
*        % Multiply
k        % Round down
         % Implicit display

Python 2, 55 bajtów

g=lambda n,k=1:n/k and~g(~n+k*(n>0),k+1)+k*(n>0)or-~n%k

59 bajtów:

g=lambda n,k=1:n<0and~g(~n,2)or n/k and k+g(n-k,k+2)or-~n%k

Tworzy cykle

[0]
[-1, -2]
[1, 2, 3]
[-3, -4, -5, -6]
[4, 5, 6, 7, 8]
...

Zmodyfikowano z mojego rozwiązania z wcześniejszego wyzwania , które jest zmodyfikowane z konstrukcji Sp3000 .

Funkcja

g=lambda n,k=1:n/k and k+g(n-k,k+2)or-~n%k

tworzy cykle nieparzystych liczb nieujemnych

[0]
[1, 2, 3]
[4, 5, 6, 7, 8]
...

Aby znaleźć prawidłowy rozmiar cyklu k, nprzesuń wejście w dół o, k=1,3,5,7,...aż wynik znajdzie się w przedziale [0,k). Cykl ten należy n->(n+1)%kwykonać z operacją , a następnie cofnąć wszystkie odejmowania wykonane na danych wejściowych. Jest to realizowane rekurencyjnie przez k+g(n-k,k+2).

Teraz potrzebujemy ujemnego, aby wykonać parzyste cykle. Zauważ, że jeśli będziemy modyfikować gzacząć k=2IN g, chcielibyśmy dostać nawet cykle-size

[0, 1]
[2, 3, 4, 5]
[6, 7, 8, 9, 10, 11]
...

Te biject do negatywów poprzez bit-dopełniacz ~. Kiedy więc njest negatywna, po prostu oceniamy g(n)jako ~g(~n,2).

Python 3, 110 bajtów

Nadal nie wymyśliłem, jak uzyskać tam lambdę

jeśli n jest liczbą trójkątów [1,3,6,10,15,21,28 itd.], to f (n) jest porządkiem na liście pomnożonym przez jeden ujemny. jeśli liczba jest ujemna, daj jej 1 + kolejny najmniejszy numer trójkąta. w przeciwnym razie przyrost.

Przykład: 5 nie jest liczbą trójkątów, więc dodaj 1.

Następna iteracja, mamy 6. 6 jest liczbą trójkątów, i jest 3 na liście, więc wychodzi -3.

Program podaje te listy

długość 1: [0]

długość 2: [1, -1]

długość 3: [2,3, -2]

długość 4: [4,5,6, -3]

długość 5: [7,8,9,10, -4]

x=int(input())
if x<0:print((x**2+x)/2+1)
else:
 a=((8*x+1)**.5-1)/2
 if a%1:print(x+1)
 else:print(-a)

Edycja: Jeszcze raz dziękuję @TuukkaX za usunięcie nadmiaru znaków.

Python 3, 146 bajtów

Dla każdej liczby większej niż 0 istnieją parzyste pętle (len 2,4,6,8 ...), a mniej niż 0, nieparzyste pętle (1,3,5,7). 0 odwzorowuje na 0.

(-3, -2, -1), (0), (1,2), (3,4,5,6)

mapy do

(-2, -1, -3), (0), (2,1), (6,3,4,5)

f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5)
x=int(input());n=f(x)
if x>0:b=n*(n-2)/4
else:b=-((n+1)/2)**2
print(b+1+(x-b-2)%n)

Edycja: @TuukkaX zdjął 8 bajtów z poprzedniego rozwiązania. I kolejne 3.

Matlab (423)

function u=f(n),if(~n)u=n;else,x=abs(n);y=factor(x);for o=1:nnz(y),e=prod(nchoosek(y,o)',1);a=log(x)./log(e);b=find(a-fix(a)<exp(-9),1);if ~isempty(b),k=e(b);l=fix(a(b));break;end;end,if(abs(n)==1)k=2;l=0;end,if(k==2)l=l+1;x=x*2;end,e=dec2base(l,k)-48;o=xor(e,circshift(e,[0 1]));g=~o(end);if(~o|nnz(o==1)~=numel(e)-g),u=n*k;else,if((-1)^g==sign(n)),u=sign(n)*k^(base2dec([e(2:end-1) 1]+48,k)-(k==2));else,u=n*k;end,end,end

• Niekonkurencyjny, ponieważ bije dobry rekord bycia kondominium do ostatniego rankingu, podczas gdy staram się skrócić go tak bardzo, jak to możliwe.

• Kilka bezsensownych błędów dotyczących dokładności w matlabie, których nie mogłem znaleźć, poza tym, że mój kod jest saratystycznie duży, z drugiej strony mapowanie, które wybrałem, dotyczyło głównych elementów i logarytmu n-ary.

Wykonanie

 f(2)

 1

 f(1)

 2

 f(-2)

 -4

 f(-4)

 -8

 f(-8)

 -1

 f(0)

 0



 ----------------------------

Wyjaśnienie

• Knonwing, po pierwsze, że dowolna liczba może być zapisana jako iloczyn wykładników liczb pierwszych N=e1^x1*e2^x2...z tej bazy, postanowiłem zmapować obrazy cykli, Cktóre są wydobywane z największego wykładnika najmniejszego czynnika (niekoniecznie liczby pierwszej), że N jest doskonałą potęgą .

• prościej, niech N=P^xgdzie P jest najmniejszym idealnym pierwiastkiem, xoznacza dokładnie dwa podstawowe terminy dla cyklu: x=Ʃ(r*P^i)termin Pjest podstawą cyklu, a także doskonałym pierwiastkiem dla liczby głównej N, i kjest stopniem cyklu C=p^k, gdzie izmienia się między 1 i k, współczynnik rjest zwiększany o 1 i ograniczony przez P-1 dla dowolnego następnego obrazu wstępnego, dopóki wszystkie współczynniki nie zostaną ustawione na r = 1, więc przechodzimy do początku tego cyklu.

• Aby uniknąć kolizji między cyklami, wybór potęgowania liczb pierwszych zamiast ich iloczynu jest dokładny, ponieważ jako przykład dwóch cykli zasad 3i 2miejsca spotkania między nimi można 3*2uniknąć, dlatego unika się tego, ponieważ cykl jest definiowany na podstawie stopnia większego niż jego podstawa, a dla punktu spotkania jest kolejny cykl podstawy 6i stopień 1.

• Liczby ujemne stanowią wyjątek, ponieważ zarezerwowałem nieparzyste stopnie dla liczb ujemnych, a nawet stopnie dla pozostałych. Jak to ?

  dla dowolnej liczby N osadzonej w cyklu P^kzapisuje się jako P^(a0*P^i0+a1*P^i1+...), że ilość (a0*P^i0+a1*P^i1+...)jest przekształcana w zasadę P-ary jako a0,a1,...., aby wyjaśnić ten punkt, jeśli (p = 2) sekwencja musi być w bazie binarnej. Jak wiadomo przede wszystkim bez ustawiania warunku stopni dodatnich / ujemnych i wyjątku (+/- 1), liczba N znajduje się na krawędziach stopnia k, tylko wtedy, gdy sekwencja Ajest zapisana jako 1111..{k+1}..10lub 111..{k}..1dla wszystkich zasad, w przeciwnym razie obrót nie jest potrzebny, więc przypisanie warunku ujemnego / dodatniego dla odpowiednich stopni nieparzystych / parzystych k/k'dla obu tworzy nieparzystą sekwencję zapisaną w formularzu 101..{k}..100, parzysta sekwencja jest zapisana w formularzu 101..{k'}..10dla początkowej krawędzi odpowiednio ujemnego / dodatniego cyklu liczbowego .

  Przykład:

  Biorąc liczbę N=2^10, x=10=2^1+2^3sekwencja A jest zapisywana A=1010, ten typ sekwencji objawia skończoną krawędź dodatniego cyklu liczbowego, co oznacza C=2^3, że następny obraz to krawędź początkowa, A=011która jest 8, Ale poprzez standaryzację tego wyniku na (+ / -) 1 wyjątek 2^10/2odwzorowuje na 8/2i poprzedni obraz nie może być obracany.

  Biorąc liczbę N=-3^9, x=9=3^2sekwencja A jest zapisywana A=100, ten typ sekwencji symbolizuje skończoną krawędź ujemnego cyklu liczbowego, co jest C=3^1, więc następnym obrazem jest krawędź początkowa, A=01która jest 3, Ale poprzez dostosowanie tego wyniku do ujemnej / dodatniej -3^9mapy warunków do -3.

• dla pary (-/+)1przewidywałem , że będę wtrącał się do niej w ramach liczby zasad cyklu 2, pod przykrywką, że zwykła sekwencja grup cyklicznych {2,4}{8,16,32,64}..składa się w innej formie {1,2}{4,8,16,32}.., co zapobiega utracie poprzednich elementów, a wykonana operacja zmienia się z trzaskiem nowy element w.

Wyniki:

uruchomienie tego małego arkusza kodu w celu zweryfikowania pierwszych rozsądnych zakresów liczb cyklicznych:

for (i=1:6) 
index=1;if(max(factor(i))>=5) index=0;end
for ind=0:index
j=f(((-1)^ind)*i); while(((-1)^ind)*i~=j)fprintf('%d ',j);j=f(j);end,fprintf('%d \n',(-1)^ind*i),pause,end,
end

To prowadzi do tych wyników

 2 1 
 -2 -4 -8 -1 
 1 2 
 -4 -8 -1 -2 
 9 27 3 
 -9 -27 -81 -243 -729 -2187 -6561 -19683 -3 
 8 16 32 64 128 256 512 4 
 -8 -1 -2 -4 
 25 125 625 3125 5 
 36 216 1296 7776 46656 6 
 -36 -216 -1296 -7776 -46656 -279936 -1679616 -10077696 -60466176 -362797056 -2.176782e+009 -1.306069e+010 ??? Error using ==> factor at 27

Ostatni to błąd segmentacji, ale pasuje do [-127,127] standardowego zakresu liczb całkowitych ze znakiem.

JavaScript (ES6), 73 bajty

f=(n,i=0,j=0,k=0,l=1,m=i<0?-i:~i)=>n-i?f(n,m,k++?j:i,k%=l,l+!k):++k-l?m:j

Działa poprzez wyliczenie sekwencji (0, -1, 1, -2, 2, -3, 3, ...), aż znajdzie n, zliczając cykle w miarę upływu czasu. izawiera bieżący wpis; jzawiera początek bieżącego cyklu, kindeks w cyklu, ldługość bieżącego cyklu i mnastępny wpis w sekwencji. Gdy się dowiemy n, bierzemy, jczy jesteśmy pod koniec cyklu, mczy nie.