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 ] |
Заголовок сообщения: | |
гипотеза ошибочна:
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/ |