Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Ср авг 15, 2018 09:38

...
Google Search
Forth-FAQ Spy Grafic

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




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

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

Пример
пусть это будут именно цифры - так проще
строка 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
Дополнение к задаче
Поскольку некоторое минимальное количество повторяющихся пар может получаться при разных символах, необходимо вывести все решения


Последний раз редактировалось вопрос Пн янв 24, 2011 19:25, всего редактировалось 2 раз(а).

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

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


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

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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4926
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.

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


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


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
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 минут, решение быстрое - за два прохода по исходной строке,
на СПФ с использованием лок. слов(переменные и массивы).

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


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

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Замечательно, виидимо, с полным перебором никто уже не станет делать...
Кстати, мне не сразу понятно, какие библиотеки нужно подключать к решению 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:


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

Зарегистрирован: Чт июл 20, 2006 11:31
Сообщения: 2113
Откуда: Екб
Благодарил (а): 0 раз.
Поблагодарили: 40 раз.
вопрос писал(а):
Кстати, мне не сразу понятно, какие библиотеки нужно подключать к решению 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. Зачем вам нужно решение с перебором?

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


Последний раз редактировалось chess Вт янв 25, 2011 15:27, всего редактировалось 2 раз(а).

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

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

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


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

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

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

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


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

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

Подумалось, что в прошлом посте это был не комментарий к коду, а описание алгоритма.
Привожу все-таки комментарий. Но писать его гораздо труднее и дольше, чем решение. :(
Код:
: 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

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


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

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

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


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

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

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


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

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
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

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


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

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


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

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Может быть ещё раз - мы именно не сумму а самую часто встречающуюся пару ищем и стараемся, чтобы она встречалась реже, поэтому если при изъятии 4 5-6 и при изьятии 3 7-8 встретились по 2 раза, то это 2 решения а не одно


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

Зарегистрирован: Вс апр 25, 2010 11:14
Сообщения: 200
Откуда: Москва
Благодарил (а): 0 раз.
Поблагодарили: 2 раз.
а 5-6 и 7-8 - это самые редко встречающиеся среди оставшихся? или наоборот? и какое отношение они имеют к строке с пробелами?


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

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


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

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


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

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