Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 16:05

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Вывести все такие числа из диапазона [0-999999999],
для каждого из которых сумма всех входящих цифр равна 9
и в которых при этом нет нулевых цифр.
Вывести также общее количество таких чисел.

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

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

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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Ср апр 23, 2008 16:30 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Для начала лобовой способ решения путем фильтрации(само собой медленный)

Код:
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

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 24, 2008 12:01 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
лобовое рекурсивное решение тривиально, но интуиция подсказывает,
что каким-то образом можно зацепиться за код Грея, т.к. существует
взаимно однозначное отображение битов числа-аккумулятора (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:05, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 24, 2008 13:04 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
вариант с перекодированием так-же тривиален
Код:
: 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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 24, 2008 15:19 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Особенно тривиальным выглядит во втором вашем решении код "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 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
Обратная задача - получение номера числа 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 
Не в сети
Аватара пользователя

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2168
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 41 раз.
При использовании для данного случая локальных переменных
быстродействие кода немного увеличивается(проверял)
При этом естественно пляски с параметрами на стеках практически отсутствуют

Код:
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 )

_________________
С уважением, chess


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пн апр 27, 2009 22:07 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
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

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

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 17:02 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Ребята вы смешные: если складывать цифры в ц=числе до одной цифры, то все числа которые делятся на 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 в процессе преобразования числа на стеке в выводимый символ...


Последний раз редактировалось Alexander Вт апр 28, 2009 17:37, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 17:36 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
гипотеза ошибочна:
    9
    18
    27
    36
    45
    54
    63
    72
    81
    90 ?
    99 ??
    108
    117
    126
    135
    144
    153
    162
    171
    180 ?
    189 ??
    198 ??
    ...


Последний раз редактировалось garbler Вт апр 28, 2009 17:39, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 17:37 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
нет, поправил предыдущую месагу ;) коли тут точку юзают.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 17:42 
Не в сети
Аватара пользователя

Зарегистрирован: Вт сен 11, 2007 11:07
Сообщения: 187
Благодарил (а): 0 раз.
Поблагодарили: 1 раз.
думаю, там одним пропуском не обойтись, диапазоны будут накапливаться, в любом случае - мысль интересная - код в студию :-)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 18:51 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
chess писал(а):
сумма всех входящих цифр равна 9

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


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

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 19:39 
Не в сети
Аватара пользователя

Зарегистрирован: Вт ноя 06, 2007 21:23
Сообщения: 227
Откуда: Екатеринбург
Благодарил (а): 4 раз.
Поблагодарили: 7 раз.
Есть, надо чтобы еще и сумма цифр не была больше 9?! ;)
эти числа делятся без остатка на 9, да еще и нуль нельзя


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт апр 28, 2009 20:20 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
Alexander писал(а):
Есть, надо чтобы еще и сумма цифр не была больше 9?!

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

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB