Existiert die Kaprekar-Konstante?

1 Lösung

#148

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 devnull (8870 Punkte) - 01.03.2017 um 22:37 Uhr

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;
}