Forth http://fforum.winglion.ru/ |
|
Задача - выбор пробела http://fforum.winglion.ru/viewtopic.php?f=19&t=2698 |
Страница 2 из 4 |
Автор: | вопрос [ Пн янв 24, 2011 23:28 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
самые часто встречающиеся среди оставшихся в строке с пробелами они встретились чаще всего, но количество их для разных строк с разными пробелами наименьшее (при других прбелах будет 3 и выше) |
Автор: | Antender [ Вт янв 25, 2011 01:06 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Перечитав дополнение, становится ясно, что оно противоречит первоначальному условию: в дополнении общее количество пар в двух случаях не равно => один из случаев не оптимален => один из случаев решением не является. Если же возникает ситуация, когда встречаемость обоих символов из чаще всего повторяющейся пары одинакова => надо добавить условие равенства в алгоритм. |
Автор: | chess [ Вт янв 25, 2011 15:23 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Если имеем несколько разных пар, число повторений которых максимально и одинаково и еще при выборе любого из двух символов такой пары в качестве разделителя, получается одно и тоже количество символов в исх. строке, то получаем не одно, а несколько решений: Код: : 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 |
Автор: | вопрос [ Вт янв 25, 2011 18:39 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Цитата: то получаем не одно, а несколько решений именно Цитата: оно противоречит первоначальному условию вот нет, не противоречит |
Автор: | вопрос [ Чт янв 27, 2011 23:47 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
В общем, вот решение на 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 |
Автор: | mOleg [ Пт янв 28, 2011 00:22 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
вопрос писал(а): В общем, вот решение на Prolog'e http://www.onlinedisk.ru/file/598520/ фиговенько вот что: Файл годен до (Valid till) : 2011-03-28 можно разместить на форуме, где нибудь в разделе О Форте и фортерах и оставить ссылку сюда. |
Автор: | вопрос [ Пт янв 28, 2011 00:34 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
mOleg писал(а): вопрос писал(а): В общем, вот решение на Prolog'e http://www.onlinedisk.ru/file/598520/ фиговенько вот что: Файл годен до (Valid till) : 2011-03-28 можно разместить на форуме, где нибудь в разделе О Форте и фортерах и оставить ссылку сюда. Да. сейчас подумаю, как его раскрасить ... Почему нет конвертера RTF -- BB update ага. не тут то было, его никак не покрасишь viewtopic.php?f=12&t=2704&start=0 |
Автор: | вопрос [ Вс янв 30, 2011 00:58 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Решение для 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 ; |
Автор: | вопрос [ Вс янв 30, 2011 12:09 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
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 |
Автор: | Mihail [ Вс янв 30, 2011 13:17 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
вопрос писал(а): можно ли ускорить этот алгоритм? С алгоритм мне тяжело. Чтобы ускорить программу, можно область переменных разместить в другом сегменте памяти Код: 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 ; |
Автор: | Antender [ Вс янв 30, 2011 16:22 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Обновил решение: Исходник на Euphoria: http://users4.jabry.com/Antender/spaces.html Скомпилированный вариант: http://www.sharomatic.com/download.php? ... 3a0ca624b5 Вроде решает всё как надо, но с не со всеми тестами вверху сходится. |
Автор: | вопрос [ Вс янв 30, 2011 16:27 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
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 нет такого |
Автор: | Antender [ Вс янв 30, 2011 16:40 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Поправил. И ещё вариант, выводящий количество найденных пар символов и количество символов. http://www.sharomatic.com/download.php? ... 9a3a65fad1 |
Автор: | вопрос [ Вс янв 30, 2011 16:52 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
Mihail писал(а): вопрос писал(а): можно ли ускорить этот алгоритм? С алгоритм мне тяжело. |
Автор: | chess [ Пн янв 31, 2011 15:42 ] |
Заголовок сообщения: | Re: Задача - выбор пробела |
вопрос писал(а): похоже ошибка Ага! Алгоритм Antender'a неверный. Заменил на почти чисто переборный. Код: M: aDO ( a u -- ) D=A A=@P @P+D DO ; \ addr len aDO эквивалентно addr+len addr DO log: 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 Код: 2 3 Ps Медленно. Правда много времени занимает собственно вывод разделителя.Elapsed time: 00:00:00:047 ( 47 ms ) Ok Нужен более быстрый алгоритм. То вопрос: А сколько дает Пролог по времени? |
Страница 2 из 4 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |