Feedback

C# - Josephus Problem lösen

Veröffentlicht von am 17.07.2013
(0 Bewertungen)
Mithilfe der jeweiligen Solve-Methode aus der hier geposteten JosephusProblem-Klasse kann man ohne viel Aufwand das Josephus-Problem lösen. Einfacher gesagt: Man kann heraus finden, wer bei einem Abzählreim übrig bleibt.

Dabei kann man entweder angeben, wie viele Elemente eine Liste enthält oder eine Liste/Array übergeben um ein spezielles Element zu erhalten.
GFU-Schulungen  [Anzeige]

XML und .NET Überblick

Um auf dem neuesten Wissensstand zu sein, sollten Sie unser aktuelles ASP .NET Komplett Seminar belegen.
Nach dem Seminar kennen Sie die wichtigsten Strömungen in der Software-Technologie

ASP.NET 2.0 und 3.5

Dieser Kurs vermittelt Ihnen alle Erweiterungen von Microsoft ASP.NET 2.0. Zu diesen zählen u. a. Data Bindung, Master Pages, und Security.

    /// <summary>
    /// Stellt Methoden zum lösen des Josephus Problems bereit.
    /// </summary>
    public static class JosephusProblem
    {
        /// <summary>
        /// Löst das Josephus Problem mit spezifischen Werten auf. Die Lösung ist nicht nullbasiert.
        /// </summary>
        /// <param name="n">Die Anzahl von Elementen im Kreis.</param>
        /// <param name="s">Die Schrittzahl, alle derer ein Element aus dem Kreis entfernt wird.</param>
        /// <returns>Die Position, auf welche aufgelöst wurde. Diese ist nicht nullbasiert!</returns>
        public static int Solve(int n, int s)
        {
            int pos = 1;
            _CheckValues(n, s, ref pos);

            if (n == 1&&pos==1)
                return 1;
            if (s == 1&&pos==1)
                return n;    

            return _Solve(n , s, pos);
        }

        /// <summary>
        /// Löst das Josephus Problem mit spezifischen Werten auf. Die Lösung ist nicht nullbasiert.
        /// </summary>
        /// <param name="n">Die Anzahl von Elementen im Kreis.</param>
        /// <param name="s">Die Schrittzahl, alle derer ein Element aus dem Kreis entfernt wird.</param>
        /// <param name="pos">Beschreibt das Element, welches beim ersten Abzählen die 1 ist. Dies ist im Normalfall das 1.</param>
        /// <returns>Die Position, auf welche aufgelöst wurde. Diese ist nicht nullbasiert!</returns>
        public static int Solve(int n, int s, int pos)
        {
            _CheckValues(n, s, ref pos);

            if (n == 1&&pos==1)
                return 1;
            if (s == 1&&pos==1)
                return n;    

            return _Solve(n , s, pos);
        }

        /// <summary>
        /// Wählt durch lösen des Josephus Problems ein Element aus einem Array aus.
        /// </summary>
        /// <typeparam name="T">Der Typ des Arrays und der Rückgabe.</typeparam>
        /// <param name="elements">Das Array, welches die Elemente enthält.</param>
        /// <param name="s">Die Schrittzahl, alle derer ein Element aus dem Kreis (dem Array) entfernt wird.</param>
        /// <returns>Das Element, aus dem Array, welches nach der Lösung des Josephus Problems übrig bleibt.</returns>
        public static T Solve<T>(IList<T> elements, int s)
        {
            if (elements == null)
                throw new ArgumentNullException("elements", "elements != null AND elements.Count >= 1!");
            int pos = 1;
            return elements[Solve(elements.Count, s, pos) - 1];
        }

        /// <summary>
        /// Wählt durch lösen des Josephus Problems ein Element aus einem Array aus.
        /// </summary>
        /// <typeparam name="T">Der Typ des Arrays und der Rückgabe.</typeparam>
        /// <param name="elements">Das Array, welches die Elemente enthält.</param>
        /// <param name="s">Die Schrittzahl, alle derer ein Element aus dem Kreis (dem Array) entfernt wird.</param>
        /// <param name="pos">Beschreibt das Element, welches beim ersten Abzählen die 1 ist. Dies ist im Normalfall das 1.</param>
        /// <returns>Das Element, aus dem Array, welches nach der Lösung des Josephus Problems übrig bleibt.</returns>
        public static T Solve<T>(IList<T> elements, int s, int pos)
        {
            if (elements == null)
                throw new ArgumentNullException("elements", "elements != null AND elements.Count >= 1!");
            return elements[Solve(elements.Count, s, pos) - 1];
        }

        #region Hilfsmethoden

        /// <summary>
        /// Löst das Josephus Problem. Die Parameter sind die selben wie in der Public-Version.
        /// </summary>
        private static int _Solve(int n, int s, int pos)
        {
            if (n == 1)
                return 1;

            int newSp = (pos + s - 2) % n + 1;

            int survivor = _Solve(n - 1, s, newSp);
            if (survivor < newSp)
            {
                return survivor;
            }
            else
                return survivor + 1;

        }

        /// <summary>
        /// Erhöhrt <paramref name="pos"/> solange um <paramref name="stride"/> bis <paramref name="pos"/> größer als 0 ist.
        /// </summary>
        /// <param name="pos">Die Startposition zum lösen.</param>
        /// <param name="stride">Die Schrittzahl, alle derer ein Element aus dem Kreis (dem Array) entfernt wird.</param>
        private static int _MakePositionPositive(int pos, int stride)
        {
            while(pos<=0)
            {
                pos += stride;
            }
            return pos;
        }

        /// <summary>
        /// Überprüft die Parameter auf Falscheingabe.
        /// </summary>
        /// <returns><c>True</c>, wenn alles korrekt übergeben wurde. Andernfalls <c>False</c> oder es wird eine Exception geworfen.</returns>
        private static bool _CheckValues(int n, int s, ref int pos)
        {
            if (n < 1)
                throw new ArgumentOutOfRangeException("n", "n >= 1!");
            if (s < 1)
                throw new ArgumentOutOfRangeException("s", "s >= 1!");        

            if (pos <= 0)//Startposition in einen Bereich größer 0 bringen, um die Indizes anzugleichen
                pos = _MakePositionPositive(pos, s);

            return true;
        }

        #endregion
    }
Abgelegt unter Josephus, Abzählen, Liste, Array.

Kommentare zum Snippet

 

Logge dich ein, um hier zu kommentieren!