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

...
Google Search
Forth-FAQ Spy Grafic

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




Начать новую тему Ответить на тему  [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пн янв 24, 2011 23:28 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
самые часто встречающиеся среди оставшихся
в строке с пробелами они встретились чаще всего, но количество их
для разных строк с разными пробелами наименьшее (при других прбелах будет 3 и выше)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вт янв 25, 2011 01:06 
Не в сети

Зарегистрирован: Вс апр 25, 2010 11:14
Сообщения: 200
Откуда: Москва
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
Перечитав дополнение, становится ясно, что оно противоречит первоначальному условию:
в дополнении общее количество пар в двух случаях не равно => один из случаев не оптимален => один из случаев решением не является.

Если же возникает ситуация, когда встречаемость обоих символов из чаще всего повторяющейся пары одинакова => надо добавить условие равенства в алгоритм.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вт янв 25, 2011 15:23 
Не в сети
Аватара пользователя

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

Код:
: get-delimiters  ( a u -- 's' )
u! a! 0. max! at! 0. n1! n2! 0. s1! s2!
0x40000 ALLOCATE THROW ar! ar 0x40000 ERASE
a u + 1- a DO I W@ 4 * ar + is at at 1+! at @ max MAX is max LOOP
emit-dlm( DUP 0x0F AND is s2 8 RSHIFT is s1 0. is n1 is n2
     a u + a DO I C@ s1 = IF n1 1+ is n1 ELSE I C@ s2 = IF n2 1+ is n2 THEN THEN LOOP
     n1 n2 > IF s1 ELSE n1 n2 = IF s1 EMIT SPACE s2 ELSE s2 THEN THEN EMIT SPACE )
ar 0x40000 + ar DO I @ max = IF I ar - 4 / emit-dlm THEN 4 +LOOP
ar FREE THROW ;

T: str 232412414534236534132175326541265325612 ;
   str get-delimiters

лог
Код:
1 2 3
  Ok
Код:
  delimiter
   1        2324 24 4534236534 32 7532654 2653256 2   32 - 4 53 - 4
   2         3 41 414534 3653413 1753 6541 653 561    41 - 4 53 - 4
   3        2 24124145 42 65 41 2175 26541265 25612   41 - 4

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вт янв 25, 2011 18:39 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
то получаем не одно, а несколько решений

именно
Цитата:
оно противоречит первоначальному условию

вот нет, не противоречит


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Чт янв 27, 2011 23:47 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
В общем, вот решение на Prolog'e
http://www.onlinedisk.ru/file/598520/

его нужно запустить либо из-под SWI-Prolog'a либо можно из-под GNU-Prolog'a. Отличаются только функции вывода. Нужно раскомментировать соответствующую. Решение не самое изящное :( но я уложился в 37 строк как и Antender на Euphoria
из него понятно, что нужно.
Задачу :( нужно вводить в виде run( [ 1,2,3,2,1,2,3,2,1,2,3,2,1,2,3,2,1,2,3 ]).
Строка в заглавном сообщении выдаст

Цитата:
SOLUTIONS
--------------------
For symbol 2 pair 5 4 found 2 times

For symbol 3 pair 2 1 found 2 times



NO SOLUTIONS
--------------------
For symbol 1 pair 3 2 found 4 times

For symbol 6 pair 3 2 found 4 times

For symbol 5 pair 3 2 found 4 times

For symbol 4 pair 3 2 found 4 times

For symbol 7 pair 3 2 found 4 times


Последний раз редактировалось вопрос Пт янв 28, 2011 00:32, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пт янв 28, 2011 00:22 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
вопрос писал(а):
В общем, вот решение на Prolog'e
http://www.onlinedisk.ru/file/598520/

фиговенько вот что: Файл годен до (Valid till) : 2011-03-28
можно разместить на форуме, где нибудь в разделе О Форте и фортерах и оставить ссылку сюда.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пт янв 28, 2011 00:34 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
mOleg писал(а):
вопрос писал(а):
В общем, вот решение на Prolog'e
http://www.onlinedisk.ru/file/598520/

фиговенько вот что: Файл годен до (Valid till) : 2011-03-28
можно разместить на форуме, где нибудь в разделе О Форте и фортерах и оставить ссылку сюда.

Да. сейчас подумаю, как его раскрасить ...
Почему нет конвертера RTF -- BB
update
ага. не тут то было, его никак не покрасишь :shock:
viewtopic.php?f=12&t=2704&start=0


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 00:58 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Решение для SPF, с целью ускорения сделано в один цикл, в кот. два блока
\ ------------------------------------------------------------------------
\ заполнить ONE_ITER_ARR - массив результатов одного прохода
\ ------------------------------------------------------------------------

\ ------------------------------------------------------------------------
\ перенести результаты (лучшие) в RESULTS
\ ------------------------------------------------------------------------
можно ли ускорить этот алгоритм?
Код:
VARIABLE ARR \ предположим, длина строки = 32 и пусть каждая цифра будет CELL
HERE  ARR !

\ зададим её прямо тут
2 , 3 , 2 , 4 , 1 , 2 , 1 , 4 , 5 , 4 , 2 , 3 , 6 , 5 , 4 , 3 , 2 , 1 , 7 , 5 , 3 , 2 , 6 , 5 , 2 , 6 , 4 , 3 , 2 , 5 , 6 , 1 ,


VARIABLE ONE_ITER_ARR \ результаты для каждого следующего пробела из перебираемых (т.е. из всех)

HERE ONE_ITER_ARR !
10 10 * CELLS ALLOT \ X Y = первый-второй в паре - число в ячейке - встречаемост

VARIABLE ARR_LENGTH 31 ARR_LENGTH ! \ Real array length - 1


VARIABLE RESULTS
HERE RESULTS !
3 \ format: amount-first_number-second_number
10 \ numbers as spaces
*  CELLS ALLOT

: RESULT_TONULL 30 0 DO I CELLS RESULTS @ +  -1 SWAP !  LOOP ;
: ONE_ITER_ARR_TONULL ONE_ITER_ARR @ 100 CELLS 0 FILL ;

VARIABLE CURR_RESULT_P \ current pointer in results-array
VARIABLE CURR_MAX \ max for current space
VARIABLE G_MAX 65535 G_MAX ! \ min for all MAX
VARIABLE CURR_STR_P \ current string pointer
VARIABLE CURR_STR_I \ current string INDEX
VARIABLE NEXT_S \ next s-l

: show
   CR CR ." SOLUTIONS " CR ." ------------------- " CR
   10 0 DO
            I 3 CELLS * RESULTS @ + DUP
            @ G_MAX @ =
            IF
               ." For space " I . ."  pair "  DUP 1 CELLS + @ . 2 CELLS + @ . ." found " G_MAX @ . ." times" CR
            ELSE 
            DROP
            THEN
       LOOP
      
   CR CR ." NO SOLUTIONS " CR ." ------------------- " CR
   10 0 DO
            I 3 CELLS *  RESULTS @ + DUP \ дважды адрес текущего блока
            @ G_MAX @ >
            IF
               ." For space " I . ."  pair " 
               DUP 1 CELLS + @ . DUP 2 CELLS + @ . ." found "  @ . ." times" CR
            ELSE DROP THEN
       LOOP
   CR CR ." ------------------- " CR CR
   ;

   
: select_space  \ or get-delimiter
   
   RESULT_TONULL 
   65535 G_MAX !
   
   9 \ space symbol currently
   BEGIN
      ONE_ITER_ARR_TONULL 
      DUP CELLS 3 * RESULTS @ +  CURR_RESULT_P !
      0 CURR_STR_P !
      0 CURR_STR_I !   
      \ ------------------------------------------------------------------------
      \ заполнить ONE_ITER_ARR - массив результатов одного прохода
      \ ------------------------------------------------------------------------
      BEGIN
         CURR_STR_I @  CELLS ARR @ +
            DUP CURR_STR_P ! 
         @
         OVER OVER = \ ( sym  strsym  flag= )
         IF DROP
         ELSE SWAP \ ( strsym sym  ) 
            CURR_STR_P @  CELL + @ DUP NEXT_S ! \ (   strsym sym  nextstr  )
            OVER =
            IF SWAP DROP
            ELSE
               SWAP 10 * NEXT_S @ + CELLS ONE_ITER_ARR @ + DUP @ 1 + SWAP !
            THEN
         THEN   
      CURR_STR_I @ 1 + DUP   
      CURR_STR_I ! ARR_LENGTH @   
      =
      UNTIL

      \ ------------------------------------------------------------------------
      \ перенести результаты (лучшие) в RESULTS
      \ ------------------------------------------------------------------------
      100 \ CELLS in ONE_ITER_ARR ( Symbol 100 )
      BEGIN
      1 -  \ 99 - 0
      DUP CELLS ONE_ITER_ARR @ + @ \ значение в ячейке 
      DUP
         IF \ не 0
            DUP
            CURR_RESULT_P @ @ 
            >   \ current greater as current result    
            IF
               OVER 10 /MOD   \ second - first
               CURR_RESULT_P @ 1 CELLS + !
               CURR_RESULT_P @ 2 CELLS + !
               DUP CURR_MAX ! CURR_RESULT_P @ !
            ELSE
               DROP
            THEN    
             
         ELSE
            DROP
         THEN    
      DUP 0 =
      UNTIL
      DROP
      CURR_MAX @ G_MAX @ < IF CURR_MAX @ G_MAX ! THEN
      
      1-
      DUP -1 =
   UNTIL
   DROP
;   
   
: run select_space show   
   ;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 12:09 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
chess писал(а):
Если имеем несколько разных пар, число повторений которых максимально и одинаково
и еще при выборе любого из двух символов такой пары в качестве разделителя, получается одно и тоже
количество символов в исх. строке, то получаем не одно, а несколько решений:

Код:
: get-delimiters  ( a u -- 's' )
u! a! 0. max! at! 0. n1! n2! 0. s1! s2!
0x40000 ALLOCATE THROW ar! ar 0x40000 ERASE
a u + 1- a DO I W@ 4 * ar + is at at 1+! at @ max MAX is max LOOP
emit-dlm( DUP 0x0F AND is s2 8 RSHIFT is s1 0. is n1 is n2
     a u + a DO I C@ s1 = IF n1 1+ is n1 ELSE I C@ s2 = IF n2 1+ is n2 THEN THEN LOOP
     n1 n2 > IF s1 ELSE n1 n2 = IF s1 EMIT SPACE s2 ELSE s2 THEN THEN EMIT SPACE )
ar 0x40000 + ar DO I @ max = IF I ar - 4 / emit-dlm THEN 4 +LOOP
ar FREE THROW ;

T: str 232412414534236534132175326541265325612 ;
   str get-delimiters
похоже ошибка

Код:
T: str 232121313212424131414234 ;
str get-delimiters
1 3  Ok

однако 3 не является решением
2_2121_1_2124241_14142_4
232_2_3_32_2424_3_4_4234

Также, кажется, видит не все решения, если решения не начинаются с 1
Код:
T: str 235236523563253625757645 ;
str get-delimiters
3  Ok


тогда как решение не одно
Код:
run


SOLUTIONS
-------------------
For space 2  pair 5 7 found 2 times
For space 3  pair 5 7 found 2 times


NO SOLUTIONS
-------------------
For space 0  pair 2 3 found 3 times
For space 1  pair 2 3 found 3 times
For space 4  pair 2 3 found 3 times
For space 5  pair 2 3 found 3 times
For space 6  pair 2 3 found 3 times
For space 7  pair 2 3 found 3 times
For space 8  pair 2 3 found 3 times
For space 9  pair 2 3 found 3 times


-------------------

Ok


Последний раз редактировалось вопрос Вс янв 30, 2011 21:12, всего редактировалось 1 раз.

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 13:17 
Не в сети

Зарегистрирован: Ср май 03, 2006 11:27
Сообщения: 1394
Откуда: St.Petersburg
Благодарил (а): 2 раз.
Поблагодарили: 11 раз.
вопрос писал(а):
можно ли ускорить этот алгоритм?


С алгоритм мне тяжело. Чтобы ускорить программу, можно область переменных разместить
в другом сегменте памяти

Код:
HERE 9999 ALLOCATE THROW DP !

VARIABLE ARR \ предположим, длина строки = 32 и пусть каждая цифра будет CELL
HERE  ARR !

\ зададим её прямо тут
2 , 3 , 2 , 4 , 1 , 2 , 1 , 4 , 5 , 4 , 2 , 3 , 6 , 5 , 4 , 3 , 2 , 1 , 7 , 5 , 3 , 2 , 6 , 5 , 2 , 6 , 4 , 3 , 2 , 5 , 6 , 1 ,


VARIABLE ONE_ITER_ARR \ результаты для каждого следующего пробела из перебираемых (т.е. из всех)

HERE ONE_ITER_ARR !
10 10 * CELLS ALLOT \ X Y = первый-второй в паре - число в ячейке - встречаемост

VARIABLE ARR_LENGTH 31 ARR_LENGTH ! \ Real array length - 1


VARIABLE RESULTS
HERE RESULTS !
3 \ format: amount-first_number-second_number
10 \ numbers as spaces
*  CELLS ALLOT

VARIABLE CURR_RESULT_P \ current pointer in results-array
VARIABLE CURR_MAX \ max for current space
VARIABLE G_MAX 65535 G_MAX ! \ min for all MAX
VARIABLE CURR_STR_P \ current string pointer
VARIABLE CURR_STR_I \ current string INDEX
VARIABLE NEXT_S \ next s-l


DP !

: RESULT_TONULL 30 0 DO I CELLS RESULTS @ +  -1 SWAP !  LOOP ;
: ONE_ITER_ARR_TONULL ONE_ITER_ARR @ 100 CELLS 0 FILL ;



Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 16:22 
Не в сети

Зарегистрирован: Вс апр 25, 2010 11:14
Сообщения: 200
Откуда: Москва
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
Обновил решение:

Исходник на Euphoria:
http://users4.jabry.com/Antender/spaces.html
Скомпилированный вариант:
http://www.sharomatic.com/download.php? ... 3a0ca624b5

Вроде решает всё как надо, но с не со всеми тестами вверху сходится.


Последний раз редактировалось Antender Вс янв 30, 2011 16:51, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 16:27 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Antender писал(а):
Обновил решение:

Исходник на Euphoria:
http://users4.jabry.com/Antender/spaces.html
Скомпилированный вариант:
http://users4.jabry.com/Antender/spaces.exe.html

Вроде решает всё как надо, но с не со всеми тестами вверху сходится.

оно не должно сходиться, каждый алгоритм оставляет ту пару, которую замечает как первую подходящую, в зависимости от порядка просмотра

http://users4.jabry.com/Antender/spaces.exe.html
нет такого


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 16:40 
Не в сети

Зарегистрирован: Вс апр 25, 2010 11:14
Сообщения: 200
Откуда: Москва
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
Поправил.

И ещё вариант, выводящий количество найденных пар символов и количество символов.

http://www.sharomatic.com/download.php? ... 9a3a65fad1


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Вс янв 30, 2011 16:52 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Mihail писал(а):
вопрос писал(а):
можно ли ускорить этот алгоритм?


С алгоритм мне тяжело.
Да, стековая эквилибристика не способствует


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача - выбор пробела
СообщениеДобавлено: Пн янв 31, 2011 15:42 
Не в сети
Аватара пользователя

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

Ага! Алгоритм Antender'a неверный. Заменил на почти чисто переборный.
Код:
M: aDO ( a u -- ) D=A A=@P @P+D DO ; \ addr len aDO эквивалентно addr+len addr DO
: space ( a u -- ) u! a! 0x40000 ut! 0x100 ud! 0 t! 0. d! ac! 0 max! u min!
ha( ALLOCATE THROW )  ut ha at!   ud 4 * ha ap!   ud ha ad!   u ha as!
\ сокращения
d~bl( a as u MOVE as u aDO I C@ d = IF BL I C! THEN LOOP )                          \ заменить символ на пробел
noBL?( is t t 0xFF AND 0x20 <> t 0xFF00 AND 0x2000 <> AND )                         \ символ не пробел?
maxp( 0 is max at ut ERASE as u + 1- as                                             \ определить макс. число пар
      DO I W@ noBL? IF t 4 * at + is ac ac 1+! ac @ max MAX is max THEN LOOP max )  \ в строке с пробелом
\ решение
a u aDO 1 I C@ ad + C! LOOP
ad ud aDO I C@ IF I ad - is d d~bl maxp d 4 * ap + ! THEN LOOP                      \ максимумы пар для каждого разделителя
ap ud 4 * + ap DO I @ DUP 0<> IF min MIN is min ELSE DROP THEN 4 +LOOP              \ найти минимум из максимумов пар
ap ud 4 * + ap DO I @ min = IF I ap - 4 / DUP EMIT 8 RSHIFT EMIT SPACE THEN 4 +LOOP \ вывести все решения
fa( FREE THROW ) at fa as fa ap fa ;                                                \ освободить хип
STARTLOG
T: str 23241214542365432175326526432561 ;
str space CR
test: 100 0 DO str space LOOP ;
REQUIRE .elapsed   G:/spf/devel/~af/lib/elapse.f
time-reset test .elapsed CR
log
Код:
2 3
Elapsed time: 00:00:00:047 ( 47 ms )
Ok
Ps Медленно. Правда много времени занимает собственно вывод разделителя.
Нужен более быстрый алгоритм.
То вопрос:
А сколько дает Пролог по времени?

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


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.

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


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

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


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

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