Forth
http://fforum.winglion.ru/

Генератор чисел с фиксированной суммой цифр
http://fforum.winglion.ru/viewtopic.php?f=19&t=1265
Страница 1 из 1

Автор:  chess [ Ср апр 23, 2008 16:20 ]
Заголовок сообщения:  Генератор чисел с фиксированной суммой цифр

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

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

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

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

Автор:  chess [ Ср апр 23, 2008 16:30 ]
Заголовок сообщения: 

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

Код:
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 [ Чт апр 24, 2008 12:01 ]
Заголовок сообщения: 

лобовое рекурсивное решение тривиально, но интуиция подсказывает,
что каким-то образом можно зацепиться за код Грея, т.к. существует
взаимно однозначное отображение битов числа-аккумулятора (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 [ Чт апр 24, 2008 13:04 ]
Заголовок сообщения: 

вариант с перекодированием так-же тривиален
Код:
: 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 [ Чт апр 24, 2008 15:19 ]
Заголовок сообщения: 

Особенно тривиальным выглядит во втором вашем решении код "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 [ Пт апр 25, 2008 08:57 ]
Заголовок сообщения: 

Обратная задача - получение номера числа 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 [ Пт апр 25, 2008 18:18 ]
Заголовок сообщения: 

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

Код:
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 [ Пн апр 27, 2009 22:07 ]
Заголовок сообщения: 

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 [ Вт апр 28, 2009 17:02 ]
Заголовок сообщения: 

Ребята вы смешные: если складывать цифры в ц=числе до одной цифры, то все числа которые делятся на 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 [ Вт апр 28, 2009 17:36 ]
Заголовок сообщения: 

гипотеза ошибочна:
    9
    18
    27
    36
    45
    54
    63
    72
    81
    90 ?
    99 ??
    108
    117
    126
    135
    144
    153
    162
    171
    180 ?
    189 ??
    198 ??
    ...

Автор:  Alexander [ Вт апр 28, 2009 17:37 ]
Заголовок сообщения: 

нет, поправил предыдущую месагу ;) коли тут точку юзают.

Автор:  garbler [ Вт апр 28, 2009 17:42 ]
Заголовок сообщения: 

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

Автор:  WingLion [ Вт апр 28, 2009 18:51 ]
Заголовок сообщения: 

chess писал(а):
сумма всех входящих цифр равна 9

Alexander писал(а):
складывать цифры в ц=числе до одной цифры


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

Автор:  Alexander [ Вт апр 28, 2009 19:39 ]
Заголовок сообщения: 

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

Автор:  WingLion [ Вт апр 28, 2009 20:20 ]
Заголовок сообщения: 

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

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

Страница 1 из 1 Часовой пояс: UTC + 3 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/