Udowodnij, że algorytm 6174(Kaprekar's constant) ma własność stopu.

Podobnie udowodnij to dla wersji tego algorytmu z trzema cyframi z liczbą 495 zamiast 6174.

podpowiedź:Sprowadź dowód do jak najmniejszej liczby przypadków, np. możesz tylko rozważać liczby o niemalejących ciagach czterech cyfr.

źródło//wazniak.mimuw.edu.pl/index.php?title=ASD_%C4%86wiczenia_1

Algorytm 6174

n jest czterocyfrową liczbą naturalną niepodzielną przez 1111
// pierwszymi cyframi n mogą być zera
1 while (n<>6174) do

2 n1 := największa liczba czterocyfrowa, której cyfry są permutacją cyfr liczby n;
3 n2 := najmniejsza liczba czterocyfrowa, której cyfry są permutacją cyfr liczby n;
4 n := n1 - n2

Czy rzeczywiście trzeba potraktować to "brutalnie" i sprawdzać tysiące przypadków programem czy ktoś ma jakiś lepszy pomysł?

zrobiłem taki programik który to sprawdza:

#include <stdio.h>

int main()
{
    int i, n = 4, j, A[4], B[4], temp = 0, c = 0, d = 0, k, l, h, g;
    A[0] = 1;
    A[1] = 2;
    A[2] = 3;
    A[3] = 4;
    c = 1234;

    for (g = 1; g < 10; ++g)
        for (h = 1; h < 10; ++h)
            for (k = 1; k < 10; ++k)
                for (l = 4; l < 10; ++l) {
                    A[0] = g;
                    A[1] = h;
                    A[2] = k;
                    A[3] = l;

                    c = 1000 * A[0] + 100 * A[1] + 10 * A[2] + A[3];
                    printf("\n %d \n ", c);
                    if (c % 1111 == 0 || c == 6174)
                        continue;

                    while (c != 6174) {

                        for (i = 0; i < n; ++i)
                            for (j = 1; j < n; ++j)
                                if (A[j - 1] < A[j]) {
                                    temp = A[j];
                                    A[j] = A[j - 1];
                                    A[j - 1] = temp;
                                }

                        for (i = 0, j = 3; i < n; ++i, --j) {

                            B[i] = A[j];
                        }

                        printf("\n c jest rowne %d \n", c);
                        c = 1000 * A[0] + 100 * A[1] + 10 * A[2] + A[3];
                        d = 1000 * B[0] + 100 * B[1] + 10 * B[2] + B[3];
                        c = c - d;
                        printf("\n c jest rowne %d \n", c);

                        A[0] = c / 1000;
                        A[1] = c / 100 - (c / 1000) * 10;
                        A[2] = c / 10 - (c / 1000) * 100 - A[1] * 10;
                        A[3] = c - A[0] * 1000 - A[1] * 100 - A[2] * 10;
                    }
                }
}

wersja na 495

 #include <stdio.h>

int main()
{
    int i, n = 3, j, A[3], B[3], temp = 0, c = 0, d = 0, k, l, h, g;
    A[0] = 1;
    A[1] = 2;
    A[2] = 3;

    c = 123;

    for (g = 1; g < 10; ++g)
        for (h = 1; h < 10; ++h)
            for (k = 2; k < 10; ++k) {

                A[0] = g;
                A[1] = h;
                A[2] = k;

                c = 100 * A[0] + 10 * A[1] + A[2];
                printf("\n %d \n ", c);
                if (c % 111 == 0 || c == 495)
                    continue;

                while (c != 495) {

                    for (i = 0; i < n; ++i)
                        for (j = 1; j < n; ++j)
                            if (A[j - 1] < A[j]) {
                                temp = A[j];
                                A[j] = A[j - 1];
                                A[j - 1] = temp;
                            }

                    for (i = 0, j = 2; i < n; ++i, --j) {

                        B[i] = A[j];
                    }

                    printf("\n c jest rowne %d \n", c);
                    c = 100 * A[0] + 10 * A[1] + A[2];
                    d = 100 * B[0] + 10 * B[1] + B[2];
                    c = c - d;

                    A[0] = c / 100;
                    A[1] = c / 10 - (c / 100) * 10;
                    A[2] = c - (c / 100) * 100 - A[1] * 10;
                }
            }
}