Matthias Apsel: Programmierung zum Wochenende

Hallo alle,

von 10 Gefängnisinsassen sollen 2 begnadigt werden. Dazu stellen sich die Gefängnisinsassen in einer Reihe auf und durch fortlaufendes Abzählen wird jeder dritte aus der Reihe entfernt, bis nur noch zwei übrig bleiben. An welche Stelle muss sich Klaus begeben, wenn er begnadigt werden möchte?

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10 /* Nr. 3, 6 und 9 fallen raus */
1 2 4 5 7 8 10
1 2 4 5 7 8 10
1 4 5 8 10
1 4 5 8 10
4 5 10
4 5 10
4 10

Klaus muss sich also an Position 4 oder 10 stellen, wenn er begnadigt werden möchte.

a) Leider hat das Gefängnis 1000 Insassen …
b) Verallgemeinere das Programm so, dass aus einer Liste mit N Elementen fortlaufend jedes K-te Element entfernt wird bis nur noch (K-1) Elemente übrig sind und der Abzählprozess an einer beliebigen Stelle beginnt.

Lösungen können per PM als gut und ausführlich kommentierter Quelltext in jeder beliebigen Programmiersprache eingereicht werden.

Bis demnächst
Matthias

--
Pantoffeltierchen haben keine Hobbys.
  1. problematische Seite

    Wie wärs denn zur Abwechslung mal mit einer praktischen Aufgabe? Zum Beispiel die Berechnung der Oktettenwertigkeiten aus einem gegebenen Codepoint. Und das Ganze dann als Webanwendung mit progressive Enhancement!

    PS: Die gesuchte Formel ist nicht auf der verlinkten Seite. Sie ist auch schwer zu finden. Der Algorithmus lässt sich jedoch durch Überlegung finden!

    MfG

    1. problematische Seite

      Hallo pl,

      Fertig

      Rolf

      --
      sumpsi - posui - clusi
  2. Aloha ;)

    Lösungen können per PM als gut und ausführlich kommentierter Quelltext in jeder beliebigen Programmiersprache eingereicht werden.

    PM ist raus 😉

    Grüße,

    RIDER

    --
    Camping_RIDER a.k.a. Riders Flame a.k.a. Janosch Zoller
    # Twitter # Steam # YouTube # Self-Wiki # Selfcode: sh:) fo:) ch:| rl:) br:^ n4:? ie:% mo:| va:) js:) de:> zu:} fl:( ss:) ls:[
    1. @@Camping_RIDER

      PM ist raus 😉

      Ich hab gerade ‚PL ist raus‘ gelesen. 😉

      LLAP 🖖

      --
      „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
      1. Das könnte Dir so passen!

        Übrigens: „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“

        Genau!

        Updated!

        1. @@pl

          Übrigens: „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“

          Genau!

          Bei dir denke ich an Tucholsky.

          Dein Beispiel ist das Gegenteil einer „praktischen Aufgabe“. Die Berechnung der Oktettenwerte in UTF-8 (o.a. Zeichencodierung) aus einem gegebenen Codepoint kommt in der Praxis der Entwicklung von Webanwendungen nicht vor.

          Bei der Entwicklung von Webanwendungen bewegt man sich auf Zeichenebene. Wenn man da in die Byte-Ebene abrutscht, ist das ein sicheres Zeichen, dass man was falsch™ gemacht hat.

          LLAP 🖖

          --
          „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
          1. @Gunnar Bittersmann

            Dein Beispiel ist das Gegenteil einer „praktischen Aufgabe“. Die Berechnung der Oktettenwerte in UTF-8 (o.a. Zeichencodierung) aus einem gegebenen Codepoint kommt in der Praxis der Entwicklung von Webanwendungen nicht vor.

            Wie bitte!?

            Bei der Entwicklung von Webanwendungen bewegt man sich auf Zeichenebene.

            Nicht nur!

            Wenn man da in die Byte-Ebene abrutscht, ist das ein sicheres Zeichen, dass man was falsch™ gemacht hat.

            So ein Unsinn!

            Entwickler von Webanwendungen haben ständig damit zu tun! HTTP steht zwar für HyperText, ist jedoch Byteebene! Aber manche haben das wohl noch gar nicht mitbekommen!

            1. Hallo pl,

              Entwickler von Webanwendungen haben ständig damit zu tun! HTTP steht zwar für HyperText, ist jedoch Byteebene! Aber manche haben das wohl noch gar nicht mitbekommen!

              Als Entwickler von Web-Anwendungen ist das völlig irrelevant. Man packt ein Zeichen auf den Transport-Layer und kriegt auf der anderen Seite ein Zeichen raus.

              LG,
              CK

              1. Als Entwickler von Web-Anwendungen ist das völlig irrelevant. Man packt ein Zeichen auf den Transport-Layer und kriegt auf der anderen Seite ein Zeichen raus.

                Genau deswegen schlagen die ja mit jedem noch so kleinsten Zeichenproblem hier auf!

                1. Hallo pl,

                  Genau deswegen schlagen die ja mit jedem noch so kleinsten Zeichenproblem hier auf!

                  Wo?

                  LG,
                  CK

                2. Tach!

                  Als Entwickler von Web-Anwendungen ist das völlig irrelevant. Man packt ein Zeichen auf den Transport-Layer und kriegt auf der anderen Seite ein Zeichen raus.

                  Genau deswegen schlagen die ja mit jedem noch so kleinsten Zeichenproblem hier auf!

                  Ja, solche Probleme gibt es, aber die löst man nicht, indem man selbst eine Schicht auf den Transportlayer draufpackt, sondern indem man die verwendete und zu verwendende Zeichenkodierung bei allen beteiligten Komponenten angibt. Das Problem ist ein gelöstes, es kommt nur noch darauf an, die beteiligten Systeme richtig zu konfigurieren.

                  dedlfix.

      2. Aloha ;)

        Ich hab gerade ‚PL ist raus‘ gelesen. 😉

        Fällt das unter Wunschdenken? 😉

        Grüße,

        RIDER

        --
        Camping_RIDER a.k.a. Riders Flame a.k.a. Janosch Zoller
        # Twitter # Steam # YouTube # Self-Wiki # Selfcode: sh:) fo:) ch:| rl:) br:^ n4:? ie:% mo:| va:) js:) de:> zu:} fl:( ss:) ls:[
  3. Hallo Matthias Apsel,

    b) Verallgemeinere das Programm so, dass aus einer Liste mit N Elementen fortlaufend jedes K-te Element entfernt wird bis nur noch (K-1) Elemente übrig sind und der Abzählprozess an einer beliebigen Stelle beginnt.

    c) N = 1000, K = 3, zufällig gewählter Startpunkt - gibt es Positionen, die besonders wahrscheinlich sind, übrig zu bleiben?

    Bis demnächst
    Matthias

    --
    Pantoffeltierchen haben keine Hobbys.
  4. Hallo Matthias Apsel,

    a) Leider hat das Gefängnis 1000 Insassen …

    226, 406

    b) Verallgemeinere das Programm so, dass aus einer Liste mit N Elementen fortlaufend jedes K-te Element entfernt wird bis nur noch (K-1) Elemente übrig sind und der Abzählprozess an einer beliebigen Stelle beginnt.

    Die eingegangenen Lösungen von @Rolf B, @1unitedpower, @Camping_RIDER, @Gunnar Bittersmann und @encoder, empfinde ich zum Teil deutlich eleganter als meine, ich überlasse es ihnen, sie hier zu posten.

    (Ich habe wirklich das Array ggf. umsortiert, die entsprechenden Positionen markiert, geschaut, wieviele noch bis zum Ende fehlen, das Array gekürzt. Aber wenigstens die while-Schleife habe ich auch verwendet)

    c) gibt es Positionen, die besonders wahrscheinlich sind, übrig zu bleiben?

    Nein. Man beginnt an der Stelle 0 und stellt fest, dass die Stelle a übrig bleibt. Beginnt man jetzt an der Stelle s, bleibt die Stelle (a + s) % length übrig, da man dieselben Operationen auf demselben Array durchführt. Das gilt für jede übrig bleibende Stelle unabhängig von n und k.

    Bis demnächst
    Matthias

    --
    Pantoffeltierchen haben keine Hobbys.
    1. Die eingegangenen Lösungen von @Rolf B, @1unitedpower, @Camping_RIDER, @Gunnar Bittersmann und @encoder, empfinde ich zum Teil deutlich eleganter als meine, ich überlasse es ihnen, sie hier zu posten.

      Zeigst du uns deine Lösung denn trotzdem?

      Ich habe Haskell bemüht:

      module Prisoners where
      
      type Index = Int
      type Size = Int
      type Prisoner = Int
      
      -- n Gefangene  haben sich in einem Kreis aufgestellt und wurden beginnend mit
      -- 1 durchnummeriert. Angefangen mit dem (i+k)-ten Gefangen wird  nun jeder
      -- k-te Gefangene zurück in seine Zelle geschickt, bis noch k-1 Gefangene übrig
      -- sind, welche dann begnadigt werden.
      -- Die Funktion `actOfGrace` liefert die Nummern der k-1 Gefangenen, die
      -- entlassen werden.
      actOfGrace :: Index -> Index -> Size -> [Prisoner]
      actOfGrace k i n = dropKth k (i-1) [1..n]
      
      -- Angefangen mit dem (i+k)-ten Element, entferne jedes k-te Element aus einem
      -- Ring bis nur noch k-1 Elemente übrig sind. Die Zählung beginnt mit 0.
      dropKth :: Index -> Index -> [a] -> [a]
      dropKth k i xs
        = if (length xs == k - 1)               -- Abbruchbedingung erreicht?
            then xs                             -- Finales Ergebnis
            else dropKth k i' xs'               -- Entferne ein Element rekursiv
          where
            out = (i + k - 1) `mod` (length xs) -- zu entferneder Index
            xs' = remove out xs                 -- Ring um ein Element verkürzt
            i'  = out `mod` (length xs')        -- Beginn nächster Zählung
      
      -- Entferne das n-te Element aus einer Liste. Die Zählung beginnt mit 0.
      remove :: Index -> [a] -> [a]
      remove n xs
        = (take n xs) ++ (drop (n+1) xs)
      
      -- Test mit 10 Gefangenen, Zählbeginn bei 1 und jeder 3-te wird zurück auf die
      -- Zelle geschickt bis nur noch 2 übrig sind.
      test :: Bool
      test
        = expected == actual
          where
            expected = [4, 10]
            actual = actOfGrace 3 1 10
      

      Aber wenigstens die while-Schleife habe ich auch verwendet

      In Haskell gibt es keine while-Schleifen oder irgendwelche Schleifen, da muss man auf Rekursion zurückgreifen. Das schöne an der Aufgabenstellung war, dass der Start-Index frei wählbar war, dadurch ergibt sich fast von alleine eine Tail-Rekrusion, die von Haskell automatisch so optimiert wird, dass der Callstack nicht anwächst.

      1. @@1unitedpower

        Zeigst du uns deine Lösung denn trotzdem?

        Wenn du mich meinst … 🤪 Die ist auf CodePen

          out = (i + k - 1) `mod` (length xs) -- zu entferneder Index
        

        So sieht das bei mir auch aus.

        LLAP 🖖

        --
        „Wer durch Wissen und Erfahrung der Klügere ist, der sollte nicht nachgeben. Und nicht aufgeben.“ —Kurt Weidemann
        1. Tach!

          Wenn du mich meinst … 🤪 Die ist auf CodePen

          Ich habe sie mal hierher geholt und nehmn sie mal etwas auseinander.

          const n = 1000, k = 3, start = 0;
          

          n und k - typisch Mathematiker. Diese Bezeichner gehen zwar so aus der Aufgabenstellung hervor, aber zum Verständnis ihrer Funktion sind sie nicht besonders geeignet.

          let prisoners = [], i;
          
          // fill array with numbers from 1 through n
          for (i = 1; i <= n; i++)
          {
          	prisoners.push(i);
          }
          

          Kommentare sollen beschreiben, was man nicht oder nur umständlich aus dem Code erkennen kann.

          Eine Zählschleife und ein Push in ein Array füllt natürlich ein Array, was auch sonst?

          i = start;
          

          Die Wiederverwendung von Variablen für unterschiedliche Aufgaben sollte man vermeiden. Das führt nur zu Missverständnissen. Besser wäre gewesen, dem i im for ein let zu spendieren, dort lebt es dann in seinem eigenen Scope. Das andere i sollte man bei der prisoners-Deklaration weglassen und stattdessen der obigen Zeile ein let voranstellen, um es für den nachfolgenden Teil anzulegen.

          while (prisoners.length >= k)
          {
          	i = (i - 1 + k) % prisoners.length; // index of next element to be removed
          	prisoners.splice(i, 1); // remove element of index i from array
          }
          

          Auch hier erklären die beiden Kommentare nichts, was nicht bereits in der Dokumentation zu splice() zu finden ist. Ein Element aus dem Array zu entfernen ist ureigenste Aufgabe von splice(). Dass das i ein Platzhalter für das zu entfernende Element sein soll, sieht man auch problemlos. Es wäre etwas anders, wenn man eine Funktion missbraucht oder in ungewöhnlicher Weise anwendet. Ein Beispiel wäre foo = bar.slice(). slice() ist eigentlich dazu da, einen Teil aus einem Array zu kopieren. Ohne Parameter kopiert es das gesamte Array (shallow copy), was dann aber kein schneiden (to slice) mehr ist. Somit stimmt der damit erledigte Anwendungsfall, eine Kopie eines Array zu erzeugen (shallow copy), nicht mehr mit dem Namen der Funktion überein. Hier könnte man einen Kommentar anbringen, wenn man davon ausgehen kann, dass das Zielpublikum diesen nicht ganz unbekannten Javascript-Trick nicht kennt.

          Jedenfalls wäre hier interessanter gewesen, die Überlegungen niederzuschreiben, die zu der verwendeten Formel führten.


          Eine Lösung (fast) ohne Kommentare kann ich auch bieten, hab sie aber eben erst erstellt und nicht eingereicht.

          const inmateCount = 10;
          const countTo = 3;
          const amnesty = countTo - 1;
          
          let inmates = [...Array(inmateCount + 1).keys()].slice(1);
          let backToCell = countTo - 1; // starts with countTo but zero-based
          while (inmates.length > amnesty) {
              let rest = inmates.length % countTo;
              inmates = inmates.filter((_, index) => index % countTo != backToCell);
              backToCell = (backToCell - rest + countTo) % countTo;
          }
          console.log(inmates);
          

          Hilfreiche Kommentare an den wichtigsten Stellen kann ich keine geben, weil ich die Lösung nicht wirklich erklären kann. Ich hab mit Hilfe von Graphit auf Pflanzenfasern gefummelt, bis ich einen funktionierenden Algorithmus hatte. Ein Bild davon zu zeigen bringt nichts, weil man aus den Zahlenreihen meine Gedankengänge nicht erkennen kann. Relativ einfach ist noch der Filter zu verstehen. Der Ausdruck muss false liefern, wenn die Zählung beim x-ten Insassen vorbeikommt. Die anderen zwei Zeilen dienen zum Nachjustieren um am Ende des Kreises den Offset für die nächste Runde zu justieren. Aber fragt mich nicht nach den Details, das ist mir zu kompliziert zu erklären.

          dedlfix.

          1. const n = 1000, k = 3, start = 0;
            

            n und k - typisch Mathematiker. Diese Bezeichner gehen zwar so aus der Aufgabenstellung hervor, aber zum Verständnis ihrer Funktion sind sie nicht besonders geeignet.

            Die Kritik trifft auch auf meine Lösung zu. Tatsächlich hatte ich in meiner Implementierung zunächst sprechende Bezeichner gewählt, bin dann allerdings auf die kurzen Bezeichner umgestiegen aus zwei Gründen: i und k sind geläufige Namen für Index-Variablen. Wenn man es allerdings genau nimmt, dann ist weder i noch k ein Index, i ist ein Offset, k eine Länge oder eine Range, das fand ich aber nicht so gravierend. Der zweite Grund ist, dass die sprechenden Bezeichner deutlich länger sind, und sie in Ausdrücken dadurch mehr in den Vordergrund treten als die Berechnungen. Vgl. (i + k - 1) `mod` (length xs) und (offset + countTo - 1) `mod` (length prisoners). Der zweite Grund ist für mich der entscheidende gewesen. Diese Argumentation kann man auch ins Extrem treiben, das machen zum Beispiel Concatenativen Programmiersprachen, da werden Values überhaupt nicht mehr benannt, sondern nur noch implizit zwischen Funktionen hin und her gereicht.

            1. Tach!

              const n = 1000, k = 3, start = 0;
              

              n und k - typisch Mathematiker. Diese Bezeichner gehen zwar so aus der Aufgabenstellung hervor, aber zum Verständnis ihrer Funktion sind sie nicht besonders geeignet.

              Die Kritik trifft auch auf meine Lösung zu. Tatsächlich hatte ich in meiner Implementierung zunächst sprechende Bezeichner gewählt, bin dann allerdings auf die kurzen Bezeichner umgestiegen aus zwei Gründen: i und k sind geläufige Namen für Index-Variablen.

              Gegen i sag ich nichts, solange seine Verwendung örtlich begrenzt ist und die Bedeutung unwichtig ist, weil die Variable nur zur Hilfe in einem sehr bekannten Fall (hier "Zählvariable in Schleife") verwendet wird.

              Hingegen bei fachlichen Dingen sollte man diese auch beim Namen nennen. Mathematik ist schon recht alt und die Sitte, mit einzelnen Buchstaben zu rechnen, ist meiner Vermutung nach auf den Wunsch nach Abkürzung statt Ausschreiben entstanden. Heutzutage haben wir aber Autovervollständigung in den Entwicklungsumgebungen und das Tippen von ein paar wenigen Buchstaben plus Autovervollständigungsbedienung (meist nur ein Enter, Tab, Leerzeichen oder Punkt) ist nicht mehr der Akt wie beim Federkiel-Schwingen. Hier plädiere ich, der Lesbarkeit den Vorzug zu geben.

              dedlfix.

          2. Hallo dedlfix,

            while (prisoners.length >= k)
            {
            	i = (i - 1 + k) % prisoners.length; // index of next element to be removed
            	prisoners.splice(i, 1); // remove element of index i from array
            }
            

            Auch hier erklären die beiden Kommentare nichts, was nicht bereits in der Dokumentation zu splice() zu finden ist.

            Doch, der erste sagt, dass ich jenes Element entfernen möchte. Warum es das richtige ist, sagt der Kommentar allerdings nicht. Aber das finde ich ja grad das Clevere im Vergleich zu meiner Lösung. Ich hatte diesen Gedanken auch, ihn aber mit „funktioniert sowieso nicht“ nicht einmal getestet.

            Bis demnächst
            Matthias

            --
            Pantoffeltierchen haben keine Hobbys.
            1. Tach!

              while (prisoners.length >= k)
              {
              	i = (i - 1 + k) % prisoners.length; // index of next element to be removed
              	prisoners.splice(i, 1); // remove element of index i from array
              }
              

              Auch hier erklären die beiden Kommentare nichts, was nicht bereits in der Dokumentation zu splice() zu finden ist.

              Doch, der erste sagt, dass ich jenes Element entfernen möchte.

              Ja, aber das ergibt sich aus dem Code selbst, ohne dass man sich die Formel genauer anschauen muss. Wenn in der zweiten Zeile das Element i entfernt wird und in der Zeile darüber eine Zuweisung an i erfolgt, dann ist es logisch, dass diese Zeile das Element ermittelt, das entfernt werden soll. Ok, meine Formulierung war nicht ganz präzise, aber das wollte ich ausdrücken: nicht das Offensichtliche kommentieren.

              Warum es das richtige ist, sagt der Kommentar allerdings nicht.

              Eben.

              Aber das finde ich ja grad das Clevere im Vergleich zu meiner Lösung. Ich hatte diesen Gedanken auch, ihn aber mit „funktioniert sowieso nicht“ nicht einmal getestet.

              Ich hatte da auch die Überlegung, ob es da nicht eine Formel oder andere Gesetzmäßigkeit gibt. Mit Rechenpower in Form einer Schleife ist das ja aus mathematischer Sicht nur mäßig spannend.

              dedlfix.

              1. Hallo dedlfix,

                Ich hatte da auch die Überlegung, ob es da nicht eine Formel oder andere Gesetzmäßigkeit gibt. Mit Rechenpower in Form einer Schleife ist das ja aus mathematischer Sicht nur mäßig spannend.

                In der Tat. Deshalb hieß es ja Programmierung und nicht Mathematik zum Wochenende. Aber ein formelmäßiger Zusammenhang wäre sicher spannend.

                Bis demnächst
                Matthias

                --
                Pantoffeltierchen haben keine Hobbys.
          3. Tach!

            Eine Lösung (fast) ohne Kommentare kann ich auch bieten, hab sie aber eben erst erstellt und nicht eingereicht.

            const inmateCount = 10;
            const countTo = 3;
            const amnesty = countTo - 1;
            
            let inmates = [...Array(inmateCount + 1).keys()].slice(1);
            let backToCell = countTo - 1; // starts with countTo but zero-based
            while (inmates.length > amnesty) {
                let rest = inmates.length % countTo;
                inmates = inmates.filter((_, index) => index % countTo != backToCell);
                backToCell = (backToCell - rest + countTo) % countTo;
            }
            console.log(inmates);
            

            Die anderen zwei Zeilen dienen zum Nachjustieren um am Ende des Kreises den Offset für die nächste Runde zu justieren. Aber fragt mich nicht nach den Details, das ist mir zu kompliziert zu erklären.

            Hmm, vielleicht doch. Eine Gesetzmäßigkeit ist, dass beim Abzählen mit einer bestimmten Zahl, immer ein Rest der Liste übrig bleibt (auch wenn der 0 ist). Und dieser Rest ist bei der nächsten Runde vom Startoffset abzuziehen. Dabei muss man beachten, dass der neue Offset nicht negativ werden darf. Man muss den Offset im Bereich 0 (inklusive) und der Abzählzahl (exklusive) halten. Der erwähnte Rest wird vor dem Kürzen der Liste ermittelt und in rest festgehalten, die dritte Zeile im while erledigt das Abziehen. Das Addieren von countTo und die anschließende Modulo-Operation sorgt dafür, dass das Ergebnis nicht ins Negative abrutscht. Diese Korrektur müsste nicht immer erfolgen, ein if < 0 wäre auch eine Variante. Aber es stört auch nicht, countTo zu oft zu addieren, denn mit dem Modulo wird das wieder in den erlaubten Wertebereich zurückgeholt. Modulo mit negativen Dividenden führt aber nicht zum Ziel, deswegen die Addition.

            dedlfix.

      2. Hallo 1unitedpower,

        Zeigst du uns deine Lösung denn trotzdem?

        <?php
        /** 
          Aus einer Liste mit N Elementen soll fortlaufend jedes K. Element entfernt
          werden bis nur noch (K-1) Elemente übrig sind. Der Prozess beginnt an 
          einer beliebigen Stelle S. 
        **/
        
        $n = 1000; 
        $k = 3; 
        $s = 0; // wenn ungleich null, muss umgestellt werden 
        
        $toskip = $k - 1; // Anzahl der zu überspringenden Elemente 
        
        for ($i = 0; $i < $n; $i++) :
          $list[$i]= $i + 1;
        endfor;
        
        echo "<h3>0. Durchlauf</h3>";
        echo "<pre>";var_dump($list);echo "</pre>"; 
        
        if ($s > 0) :
          for ($i = 0; $i < $s - 1; $i++) :
            $list[$n + $i] = $list[$i]; // vordere Elemente hinten anhängen
          endfor;
          array_splice($list, 0, $s - 1); // und vorn entfernen
        endif;
        
        echo "<h3>0. Durchlauf</h3>";
        echo "<pre>";var_dump($list);echo "</pre>"; 
        
        $len = sizeof($list);
        $start = $toskip; // erstes Element, das entfernt wird 
        $durchlauf = 0;
        
        while ($len > $toskip) : // solange noch Elemente übersprungen werden können 
          $durchlauf++;
          // markiere die entsprechenden Listenelemente 
          for ($i = 0; $k * $i + $start < $len; $i++) :
            $list[$k * $i + $start] = 0;
          endfor;
          
          // in der Liste sind noch $rest Elemente übrig, die zu beachten sind 
          $rest = $len - 1 - ($k * ($i-1) + $start);
          
          // entferne die markierten Listenelemente 
          for ($i = sizeof($list) - 1; $i >= 0; $i--) :
            if ($list[$i] == 0) array_splice($list, $i, 1);
          endfor;
          
          $len = sizeof($list); // neue Länge 
          $start = $toskip - $rest; // neuer Start 
          echo "<h3>$durchlauf. Durchlauf</h3>";
          echo "<pre>";var_dump($list);echo "</pre>"; 
        endwhile; 
        ?>
        
        // Ausgabe13. Durchlauf
        
        array(5) {
          [0]=>
          int(226)
          [1]=>
          int(377)
          [2]=>
          int(604)
          [3]=>
          int(706)
          [4]=>
          int(949)
        }
        
        14. Durchlauf
        
        array(3) {
          [0]=>
          int(226)
          [1]=>
          int(604)
          [2]=>
          int(706)
        }
        
        15. Durchlauf
        
        array(2) {
          [0]=>
          int(226)
          [1]=>
          int(604)
        }
        

        Bis demnächst
        Matthias

        --
        Pantoffeltierchen haben keine Hobbys.
        1. Tach!

          Eine Anmerkung hätte ich.

          for ($i = 0; $i < $n; $i++) :
            $list[$i]= $i + 1;
          endfor;
          

          $list ist hier (und auch vorher) nicht grundlegend initialisiert worden. Wenn in zeitlich vorhergehendem Code $list ein Array war, dann werden in der Schleife die Werte nur überschrieben, wenn es einen gleichnamigen Schlüssel gibt, nicht vorhandene Schlüssel werden angehängt und überzählige bleiben drin. Die Reihenfolge wird dabei auch nicht numerisch sortiert, sondern beibehalten wie sie war. Damit läuft dann auch der nachfolgende Code nicht mehr intentionsgemäß.

          Ebenso unangenehm ist es, wenn $list ein String wäre, denn die Array-Zugriffssyntax ist dieselbe wie beim Zugreifen auf einzelnen Zeichen eines Strings. Besser ist, die Arbeit PHP zu überlassen und das Ergebnis als Schreibzugriff zuzuweisen, dann sind eventuelle vorherige Werte garantiert weg.

          $list = range(1, $n);
          

          Wenn es range() nicht gäbe, wäre außerdem semantisch besser, die Schleife nicht von 0 bis < $n laufen zu lassen, und dann im inneren eine 1 zu addieren, sondern gleich mit den richtigen Werten, also 1 bis <= $n. Und $list = []; vor der Schleife erstellt ein garantiert leeres Array in $list.

          dedlfix.

          1. Hallo dedlfix,

            Danke für deine Anmerkungen.

            wäre außerdem semantisch besser, die Schleife […] gleich mit den richtigen Werten, also 1 bis <= $n [laufen zu lassen].

            Ja. Allerdings war ich nicht sicher, ob ich dann mit dem modulo-Operator noch die richtigen Ergebnisse kriege.

            Bis demnächst
            Matthias

            --
            Pantoffeltierchen haben keine Hobbys.
            1. Hallo Matthias Apsel,

              Ja. Allerdings war ich nicht sicher, ob ich dann mit dem modulo-Operator noch die richtigen Ergebnisse kriege.

              Und was array_splice macht, wenn ich das erste Element entferne, was ja den Index 1 und nicht 0 hat.

              Bis demnächst
              Matthias

              --
              Pantoffeltierchen haben keine Hobbys.
              1. Tach!

                Ja. Allerdings war ich nicht sicher, ob ich dann mit dem modulo-Operator noch die richtigen Ergebnisse kriege.

                Und was array_splice macht, wenn ich das erste Element entferne, was ja den Index 1 und nicht 0 hat.

                Ach ja, du setzt ja in der Schleife auch den Index selbst. Kann man weglassen, der zählt von selbst von 0 an aufwärts, wenn das Array definiert leer ist. (Aber range() lässt diese Probleme gar nicht erst entstehen.)

                dedlfix.

    2. Hallo Matthias,

      ich hoffe, Du meinst 226 und 604.

      Ich habe eine Lösung mit echtem Abzählreim: https://jsfiddle.net/Rolf_b/m7cgk58t/ 😂

      Rolf

      --
      sumpsi - posui - clusi
    3. Aloha ;)

      Ich hatte die selbe Idee zur Rekursion wie @1unitedpower, war aber zu faul mir über eine echt funktionale Implementierung Gedanken zu machen und habe JavaScript bemüht.

      /**
       * returns an array of the k-1 numbers remaining in the following process: 
       * take numbers from 1 to n and continuously count out each k-th number,
       * begin counting at startnumber
       *
       * @param n quantity of numbers to select from
       * @param k index-distance between removed numbers
       * @param startnumber first number to count, defaults to 1
       * @returns array of remaining numbers or undefined if the parameters are not well defined
       */
      function findRemainingNumbers(n, k, startnumber) {
          // n is a positive integer
          if (!Number.isInteger(n) || n <= 0) return undefined;
      
          // k is an integer and can not be less than 2
          if (!Number.isInteger(k) || k < 2) return undefined;
          
          // provide default value for startnumber
          if (startnumber === undefined) startnumber = 1;
      
          // startnumber has to be a valid integer inside of 1..n
          if (!Number.isInteger(startnumber) || n < startnumber || startnumber < 1) return undefined;
      
          // create array with numbers
          let elements = [];
          for (let i = 1; i <= n; i++) { elements.push(i); }
      
          // delegate to universal function
          // if the numbers until startnumber shall not be counted, counting starts at 1 - startnumber
          // e.g. if the number 3 shall be counted as first, the countoffset has to be -2
          const countoffset = 1 - startnumber;
          return findRemainingElements(elements, k, countoffset);
      }
      
      /**
       * continuously count out the k-th element from the given elements
       * until there are not more than k-1 left 
       * and return the remaining elements
       *
       * @param elements array of elements to work on
       * @param k index-distance between removed elements
       * @param countoffset where to start counting - first element is counted as countoffset + 1
       * @returns array of remaining elements or undefined if the parameters are not well defined
       */
      function findRemainingElements(elements, k, countoffset) {
          // elements must be an array
          if (!Array.isArray(elements)) return undefined;
      
          // k is an integer and can not be less than 2
          if (!Number.isInteger(k) || k < 2) return undefined;
      
          // provide default value for countoffset
          if (countoffset === undefined) countoffset = 0;
      
          // countoffset is an integer
          if (!Number.isInteger(countoffset)) return undefined;
      
          // only do something if there are more than k elements
          if (elements.length < k) return elements;
      
          // choose by counting for one iteration
          let remainingElements = elements.filter(
              // keep elements where the counted number is less than one
              // keep elements where the counted number is not divisible by k
              // the counted number equals to the sum of index and countoffset plus 1
              (_, index) => index + countoffset + 1 < 1 || (index + countoffset + 1) % k != 0
          );
      
          // calculate where to start counting in the next iteration:
          // for the last element in the array, the counted number is
          // lastIndex + countOffset + 1, and because lastIndex + 1 equals elements.length
          // the offset for the next count is elements.length + countoffset
          const nextoffset = elements.length + countoffset;
      
          // do next iterations
          return findRemainingElements(remainingElements, k, nextoffset);
      }
      

      Wenn man sich die Prüfung der Variablen auf Typ und sinnvollen Wertebereich spart kann man das sogar in einen noch einigermaßen überschaubaren Einzeiler packen - der Rekursion sei Dank:

      function findRemainingElements(elements, k, countoffset) {
        return elements.length < k ? elements : findRemainingElements(elements.filter((_, index) => index + countoffset + 1 < 1 || (index + countoffset + 1) % k != 0), k, elements.length + countoffset);
      }
      

      Zu Aufgabenteil c hab ich zwei Lösungsansätze formuliert - einer induktiv, der andere deduktiv:

      var positions = {};
      for (let i = 1; i <= 1000; i++) {
      	positions[i+''] = 0;
      }
      for (let i = 1; i <= 1000; i++) {
      	let nrs = findRemainingNumbers(1000,3,i);
      	positions[nrs[0]+'']++;
          positions[nrs[1]+'']++;
      }
      console.log(positions);
      

      Ergibt ein Objekt mit 1000 Einträgen, die jeweils 2 sind. Demnach sind bei variablem Startpunkt alle Positionen gleich wahrscheinlich.

      Das lässt sich auch logisch begründen. Das Verschieben des Startpunkts um x nach rechts entspricht dem Verschieben aller Werte um x nach links bei gleichbleibendem Startpunkt. Dann ist aber nach 1000-x Verschiebungen genau die ursprüngliche Anordnung erreicht, es werden also genau dieselben Verschiebungen durch den Algorithmus gejagt, nur in einer anderen Reihenfolge.

      Da der Algorithmus nicht von der Reihenfolge seiner Aufrufe abhängt muss die Wahrscheinlichkeit daher vom Startpunkt unabhängig sein.

      Die Aufgabenstellung hat mich übrigens an meine Vorlesungen „Einführung in die Programmierung“ und „Paradigmen der Programmierung“ erinnert.

      Die Übungsblätter dazu habe ich echt genossen; eine Lösung zu programmiertechnischen Problemen zu finden ist eine Aufgabe mit sehr selbstbelohnendem Charakter.

      So viel Genugtuung wie ein gelöstes Programmierproblem hat mir ein selbst geglückter Beweis eines mathematischen Satzes noch nie bereitet.

      Grüße,

      RIDER

      --
      Camping_RIDER a.k.a. Riders Flame a.k.a. Janosch Zoller
      # Twitter # Steam # YouTube # Self-Wiki # Selfcode: sh:) fo:) ch:| rl:) br:^ n4:? ie:% mo:| va:) js:) de:> zu:} fl:( ss:) ls:[
      1. Tach!

        Ich hab da mal noch ein, zwei Gedanken zum Code, nicht zum Algorithmus.

            // provide default value for startnumber
            if (startnumber === undefined) startnumber = 1;
        

        Der schreibfaule Javascript-Programmierer kürzt sowas gern ab zu

        startnumber = startnumber || 1;
        

        und das gern auch ohne extra Zeile sondern nimmt lediglich den Teil nach dem = bei der ersten Verwendung (falls es die Situation zulässt).

        function findRemainingElements(elements, k, countoffset) {
            // elements must be an array
            if (!Array.isArray(elements)) return undefined;
            // und weitere Prüfungen der Parameter
        

        Wenn man davon ausgehen kann, dass diese Funktion lediglich eine Hilfsfunktion der eigentlich aufgerufenen findRemainingNumbers() ist, dann sind diese Prüfungen der übergebenen Parameter so hilfreich, wie sich die Schuhe anzuziehen und beim anschließenden Verlassen des Hauses nochmal zu prüfen, ob man Schuhe anhat. Hier wird die Funktion kontrolliert aufgerufen, mit Parametern, die passend initialisiert wurden und/oder deren Inhalt bereits geprüft wurde. In anderen Umgebungen (Typescript zum Beispiel) würde man diese Funktion als private Methode einer Klasse ausführen. (Ja, bekommt man auch mit Vanilla-JS hin, nur nicht ganz so einfach.)

        Wenn du allerdings davon ausgehst, dass sie soweit von nutzen ist, sie aus anderen Kontexten aufzurufen, dann wird man das wohl auch eher so machen müssen.

        Einige Prüfungen kann man sich aber auch dann sparen, nämlich die, wenn die Funktion lediglich ein unbrauchbares Ergebnis liefert, wenn unbrauchbare Eingabewerte übergeben werden, aber sonst nichts weiter kaputtgeht. Wer Garbage übergibt, kann nicht damit rechnen, keinen Garbage zurückzubekommen. Ob man so genau sein muss, den Aufrufer auf seine möglichen Fehler hinzuweisen, kann man sich trotzdem noch überlegen. In einigen Situationen ist das durchaus nicht unangebracht.

        Beim Entwickeln meiner Lösung hatte ich mir eine nicht eintretende Abbruchbedingung eingehandelt. Das hat dem Browser ganz schön zugesetzt. Solche Fälle vermeiden zu können, ist auf alle Fälle wert, eine entsprechende Prüfung einzubauen.

        dedlfix.

        1. Aloha ;)

              // provide default value for startnumber
              if (startnumber === undefined) startnumber = 1;
          

          Der schreibfaule Javascript-Programmierer kürzt sowas gern ab zu

          startnumber = startnumber || 1;
          

          Guter Hinweis! Ich hab tatsächlich jetzt schon ein paar Tage kein „echtes“ JavaScript mehr geschrieben, weil ich in der letzten Zeit durch meine Bachelorarbeit mehr mit TypeScript am Hut hatte.

          Wenn man davon ausgehen kann, dass diese Funktion lediglich eine Hilfsfunktion der eigentlich aufgerufenen findRemainingNumbers() ist, dann sind diese Prüfungen der übergebenen Parameter so hilfreich, wie sich die Schuhe anzuziehen und beim anschließenden Verlassen des Hauses nochmal zu prüfen, ob man Schuhe anhat.

          Andersrum wird ein Schuh draus (pun intended), denn...

          Wenn du allerdings davon ausgehst, dass sie soweit von nutzen ist, sie aus anderen Kontexten aufzurufen, dann wird man das wohl auch eher so machen müssen.

          Genau. Für mich war findRemainingElements die allgemeine Grundfunktionalität (z.B., um ein Array mit Gefangenen-Objekten zu übergeben) und findRemainingNumbers die Spezialfunktion für n natürliche Zahlen. Aber klar, demnach hätte man sich zumindest für k die Überprüfung bei findRemainingNumbers auch sparen können, denn k wird nur durchgereicht. Was die anderen Parameter angeht sind die Überprüfungen nicht ohne weiteres obsolet, auch wenn der Gedanke

          Wer Garbage übergibt, kann nicht damit rechnen, keinen Garbage zurückzubekommen.

          natürlich auch seine Berechtigung hat. Es kommt eben immer drauf an, gegenüber welchen Fehleingaben die Funktionalität wie gewappnet sein soll.

          Beim Entwickeln meiner Lösung hatte ich mir eine nicht eintretende Abbruchbedingung eingehandelt. Das hat dem Browser ganz schön zugesetzt. Solche Fälle vermeiden zu können, ist auf alle Fälle wert, eine entsprechende Prüfung einzubauen.

          Ja. Manche Prüfungen mögen nicht zwingend notwendig sein, bringen aber doch einiges an Komfort für den Entwickler, der damit arbeiten muss. JavaScript hat ja ganz grundsätzlich das „Problem“, nicht typisiert zu sein. In einer typisierten Sprache erledigen sich viele Überprüfungen schon von ganz alleine, daher halte ich es nicht für unangebracht, im nicht typisierten JavaScript solche Überprüfungen „manuell“ durchzuführen.

          Allerdings ist mein Code da an der Stelle auch nicht ganz päpstlich, denn statt undefined zurückzugeben sollte man dort vielleicht eher mit errors um sich werfen.

          Grüße,

          RIDER

          --
          Camping_RIDER a.k.a. Riders Flame a.k.a. Janosch Zoller
          # Twitter # Steam # YouTube # Self-Wiki # Selfcode: sh:) fo:) ch:| rl:) br:^ n4:? ie:% mo:| va:) js:) de:> zu:} fl:( ss:) ls:[
          1. Hallo Camping_RIDER,

            gerade bei einer rekursiv genutzten Funktion ist ein intensives Prüfen der Parameter pro Aufruf nicht effizient. In dem Fall sollte man eine interne Funktion verwenden, die die Rekursion durchführt, und vor dem Einstieg in die Rekursion genau 1x die Parameter prüfen.

            Und statt Array.isArray hätte man auch auf Duck Typing zurückfallen können, du brauchst lediglich ein Dings, das dings.length > 0 hat und eine Filter-Funktion kennt.

            Rolf

            --
            sumpsi - posui - clusi
      2. Die Aufgabenstellung hat mich übrigens an meine Vorlesungen „Einführung in die Programmierung“ und „Paradigmen der Programmierung“ erinnert.

        Die Übungsblätter dazu habe ich echt genossen; eine Lösung zu programmiertechnischen Problemen zu finden ist eine Aufgabe mit sehr selbstbelohnendem Charakter.

        So viel Genugtuung wie ein gelöstes Programmierproblem hat mir ein selbst geglückter Beweis eines mathematischen Satzes noch nie bereitet.

        Am schönsten ist es, wenn man beides kombiniert, sagt dir der Curry-Howard isomorphism etwas? Intuitiv sagt der aus, dass Programme in rein funktionalen Sprachen, das gleiche sind wie Beweise. Der Typ eines Ausdrucks kodiert einen Satz oder eine Proposition, die Implementierung ist der Beweis dafür, dass der Satz bzw. die Proposition unter gewissen Umständen hält. Um damit auch Beweise über nicht-triviale Eigenschaften machen zu können, muss das Typsystem der Programmiersprache allerdings auch über eine entsprechende Aussagekraft verfügen. Das trifft derzeit leider nicht mal auf Haskell zu, obwohl es sich dahin bewegt. Idris ist eine Programmiersprache, die extra für Programmier entworfen wurde um dieses Paradigma voranzutreiben. Für Mathematiker existieren schon länger vergleichbare "Programmiersprachen", z.B.Coq und Isabelle.