Die Herausforderung

Schreiben Sie eine Funktion, die zwei positive ganze Zahlen n und k als Argumente verwendet und die Nummer der letzten von n verbleibenden Person nach dem Auszählen jeder k- ten Person zurückgibt .

Dies ist eine Code-Golf-Herausforderung, also gewinnt der kürzeste Code.

Das Problem

n Personen (nummeriert von 1 bis n ) stehen in einem Kreis und jedes k- te wird ausgezählt, bis eine einzelne Person übrig bleibt (siehe den entsprechenden Wikipedia-Artikel ). Bestimmen Sie die Nummer dieser letzten Person.

ZB für k = 3 werden zwei Personen übersprungen und die dritte Person wird ausgezählt. Dh für n = 7 werden die Zahlen in der Reihenfolge 3 6 2 7 5 1 (im Detail 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 1 4 ) ausgezählt und die Antwort lautet somit 4 .

Beispiele

J(7,1) = 7      // people are counted out in order 1 2 3 4 5 6 [7]
J(7,2) = 7      // people are counted out in order 2 4 6 1 5 3 [7]
J(7,3) = 4      // see above
J(7,11) = 1
J(77,8) = 1
J(123,12) = 21

GolfScript, 17 Bytes

{{@+\)%}+\,*)}:f;

Nimmt n kden Stapel auf und belässt das Ergebnis auf dem Stapel.

Präparation

Dies verwendet die Wiederholung g(n,k) = (g(n-1,k) + k) % nmit g(1, k) = 0(wie im Wikipedia-Artikel beschrieben), wobei die Rekursion durch eine Falte ersetzt wird.

{          # Function declaration
           # Stack: n k
  {        # Stack: g(i-1,k) i-1 k
    @+\)%  # Stack: g(i,k)
  }+       # Add, giving stack: n {k block}
  \,*      # Fold {k block} over [0 1 ... n-1]
  )        # Increment to move from 0-based to 1-based indexing
}:f;

Minsky Register Machine (25 Non-Stop-Zustände)

Technisch gesehen keine Funktion, aber es handelt sich um ein Rechenparadigma, das per se keine Funktionen hat ...

Dies ist eine geringfügige Abweichung vom Haupttestfall meiner ersten MRM-Interpretationsaufgabe :

Eingabe in Register nund k; Ausgabe im Register r; Es wird davon ausgegangen, dass r=i=t=0bei der Einreise. Die ersten beiden Halt-Anweisungen sind Fehlerfälle.

Python, 36

Ich habe auch die Formel aus Wikipedia verwendet:

J=lambda n,k:n<2or(J(n-1,k)+k-1)%n+1

Beispiele:

>>> J(7,3)
4
>>> J(77,8)
1
>>> J(123,12)
21

Mathematica, 38 36 Bytes

Gleiche Wikipedia-Formel:

1~f~_=1
n_~f~k_:=Mod[f[n-1,k]+k,n,1]

C 40 Zeichen

Dies ist so ziemlich genau die Formel, die der oben verlinkte Wikipedia-Artikel angibt:

j(n,k){return n>1?(j(n-1,k)+k-1)%n+1:1;}

Hier ist eine Implementierung, die die Simulation ausführt (99 Zeichen):

j(n,k,c,i,r){char o[999];memset(o,1,n);for(c=k,i=0;r;++i)(c-=o[i%=n])||(o[i]=!r--,c=k);
return i;}

Gleichstrom, 27 Bytes

[d1-d1<glk+r%1+]dsg?1-skrxp

Verwendet die Wiederholung aus dem Wikipedia-Artikel. Erläuterung:

# comment shows what is on the stack and any other effect the instructions have
[   # n
d   # n, n
1-  # n-1, n
d   # n-1, n-1, n
1<g # g(n-1), n ; g is executed only if n > 1, conveniently g(1) = 1
lk+ # g(n-1)+(k-1), n; remember, k register holds k-1
r%  # g(n-1)+(k-1) mod n
1+  # (g(n-1)+(k-1) mod n)+1
]
dsg # code for g; code also stored in g
?   # read user input => k, n, code for g
1-  # k-1, n, code for g
sk  # n, code for g; k-1 stored in register k
r   # code for g, n
x   # g(n)
p   # prints g(n)

J, 45 Zeichen

j=.[:{.@{:]([:}.]|.~<:@[|~#@])^:(<:@#)>:@i.@[

Führt die Simulation aus.

Alternativ können Sie die Formel (31 Zeichen) verwenden:

j=.1:`(1+[|1-~]+<:@[$:])@.(1<[)

Ich hoffe Howard macht es nichts aus, dass ich das Eingabeformat leicht angepasst habe, um es einem dyadischen Verb in J anzupassen.

Verwendung:

   7 j 3
4
   123 j 12
21

GolfScript, 32 24 Bytes

:k;0:^;(,{))^k+\%:^;}/^)

Verwendung: Erwartet, dass sich die beiden Parameter n und k im Stapel befinden, und verlässt den Ausgabewert.

(Danke an Peter Taylor, der einen iterativen Ansatz und viele andere Tipps vorgeschlagen hat.)

Der alte (rekursive) Ansatz von 32 Zeichen:

{1$1>{1$(1$^1$(+2$%)}1if@@;;}:^;

Dies ist mein erstes GolfScript. Bitte teilen Sie mir Ihre Kritik mit.

R 48

J=function(n,k)ifelse(n<2,1,(J(n-1,k)+k-1)%%n+1)

Laufende Version mit Beispielen: http://ideone.com/i7wae

Groovy, 36 Bytes

def j(n,k){n>1?(j(n-1,k)+k-1)%n+1:1}

Haskell, 68

j n=q$cycle[0..n]
q l@(i:h:_)k|h/=i=q(drop(k-1)$filter(/=i)l)k|1>0=i

Führt die eigentliche Simulation durch. Demonstration:

GHCi> j 7 1
7
GHCi> j 7 2
7
GHCi> j 7 3
4
GHCi> j 7 11
1
GHCi> j 77 8
1
GHCi> j 123 12
21

Scala, 53 Bytes

def?(n:Int,k:Int):Int=if(n<2)1 else(?(n-1,k)+k-1)%n+1

C 88 Zeichen

Tut die Simulation, berechnet die Formel nicht.
Viel länger als die Formel, aber kürzer als die andere C-Simulation.

j(n,k){
    int i=0,c=k,r=n,*p=calloc(n,8);
    for(;p[i=i%n+1]||--c?1:--r?p[i]=c=k:0;);
    return i;
}

Anmerkungen:
1. Belegt den Speicher und gibt ihn niemals frei.
2. Ordnet n*8anstelle von zun*4 , weil ich benutze p[n]. Konnte zuordnen (n+1)*4, aber es ist mehr Zeichen.

C ++, 166 Bytes

Golf gespielt:

#include<iostream>
#include <list>
int j(int n,int k){if(n>1){return(j(n-1,k)+k-1)%n+1;}else{return 1;}}
int main(){intn,k;std::cin>>n>>k;std::cout<<j(n,k);return 0;}

Ungolfed:

#include<iostream>
#include <list>
int j(int n,int k){
    if (n > 1){
        return (j(n-1,k)+k-1)%n+1;
    } else {
        return 1;
    }
}
int main()
{
    int n, k;
    std::cin>>n>>k;
    std::cout<<j(n,k);
    return 0;
}

J, 8 Bytes

1&|.&.#:

       1&|.&.#: 10
    5

       1&|.&.#: 69
    11

        1&|.&.#: 123456
    115841

        1&|.&.#: 123245678901234567890x NB. x keeps input integral
    98917405212792722853

All credit to Roger Hui, co-inventor of J and all-round uber-genius
www.jsoftware.com for free j software across many platforms

Explanation
    (J works right-to-left)
     #:       convert input to binary
     &.       a&.b <=> perform b, perform a, perform reverse of b
     1&|.     rotate bitwise one bit left

So
    1&|.&.#: 10

    a. #:            convert input (10) TO binary -> 1 0 1 0
    b. 1&|.          rotate result 1 bit left -> 0 1 0 1
    c. due to the &. perform convert FROM binary -> 5 (answer)

Ruby, 39 Bytes

def J(n,k)
n<2?1:(J(n-1,k)+k-1)%n+1
end

Laufende Version mit Testfällen: http://ideone.com/pXOUc

Q, 34 Bytes

f:{$[x=1;1;1+mod[;x]f[x-1;y]+y-1]}

Verwendung:

q)f .'(7 1;7 2;7 3;7 11;77 8;123 12)
7 7 4 1 1 21

Ruby, 34 Bytes

J=->n,k{n<2?1:(J(n-1,k)+k-1)%n+1}

Haskell, 29

Verwendung der Formel aus Wikipedia.

1#_=1
n#k=mod((n-1)#k+k-1)n+1

JavaScript (ECMAScript 5), 48 Byte

ECMAScript 5 wurde verwendet, da dies die neueste Version von JavaScript war, als diese Frage gestellt wurde.

function f(a,b){return a<2?1:(f(a-1,b)+b-1)%a+1}

ES6-Version (nicht konkurrierend), 33 Byte

f=(a,b)=>a<2?1:(f(a-1,b)+b-1)%a+1

Erläuterung

Hier gibt es nicht viel zu sagen. Ich implementiere nur die Funktion, die mir der Wikipedia-Artikel gibt.

05AB1E , 11 Bytes

L[Dg#²<FÀ}¦

Probieren Sie es online!

L           # Range 1 .. n
 [Dg#       # Until the array has a length of 1:
     ²<F }  #   k - 1 times do:
        À   #     Rotate the array
          ¦ #   remove the first element

8. 82 Bytes

Code

: j >r >r a:new ( a:push ) 1 r> loop ( r@ n:+ swap n:mod ) 0 a:reduce n:1+ rdrop ;

SED (Stack Effect Diagram) ist:n k -- m

Verwendung und Erklärung

Der Algorithmus verwendet ein Array von Ganzzahlen wie folgt: Wenn der Personenwert 5 ist, ist das Array [1,2,3,4,5].

: j \ n k -- m
    >r                               \ save k
    >r a:new ( a:push ) 1 r> loop    \ make array[1:n]
    ( r@ n:+ swap n:mod ) 0 a:reduce \ translation of recursive formula with folding using an array with values ranging from 1 to n
    n:1+                             \ increment to move from 0-based to 1-based indexing
    rdrop                            \ clean r-stack
;

ok> 7 1 j . cr
7
ok> 7 2 j . cr
7
ok> 7 3 j . cr
4
ok> 7 11 j . cr
1
ok> 77 8 j . cr
1
ok> 123 12 j . cr
21

J , 24 Bytes

1+1{1([:|/\+)/@,.1|.!.0#

Probieren Sie es online!

Ein iterativer Ansatz, der auf der dynamischen Programmierlösung basiert.

Erläuterung

1+1{1([:|/\+)/@,.1|.!.0#  Input: n (LHS), k (RHS)
                       #  Make n copies of k
                 1|.!.0   Shift left by 1 and fill with zero
    1          ,.         Interleave with 1
             /@           Reduce using
           +                Addition
        |/\                 Cumulative reduce using modulo
  1{                      Select value at index 1
1+                        Add 1

J , 19 Bytes

1+(}:@|.^:({:@])i.)

Probieren Sie es online!

Wie es funktioniert

1+(}:@|.^:({:@])i.)   Left: k, Right: n
                i.    Generate [0..n-1]
        ^:            Repeat:
   }:@|.                Rotate left k items, and remove the last item
          ({:@])        n-1 (tail of [0..n-1]) times
1+                    Add one to make the result one-based

Dart , 33 Bytes

f(n,k)=>n<2?1:(f(n-1,k)+k-1)%n+1;

Probieren Sie es online!

Japt , 15 Bytes

_é1-V Å}h[Uõ] Ì

Probieren Sie es online!

Ein Byte könnte durch 0-Indizierung von k gespeichert werden , aber es ist eigentlich kein Index, deshalb habe ich mich dagegen entschieden.

Erläuterung:

         [Uõ]      :Starting with the array [1...n]
_      }h          :Repeat n-1 times:
 é1-V              : Rotate the array right 1-k times (i.e. rotate left k-1 times)
      Å            : Remove the new first element
              Ì    :Get the last value remaining

Japt -h, 10 Bytes

õ
£=éVn1¹v

Versuch es

Powershell, 56 Bytes

param($n,$k)if($n-lt2){1}else{((.\f($n-1)$k)+$k-1)%$n+1}

Wichtig! Das Skript ruft sich selbst rekursiv auf. Speichern Sie das Skript alsf.ps1 Datei im aktuellen Verzeichnis. Sie können auch eine Skriptblockvariable anstelle einer Skriptdatei aufrufen (siehe das Testskript unten). Dieser Anruf hat die gleiche Länge.

Testskript:

$f = {

param($n,$k)if($n-lt2){1}else{((&$f($n-1)$k)+$k-1)%$n+1}

}

@(
    ,(7, 1, 7)
    ,(7, 2, 7)
    ,(7, 3, 4)
    ,(7, 11, 1)
    ,(77, 8, 1)
    ,(123,12, 21)
) | % {
    $n,$k,$expected = $_
    $result = &$f $n $k
    "$($result-eq$expected): $result"
}

Ausgabe:

True: 7
True: 7
True: 4
True: 1
True: 1
True: 21