Forth
http://fforum.winglion.ru/

Задача - выбор пробела
http://fforum.winglion.ru/viewtopic.php?f=19&t=2698
Страница 1 из 4

Автор:  вопрос [ Сб янв 22, 2011 01:53 ]
Заголовок сообщения:  Задача - выбор пробела

Есть строка символов, без пробелов вначале.
Нужно составить код, который решит, какой из символов считать за пробел, чтобы в оставшихся подстроках максимальное число повторений одной пары символов было наименьшим

Пример
пусть это будут именно цифры - так проще
строка 232342323 будет разбита на 2 подстроки, если выбрать пробельным символом 4
232342323
причм, в оставшихся подстроках дважды встретится 32 и четырежды 23 - всего 6 пар чисел, для которых есть одинаковые, из них максимальное число повторений одной пары для 23 - 4
это плохой результат, выбрав "пробелом" 2 или 3 мы добиваемся полного отсутствия повторний
2 2 42 2

если бы строка была такой 23234232342, следовало бы выбрать 2 а не 3 , т.к. 3 оставляло бы 2 пары 2 2 42 2 42

учитывается порядок 32 <> 23

Задачу можно решить полным перебором или с оптимизацией. Насколько быстрое решение получится?

пусть для простоты строка представляет собою массив чисел, соответствующих цифрам

VARIABLE SYMARRAY
HERE SYMARRAY !
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 ,

всего 32 числа


update
Дополнение к задаче
Поскольку некоторое минимальное количество повторяющихся пар может получаться при разных символах, необходимо вывести все решения

Автор:  Antender [ Сб янв 22, 2011 16:29 ]
Заголовок сообщения:  Re: Задача - выбор пробела

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

Автор:  mOleg [ Сб янв 22, 2011 18:54 ]
Заголовок сообщения:  Re: Задача - выбор пробела


M Тема почищена от мусора и разборок с модератором.
лишнее частично находится тут


Автор:  chess [ Сб янв 22, 2011 20:59 ]
Заголовок сообщения:  Re: Задача - выбор пробела

RAM-реализация алгоритма Antender'a
Код:
: get-delimiter ( a u -- 's')  u! a! 0 max! 0. n1! n2!
  0xFFFF ar] ar 0xFFFF ERASE  a u + 1- a DO I W@ ar + 1+! LOOP
  0 ar 0xFFFF + ar DO I C@ 2DUP < IF I is max THEN MAX LOOP DROP
  max ar - DUP s1! 8 RSHIFT s2!
  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 s2 THEN EMIT ;

\ EOF

T: str 23241214542365432175326526432561 ;

   str  get-delimiter

log
Код:
2
Ok

Ps. Решение писал около 5 минут, решение быстрое - за два прохода по исходной строке,
на СПФ с использованием лок. слов(переменные и массивы).

Автор:  вопрос [ Сб янв 22, 2011 22:38 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Замечательно, виидимо, с полным перебором никто уже не станет делать...
Кстати, мне не сразу понятно, какие библиотеки нужно подключать к решению chess
Код:
Exception #-2003 at: chessPair.f:1:34:
: get-delimiter ( a u -- 's')  u! a! 0 max! 0. n1! n2!
                                ^ -2003 WORD OR FILE NOT FOUND
:evil:

Автор:  chess [ Вс янв 23, 2011 20:33 ]
Заголовок сообщения:  Re: Задача - выбор пробела

вопрос писал(а):
Кстати, мне не сразу понятно, какие библиотеки нужно подключать к решению chess

Файл для трансляции текста решения: http://narod.ru/disk/4181248001/spf419mal.exe.html

Более быстрое и общее решение (объем исходной строки ограничен 2^32 символами)
Код:
: get-delimiter  ( a u -- 's' )  u! a! 0. max! Imax! 0 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 > IF I is Imax THEN at @ max MAX is max LOOP
  Imax C@ is s1 Imax 1+ C@ is s2 ar FREE THROW
  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 s2 THEN EMIT ;

\ EOF
T: str  23241214542365432175326526432561 ;
  str get-delimiter

ps. Зачем вам нужно решение с перебором?

Автор:  вопрос [ Вс янв 23, 2011 22:08 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Цитата:
ps. Зачем вам нужно решение с перебором?
Спасибо за решение.
Хотел на примере этой задачки пояснять некоторые идеи.
Цитата:
Более быстрое и общее решение

Нельзя ли к коду хотя бы минимальный комментарий

Автор:  chess [ Вс янв 23, 2011 22:52 ]
Заголовок сообщения:  Re: Задача - выбор пробела

вопрос писал(а):
Нельзя ли к коду хотя бы минимальный комментарий

Каждая пара соседних символов исходной строки рассматривается как смещение к адресу массива (нулевого) объемом 64к ячеек. По этому смещению прибавляется 1-ца в ячееку массива в 64к.
Параллельно с подсчетом числа различных пар символов находим максимально повторенную пару. Потом определяем какого символа из найденной пары символов больше в исходной строке. Этот символ и есть разделитель. (Алгоритм Antender'a без хэшей)

Автор:  chess [ Пн янв 24, 2011 17:30 ]
Заголовок сообщения:  Re: Задача - выбор пробела

вопрос писал(а):
Нельзя ли к коду хотя бы минимальный комментарий

Подумалось, что в прошлом посте это был не комментарий к коду, а описание алгоритма.
Привожу все-таки комментарий. Но писать его гораздо труднее и дольше, чем решение. :(
Код:
: get-delimiter  ( a u -- 's' )  u! a!  \ создаем локально-именованные переменные u - длина строки и a - начальный адрес строки
                                        \ и создаем код присвоения этим переменным значения на стеке 
  0x40000 ALLOCATE THROW ar!            \ создаем массив в хипе величиной 64K байтов с именем ar
  ar 0x40000 ERASE                      \ обнуляем все его ячейки
  0. max! Imax!                         \ создаем переменные max - количество самых повторяемых пар соседних символов в исх. строке
                                        \ Imax - последний адрес самой частой пары символов в исх. строке
  0 at!                                 \ переменная at - принимает значения адресов массива ar, в которых накапливаем число разных пар символов
                                        \ в исходной строке( at=ar+offset, где смещение равно коду пары символов s1s2(16 разрядов) умноженному на 2
                                        \ чтобы макс. число пар могло быть до 2^32

  a u + 1- a                            \ определение самой частой пары символов в исх. строке
  DO
     I W@ 2* ar + is at at 1+!
     at @ max > IF I is Imax THEN
     at @ max MAX is max
  LOOP
  Imax C@ s1!                           \ s1 - первый символ
  Imax 1+ C@ s2!                        \ s2 - второй символ
  ar FREE THROW                         \ освободить память в хипе
  0. n1! n2!                            \ счетчики первого и второго символов в исх. строке

  a u + a                               \ подсчет количества символов s1 и s2 в исходной строке
  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 s2 THEN EMIT ;

\ EOF
T: str 23241214542365432175326526432561 ; \ эквивалентно : str S" 23241214542365432175326526432561" ;
                                          \ но можно писать строку в несколько 'этажей'
   str get-delimiter

Автор:  вопрос [ Пн янв 24, 2011 19:21 ]
Заголовок сообщения:  Re: Задача - выбор пробела

:(
Дополнение к задаче
Поскольку некоторое минимальное количество повторяющихся пар может получаться при разных символах, необходимо вывести все решения

интересно, можно ли расширить уже имеющийся алгоритм на такие случаи

Автор:  Antender [ Пн янв 24, 2011 19:23 ]
Заголовок сообщения:  Re: Задача - выбор пробела

А пару-тройку тестов на такие случаи можно привести?

Автор:  вопрос [ Пн янв 24, 2011 19:46 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Antender писал(а):
А пару-тройку тестов на такие случаи можно привести?

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
For symbol 3 pair 2 1 found 2 times

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
For symbol 2 pair 5 4 found 2 times

Это пример.
позже отвечу

Автор:  Antender [ Пн янв 24, 2011 20:22 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Изначально моим алгоритмом решалась задача максимального уменьшения количества пар: по крайней мере такие тесты были преведены изначально. В случае когда требуется чтобы наличие не суммы встресаемости пар, а встречаемость отдельных пар была минимальной -> надо просто не сравнивать одиночные символы в конце программы, а выдавать пару, найденную, как самая часто встречающаяся.

Автор:  вопрос [ Пн янв 24, 2011 22:39 ]
Заголовок сообщения:  Re: Задача - выбор пробела

Может быть ещё раз - мы именно не сумму а самую часто встречающуюся пару ищем и стараемся, чтобы она встречалась реже, поэтому если при изъятии 4 5-6 и при изьятии 3 7-8 встретились по 2 раза, то это 2 решения а не одно

Автор:  Antender [ Пн янв 24, 2011 23:16 ]
Заголовок сообщения:  Re: Задача - выбор пробела

а 5-6 и 7-8 - это самые редко встречающиеся среди оставшихся? или наоборот? и какое отношение они имеют к строке с пробелами?

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