Tantangan

Tulis fungsi yang mengambil dua bilangan bulat positif n dan k sebagai argumen dan mengembalikan jumlah orang terakhir yang tersisa dari n setelah menghitung masing-masing orang ke- k .

Ini adalah tantangan kode-golf, sehingga kode terpendek menang.

Masalah

n orang (yang diberi nomor dari 1 hingga n ) berdiri dalam lingkaran dan setiap k dihitung hingga satu orang tersisa (lihat artikel wikipedia yang sesuai ). Tentukan jumlah orang terakhir ini.

Misalnya untuk k = 3 dua orang akan dilewati dan yang ketiga akan dihitung. Yaitu untuk n = 7 angkanya akan dihitung dalam urutan 3 6 2 7 5 1 (secara detail 1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 ) dan dengan demikian jawabannya adalah 4 .

Contohnya

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 byte

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

Mengambil n ktumpukan, dan meninggalkan hasilnya di tumpukan.

Pembedahan

Ini menggunakan pengulangan g(n,k) = (g(n-1,k) + k) % ndengan g(1, k) = 0(seperti yang dijelaskan dalam artikel Wikipedia) dengan rekursi diganti dengan lipatan.

{          # 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;

Mesin Pendaftaran Minsky (25 negara bagian)

Secara teknis bukan fungsi, tetapi dalam paradigma komputasi yang tidak memiliki fungsi ...

Ini adalah sedikit variasi pada kasus uji utama tantangan interpretasi MRM pertama saya :

Masukan dalam register ndan k; output dalam register r; diasumsikan bahwa r=i=t=0pada entri. Dua instruksi penghentian pertama adalah kasus kesalahan.

Python, 36

Saya juga menggunakan rumus dari wikipedia:

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

Contoh:

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

Mathematica, 38 36 byte

Rumus Wikipedia yang sama:

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

C, 40 karakter

Ini hanya rumus yang diberikan oleh artikel wikipedia di atas:

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

Untuk variasi, inilah implementasi yang benar-benar menjalankan simulasi (99 karakter):

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

dc, 27 byte

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

Menggunakan pengulangan dari artikel Wikipedia. Penjelasan:

# 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 karakter

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

Menjalankan simulasi.

Atau, gunakan rumus (31 karakter):

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

Saya berharap Howard tidak keberatan bahwa saya telah menyesuaikan format input sedikit agar sesuai dengan kata kerja diad di J.

Pemakaian:

   7 j 3
4
   123 j 12
21

GolfScript, 32 24 byte

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

Penggunaan: Mengharapkan dua parameter n dan k berada di tumpukan dan meninggalkan nilai output.

(terima kasih kepada Peter Taylor untuk menyarankan pendekatan berulang dan banyak tips lainnya)

Pendekatan lama (rekursif) dari 32 karakter:

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

Ini GolfScript pertama saya, jadi tolong beri tahu saya kritik Anda.

R, 48

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

Menjalankan Versi dengan contoh: http://ideone.com/i7wae

Groovy, 36 byte

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

Apakah simulasi yang sebenarnya. Demonstrasi:

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 byte

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

C, 88 karakter

Apakah simulasi, tidak menghitung rumus.
Jauh lebih lama dari rumus, tetapi lebih pendek dari simulasi C lainnya.

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

Catatan:
1. Mengalokasikan memori dan tidak pernah melepaskan.
2. Alokasikan n*8bukannya n*4, karena saya gunakan p[n]. Bisa mengalokasikan (n+1)*4, tetapi lebih banyak karakter.

C ++, 166 byte

Golf:

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

Tidak Terkumpul:

#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 byte

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 byte

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

Menjalankan versi dengan kasus uji: http://ideone.com/pXOUc

Q, 34 byte

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

Pemakaian:

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

Ruby, 34 byte

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

Haskell, 29

Menggunakan rumus dari wikipedia.

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

JavaScript (ECMAScript 5), 48 byte

Menggunakan ECMAScript 5 karena itu adalah versi terbaru dari JavaScript pada saat pertanyaan ini diajukan.

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

Versi ES6 (non-bersaing), 33 byte

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

Penjelasan

Tidak banyak bicara di sini. Saya hanya mengimplementasikan fungsi yang diberikan artikel Wikipedia kepada saya.

05AB1E , 11 byte

L[Dg#²<FÀ}¦

Cobalah 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 byte

Kode

: 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) adalah:n k -- m

Penggunaan dan penjelasan

Algoritma menggunakan array bilangan bulat seperti ini: jika nilai orang adalah 5 maka array akan menjadi [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 byte

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

Cobalah online!

Pendekatan berulang berdasarkan solusi pemrograman dinamis.

Penjelasan

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 byte

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

Cobalah online!

Bagaimana itu bekerja

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 byte

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

Cobalah online!

Japt , 15 byte

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

Cobalah online!

Satu byte bisa disimpan dengan pengindeksan 0 k , tetapi sebenarnya bukan indeks, jadi saya memutuskan untuk tidak melakukannya.

Penjelasan:

         [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 byte

õ
£=éVn1¹v

Cobalah

Powershell, 56 byte

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

Penting! Script menyebut dirinya secara rekursif. Jadi simpan skrip sebagaif.ps1 file di direktori saat ini. Anda juga dapat memanggil variabel blok skrip alih-alih file skrip (lihat skrip pengujian di bawah). Panggilan itu memiliki panjang yang sama.

Skrip uji:

$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"
}

Keluaran:

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