C :: Aufgabe #148
1 Lösung
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:
Konsolenausgabe:
4-stellige Zahl eingeben : 7392
Die Kaprekar-Konstante ist: 6174
C-Code
/******************************************** * kaprekar.c Kaprekar-Konstante für nnnn ********************************************/ #include <stdlib.h> #include <stdio.h> #define LSIZE 4 /* size of digits array */ #define swap(a,b,t) {t=(a);a=(b);b=(t);} /* swap values for sorting */ enum so_t {ASCENDING, DESCENDING}; /* sorting order */ /* digits array to integer number */ int a2i(int *arr, size_t n) { int pow=1, sum=0; while (n) { sum += arr[--n] * pow; pow *= 10; } return sum; } /* integer number to digits array */ int *i2a(int *arr, size_t n, int d) { while (d) { arr[--n] = d % 10; d /= 10; } return arr; } /* sorting with simple bubble sort */ void sort_int(int list[], size_t n, enum so_t so) { int i, j, t, sign; sign = (so==DESCENDING)?-1:1; for (i=0; i < n-1; i++) for (j=0; j<n-i-1; j++) if (sign*list[j] > sign*list[j+1]) swap(list[j], list[j+1], t); } /* main */ int main() { int ad[LSIZE]; int d,d1,d2,dn; /* input number (w/o checking) */ printf("%d-stellige Zahl eingeben : ", LSIZE); scanf("%u", &dn); /* iteration */ do { d = dn; sort_int(i2a(ad, LSIZE, d), LSIZE, DESCENDING); d1 = a2i(ad, LSIZE); sort_int(i2a(ad, LSIZE, d), LSIZE, ASCENDING); d2 = a2i(ad, LSIZE); dn = d1-d2; } while (dn != d); printf("Die Kaprekar-Konstante ist: %d\n", d); return 0; }