Forth
http://fforum.winglion.ru/

"Треугольные" тройки чисел
http://fforum.winglion.ru/viewtopic.php?f=19&t=2397		 Страница 3 из 3
Автор:  chess [ Сб янв 23, 2010 10:21 ]
Заголовок сообщения: 
mOleg писал(а):
таким образом считать ничего не надо особо.

Условие задачи вами не понято.
Вот пример: N=6
1 2 3 4 5 6
треугольные тройки:
(234) (245) (256) (345) (346) (356) (456)
Q3=7
Ни в одной тройке нет одинаковых чисел.
Автор:  mOleg [ Сб янв 23, 2010 11:13 ]
Заголовок сообщения: 
<pre>
\ количество троек различных треугольников # с одной фиксированной вершиной u
: nnn ( u --> # )
0 >R
3 - BEGIN DUP 0 > WHILE
DUP R+
2 -
REPEAT DROP R> ;

\ общее количество = сумме ряда кол-во треугольников для u-1 + количество треугольников для u
: xxx ( u --> # )
0 >R
3 BEGIN DDUP - WHILE
DUP nnn R+
1 +
REPEAT DDROP R> ;

\
: triangles ( u --> ) BEGIN DUP xxx . CR 1 - DUP 3 = UNTIL DROP ;

\ поэтому, собственно можно не считать в цикле каждый раз
\ как сделано выше, а использовать накопительную переменную
: tr ( u --> )
3 0 >R BEGIN DDUP - WHILE
DUP nnn R+
R@ . CR
1 +
REPEAT DDROP RDROP ;

</pre>
log:
<pre>
FORTH(0)> 33 triangles
2360
2135
1925
1729
1547
1378
1222
1078
946
825
715
615
525
444
372
308
252
203
161
125
95
70
50
34
22
13
7
3
1
0
</pre>

принцип тот же, что и в решении с неправильно понятым ТЗ.
Автор:  chess [ Сб янв 23, 2010 23:56 ]
Заголовок сообщения: 
можно еще проще:
Код:
: Q3 ( N -- Q )
0 OVER 2/ 1+ 1  DO  OVER I 2* - DUP 1- * 2/ +  LOOP NIP ;
Автор:  chess [ Пн янв 25, 2010 12:57 ]
Заголовок сообщения: 
Чуть изменил код на форте, для переписывания на встроенном асс-ме:

Код:
: Q3 ( N -- Q )
0 OVER 2/ 1 SWAP DO OVER I 2* - DUP 1- * 2/ + -1 +LOOP NIP ;

SEE Q3

\ код на ассме
: Q3a ( N -- Q )
S^S ( сумма ) B=A ( N ) C=A 1C>> ( I )
L1: D=B A=C 1A<< D-A A=D A-- *D 1A>> S+A C-- L1 J0<> A=S ;

SEE Q3a

: pr-fvm  5000 Q3  ;  METER pr-fvm

: pr-trg  5000 Q3a ;  METER pr-trg

лог
Код:
CODE Q3
5AEB13 8945FC           MOV     FC [EBP] , EAX
5AEB16 C745F800000000   MOV     F8 [EBP] , # 0
5AEB1D D1F8             SAR     EAX , 1
5AEB1F C745F401000000   MOV     F4 [EBP] , # 1
5AEB26 BA00000080       MOV     EDX , # 80000000
5AEB2B 2B55F4           SUB     EDX , F4 [EBP]
5AEB2E 8D1C02           LEA     EBX , [EDX] [EAX]
5AEB31 8B45F8           MOV     EAX , F8 [EBP]
5AEB34 8D6DFC           LEA     EBP , FC [EBP]
5AEB37 6877EB5A00       PUSH    , # 5AEB77
5AEB3C 52               PUSH    EDX
5AEB3D 53               PUSH    EBX
5AEB3E 90               XCHG     EAX, EAX
5AEB3F 90               XCHG     EAX, EAX
5AEB40 8945FC           MOV     FC [EBP] , EAX
5AEB43 8B4500           MOV     EAX , 0 [EBP]
5AEB46 8945F8           MOV     F8 [EBP] , EAX
5AEB49 8B0424           MOV     EAX , [ESP]
5AEB4C 2B442404         SUB     EAX , 4 [ESP]
5AEB50 8D044500000000   LEA     EAX , 0 [EAX*2]         
5AEB57 F7D8             NEG     EAX
5AEB59 0345F8           ADD     EAX , F8 [EBP]
5AEB5C 8945F8           MOV     F8 [EBP] , EAX
5AEB5F 8D40FF           LEA     EAX , FF [EAX]
5AEB62 F76DF8           IMUL    F8 [EBP]
5AEB65 D1F8             SAR     EAX , 1
5AEB67 0345FC           ADD     EAX , FC [EBP]
5AEB6A 810424FFFFFFFF   ADD     [ESP] , # FFFFFFFF
5AEB71 71CD             JNO     5AEB40
5AEB73 8D64240C         LEA     ESP , C [ESP]
5AEB77 8D6D04           LEA     EBP , 4 [EBP]
5AEB7A C3               RET     NEAR
END-CODE
( 104 bytes, 32 instructions )

CODE Q3a
5AEB8B 33F6             XOR     ESI , ESI
5AEB8D 8BD8             MOV     EBX , EAX
5AEB8F 8BC8             MOV     ECX , EAX
5AEB91 D1E9             SHR     ECX , 1
5AEB93 8BD3             MOV     EDX , EBX
5AEB95 8BC1             MOV     EAX , ECX
5AEB97 D1E0             SHL     EAX , 1
5AEB99 2BD0             SUB     EDX , EAX
5AEB9B 8BC2             MOV     EAX , EDX
5AEB9D 48               DEC     EAX
5AEB9E F7EA             IMUL    EDX
5AEBA0 D1E8             SHR     EAX , 1
5AEBA2 03F0             ADD     ESI , EAX
5AEBA4 49               DEC     ECX
5AEBA5 75EC             JNE     5AEB93
5AEBA7 8BC6             MOV     EAX , ESI
5AEBA9 C3               RET     NEAR
END-CODE
( 31 bytes, 17 instructions )

26829 26667  ( при Ft=3ГГц  t=8,6 мкс)
14229 14157  ( при Ft=3ГГц  t=4,6 мкс)
Ok


ps.
1. Рациональная организация входных данных может резко упростить алгоритм решения и его кодирование.
( если бы числа нат. ряда были расположены в случайном порядке, то сложность была бы значительно выше ).
Поэтому есть смысл в анализе необходимости этапа подготовки исх. данных.

2. Алгоритм настолько прост, что можно было убрать все аспекты эмуляции
виртуальной машины форта, в том числе и стек данных, то есть
привести код к виду оптимальному для данной целевой машины(вручную конечно).
(нет переписывания кэш-памяти данных и кода по ходу исполнения - приоритет 1,
все вычисления только в регистрах - приоритет 2)
В результате сравнения видно, что ускорение "родного" кода по сравнению с peephole-оптимизированным
кодом спф4 всего-то в два раза. Куски peephole-оптимизированного кода сращиваются друг с другом
через стек данных. Собственно это обстоятельство и приводит к замедлению кода в два раза.
Автор:  garbler [ Пн янв 25, 2010 15:34 ]
Заголовок сообщения: 
WingLion писал(а):
garbler писал(а):
требование одно единственное: А+Б > В

ой ли?
...skip...
Возьмите числа 1,2,100 и попробуйте треугольник с такими длинами построить.
В евклидовом пространстве это явно не получится. А неевклидово пространство - не от этой задачи


разумеется имелась ввиду отсортированная последовательность (т.е. условие автоматически накладывается на все стороны).

и вообще: http://www.research.att.com/~njas/sequences/A002623 - number of nondegenerate triangles that can be made from rods of length 1,2,3,4,...,n ..... и куча других формулировок. все формулы в конце.

тема закрыта?
Автор:  forther [ Пн янв 25, 2010 23:05 ]
Заголовок сообщения: 
да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:

Код:
: q3 ( n -- q ) 3 - dup 2 + over 2* 3 + over 2 + * * 24 / ;


оптимизация ...
Автор:  Hishnik [ Пн янв 25, 2010 23:35 ]
Заголовок сообщения: 
Да еще проще.

Код:
: q3 ( n -- q ) CELLS solution-table[] + @ ;
Автор:  forther [ Пн янв 25, 2010 23:52 ]
Заголовок сообщения: 
без определения solution-table[] это не решение. незачот.
Автор:  forther [ Вт янв 26, 2010 00:30 ]
Заголовок сообщения: 
Кстати, chess, при N=5000 результат 34 битный, так что ваши сравнения на таких N могут не совсем корректно сравнивать. Если, конечно, у вас не 64 битный форт. Имеет смысл считать двойной результат:
Код:
: q3 ( n -- d ) 3 - dup 2 + over 2* 3 + over 2 + m* rot 24 m*/ ;
Автор:  chess [ Вт янв 26, 2010 13:14 ]
Заголовок сообщения: 
forther писал(а):
да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:

Код:
: q3 ( n -- q ) 3 - dup 2 + over 2* 3 + over 2 + * * 24 / ;

Ага,
сделано уже (с)

У вас ошибка, правильно так:
Код:
: q3 ( n -- q )
4 - DUP 2 + SWAP 2* 3 + OVER 2 + * * 24 / ;

можно проще
Код:
: Q3
DUP 2- DUP 2* 1- * * 24 /  ;

forther писал(а):
Имеет смысл считать двойной результат:
Код:
: q3 ( n -- d ) 3 - dup 2 + over 2* 3 + over 2 + m* rot 24 m*/ ;


В СПФ нет функции UD/ ( ud un --> ud ), определим на ассме:

Код:
: UD/ ( ud un --> ud )
D^D S=A A=@P $ 4 Pa /S
B=A A=@P /S
@P=A A=B ;

: QQ3 ( n -- dq )
DUP 2- DUP 2* 1- * M* 24 UD/  ;   20000 QQ3  D.


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