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: Задача - выбор пробела | ||
|
Автор: | 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 |
Автор: | 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/ |