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

Поиск:

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


Опытный
**


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

Репутация: 1
Всего: 30



П/р по теме "Строки". Нельзя использовать массивы.
Цитата(Задание)
Найти в строке самый большой набор слов, никакие два из которых не имеют общих букв.
Далее, после моих вопросов было получено несколько уточнений:
  • слово - одна буква (заглавная или строчная, латинского или русского алфавита), а также их любая комбинация;
  • слово может содержать цифры (например: "3" - не слово; "п67ы" - слово);
  • цифры повторятся могут;
  • пробел и знаки препинания (а именно: точка, запятая, двоеточие, точка с запятой, вопросительный и восклицательный знаки) - разделители (например: "стройная, красивая девушка" - 3 слова; "dgh3dg?4 ghd!fc" - тоже 3 слова ("dgh3dg", "ghd" и "fc"));
  • найти нужно именно максимальное кол-во слов (а не, например, слова, содержащие максимальное кол-во неповторяющихся букв).
Пока мой мозг додумался только до того, что самое "выгодное" слово - слово, состоящее из одной буквы ("поедает" минимальное кол-во букв и приносит максимальное кол-во слов, которые можно составить из одной буквы). Чем меньше букв в слове, тем оно "лучше".
Ну и еще до того, что, наверно, нужно организовать три строки:
а) исходная - к ней не прикасаемся (или заменяем/удаляем лишь то, что точно не понадобится и только мешает (пока не знаю, что это может быть);
б) рабочая - в которой перебираем варианты, составляем разные комбинации;
в) промежуточно-результативная - в которой сохраняем наилучший вариант, полученный на данный момент.

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

Примерно тот же подход можно применить и к рабочей "строке" (только без переменной, коллекционирующей, слова - она ей ни к чему; задача рабочей строки - просто перебрать и посчитать кол-во слов, а не выдать набор слов):
а) переменная целого типа - кол-во слов;
б) переменная-строка - записываем уже задействованные буквы.


Короче не знаю, путано все, сложно и непонятно... smile 
Помогите, пожалуйста! Спасибо за то, что обратили внимание на мою полуламерскую, очень смутную тему.
PM MAIL   Вверх
JackYF
Дата 26.11.2007, 18:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


полуавантюрист
****


Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 2
Всего: 162



Цитата(KasMP @  26.11.2007,  17:53 Найти цитируемый пост)
Нельзя использовать массивы.

Круто. А что можно? строка - не массив?  smile 

В общем, идея дубового решения такова (очень похожа на идею решения задачи на графах, правда, какой, не помню smile):

1. Выделить все слова из строки.
2. Из каждого слова сформировать набор, пока состоящий из этого слова.
3. Затем, для каждой группы и для каждого другого слова сравнить его набор букв с набором букв слов из группы, если не совпали, добавить в группу.
После этого этапа мы будем иметь группы из одного слова и группы из двух. Группы из одного слова нам уже не нужны, забиваем на них.
4. Повторяем процедуру №3, вычёркиваем все группы, состоящие уже из двух слова, оставляем только трёхсловные группы.
4+. И так далее, пока нечего будет добавлять к группам.
5. Пройтись по группам, подсчитать количество слов в группах.

Как это дело организовать "без массивов", я не очень себе представляю. Массив - одна из базовых структур языка программирования, без них как без ног...


--------------------
Пожаловаться на меня как модератора можно здесь.
PM MAIL Jabber   Вверх
Akina
Дата 26.11.2007, 18:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 17
Всего: 454



Для начала поменяй все символы-разделители на, скажем, пробелы.
Сперва посчитай количество слов (нельзя массивы - можно байтовую маску), создай строку с количеством байтов = количеству слов.

И понеслась... берем слово 1. Прикладываем слово 2, проверяем на соответствие условию. Да? к полученной группе прикладываем слово 3... нет? откидываем вариант 2, берем вариант 1-3... пробуем приложить слово 4.... и так перебираем все возможнвые варианты. На каждом шаге смотрим количество слов в группе, и запоминаем, если она больше предыдущей запомненной...


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
KasMP
Дата 26.11.2007, 23:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 30



Цитата(JackYF @  26.11.2007,  18:33 Найти цитируемый пост)
Круто. А что можно? строка - не массив?
Я не спорю, строка - разновидность массива smile ... Но дословно было сказано именно так smile .
Цитата(JackYF @  26.11.2007,  18:33 Найти цитируемый пост)
В общем, идея дубового решения такова (очень похожа на идею решения задачи на графах, правда, какой, не помню smile):
Спасибо за дубовый алгоритм (в нем тоже есть своя прелесть smile ). Но у нас упор делается именно на рациональность алгоритма, его низкую сложность, красоту построения, т.п..
Цитата(JackYF @  26.11.2007,  18:33 Найти цитируемый пост)
Как это дело организовать "без массивов", я не очень себе представляю. Массив - одна из базовых структур языка программирования, без них как без ног... 
А вот я попробую подумать smile и представить smile  . Это же интересно... smile 
_____________________________________________________________________
Цитата(Akina @  26.11.2007,  18:39 Найти цитируемый пост)
Для начала поменяй все символы-разделители на, скажем, пробелы.
У меня была такая мысль. Но зачем?
Имхо программа не станет проще от того, что вместо сравнения символа с несколькими заданными символами-разделителями
 будет производиться сначала поиск разделителей (т.е. по сути опять то же сравнение, о котором говорилось только что), а затем замена, а посл снова поиск.
Хотя smile ... Ведь при поиске слов мы будем обращаться к одному и тому же символу далеко не один раз (рассматриваем разные комбинации). Т.е. с этой зрения рациональнее все же заменить: вместо многократных сравнений с несколькими символами мы получим многократные сравнения с одним символом -> сложность уменьшается в разы. Кажется, я поняла!
Цитата(Akina @  26.11.2007,  18:39 Найти цитируемый пост)
байтовую маску
Я пыталась понять, что это здесь и здесь. Видимо, не там искала?
PM MAIL   Вверх
Akina
Дата 27.11.2007, 10:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 17
Всего: 454



Цитата(KasMP @  27.11.2007,  00:54 Найти цитируемый пост)
Я пыталась понять, что это 

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
KasMP
Дата 27.11.2007, 15:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 30



А если не доходит, как реализовать это на паскале, то лучше создать новую тему (чтобы был порядок) или можно продолжить здесь (чтобы не забивать форум)? 
Цитата(Akina @  26.11.2007,  18:39 Найти цитируемый пост)
проверяем на соответствие условию
В данном случае подразумевается, что мы берем каждую букву первого слова и сравниваем ее с каждой буквой второго (т.е. занимаемся простым перебором)? Или что?
(потом каждую буквы первых двух с каждой буквой третьего и т.д.?)
Цитата(Akina @  27.11.2007,  10:06 Найти цитируемый пост)
по памяти нас не ограничивали
Как сказать... Чем меньше памяти - тем лучше (даже в нашем случае). Думаю, это будет оценено и принято во внимание преподавателем (и я тоже хочу сделать максимально хорошо).

Вот, например, строчка:
Цитата
dr6v!пу?56vf hf;!d 5?gdке
1. заменяем разделители на пробелы (несколько идущих подряд разделителей заменяем на один пробел (другими словами, если ((s[i-1]=разделитель_кром) и (s[i]=разделитель)), то s[i-1] уже заменен на пробел, а s[i] просто удаляем)).
Результат: "dr6v пу 56vf hf d 5 gdке".
2. вычеркиваем "не слова" (другими словами, одну или несколько цифр, окруженных пробелами).
Результат: "dr6v пу 56vf hf d gdке".
3. считаем кол-во слов (на это ума много не надо).
Результат: "6" (обозначим как t).
4. создаем строку с кол-вом байтов, равном кол-ву слов (другими словами, ... (что мы делаем?!?!).
Результат: пустая строка с кол-вом байтов, равном t.
5. ух, чего-то там делаем... (не дошло).
6. еще чего-то делаем... (группируем, прикладываем, не знаю, не дошло...).
7. какие-то "да"/"нет"... (примерно понятно, но нет конкретики, т.к. пробелы в понимании предыдущих шагов).
8. не забываем при каждой новой комбинации обновлять кол-во слов в группе, если оно больше предыдущего значения.
9. ну а теперь любой баран сможет взять нужные переменные и вывести их как результат.

Кстати, может быть, компу удобнее заменять разделители не на пробелы, а на что-то, что расположено в используемых таблица ближе (символ с кодом N достигается немного быстрее, чем символ с кодом N+K)? Нет?


 smile  smile  smile  smile  smile 
 smile  smile  smile  smile  smile 

Это сообщение отредактировал(а) KasMP - 27.11.2007, 15:11
PM MAIL   Вверх
GIK
Дата 27.11.2007, 16:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 4
Всего: 14



Яб сделал так:
1) Можно конечно заменить все знаки припинания на пробелы, но можно и в условии просто проверять (причем побитово) на всме имеющиеся знаки препинания. Короче, в массиве сохраняем "якоря" (так я называю индексы эллементов некоторой сушьности)
2) Подсчитали кол-во пропусков, пропускаем через цикл эти индексы, например так:
 
Код

for(int i=0; i<12; i++) //Допустим 12 пробелов
 { 
   int len= mas[i+1] - mas[i]; //Нужна вычислить длину слова
   
    for(int d=1; d<=len; d++) //Берем каждую букву с самого начала 
     for(int ch=d+1; ch<=len; ch++) //возвращатся нет смысла, так что с d и дальше
    { 
        if(str[mas[i]+d]==str[mas[i]+ch])
         not=true; //Нашли, обломались, ну фиг с ним :)
        //str[mas[i]+d]; //читается как, индекс начала слова+последующие буквы
    }
  if(!not)
      //Забиваем массив слов которые не имеют одинаковых букв
  
}
3) Все вроде...

Это сообщение отредактировал(а) GIK - 27.11.2007, 16:08


--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
KasMP
Дата 27.11.2007, 18:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 30



GIK, а где у тебя сохраняется промежуточный (наилучший на данный момент) результат? Имхо если мы нашли совпадение и обломались, то не фиг, а надо сначала сравнить этот "фиг" с наилучшим на данный момент результатом.
К слову, массивы использовать нельзя.

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

PM MAIL   Вверх
Akina
Дата 27.11.2007, 18:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 17
Всего: 454



Попробую пояснить мысль подбора вариантов. Допустим, у нас вот те самые 6 слов "dr6v пу 56vf hf d gdке". Я буду оперировать битовой маской, а байтовую предложил для того, чтобы в Паскале тебе не заморачиваться на биты и лишние вычисления.

Начинаем, само собой, с 000000. Оно смысла не имеет, значит сразу с 000001.
Это "gdке". Запускаем в тест повтора символов - на выходе нам говорят что повтора нет. Запоминаем текущее наилучшее (1 слово) и соотв. маску (000001).
Далее прибавляем к маске единичку - получаем 000010. Это "d". Запускаем в тест повтора символов - на выходе нам говорят что повтора нет. Сравниваем длину - 1 слово, у нас такой вариант есть. Пропускаем.
Далее прибавляем к маске единичку - получаем 000011. Это "d gdке". Запускаем в тест повтора символов, удалив разделители, т.е. "dgdке" - на выходе нам говорят что повтор есть. Пропускаем.
Далее 000100 = "hf". Нет. 1. Пропускаем.
Далее 000101 = "hfgdке". Нет. 2. Запоминаем.
Далее 000110 = "hfd". Нет. 2. Пропускаем.
Далее 000101 = "hfdgdке". Да. Пропускаем.

И так далее.

В данном случае пример не очень удачен - произойдет полный перебор вариантов. Но на самом деле в реальной работе будут пропуски, например:

Если маска 010100 дает дублирование символов, то мы переходим не к 010101, а сразу к 011000, потому что проверка 010101..010111 бессмысленна. Т.е. на каждом шагу мы прибавляем к маске 1, если в текущей группе не было дублирования символов, и единичку в последний ненулевой бит текущей маски (в приведенном примере это третий от хвоста бит), если оно было.



--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
GIK
Дата 28.11.2007, 12:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Добрый человек
**


Профиль
Группа: Участник
Сообщений: 985
Регистрация: 3.6.2005
Где: я только не небыв ал

Репутация: 4
Всего: 14



Цитата

а надо сначала сравнить этот "фиг" с наилучшим на данный момент результатом.
К слову, массивы использовать нельзя.

Я наверно задачу не правильно понял smile 
Надо было найти слова не имеющие общих букв, а я отсекал слова имеющие одинаковые буквы в этом же слове, лоханулся короче smile 
Вобщем строки использовать нельзя, так?



--------------------
Математика=>пиво=> програмирование, три вещи последовательны и совместимы !!!
Программирование - это не деятельнось! Программирование - это состояние души!
Бог - самый крутой программист.
PM MAIL ICQ   Вверх
SaDFromSpb
Дата 28.11.2007, 17:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: нет
Всего: 3



Цитата(Akina @  27.11.2007,  18:57 Найти цитируемый пост)
В данном случае пример не очень удачен - произойдет полный перебор вариантов.

Вроде как, это задача на NP-полноту, то есть самое оптимальное решение может быть достигнуто только полным перебором. (Отбрасывание заведомо лишних комбинаций здесь не в счет). Чтобы утверждать наверняка, нужно это четко доказать. Как это делается, я не знаю. 



--------------------
"За исключением части, касающейся потоков, библиотека Loki написана на стандартном языке С++. Увы, это означает, что многие современные компиляторы не смогут работать с ней в полном объеме." (А. Александреску. Modern C++ design. 2001)
PM   Вверх
Akina
Дата 28.11.2007, 18:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 17
Всего: 454



Цитата(SaDFromSpb @  28.11.2007,  18:59 Найти цитируемый пост)
Вроде как, это задача на NP-полноту, то есть самое оптимальное решение может быть достигнуто только полным перебором. 

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

Цитата(SaDFromSpb @  28.11.2007,  18:59 Найти цитируемый пост)
Чтобы утверждать наверняка, нужно это четко доказать.

Достаточно того, что вероятность наличия какого-либо символа в каком-либо слове не может быть рассчитана на основании знания части или всех остальных слов. Т.е. каждое из слов полностью независимо. Впрочем, можно доказать, что ПОЛНОГО перебора в общем случае нет - количество слов в группе заведомо не больше количества символов в алфавите, но на суть это не влияет.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
KasMP
Дата 2.12.2007, 15:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 30



Цитата(Akina @  27.11.2007,  18:57 Найти цитируемый пост)
Попробую пояснить мысль подбора вариантов.
Спасибо большое, теперь ясно!
Правда есть недочет: формулировка "никакие 2 из которы не имеют общих букв" подразумевает, что внутри одного слова буквы могут повторяться (т.е. склеивать слова в одну строку и только потом сравнивать нельзя).
Цитата(GIK @  28.11.2007,  12:46 Найти цитируемый пост)
Я наверно задачу не правильно понял
 Возможно.
Цитата(GIK @  28.11.2007,  12:46 Найти цитируемый пост)
Вобщем строки использовать нельзя, так?
 Строки можно и нужно, просто необходимо использовать - к/р по теме "Строки".

А то, что написано в посте Akina от 28.11.2007, 18:41 приведу тогда, когда опять преподаватель начнет: "но это же просто перебор... слишком много раз бегаем по строке..." (при этом ничего более оптимального не предлагает!!)
PM MAIL   Вверх
KasMP
Дата 9.12.2007, 10:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 30



Пожалуйста, не бросайте на произвол судьбы!!
PM MAIL   Вверх
skyboy
Дата 15.12.2007, 14:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 5
Всего: 260



все пытаюсь привести постановку задачи к задаче на графах.
пока "дошел" до уровня матрицы смежности.
пускай матрица определяется так: каждая ячейка {i,j} представляет собой флаг(1 или 0) - является ли слово i имеющим общие со словом j буквы(1 - если имеются, 0 - еслши не имеются). все ячейки с одинаковым номером столбца и строки - имеют значение 0(для упрощения считаем, что слово с самим собой общих букв не имеет). Тогда у нас будет матрица из 0 и 1 размерностью NxN. Удаление слова из списка - удаление строки и столбца с одинаковым номером. теперь надо удалить минимальное количество строк, чтоб оставшаяся матрица состояла из одних нулей.
PM MAIL   Вверх
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   Вверх
Akina
Дата 21.12.2007, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


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


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

Репутация: 17
Всего: 454



Так... ну тебе же разрешили массивы!

Значит, сразу это используй. Первые этапы работы:

0) Получение копии исходной строки (чтобы не пакостить ее)
1) Замена на пробелы всех других возможных разделителей
2) Разбивка полученной строки в массив по разделителю-пробелу (Split) - в каждом элементе массива получается 1 слово
3) Обработка этого массива с выбрасыванием не-слов и со сжатием слов (удалением дублирующихся в слове символов)

А дальше уже любым способом организуй перебор (да хоть полным перебором вариантов сочетаний). Сделай отдельной функцией проверку на существование повторяющихся символов - так будет удобнее.

В общем, начинай создавать код. А мы заодно поймем. на каком языке программирования ты делаешь работу  smile 


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
KasMP
Дата 22.12.2007, 11:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

Репутация: 1
Всего: 30



Akina, уж теперь-то мне наврядли потребуется чья-то помощь smile . тем более, что задачки-элементы я уже делала smile (например, однажды было дано два числа и нужно была выписать цифры, присутствующие в первом и отсутствующие во втором: делала я отдельную процедуру для сравнения и т.д.)
к слову, я собиралась делать именно так, как ты написал smile (только слова "сжать" не догадалась, спасибо за мысль smile )

зато теперь есть уверенность, что выбрала один из самых рациональных, правильных алгоритмов (ведь он одобрен Akina) smile 

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


Это сообщение отредактировал(а) KasMP - 22.12.2007, 11:19
PM MAIL   Вверх
Страницы: (3) [Все] 1 2 3 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

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


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

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

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

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


 




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


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

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