Existiert die Kaprekar-Konstante?

4 Lösungen

#165

Anfänger - C# von hollst - 23.02.2017 um 13:29 Uhr

Man weise numerisch nach, ob die Behauptung des indischen Mathematikers Kaprekar richtig ist.

Kaprekar hat folgendes behauptet (1949):

1.) Man nehme eine vierstellige Dezimalzahl D, wobei nicht alle vier Stellen identisch sein dürfen
(also 1111, 2222 etc. sind nicht erlaubt, aber z. B. 0001 ist erlaubt).
2.) D überführe man in zwei Zahle D1 und D2, indem bei D1 die Digits in absteigender und bei D2 in aufsteigender Reihenfolge
angeordnet werden (also z. B. D = 1724 -> D1 = 7421 und D2 = 1247; oder D = 1 -> D1 = 1000 und D2 = 1).
3.) Man subtrahiere nun D2 von D1; mit dem Ergebnis (Dneu = D1 - D2) wiederhole man Pkt. 2 durch Ersetzen von D durch Dneu solange,
bis sich nichts mehr ändert.

Die unglaubliche Behauptung ist, dass bei diesem Algorithmus stets das gleiche Ergebnis herauskommt (die sogenannte Kaprekar-Konstante),
egal, mit welchem D man beginnt.

Frage: Wie lautet die Kaprekar-Konstante?

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von Mexx (2370 Punkte) - 24.02.2017 um 18:09 Uhr

C#-Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace A165_KaprekarKonstante
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = string.Empty;
            int zahl;
            do
            {
                Console.WriteLine("Geben Sie eine beliebige vierstellige Zahl ein, welche keine Schnapszahl ist!\n" + 
                    "Mit exit schließen Sie das Programm");
                input = Console.ReadLine();

                //Eingabe Prüfen
                if (input.Length != 4 || !int.TryParse(input, out zahl))
                {
                    Console.WriteLine("Fehlerhafte Eingabe! Versuchen Sie es erneut\n\n");
                    continue;
                }

                //Kaprekarkonstante errechnen
                int kaprekarKonstante = KaprekarKonstanteErmitteln(zahl);
                string output;

                if (kaprekarKonstante == 0)
                    output = "\nDas Ergebnis der berechnung ist 0... Haben Sie eine Schnapszahl eingegeben?!\n\n";
                else
                    output = string.Format("\nDie Kaprekar-Konstane lautet: {0}\n\n", kaprekarKonstante);
                Console.WriteLine(output);

            } while (input != "exit");
        }

        /// <summary>
        /// Hilfsvariable für die Funktion KaprekarKonstanteErmitteln
        /// </summary>
        static int memory = 0;

        /// <summary>
        /// Ermittelt die Kaprekar-Konstante für die übergebene vierstellige Zahl
        /// </summary>
        /// <param name="zahl">Zahl für die die Kaprekarkonstante ermittelt werden soll</param>
        /// <returns>Die Kaprekar-Konstante oder Null, falls eine Schnapszahl eingegeben wurde</returns>
        private static int KaprekarKonstanteErmitteln(int zahl)
        {
            //Zahl zurückgeben, falls sich durch die letzte Berechnung keine Änderung ergeben hat
            if (zahl == memory)
                return zahl;

            #region Größte Zahl bilden
            //Zahl als Byte-Liste mit den binären Werten des Zeichens speichern
            List<byte> digits = ASCIIEncoding.UTF8.GetBytes(zahl.ToString()).ToList();
            string d1 = string.Empty;

            //Liste digits mit Nullen füllen, falls Zahl weniger als vier Stellen hat
            while (digits.Count < 4)
                digits.Add(ASCIIEncoding.UTF8.GetBytes("0")[0]);

            //Größtmögliche Zahl bilden
            while (digits.Count > 0)
            {
                //Zeichen mit dem aktuell größten Wert ermitteln und an d1 anhängen
                d1 += ASCIIEncoding.UTF8.GetString(new byte[] { digits.Max() });

                //Zuletzt ermitteltes Zeichen aus der Liste löschen
                byte currentDigit = digits.Max();
                for (int i = 0; i < digits.Count; i++)
                {
                    if (digits[i] == currentDigit)
                    {
                        digits.RemoveAt(i);
                        break;
                    }
                }
            }
            #endregion

            #region Kleinste Zahl bilden
            //Zahl als Byte-Liste mit den binären Werten des Zeichens speichern
            digits = ASCIIEncoding.UTF8.GetBytes(zahl.ToString()).ToList();
            string d2 = string.Empty;

            //Liste digits mit Nullen füllen, falls Zahl weniger als vier Stellen hat
            while (digits.Count < 4)
                digits.Add(ASCIIEncoding.UTF8.GetBytes("0")[0]);

            //Kleinstmögliche Zahl bilden
            while (digits.Count > 0)
            {
                //Zeichen mit dem aktuell kleinsten Wert ermitteln und an d2 anhängen
                d2 += ASCIIEncoding.UTF8.GetString(new byte[] { digits.Min() });

                //Zuletzt ermitteltes Zeichen aus der Liste löschen
                byte currentDigit = digits.Min();
                for (int i = 0; i < digits.Count; i++)
                {
                    if (digits[i] == currentDigit)
                    {
                        digits.RemoveAt(i);
                        break;
                    }
                }
            }
            #endregion

            //Berechnen
            int iD1 = int.Parse(d1);
            int iD2 = int.Parse(d2);
            int iNeu = iD1 - iD2;

            //Zuletzt berechnete Zahl zwischenspeichern und Funktion mit dieser erneut aufrufen
            memory = zahl;
            KaprekarKonstanteErmitteln(iNeu);

            //Errechnete Kaprekar-Konstante zurückgeben
            return memory;
        }
    }
}