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 Umfegumfe (50 Punkte) - 27.02.2017 um 09:44 Uhr

C#-Code

namespace Kaprekar
{
    class Program
    {
        static void Main(string[] args)
        {
            int d = GetKaprekarStart();
            int kaprekar = GetKaprekarNumber(d);
            Console.WriteLine("Die vierstellige Kaprekar-Zahl lautet {0}!", kaprekar);
            Console.WriteLine("Bitte Taste drücken!");
            Console.ReadKey();
        }

        static int GetKaprekarNumber(int startNumber)
        {
            int[] digits = NumberToFourDigitArray(startNumber);
            int[] sortedDigits = sortedFourDigitArray(digits);
            int[] sortedDigitsInverted = invertDigitArray(digits);
            int d1 = digitArrayToInt(sortedDigitsInverted);
            int d2 = digitArrayToInt(sortedDigits);
            int d = d1 - d2;
            Console.WriteLine("Zwischenschritt: d={0}, d1={1}, d2={2}, d1-d2={3}...", startNumber, d1, d2, d);
            if (d == startNumber) return d;
            return GetKaprekarNumber(d);
        }

        static int GetKaprekarStart()
        {
            while (true)
            {
                Console.Write("Bitte vierstellige Startzahl eingeben: ");
                string s = Console.ReadLine();
                int number = Convert.ToInt32(s);
                if (number > 0 && number < 10000)
                {
                    if (IsNumberValidForKaprekar(number)) return number;
                }
                Console.WriteLine("Keine gültige Startzahl, bitte wiederholen!");
            }
        }

        static bool IsNumberValidForKaprekar(int number)
        {
            int[] kaprekarDigits = NumberToFourDigitArray(number);
            int start = kaprekarDigits[0];
            for (int i = 1; i < kaprekarDigits.Length; i++)
            {
                if (kaprekarDigits[i] != start) return true;
            }
            return false;
        }

        static int[] NumberToFourDigitArray(int number)
        {
            int[] retVal = new int[4];
            for (int i = 0; i < 4; i++)
            {
                retVal[i] = number % 10;
                number = number / 10;
            }
            return retVal;
        }

        static int[] sortedFourDigitArray(int[] digits)
        {
            bool sorted;
            do
            {
                sorted = true;
                for (int i = 0; i < digits.Length - 1; i++)
                {
                    if (digits[i] > digits[i + 1])
                    {
                        int temp = digits[i];
                        digits[i] = digits[i + 1];
                        digits[i + 1] = temp;
                        sorted = false;
                    }
                }
            } while (!sorted);
            return digits;
        }

        static int[] invertDigitArray(int[] digits)
        {
            int[] retVal = new int[digits.Length];
            for (int i = 0; i < digits.Length; i++)
            {
                retVal[i] = digits[digits.Length - i - 1];
            }
            return retVal;
        }

        static int digitArrayToInt(int[] digits)
        {
            int retVal = 0;
            int multiplier = 1;
            int[] invertedDigits = invertDigitArray(digits);
            for (int i = 0; i < invertedDigits.Length; i++)
            {
                retVal = retVal + invertedDigits[i] * multiplier;
                multiplier = multiplier * 10;
            }
            return retVal;
        }
    }
}