Генератор чисел с фиксированной суммой цифр

chess

Вывести все такие числа из диапазона [0-999999999],
для каждого из которых сумма всех входящих цифр равна 9
и в которых при этом нет нулевых цифр.
Вывести также общее количество таких чисел.

Порядок вывода искомых чисел произвольный,
но выводимые числа не должны повторяться.

Пример результата вывода:
9 18 81 27 72 36 63 .... 111111111 256
где 256 - общее количество искомых чисел

Основной критерий оценки - скорость исполнения.

chess

Для начала лобовой способ решения путем фильтрации(само собой медленный)

Код:

0 VALUE rst
0 VALUE sum-dg
0 VALUE st-q

: print-q ( N --)
TO rst
0 TO sum-dg
BEGIN
    rst 10 /MOD TO rst DUP
    IF
         sum-dg + TO sum-dg
         rst 0= sum-dg 9 = AND
         IF st-q 1+ TO st-q CR . EXIT THEN
    ELSE
         2DROP EXIT
    THEN
AGAIN
;
: output-q
111111112 9 DO I I print-q LOOP st-q .
;
STARTLOG
output-q

лог

Код:

9
18
27
36
45
54
63
72
81
117
..............
3111111
11111112
11111121
11111211
11112111
11121111
11211111
12111111
21111111
111111111 256

garbler

лобовое рекурсивное решение тривиально, но интуиция подсказывает,
что каким-то образом можно зацепиться за код Грея, т.к. существует
взаимно однозначное отображение битов числа-аккумулятора (0..255)
и чисел с требуемыми параметрами (сумма цифр десятичного
представления)

Код:

: enum ( start limit count -- count' )
    OVER IF
        ROT 10 * -ROT
        BEGIN OVER WHILE
            >R 1 -1 D+ 2DUP R>
            RECURSE
        REPEAT
        NIP NIP
    ELSE 1 + NIP SWAP . CR THEN
;

0 9 0 enum . CR

garbler

вариант с перекодированием так-же тривиален

Код:

: convert ( x -- n )

    1 0 ROT 8 0 DO
        >R OVER +
        R@ 1 AND 0= IF SWAP 10 * SWAP THEN
        R> 2/
    LOOP DROP +
;

: enum 256 0 DO I convert . CR LOOP 256 . CR ;

enum

chess

Особенно тривиальным выглядит во втором вашем решении код "256 . CR ;":)

Остается понять почему число таких чисел всегда равно двойке в степени
на единицу меньшей чем разрядность максимального 10-го числа
из исходного диапазона чисел.
Для этого можно представить последовательность из 9-ти любых объектов,
для конкретности например такую:
1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1
Можно заметить, что между соседними объектами ровно на 1-цу меньше,
чем число самих объектов, промежутков(в них запятые).
Если рассмотреть все случаи когда запятые стоят в произвольном
количестве от 0 до 8, то общее число таких "разбиений" будет 256,
а требуемые в задаче числа будут получаться как количество объектов
между запятыми:
1 , 1 1 1 , 1 1 , 1 , 1 1
1 3 2 1 2
При этом сумма этих чисел будет постоянна и равна общему количеству объектов.

А решения, если их брать без первого(моего), представляются совсем нетривиальными.
С кодом Грея никаких ассоциаций правда у меня не появилось.

chess

Обратная задача - получение номера числа c постоянной суммой цифр(кодирование)

Код:

: coder ( n -- x )
0 1
BEGIN
  ROT 10 /MOD >R LSHIFT DUP ROT OR SWAP
  R@ 0= IF RDROP XOR 1 RSHIFT . EXIT
        ELSE R> -ROT THEN
AGAIN
;

Тогда декодер, согласованный с вышеописанным кодером, будет выглядеть так:
(чуть изменненное слово convert от garblera)

Код:

 : decoder ( x -- n )
    INVERT
    1 0 ROT 8 0 DO
        >R OVER +
        R@ 1 AND 0= IF SWAP 10 * SWAP THEN
        R> 2/
    LOOP DROP + .
;

\EOF
9   coder
18  coder
117 coder
111111111 coder
CR
0   decoder
128 decoder
192 decoder
255 decoder

chess

При использовании для данного случая локальных переменных
быстродействие кода немного увеличивается(проверял)
При этом естественно пляски с параметрами на стеках практически отсутствуют

Код:

REQUIRE { LIB\EXT\locals.f

: coder ( n -- x )
1 { n 1_ \ x }
BEGIN
  1_ n 10 /MOD TO n LSHIFT TO 1_ 1_ x OR TO x n 0=
UNTIL
1_ x XOR 1 RSHIFT
;

Ассемблерный вариант потребовал одной ячейки на стеке возвратов
Само собой он самый быстрый

Код:

REQUIRE IDN ~chess\assm\sp-assm.f

L: coder-asm
    S^S RS=S S++ $ A B=#
L2: D^D /B C=D S<< D=RS D|S RS=D
    $ 0 A=#? L1 J0= L2 JMP
L1: D=RS S^D 1S>> A=S
L;

\ EOF
STARTLOG

SEE coder-asm

1233 coder-asm

лог

Код:

CODE coder-asm
5A539F 33F6             XOR     ESI , ESI
5A53A1 56               PUSH    ESI
5A53A2 46               INC     ESI
5A53A3 C7C30A000000     MOV     EBX , # A
5A53A9 33D2             XOR     EDX , EDX
5A53AB F7FB             IDIV    EBX
5A53AD 8BCA             MOV     ECX , EDX
5A53AF D3E6             SHL     ESI , CL
5A53B1 5A               POP     EDX
5A53B2 0BD6             OR      EDX , ESI
5A53B4 52               PUSH    EDX
5A53B5 81F800000000     CMP     EAX , # 0
5A53BB 7402             JE      5A53BF
5A53BD EBEA             JMP     5A53A9
5A53BF 5A               POP     EDX
5A53C0 33F2             XOR     ESI , EDX
5A53C2 D1EE             SHR     ESI , 1
5A53C4 8BC6             MOV     EAX , ESI
5A53C6 C3               RET     NEAR
END-CODE

 Ok ( 164 )

WingLion

1|1|1|1|1|1|1|1|1

9 единичек, 8 перегородок, которые либо есть либо нет...
Если перегородка есть - она - разделитель между цифрами. Если перегородки нет - сумма единичек между соседними перегородками - цифра.
2<sup>8</sup> комбинаций...

00000000 -> 9
00000001 -> 81
00000010 -> 72
00000011 -> 711
...
11111111 -> 111111111

код 94h
10010010 -> 1332

и так далее - прямое соответствие требуемого числа двоичному коду

Alexander

Ребята вы смешные: если складывать цифры в ц=числе до одной цифры, то все числа которые делятся на 9 дают девятку, еще есть числа из числа 6 и 3, те образуют ряды 3 6 9.
Смотрим на таблицу Пифагора.
1 2 3 4 5 6 7 8 9
2 4 6 8 1 3 5 7 9
3 6 9 3 6 9 3 6 9
4 8 3 7 2 6 1 3 9
5 1 6 2 7 3 8 4 9
6 3 9 6 3 9 6 3 9
7 5 3 1 8 6 4 2 9
8 7 6 3 4 3 2 1 9
9 9 9 9 9 9 9 9 9
Как видно начав с 9 и прибавляя 9 мы найдем требуемы числа или моет не все, надо проверить.
Осталось выявить 0 в процессе преобразования числа на стеке в выводимый символ...

garbler

гипотеза ошибочна:

Alexander

нет, поправил предыдущую месагу

коли тут точку юзают.

garbler

думаю, там одним пропуском не обойтись, диапазоны будут накапливаться, в любом случае - мысль интересная - код в студию :-)

WingLion

chess писал(а):

сумма всех входящих цифр равна 9

Alexander писал(а):

складывать цифры в ц=числе до одной цифры

есть разница?

Alexander

Есть, надо чтобы еще и сумма цифр не была больше 9?!

эти числа делятся без остатка на 9, да еще и нуль нельзя

WingLion

Alexander писал(а):

Есть, надо чтобы еще и сумма цифр не была больше 9?!

Дык, написано же - сумма всех входящих цифр равна 9 - а равно - это и не больше, и не меньше!

Генератор чисел с фиксированной суммой цифр

Кто сейчас на конференции