Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алгоритм] Строки: найти макс.набор слов, не имеющих общих букв 
:(
    Опции темы
KasMP
Дата 16.12.2007, 08:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
гм... интересно.
а разве можно все это реализовать без массивов? подбирать слова (т.е. удалять строки и столбцы) простым перебором?

P.S.. до среды осталось два дня...
PM MAIL   Вверх
SelenIT
Дата 16.12.2007, 12:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


баг форума
****


Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 5
Всего: 401
Если попытаться подойти с другой стороны - для каждой буквы алфавита посчитать количество слов в строке, в которых она встречается, а потом оставить слова только из тех букв, для которых это количество равно единице? Без массивов, конечно, такое сделать трудно...

Upd.: пришла идея алгоритма. Всего используем 4 строки - исходная, полный алфавит, вспомогательная и результат (две последние изначально пусты).

Этап первый. Берем первую букву алфавита и ищем ее в исходной строке. Нашли - добавляем ее во вспомогательную строку и продолжаем анализировать исходную. Если после обнаружения этой буквы в исходной строке встретился символ не из алфавита, а потом, спустя сколько-то символов, опять эта буква - это значит, что она повторяется как минимум в двух словах и нам не подходит - удаляем ее из вспомогательной строки и переходим к следующей букве алфавита. В конце первого этапа вспомогательная строка будет состоять исключительно из букв, встречающихся лишь в одном слове.

Этап второй. Берем исходную строку и ищем слова, состоящие исключительно из букв вспомогательной строки. Нашли - копируем посимвольно в результат и добавляем пробел. Когда исходная строка пройдена до конца, удаляем из результата лишний концевой пробел и выводим его (результат).

Upd 2 [obsoleted by Upd. 3]

Upd 3: не... вроде, померещилось, "походу" все верно)

Это сообщение отредактировал(а) SelenIT - 16.12.2007, 15:24


--------------------
Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!
PM MAIL   Вверх
skyboy
Дата 16.12.2007, 14:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


неОпытный
****


Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 5
Всего: 260
Цитата(SelenIT @  16.12.2007,  11:30 Найти цитируемый пост)
для каждой буквы алфавита посчитать количество слов в строке, в которых она встречается, а потом оставить слова только из тех букв, для которых это количество равно единице?

Цитата

ложка ложка ложка

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

Добавлено через 26 секунд
Цитата(KasMP @  16.12.2007,  07:19 Найти цитируемый пост)
гм... интересно.

не. слишком заумно.
кроме того, алгоритм так и не сформировался. думаю.
PM MAIL   Вверх
SelenIT
Дата 16.12.2007, 14:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


баг форума
****


Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 5
Всего: 401
skyboy, а кстати, что делать с повторяющимися словами, непонятно. Имхо, вводить некий "словарь" и считать одинаковые последовательности одним словом - это уже усложнение, не предусмотренное исходной постановкой задачи. Может, еще словоформы учитывать будем ;)? Имхо, согласно поставленным условиям вполне логично считать все три "ложки" разными словами из одинаковых букв - т.к. никакого словаря и, следовательно, никакой ложки в формулировке задачи нет... ;)


--------------------
Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!
PM MAIL   Вверх
KasMP
Дата 16.12.2007, 15:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(skyboy @  16.12.2007,  14:12 Найти цитируемый пост)
не. слишком заумно.
кроме того, алгоритм так и не сформировался. думаю. 
не более заумно, чем с битовой маской.
да и там (где маска) непонятно, как отличить два слова, одно из которых имеет две одинаковы буквы ("паскаль", "мяч") от двух слов, имеющих общие буквы ("мяч", "грач"), ведь мы два слова вроде как объединяем (хотя, по идее, ничто не мешает не тупо соединить слова, а соединить, поставив между ними пробел).
(вот только у меня не получается представить эти матрицы без массивов)

SelenIT, до меня пока не дошло (скоро должно дойти).
Цитата(SelenIT @  16.12.2007,  14:35 Найти цитируемый пост)
Имхо, согласно поставленным условиям вполне логично считать все три "ложки" разными словами из одинаковых букв
 smile  smile 
PM MAIL   Вверх
SelenIT
Дата 16.12.2007, 15:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


баг форума
****


Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 5
Всего: 401
Упс... KasMP, сорри, я понял свою ошибку. Я ловил буквы, встречающиеся в одном слове в исходной строке, а нужно было добиваться, чтоб они не повторялись в словах результирующего набора. Т.е. если одна буква повторяется в двух словах - мой алгоритм выкинет их оба, а нужно выкинуть лишь одно из них. Сейчас подумаю над модификацией...


--------------------
Осторожно! Данный юзер и его посты содержат ДГМО! Противопоказано лицам с предрасположенностью к зонеризму!
PM MAIL   Вверх
powerfox
Дата 16.12.2007, 16:02 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


I wanna fork()
****


Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: 3
Всего: 97
Прочитать всё не смог. В принципе, здесь можно использовать что-то наподобие алгоритма связности. Иметь структуру (слово, указатель на следующее связанное с ним). Каждый раз при анализе нового слова пробегать по всем таким двусвязным списком. Если выполняется условие связности, то добавлять слово в набор (причём одно и тоже слово может быть в разных наборах).


--------------------
user posted image
PM WWW   Вверх
KasMP
Дата 16.12.2007, 17:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(powerfox @  16.12.2007,  16:02 Найти цитируемый пост)
Прочитать всё не смог.
бывает иногда и такое smile 
Цитата(powerfox @  16.12.2007,  16:02 Найти цитируемый пост)
В принципе, здесь можно использовать что-то наподобие алгоритма связности. Иметь структуру (слово, указатель на следующее связанное с ним). Каждый раз при анализе нового слова пробегать по всем таким двусвязным списком. Если выполняется условие связности, то добавлять слово в набор (причём одно и тоже слово может быть в разных наборах). 
ну а в рамках паскаля как организовать smile такую структуру? smile
как потом по ней бегать? smile 
Цитата(SelenIT @  16.12.2007,  15:56 Найти цитируемый пост)
Упс... KasMP, сорри, я понял свою ошибку.
 smile 
самое интересное, что мой вклад в ваше понимание равен нулю. и извиняться вам тем более не за что
PM MAIL   Вверх
powerfox
Дата 16.12.2007, 18:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


I wanna fork()
****


Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: 3
Всего: 97
Цитата(KasMP @  16.12.2007,  18:29 Найти цитируемый пост)
ну а в рамках паскаля как организовать smile такую структуру? smile


Код

type
PList = ^TList

TList = record;
  str:string;
  next: PList;
  end;



Цитата(KasMP @  16.12.2007,  18:29 Найти цитируемый пост)
как потом по ней бегать? smile 

Код

cur: PList;
...
cur:=first;
while cur^.next <> NIL do
 begin
 {Какие-то манипуляции}
 cur:=cur^.next; // Теперь cur указывает на следующий элемент
 end;


Главное, нормально написать инициализацию новых элементов (не забыть о выделении памяти).


--------------------
user posted image
PM WWW   Вверх
KasMP
Дата 16.12.2007, 20:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
вообще я думала о записях, но дальше мысли "а может быть использовать записи? определенными возможностями массивов они обладают" не продвинулась.

ладно, думается мне, проще сделать то, что предложил Akina. в понедельник-вторник вечером этим и займусь... (пока иду по самому простому пути, т.к. кроме этих задачек еще зачетов дофига...)
PM MAIL   Вверх
KasMP
Дата 20.12.2007, 16:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
ура, товарищи, мы празднуем победу!!

третью (или четвертую?) пару рассказывала про разные возможные извращенные варианты, как то битовая маска Akina (для меня ее реализовать не так-то просто), матрица skyboy и вычеркивание столбцов-строк из нее, структура powerfox, рекурсия одного хорошего мальчика с хорошим алгоритмическим мышлением, создания указывающих на начало/конец слова якорьков (записываемых в отдельную строку: причем т.к. слова может начинать с позиции, номер которой записывается не одной цифрой, а несколькими, то тоже пришлось извратиться: сохранять в строку символ, код которого равен номеру позиции; а потом, чтобы получить номер позиции, извлекать номер этого символа...).

так вот, преподаватель сдалась и разрешила использовать массивы!!!!!! smile  smile 
(ну а теперь-то у меня точно получится)
PM MAIL   Вверх
GoshaNahui
Дата 20.12.2007, 18:01 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 24
Регистрация: 19.12.2007

Репутация: нет
Всего: нет
дак с массивами то всё просто. тогда перебираешь с рекурсией и всё
а поотом мы сделаем с масивами а потом и без них!
то-то она рада будет

Добавлено через 2 минуты и 58 секунд
дак с массивами то всё просто. тогда перебираешь с рекурсией и всё
а поотом мы сделаем с масивами а потом и без них!
то-то она рада будет
PM MAIL   Вверх
skyboy
Дата 20.12.2007, 18:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


неОпытный
****


Профиль
Группа: Модератор
Сообщений: 9820
Регистрация: 18.5.2006
Где: Днепропетровск

Репутация: 5
Всего: 260
Цитата(KasMP @  20.12.2007,  15:46 Найти цитируемый пост)
так вот, преподаватель сдалась и разрешила использовать массивы!!!!!!

лучше бы она сдалась и поставила оценку только за реализацию анализа  smile
теперь бы придумать алгоритм получения пустого графа за минимальное количество шагов... ни у кого нет подборки алгоритмов трансформации графа?
PM MAIL   Вверх
Akina
Дата 20.12.2007, 18:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 17
Всего: 454
Цитата(KasMP @  16.12.2007,  16:20 Найти цитируемый пост)
непонятно, как отличить два слова, одно из которых имеет две одинаковы буквы ("паскаль", "мяч") от двух слов, имеющих общие буквы ("мяч", "грач"),

Вообще-то если В ОДНОМ СЛОВЕ разрешены повторы - текст должен пройти предобработку, которая их уберет (грубо - превратит каждое слово в набор уникальных для этого слова символов), и плевать что смысл слова потеряется, для задачи он как раз нахрен не нужен, ибо исходный массив не трогается, а мыв оперируем не словом, а его позицией в исходном тексте для его идентификации (во блин завернул!). В условиях запрета на массивы это пришлось бы делать с каждым словом в процессе обработки. Но не суть. Т.е. тот же "паскаль" превращается хоть в "паскль", хоть в "скальп" - неважно, на поиск совпадающих символов это никак не влияет.

Добавлено через 1 минуту и 11 секунд
Цитата(skyboy @  20.12.2007,  19:37 Найти цитируемый пост)
теперь бы придумать алгоритм получения пустого графа за минимальное количество шагов... 

Не факт, что это будет оптимальный для задачи граф :(

Добавлено через 6 минут и 5 секунд
Цитата(SelenIT @  16.12.2007,  15:35 Найти цитируемый пост)
что делать с повторяющимися словами, непонятно

По-любому в результирующий оптимальный набор войдет только одно из них (или ни одного). Но если войдет - пофиг какое, задача найти один любой оптимум, а не все существующие оптимумы.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.
PM MAIL WWW ICQ Jabber   Вверх
KasMP
Дата 20.12.2007, 19:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Завсегдатай
Сообщений: 586
Регистрация: 8.8.2006

Репутация: 1
Всего: 30
Цитата(skyboy @  20.12.2007,  18:37 Найти цитируемый пост)
лучше бы она сдалась и поставила оценку только за реализацию анализа
ну, это она тоже оценила (я же вижу и чувствую, что она ко мне очень "+" относится) и в будущем мне это поможет. она не забудет (т.к. и так не забывает). smile 
Цитата(skyboy @  20.12.2007,  18:37 Найти цитируемый пост)
теперь бы придумать алгоритм получения пустого графа за минимальное количество шагов... ни у кого нет подборки алгоритмов трансформации графа? 
какой увлеченный человек smile 
Цитата(Akina @  20.12.2007,  18:50 Найти цитируемый пост)
Вообще-то если В ОДНОМ СЛОВЕ разрешены повторы - текст должен пройти предобработку, которая их уберет (грубо - превратит каждое слово в набор уникальных для этого слова символов), и плевать что смысл слова потеряется, для задачи он как раз нахрен не нужен, ибо исходный массив не трогается, а мыв оперируем не словом, а его позицией в исходном тексте для его идентификации (во блин завернул!). В условиях запрета на массивы это пришлось бы делать с каждым словом в процессе обработки. Но не суть. Т.е. тот же "паскаль" превращается хоть в "паскль", хоть в "скальп" - неважно, на поиск совпадающих символов это никак не влияет.
да, но столько сложностей возникает smile : одна доп. строка, другая, строка с указателями (может быть, для опытного программиста вроде Akina это и ерунда, но для моего маленького неподготовленного мозга весьма ограниченной емкости это нелегко).
да и по строке бегать много раз. но вроде как по-другому без массивов не получиться
спасибо вам (тебе) за все smile 
(как лучше обращаться, на ты или на вы?)
Цитата(Akina @  20.12.2007,  18:50 Найти цитируемый пост)
Вообще-то если В ОДНОМ СЛОВЕ...
будь(те), пожалуйста smile , немного терпимее к моим полуламерским вопросикам smile 
PM MAIL   Вверх
Страницы: (3) Все 1 [2] 3 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0868 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.