Автор |
Сообщение |
|
|
Заголовок сообщения: |
|
|
|
Alexander писал(а): Есть, надо чтобы еще и сумма цифр не была больше 9?!
Дык, написано же - сумма всех входящих цифр равна 9 - а равно - это и не больше, и не меньше!
[quote="Alexander"]Есть, надо чтобы еще и сумма цифр не была больше 9?![/quote]
Дык, написано же - сумма всех входящих цифр [b]равна[/b] 9 - а равно - это и не больше, и не меньше!
|
|
|
|
Добавлено: Вт апр 28, 2009 20:20 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Есть, надо чтобы еще и сумма цифр не была больше 9?!
эти числа делятся без остатка на 9, да еще и нуль нельзя
Есть, надо чтобы еще и сумма цифр не была больше 9?! ;)
эти числа делятся без остатка на 9, да еще и нуль нельзя
|
|
|
|
Добавлено: Вт апр 28, 2009 19:39 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
chess писал(а): сумма всех входящих цифр равна 9 Alexander писал(а): складывать цифры в ц=числе до одной цифры
есть разница?
[quote="chess"]сумма всех входящих цифр равна 9 [/quote] [quote="Alexander"]складывать цифры в ц=числе до одной цифры[/quote]
есть разница?
|
|
|
|
Добавлено: Вт апр 28, 2009 18:51 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
думаю, там одним пропуском не обойтись, диапазоны будут накапливаться, в любом случае - мысль интересная - код в студию
думаю, там одним пропуском не обойтись, диапазоны будут накапливаться, в любом случае - мысль интересная - код в студию :-)
|
|
|
|
Добавлено: Вт апр 28, 2009 17:42 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
нет, поправил предыдущую месагу коли тут точку юзают.
нет, поправил предыдущую месагу ;) коли тут точку юзают.
|
|
|
|
Добавлено: Вт апр 28, 2009 17:37 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
гипотеза ошибочна:
9 18 27 36 45 54 63 72 81 90 ? 99 ?? 108 117 126 135 144 153 162 171 180 ? 189 ?? 198 ?? ...
гипотеза ошибочна:
[list]9 18 27 36 45 54 63 72 81 90 ? 99 ?? 108 117 126 135 144 153 162 171 180 ? 189 ?? 198 ?? ...[/list]
|
|
|
|
Добавлено: Вт апр 28, 2009 17:36 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Ребята вы смешные: если складывать цифры в ц=числе до одной цифры, то все числа которые делятся на 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 в процессе преобразования числа на стеке в выводимый символ...
Ребята вы смешные: если складывать цифры в ц=числе до одной цифры, то все числа которые делятся на 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 в процессе преобразования числа на стеке в выводимый символ...
|
|
|
|
Добавлено: Вт апр 28, 2009 17:02 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
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
и так далее - прямое соответствие требуемого числа двоичному коду
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
и так далее - прямое соответствие требуемого числа двоичному коду
|
|
|
|
Добавлено: Пн апр 27, 2009 22:07 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
При использовании для данного случая локальных переменных
быстродействие кода немного увеличивается(проверял)
При этом естественно пляски с параметрами на стеках практически отсутствуют
Код: 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 )
При использовании для данного случая локальных переменных
быстродействие кода немного увеличивается(проверял)
При этом естественно пляски с параметрами на стеках практически отсутствуют
[code]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 ;[/code] Ассемблерный вариант потребовал одной ячейки на стеке возвратов Само собой он самый быстрый
[code]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] лог [code]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 )[/code]
|
|
|
|
Добавлено: Пт апр 25, 2008 18:18 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Обратная задача - получение номера числа 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
Обратная задача - получение номера числа c постоянной суммой цифр(кодирование)
[code]: 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 ;[/code] Тогда декодер, согласованный с вышеописанным кодером, будет выглядеть так: (чуть изменненное слово convert от garblera) [code] : 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[/code]
|
|
|
|
Добавлено: Пт апр 25, 2008 08:57 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Особенно тривиальным выглядит во втором вашем решении код "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
При этом сумма этих чисел будет постоянна и равна общему количеству объектов.
А решения, если их брать без первого(моего), представляются совсем нетривиальными.
С кодом Грея никаких ассоциаций правда у меня не появилось.
Особенно тривиальным выглядит во втором вашем решении код [b]"256 . CR ;"[/b]:)
Остается понять почему число таких чисел всегда равно двойке в степени
на единицу меньшей чем разрядность максимального 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
При этом сумма этих чисел будет постоянна и равна общему количеству объектов.
А решения, если их брать без первого(моего), представляются совсем нетривиальными.
С кодом Грея никаких ассоциаций правда у меня не появилось.
|
|
|
|
Добавлено: Чт апр 24, 2008 15:19 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
вариант с перекодированием так-же тривиален
Код: : 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
вариант с перекодированием так-же тривиален
[code] : 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 [/code]
|
|
|
|
Добавлено: Чт апр 24, 2008 13:04 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
лобовое рекурсивное решение тривиально, но интуиция подсказывает,
что каким-то образом можно зацепиться за код Грея, т.к. существует
взаимно однозначное отображение битов числа-аккумулятора (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
лобовое рекурсивное решение тривиально, но интуиция подсказывает,
что каким-то образом можно зацепиться за код Грея, т.к. существует
взаимно однозначное отображение битов числа-аккумулятора (0..255)
и чисел с требуемыми параметрами (сумма цифр десятичного
представления)
[code] : 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 [/code]
|
|
|
|
Добавлено: Чт апр 24, 2008 12:01 |
|
|
|
|
|
Заголовок сообщения: |
|
|
|
Для начала лобовой способ решения путем фильтрации(само собой медленный)
Код: 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
Для начала лобовой способ решения путем фильтрации(само собой медленный)
[code]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[/code]
лог [code]9 18 27 36 45 54 63 72 81 117 .............. 3111111 11111112 11111121 11111211 11112111 11121111 11211111 12111111 21111111 111111111 256[/code]
|
|
|
|
Добавлено: Ср апр 23, 2008 16:30 |
|
|
|
|
|
Заголовок сообщения: |
Генератор чисел с фиксированной суммой цифр |
|
|
Вывести все такие числа из диапазона [0-999999999],
для каждого из которых сумма всех входящих цифр равна 9
и в которых при этом нет нулевых цифр.
Вывести также общее количество таких чисел.
Порядок вывода искомых чисел произвольный,
но выводимые числа не должны повторяться.
Пример результата вывода:
9 18 81 27 72 36 63 .... 111111111 256
где 256 - общее количество искомых чисел
Основной критерий оценки - скорость исполнения.
Вывести все такие числа из диапазона [0-999999999],
для каждого из которых сумма всех входящих цифр равна 9
и в которых при этом нет нулевых цифр.
Вывести также общее количество таких чисел.
Порядок вывода искомых чисел произвольный,
но выводимые числа не должны повторяться.
Пример результата вывода:
9 18 81 27 72 36 63 .... 111111111 256
где 256 - общее количество искомых чисел
Основной критерий оценки - скорость исполнения.
|
|
|
|
Добавлено: Ср апр 23, 2008 16:20 |
|
|
|
|