C# :: Aufgabe #165
4 Lösungen
Existiert die Kaprekar-Konstante?
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?
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?
Lösungen:
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;
}
}
}
C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Globalization;
namespace kaprekar {
class Program {
static void Main() {
String LZ = " ";
ulong digits = 4;
String input = String.Empty;
List<ulong> constanten = new List<ulong>();
double BASIS = 10;
ulong imax = (ulong)Math.Pow(BASIS, digits);
((imax - 1).ToString("n0") + LZ + ulong.MaxValue.ToString("n0")).Message();
for (ulong i = 1; i < imax; i++) {
input = i.ToString();
String sD1 = input.Sort(true, digits);
String sD2 = input.Sort(false, digits);
NumberStyles style = NumberStyles.Integer;
ulong D, D1, D2;
List<ulong> LD = new List<ulong>();
int circle = 0;
int steps = 0;
while (true) {
D1 = ulong.Parse(sD1, style);
D2 = ulong.Parse(sD2, style);
D = D1 - D2;
if (LD.Contains(D)) {
circle = LD.Count - LD.IndexOf(D);
if (circle == 1) {
if (!constanten.Contains(D)) {
("add " + D.ToString("n0") + LZ + D.ToString("X") +
" steps: " + steps.ToString()).Message();
constanten.Add(D);
}
}
break;
}
else
if (D != 0)
LD.Add(D);
else
break;
String sD = D.ToString();
sD1 = sD.Sort(true, digits);
sD2 = sD.Sort(false, digits);
steps++;
};
}
"Kaprekar-Konstanten:".Message();
for(var i = 0; i < constanten.Count; i++)
(constanten[i].ToString("n0") + LZ + constanten[i].ToString("X")).Message();
"ready".EndMessage();
}
}
public static class MyKaprekar {
public static string Sort(this string s, Boolean bo_downward, ulong digits) {
while ((ulong)s.Length < digits)
s = "0" + s;
String result = string.Empty;
Char[] c = s.ToCharArray();
Array.Sort(c);
for (var i = 0; i < c.Length; i++)
if (!bo_downward)
result += c[i].ToString();
else
result += c[c.Length - 1 - i].ToString();
return result;
}
public static void Message(this string s) {
Console.WriteLine(s);
}
public static void EndMessage(this string s) {
s.Message(); Console.ReadKey();
}
}
}
C#-Codenamespace 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;
}
}
}
C#-Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace KapKon
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Geben Sie eine vierstellige Zahl ein, welche nicht vier identische Stellen hat\n" +
"Mit exit schließen Sie das Programm");
String d = Console.ReadLine();
int number;
while((d.Length != 4 || !(int.TryParse(d, out number)) || (d.Distinct().Count() == 1))||d == "exit")
{
if (d == "exit")
{
System.Environment.Exit(1);
}
else
{
Console.WriteLine("Fehlerhafte Eingabe! Versuchen Sie es erneut\n\n");
d = Console.ReadLine();
}
}
String dnew = "";
dnew = doWork(d);
while (dnew.CompareTo(d) != 0)
{
d = "" + dnew;
dnew = doWork(dnew);
//Console.WriteLine(check);
}
Console.WriteLine("Die Kaprekar-Zahl lautet {0}.", d);
Console.ReadKey();
}
public static String doWork(String _d)
{
String d1 = descOrder(_d);
String d2 = ascOrder(_d);
String _dnew = SubstractStrings(d2.PadLeft(4,'0'),d1.PadRight(4,'0'));
Console.WriteLine(d1 + " - " + d2 + "="+_dnew);
return _dnew;
}
public static String SubstractStrings(String _d1, String _d2)
{
String dnew = ""+((Int32.Parse(_d2)) -(Int32.Parse(_d1)));
return dnew;
}
public static String descOrder(String _d)
{
Char[] splittedString = new Char[4];
splittedString = _d.ToCharArray();
if (_d.Distinct().Count() != 1)
{
Array.Sort<Char>(splittedString);
Array.Reverse(splittedString);
}
String reverseD = new String(splittedString);
return reverseD;
}
public static String ascOrder(String _d)
{
Char[] splittedString = new Char[4];
splittedString = _d.ToCharArray();
Array.Sort(splittedString);
String ascD = new String(splittedString);
return ascD;
}
}
}