Na tej stronie jest pytanie podobne do tego pytania, ale dodałem zwrot.

Masz trzy dane wejściowe, liczbę osób w kręgu n , k-ta osoba odliczana na każdym kroku i q-ta osoba, która przeżyła. Ludzie w kręgu są ponumerowani od 1 do n .

Na przykład w kręgu 20 osób 20. osoba, która przeżyła, jest pierwszą usuniętą osobą, a 19. osoba, która przeżyła, to druga osoba usunięta i tak dalej. Zazwyczaj problemem Józefa Flawiusza jest określenie ostatniej osoby, która została usunięta, zwanej tutaj pierwszą osobą, która przeżyła.

Napisz najkrótszy program lub funkcję, która przy tych trzech wejściach zwraca liczbę q- tej osoby, która przeżyła.

Jeśli są jakieś problemy z jasnością, daj mi znać.

Kilka przykładów:

>>> josephus(20, 3, 9)
4
>>> josephus(4, 3, 1)
1
>>> josephus(100, 9, 12)
46

Edycja: Załóż, że wszystkie dane wejściowe są prawidłowe. To znaczy, że nikt nie poprosi o 0 lub jakiekolwiek liczby ujemne i nikt nie poprosi o 20. ocalałego w kręgu 5 osób (to znaczy 1 ≤ q ≤ n)

Edycja: Przyjmę odpowiedź o północy UTC + 7 na początku 2 grudnia.

Pyth, 16 bajtów

eu.<PGvzh-QvwShQ

Wypróbuj online: pakiet demonstracyjny lub testowy

Dane wejściowe mają formę k<newline>n<newline>q.

Wyjaśnienie:

eu.<PGvzh-QvwShQ   implicit: z = first input line (string)
                             Q = second input line (integer)
              hQ   Q + 1
             S     the range [1, 2, ..., Q+1]
 u      h-Qvw      apply the following statement (Q-input()+1) times to G=^
    PG                remove the last number of G
  .<  vz              and rotate eval(z) to the left
e                  print the last number of the resulting list  

Piet, 280 273 kodeksów

Edycja: Grałem trochę w golfa i myślę, że mogę pograć w golfa jeszcze bardziej, ale to dopiero nadejdzie. Na razie cieszę się, że to działa i że mam miejsce na podpis w lewym dolnym rogu. Dwa pomysły, które muszę zapisać więcej kodów to: a) zmiana instrukcji końcowych to pop, push 1, add, out num(pop n, wyjście r + 1) i b) powtórzenie w lewym dolnym rogu, aby zapisać kody w manipulacji stosem później w pętli.

Obrazek powyżej to mój kod przy 8 pikselach na kodel. Zasadniczo jest to ten sam algorytm, co moja odpowiedź w języku Python, ale z danymi wejściowymi w kolejności k , q , n . W praktyce istnieje również wiele manipulacji stosami. Możesz spróbować tutaj , otwierając tam obraz i uruchamiając z nim kod.

Wyjaśnienie

Jest to krok po kroku rozwiązanie problemu.

in num    get k
dup       Stack: k k
push 1
subtract  Stack: k k-1
in num    get q
dup       Stack: k k-1 q q
dup       Stack: k k-1 q q q
push 4
push 2
roll      Stack: k q q k-1 q
mod       Stack: k q q r
in num    get n
# note: the loop will return to the following codel
dup       Stack: k q q r n n
push 4
push 3
roll      Stack: k q r n n q
greater   1 or 0
pointer   Here the loop begins. If q>n, the pointer moves clockwise.
          Else, it points straight ahead

LOOP:     Stack: k i r n (i=q at the start of the loop)
push 4
push 2
roll      Stack: r n k i
push 1
add       Stack: r n k i=i+1
push 2
push 1
roll      Stack: r n i k
dup       Stack: r n i k k
push 5
push 4
roll      Stack: n i k k r
add       Stack: n i k m=r+k
push 3
push 2
roll      Stack: n k m i
dup       Stack: n k m i i
push 3
# here it turns the corner
push 1
roll      Stack: n k i m i
mod       Stack: n k i r=m%i
push 4
# here it turns the corner and avoids the black codels
push 1
roll      Stack: r n k i
dup       Stack: r n k i i
push 5
push 3
roll      Stack: k i i r n
dup       Stack: k i i r n n
# and we meet up with the dark green codel once more
push 4
push 3
roll      Stack: k i r n n i
greater   Stack: k i r n (0 or 1)
pointer   if else again

# else    Stack: k i r n
push 2    
push 1
roll      Stack: k i n r
# and turn the corner
push 1
add       Stack: k i n r+1
out num   print r+1
# turn the corner into the end pattern (the shape with the black edges)
END

CJam, 22 20 19 bajtów

q~_,@a@*{m<)\}%\~=)

Odczytuje to dane wejściowe jako q k n. Wypróbuj online w interpretatorze CJam .

Jak to działa

q~                   Read and evaluate all input. This pushes q, k, and n.
  _,                 Push A := [0 ... n-1].
    @a               Rotate on top of the stack and wrap it in an array.
      @*             Rotate the original n on top and repeat [k] n times.
        {    }%      For each of the n k's:
         m<            Rotate A k units to the left.
           )\          Pop the last element and swap it with A.
               \~    Swap the resulting array with q and apply bitwise NOT.
                 =)  Select the corresponding element and add 1 to it.

Golfscript, 58 56 55 35 31 30 bajtów

Zakładając, że trzy wejścia są już na stosie, w kolejności n , k , q

~1$(1$%3$),@),-{\2$+\%}%\)])\;

To rozwiązanie zakłada, że ​​muszę pozbyć się wszystkiego oprócz ostatecznej odpowiedzi.

Jak to działa

j(n,k,q)Więcej szczegółów znajdziesz w moim rozwiązaniu Python 3.

~                                   Read the inputs n, k, q
 1$(                                Duplicate k, decrement
    1$                              Duplicate q
      %                             (k-1)%q
       3$),                         Create array [0..n+1]
           @),                      Create array [0..q+1]
              -                     Subtract the second array from the first,
                                        leaving only [q+1..n+1]
               {      }%            Map the following statement onto [q+1..n+1].
                                        The numbers from this array will be denoted i.
                \                   Swap i and r
                 2$+                Duplicate k, add to r
                    \               Swap r and i
                     %              r mod i
                        \)          Swap the leftover array from map with r, increment
                          ]         Put the whole stack into an array
                           )        Remove the last member of the array, r
                            \;      Pop the array, leaving only the result

Edycja 1: Użyto sugestii @ Doorknob (Dodano znak +, aby uzyskać wszystkie dane wejściowe do tablicy)

Dawniej,

\.(2$2$*1$4$%-{.5$3$*>!}{~)2$*1$/~)}while 4$3$*\-)\;\;\;\;

Edycja 2: Dodano ~, zgodnie z zasadami wiki i skrócono kod. Dzięki @Dennis

Dawniej,

[\.(2$2$*1$4$%-{.5$3$*>!}{~)2$*1$/~)}while 4$3$*\-)]+)\;

Edycja 3: Zaimplementowano krótszy algorytm.

Dawniej,

~\.(2$2$*1$4$%-{.5$3$*>!}{~)2$*1$/~)}while 4$3$*\-)]-1=

Edycja 4: Zrozumiałem, że mogę użyć %jako mapy.

Dawniej,

~1$(1$%{1$4$<}{\)\2$+1$%}while)])\;

Edycja 5: Drobna edycja. Zmieniły 2$się @dokonać [0..q-1]i 3$aby 2$odzyskać k. Zapisane ugryzienie

Dawniej,

~1$(1$%3$),2$),-{\3$+\%}%\)])\;

JavaScript (ES6), 56 bajtów

(n,k,q)=>{r=(k-1)%q;for(i=q;i<n;r=(r+k)%++i);return r+1}

Nie golfił

Zasadniczo adaptacja JavaScript odpowiedzi Python @ Sherlock9 .

(n,k,q)=>{
  r=(k-1)%q;
  for(i=q;i<n;r=(r+k)%++i);
  return r+1
}

Test

n = <input type="number" id="N" value="100" /><br />
k = <input type="number" id="K" value="9" /><br />
q = <input type="number" id="Q" value="12" /><br />
<button onclick="result.innerHTML=(

(n,k,q)=>{r=(k-1)%q;for(i=q;i<n;r=(r+k)%++i);return r+1}

)(+N.value,+K.value,+Q.value)">Go</button><br />
<pre id="result"></pre>

Mathematica, 50 bajtów

<<Combinatorica`
Tr@Position[Josephus@##2,1+#2-#]&

Anonimowa funkcja. Pobiera dane wejściowe w kolejności q,n,k.

C, 81 73 bajtów

Na podstawie implementacji JavaScript @ user81655 mojej odpowiedzi w języku Python.

Edycja: Usunięto i

int j(int n,int k,int q){int r=(k-1)%q;for(;q<n;r=(r+k)%++q);return r+1;}

Test

#include <stdio.h>
int j(int n,int k,int q){int r=(k-1)%q;for(;q<n;r=(r+k)%++q);return r+1;}
int main()
{
    printf("%d\n", j(20,3,9));
    return 0;
}

Python 3, 72 66 62 bajtów

Dynamiczna funkcja programowania w 62 bajtach. Na podstawie algorytmu z Wikipedii. Kiedyś na tej stronie istniała bezpośrednia implementacja tego algorytmu, gdy q = 1 (tj. I = 1, r = 0), ale widzę, że został teraz usunięty.

Edycja 1: Usunąłem, iaby zapisać 4 bajty. Wyjaśnienie pozostaje niezmienione.

Edycja 2: Przeliczenie w liczbie bajtów. Używałem \r\ndo EOL i nie zauważył, że gdy dodaje 3 bajty. Odpowiednio obniżyłem liczbę bajtów.

def j(n,k,q):
 r=(k-1)%q
 while q<n:q+=1;r=(r+k)%q
 return r+1

Jak to działa

def j(n,k,q):
 i=q;r=(k-1)%q              We start with the smallest possible circle to have a q-th
                                survivor, a circle of q people.
 while i<n:i+=1;            Iterate from q to n
                r=(r+k)%i   Every time you add people to the circle, r increases by k, 
                                modulo the current size of the circle i.
 return r+1                 Return the result.

Dzięki @Dennis za przypomnienie, że powinienem wyjaśnić mój kod (choćby pośrednio, ponieważ on umieścił jeden w swojej odpowiedzi). Jeśli coś jest niejasne, daj mi znać.

Edytować:

Dawniej,

Funkcja iteracyjna zaadaptowana z gry Concrete Mathematics przez Grahama, Knutha i Patashnika. Chociaż ten algorytm jest dłuższy, jest szybszy dla dużych n i małych k .

def t(n,k,q):
 m=k-1;z=q*k-m%q
 while z<=n*m:z=-(-z*k//m)
 return n*k-z+1

PHP, 71 bajtów

Na podstawie odpowiedzi @ Sherlock9. Zobacz jego odpowiedź na algorytm dla Pythona.

function a($n,$k,$q){for($r=($k-1)%$q;$q<$n;$r=($r+$k)%++$q);echo$r+1;}

Alternatywnie, oto moje oryginalne naiwne podejście bez algorytmu. Wykorzystuje tablicę do oznaczenia osób, które zostaną znalezione.

91 bajtów

function a($n,$k,$q){for($r=--$i;$q<=$n;++$i%$k||$c[$r]=$q++)while($c[$r=++$r%$n]);echo$r;}

Haskell, 48 47 43 bajtów

(n!k)q=1+foldl(mod.(k+))(mod(k-1)q)[q+1..n]

Oparty na algorytmie Haskell na stronie Kod Rosetty funkcji Józefa z dwoma danymi wejściowymi. Sugestie dotyczące gry w golfa są mile widziane.

Edit: Dziękuję Nimi o pomoc z golfa pierwszego algorytmu poprzez sugerując wersję pointfree, a za pomoc w golfa drugi algorytm, pozwalając mi znać, że untilkluczowe istnieje.

(n#k)q|m<-k-1=1+n*k-until(>n*m)(\z-> -div(-z*k)m)(q*k-mod m q)

Wersja algorytmu na końcu mojej odpowiedzi w Pythonie zaadaptowana z gry Concrete Mathematics przez Grahama, Knutha i Patashnika. Chociaż ten algorytm ma dłuższą wartość 62 bajtów i nie został obniżony tak bardzo jak pierwszy, jest szybszy dla dużych ni małych k.

Nie golfowany:

Pierwszy algorytm

jos_g num step q = 1 + foldl (\x -> mod (x + step) ) (mod (step-1) q) [q+1..num]

Drugi algorytm

jos_gkp num step q
    -- ceiling throws a type-related fit with ceiling(z*k/(k-1))
    -- better to use - div (-z * k) (k - 1)
    | m <- step-1 = 1 + num*step - until (>num*m)(\z-> -div (-z*k) m) (q*step - mod m q) 

GameMaker Language (GML), 88 bajtów

Na podstawie odpowiedzi @ user81655

r=argument0
k=argument1
q=argument2
r=(k-1)mod q;for(i=q;i<n;r=(r+k)mod ++i){}return r+1

Galaretka , 14 13 bajtów

Rµṙ⁴ṖµL>⁵µ¿⁴ị

TryItOnline!

W jaki sposób?

Rµṙ⁴ṖµL>⁵µ¿⁴ị - Main link: n, k, q
 µ            - monadic chain separation
R             - range(n): [1,2,3,...,n] - the circle of people
     µ   µ¿   - while
      L       -     length
       >      -     greater than
        ⁵     -     5th program argument (3rd input), i.e. q
  ṙ           -         rotate left by
   ⁴          -         4th program argument (2nd input) i.e. k
    Ṗ         -         pop - remove the rightmost person
            ị - get index
           ⁴  - 4th program argument (2nd input), i.e. k

Rubin, 53 48 bajtów

Lambda

->n,k,q{r=(k-1)%q;(q+=1;r=(r+k)%q)while q<n;r+1}

Jak to działa

def j(n,k,q)
  r=(k-1)%q   # r starts at j[q,k,q]
  while q<n
    q+=1
    r=(r+k)%q # Every time you add people to the circle, r increases by k, 
              # modulo the current size of the circle q.
  end
  r+1         # Return the result.
end