Получить единичку из любого натурального числа

[Ktina]

С десятичной записью натурального числа разрешается проделывать следующую операцию: выбрать две соседние цифры $d$ и $d'$ (причём $d$ стоит слева от $d'$, а в качестве $d$ можно выбрать также нуль (например, число 1234 можно представить как 01234 и выбрать 0 и 1)), стереть их и записать на их месте число $d+2d'$.

Доказать, что посредством конечного числа таких операций можно из любого натурального числа получить единичку.

[Shadow]

Достаточно показать, что любое двуцифренное можно превратить в 01. Ну и по очереди убирать по циферку. Достаточно проверить друцифренных до 27. (ясно почему)
Значит:
27,16,13,07,14,09,18,17,15,11,03,06,12,05,10,01. Чего еще не было? 26
26,14 - было
25,12 -
24,10 красота
23,08,16
22,06
и т.д
Конечно, продолжать до 1 имеет смысл только когда останется двуцифренное число. Иначе любой старший 0 уменьшает разрядность.

[Ktina]

Shadow, можно ещё чуть-чуть проще.

-- 24.09.2012, 14:07 --

Хотя, нет. У Вас тоже достаточно просто.

[Shadow]

Ktina в сообщении #622945 писал(а):

У Вас тоже достаточно просто

У меня даже тупо. Напишите красивое решение, а то остается впечатление, что задача из последей олимпиады специализированной школы. (для детей с частичной олигофрении "Павлик Морозов").

[Ktina]

Shadow в сообщении #622958 писал(а):

Ktina в сообщении #622945 писал(а):

У Вас тоже достаточно просто

У меня даже тупо. Напишите красивое решение, а то остается впечатление, что задача из последей олимпиады специализированной школы. (для детей с частичной олигофрении "Павлик Морозов").

Любое однозначное можно превратить в единичку:
2-4-8-16-13-7-14-9-18-17-15-11-3-6-12-5-10-1

Если число не однозначное и начинается с 19, то 019....--029....--020....--02....
Если же не начинается с 19, то тупо берём первые две цифры и производим разрешённую операцию. Полученное число всегда будет меньше исходного, а значит, рано или поздно станет однозначным.

[Shadow]

Так лучше. Мой перебор зациклит на 19

[_Ivana]

Цитата:

Любое однозначное можно превратить в единичку:
2-4-8-16-13-7-14-9-18-17-15-11-3-6-12-5-10-1

Если число не однозначное и начинается с 19, то 019....--029....--020....--02....
Если же не начинается с 19, то тупо берём первые две цифры и производим разрешённую операцию. Полученное число всегда будет меньше исходного, а значит, рано или поздно станет однозначным.

Мое решение такое же, за исключением последнего утверждения. Если начинается не с 1 - добавляем незначащий ноль и превращаем бывший первый значащий разряд в 1. Если далее 2 разряда получается 19 - действуем как написала Ktina - избавляемся от 9-ки, если не 19 - любое 1d при d <> 9 превращается в однозначное число (можно показать, проверив с 10 по 18), которое затем превращаем в единичку.

ЗЫ нелишне заметить, что при данной операции превращения мы никогда не получим ноль из ненулевого исходного числа, а то утверждение было бы неверно.

[Ktina]

_Ivana в сообщении #623082 писал(а):

ЗЫ нелишне заметить, что при данной операции превращения мы никогда не получим ноль из ненулевого исходного числа, а то утверждение было бы неверно.

Обобщая, можно сказать, что множество $\mathbb N$ замкнуто относительно операции, описанной в условии данной задачи. На этом и строится решение. Любое >1 значное можно уменьшить, а из любого однозначного сделать единичку. Если бы мы имели выход за рамки множества $\mathbb N$, этого было бы не достаточно, так как уменьшая число, являющееся более, чем однозначным, теоретически можно было "перескочить" через однозначные числа.

[_Ivana]

(Оффтоп)

function Ivana_int2one(int, hist)

if int == 1
    hist
    return
end

str = num2str(int);
d_1 = str2num(str(1));
str(1) = [];

if d_1 == 1
    d_2 = str2num(str(1));
    
    if d_2 == 9
        dd = 1;
        dd = fix(dd/10) + 2*mod(dd, 10); int = str2num([num2str(dd), str]); hist = [hist, int];
        
        str(1) = [];
        dd = 29;
        dd = fix(dd/10) + 2*mod(dd, 10); int = str2num([num2str(dd), str]); hist = [hist, int];
    else
        str(1) = [];
        dd = d_1*10 + d_2;
        while dd > 9
        dd = fix(dd/10) + 2*mod(dd, 10); int = str2num([num2str(dd), str]); hist = [hist, int];
        end
    end
else
    dd = d_1;
    while dd ~= 1
        dd = fix(dd/10) + 2*mod(dd, 10); int = str2num([num2str(dd), str]); hist = [hist, int];
    end
end

Ivana_int2one(int, hist);

Вызов

n = 49794591;
hist = n;
Ivana_int2one(n, hist);

[_Ivana]

(Оффтоп)

Поскольку возникают вопросы что это за код я написал сообщением выше, привожу результат его работы - массив последовательных превращений числа 49794591, слева направо сверху вниз. По алгоритму, описанному мной выше.

Columns 1 through 8

    49794591    89794591   169794591   139794591    79794591   149794591    99794591   189794591

  Columns 9 through 16

   179794591   159794591   119794591    39794591    69794591   129794591    59794591   109794591

  Columns 17 through 24

    19794591    29794591    20794591    40794591    80794591   160794591   130794591    70794591

  Columns 25 through 32

   140794591    90794591   180794591   170794591   150794591   110794591    30794591    60794591

  Columns 33 through 40

   120794591    50794591   100794591    10794591     1794591     1594591     1194591      394591

  Columns 41 through 48

      694591     1294591      594591     1094591      194591      294591      204591      404591

  Columns 49 through 56

      804591     1604591     1304591      704591     1404591      904591     1804591     1704591

  Columns 57 through 64

     1504591     1104591      304591      604591     1204591      504591     1004591      104591

  Columns 65 through 72

       14591        9591       18591       17591       15591       11591        3591        6591

  Columns 73 through 80

       12591        5591       10591        1591        1191         391         691        1291

  Columns 81 through 88

         591        1091         191         291         201         401         801        1601

  Columns 89 through 96

        1301         701        1401         901        1801        1701        1501        1101

  Columns 97 through 104

         301         601        1201         501        1001         101          11           3

  Columns 105 through 109

           6          12           5          10           1

[Shadow]

А так быстрее

  49794591
  22794591
   6794591
   2094591
    294591
    204591
     24591
     10591
      1591
      1191
       391
       211
        41
         6
        12
         5
        10
         1

[_Ivana]

Цитата:

А так быстрее

Вы правы. Но я не оптимизировал свой алгоритм ни в смысле минимизации количества шагов преобразований исходного числа, ни в смысле минимизации объема кода или требуемого объема ОЗУ при выполнении. Я просто реализовал гарантированный простой алгоритм, который придумал. Или Вы предлагаете поставить и решить в общем виде задачу минимизации алгоритма по какому-либо из вышеназванных критериев?

[Shadow]

В общем виде не берусь, но в любом случае, отусутствие лишнего условия улучшит алгоритм как

_Ivana в сообщении #623387 писал(а):

в смысле минимизации количества шагов преобразований исходного числа

так и

_Ivana в сообщении #623387 писал(а):

в смысле минимизации объема кода

[_Ivana]

Уговорили, оптимизировал
UPD, исправил ошибку

function Ivana_int2one_1(int, hist)

if int == 1
    hist
    return
    
elseif int > 9
    str = num2str(int);
    dd = str2num(str(1:2));
    str(1:2) = [];

    while dd > 9
        if dd == 19
            dd = 29;
        else
            dd = fix(dd/10) + 2*mod(dd, 10);
        end
        int = str2num([num2str(dd), str]); hist = [hist, int];
    end
    
else
    while int ~= 1
        int = fix(int/10) + 2*mod(int, 10); hist = [hist, int];
    end
    
end
Ivana_int2one_1(int, hist);

    49794591    22794591     6794591     2094591      294591      204591       24591       10591
        1591        1191         391         211          41           6          12           5
          10           1