Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 02:36

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

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

Код:
: q3 ( n -- q ) CELLS solution-table[] + @ ;
Сообщение Добавлено: Пн янв 25, 2010 23:35
  Заголовок сообщения:   Ответить с цитатой
да, закрыта. спасибо за ссылку! для тех, кто поленился посмотреть в конец:

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


оптимизация ...
Сообщение Добавлено: Пн янв 25, 2010 23:05
  Заголовок сообщения:   Ответить с цитатой
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 ..... и куча других формулировок. все формулы в конце.

тема закрыта?
Сообщение Добавлено: Пн янв 25, 2010 15:34
  Заголовок сообщения:   Ответить с цитатой
Чуть изменил код на форте, для переписывания на встроенном асс-ме:

Код:
: 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-оптимизированного кода сращиваются друг с другом
через стек данных. Собственно это обстоятельство и приводит к замедлению кода в два раза.
Сообщение Добавлено: Пн янв 25, 2010 12:57
  Заголовок сообщения:   Ответить с цитатой
можно еще проще:
Код:
: Q3 ( N -- Q )
0 OVER 2/ 1+ 1  DO  OVER I 2* - DUP 1- * 2/ +  LOOP NIP ;
Сообщение Добавлено: Сб янв 23, 2010 23:56
  Заголовок сообщения:   Ответить с цитатой
<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>

принцип тот же, что и в решении с неправильно понятым ТЗ.
Сообщение Добавлено: Сб янв 23, 2010 11:13
  Заголовок сообщения:   Ответить с цитатой
mOleg писал(а):
таким образом считать ничего не надо особо.

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

\ и подсчет ряда:
: triangles ( u --> )
BEGIN DUP WHILE
DUP Count . CR
1 -
REPEAT DROP ;
</pre>

лог:
<pre>
FORTH(0)>20 triangles
110
100
90
81
72
64
56
49
42
36
30
25
20
16
12
9
6
4
2
1
</pre>
Сообщение Добавлено: Сб янв 23, 2010 09:51
  Заголовок сообщения:   Ответить с цитатой
мндя, у мя получаются другие числа.
Для того, чтобы получился треугольник, нужно, чтобы сумма двух других сторон была больше на 1 самой длинной.
то есть, для длины в 1, возможен только один равносторонний треугольник с длинами 1+1
<pre>
для 2: 2+2;2+1 = 2 варианта
для 3: 3+3;3+2;3+1
2+2 = 4 варианта
для 4: 4+4;4+3;4+2;4+1
3+3;3+2 = 6 вариантов
для 5: 5+5;5+4;5+3;5+2;5+1
4+4;4+3;4+2
3+3 = 9 вариантов
12
16
20
25
и так далее.
</pre>
Сообщение Добавлено: Сб янв 23, 2010 09:23
  Заголовок сообщения:   Ответить с цитатой
chess, a вот эту программку не прогоните через свой METER?
Код:
: q3" ( n -- q )
  0 over 1 do          \ j = 1 .. n
    over i - 0 do      \ i = 0 .. n-j
      i j min +
    loop
  loop
  swap drop
;


EDIT: уже не надо
Сообщение Добавлено: Сб янв 23, 2010 01:52
  Заголовок сообщения:   Ответить с цитатой
chess писал(а):
forther писал(а):
a вот как я сделал:

Выглядит кратко, но при ближайшем рассмотрении очень медленный вариант.
сравним варианты:

Код:
: forther 1000 q3 ;
: chess   1000 Q3 ;

REQUIRE METER ~CHESS\TASK\METER.F

STARTLOG
METER forther
METER chess

лог
Код:
521252451 521555310
5688 5553
Ok

что и требовалось доказать.


бесспорно!

интересно, а аналитическое решение кто нибудь покажет?
Сообщение Добавлено: Сб янв 23, 2010 01:28
  Заголовок сообщения:   Ответить с цитатой
Если вдуматься, то для каждой пары существует гипотетичеких 2(A+B)-1... вариантов треугольников с длиной стороны С,
Остается исключить не подходящие и повернутые (повторяющиеся в разлчной ротации тройки чисел) треугольники.
Так для случая когда стороны A и B равны 1, - имеем равносторонний треугольник.
Сообщение Добавлено: Сб янв 23, 2010 01:14

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


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