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.
    /// <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!