Алгоритм действия над произвольным (n+1)-значным числом

[_v_l]

Заранее прошу извинить за название, оно возможно не полностью отражает суть задачи.

Преамбула:
Есть простая задачка (источник):

Цитата:

Возраст человека в 1998 г. оказался равным сумме цифр года его рождения. Сколько ему лет?

Задачу просто решить аналитически и найти ответ (18,1980).

По ходу решения созрел план написать простую программу, которая бы находила возраст и год рождения для произвольного года рождения из XX и XXI веков. Организовал всё просто (до безобразия; я не программист по образованию, но программированию учили): 4 вложенных цикла, в каждом переменная пробегает значение от 0 до 9.

Дальше --- больше. Захотелось найти "все" решения, т.е. распутать цепочку:
если
a=заданное число
b=год рождение
в следующем цикле a=b и т.д. пока не дойдём до 1 или 0. Что ж сложного написал.

Но программа (была на C или C++) работала не столь уж шустро. А потом пришла мысль взять произвольное (n+1)-значное число (только чтобы вмешалось в unsigned long). Уже ни о каких вложенных циклах речи быть не может: тут нужен анализ задачи.

Задача:

Пусть нам дано произвольное $(n+1)$-значное число $p$ (рассматриваем только натуральные числа, как в исходной задаче и предполагалось), запишем его десятичное разложение
$p=a_{n}10^{n}+\ldots+a_{0}$.
Нужно найти такое число $k$ (оно тоже должно быть $(n+1)$-значным, это очевидно, но не доказывал)
$k=b_{n}10^{n}+\ldots+b_{0}$
что
$p-k=b_{0}+\ldots+b_{n}.$

Рассмотрим для простоты анализа $n=3$, имеем
$(a_{3}-b_{3})10^{3}+(a_{2}-b_{2})10^{2}+(a_{1}-b_{1})10+(a_{0}-b_{0})=b_{0}+b_{1}+b_{2}+b_{3}.$
Правая часть не может быть больше 36, поэтому возможны два варианта:

1. $b_{3}=a_{3}$.
   Этот случай приводит к двум вариантам для $b_{2}$:
   
   1. $b_{2}=a_{2}$, дальше перебор: $b_{1}\leqslant a_{1}$, $0\leqslant b_{0}\leqslant 9$
   2. $b_{2}=a_{2}-1$, дальше перебор: $0\leqslant b_{1}\leqslant 9$, $0\leqslant b_{0}\leqslant 9$
2. $b_{3}=a_{3}-1$.
   Второй случай приводит к $b_{2}=a_{2}-9$ и перебору $0\leqslant b_{1}\leqslant 9$, $0\leqslant b_{0}\leqslant 9$.

Таким образом количество циклов (переборов) уменьшилось.

Если $n$ число произвольное, тогда начиная с $l=[\lg(n+1)]+1$ порядка начинается полный перебор или перебор с ограничением. Для остальных возможны только случаи $b_{i}=a_{i}$ или $b_{i}=a_{i}-1$ и т.д.

Встал вопрос о том, как реализовать этот алгоритм на C++.

Вижу это так: задаётся число, определяю цифры, из которых состоит число, записываю их хитрую структуру, и прохожу её (как дерево) от верха ($a_{n}$) до низу ($a_{0}$) и определяю $b_{i}$.

Может есть более простой вариант?

[12d3]

_v_l в сообщении #253607 писал(а):

Может есть более простой вариант?

Есть.

int summa_cifr(int x) {
   int s=0;
   while (x) {
        s +=  x%10;
        x /= 10;
   }
   return s;
}
int main() {
    int a;
    cin<<a;
    for (int i=0;i<200;i++) {
        if (i == summa_cifr(a-i))    cout<<a-i<<endl;
    }
    return 0;
}

Код не компилировал, проверяйте сами.

[Circiter]

212d3
С точностью до орфографии все работает как надо.

Вот, "причесал" немного код:

#include <iostream>

typedef unsigned long ulong;

ulong Sum(ulong Number)
{
    ulong Result=0;
    do Result+=Number%10; while(Number/=10);
    return Result;
}

int main()
{
    ulong Year;

    std::cin >> Year;

    for(ulong Age=0; Age<Year; Age++)
        if(Age==Sum(Year-Age))
            std::cout << Year-Age << std::endl;

    return 0;
}

2_v_l

Цитата:

оно тоже должно быть $(n+1)$-значным, это очевидно, но не доказывал

Это не так. Контрпример (первый попавшийся) для $p=12$: $k=6$. На деле, $k\leqslant p$ (год рождения не может превосходить "текущий" год).

Вы доказывали, что для любого целого $p$ решение ($k$), вообще говоря, не единственно (а для некоторых $p$ решений не существует)?

P.S.: Интересно, можно ли вывести прямую формулу, без цикла?

[venco]

Можно сделать рекурсией по номеру цифры, плюс условие, что возраст и год рождения должны быть равны по модулю 9 (если не учитывать ситуацию, что день рождения в текущем году ещё не настал).

[_v_l]

Circiter в сообщении #253695 писал(а):

Вот, "причесал" немного код:
Код:

#include <iostream>

typedef unsigned long ulong;

ulong Sum(ulong Number)
{
    ulong Result=0;
    do Result+=Number%10; while(Number/=10);
    return Result;
}

int main()
{
    ulong Year;

    std::cin >> Year;

    for(ulong Age=0; Age<Year; Age++)
        if(Age==Sum(Year-Age))
            std::cout << Year-Age << std::endl;

    return 0;
}

Идею понял.

Да, я не программист по натуре и образованию .

Circiter в сообщении #253695 писал(а):

2_v_l

Цитата:

оно тоже должно быть $(n+1)$-значным, это очевидно, но не доказывал

Это не так. Контрпример (первый попавшийся) для $p=12$: $k=6$. На деле, $k\leqslant p$ (год рождения не может превосходить "текущий" год).

Моя вина, я имел в виду $n>4$, для $n<4$ проще не организовывать сложный алгоритм, а просто перебрать все варианты. Как оказалось, я вообще не в том направлении двигался.

Circiter в сообщении #253695 писал(а):

Вы доказывали, что для любого целого $p$ решение ($k$), вообще говоря, не единственно (а для некоторых $p$ решений не существует)?

Нет, но процессе работы над первой версией программы обнаружил, что возможны два решения. Кстати, если посмотреть на мой алгоритм (нет, просто рассуждения), то возможны двойные решения. Возможны, но опять-таки не проверял, тройные и большее количество решений. Меня заинтересовала длина цепочки, см. мой первый пост.

Circiter в сообщении #253695 писал(а):

P.S.: Интересно, можно ли вывести прямую формулу, без цикла?

Если честно, то не понял суть вопроса. Если вы имеете в виду конечную алгебраическую/арифметическую формулу, то незнаю, получится ли, т.к. возможны более чем два решения.

P.S. На разработку такого странного алгоритма меня натолкнуло не только то, что я не программист, но и то, что при больших $p$, количество циклов остаётся ограниченным (я не прав?), или, скорее всего так, количество бесполезных циклов уменьшается.

Приведённый код работает отлично для малых чисел (1998, 9999, 10001). Но я попробовал его при 12345678910, сразу появилось решение 12345678860 и долгая пауза. Очевидно, что других решений не будет (если $k$ имеет другую кратность чем $p$, о чём говорил выше, но не выделил особо) и цикл будет работать в пустую.

А теперь вспомним, что unsigned long это до $2^{32}$, а unsigned long long это до $2^{64}$. Так что в холостую тратить ресурсы нас научили