П/р по теме "Строки". Нельзя использовать массивы.Далее, после моих вопросов было получено несколько уточнений:

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

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

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

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


Короче не знаю, путано все, сложно и непонятно...  
Помогите, пожалуйста! Спасибо за то, что обратили внимание на мою полуламерскую, очень смутную тему.

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

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

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

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

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

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

Я не спорю, строка - разновидность массива  ... Но дословно было сказано именно так  .Спасибо за дубовый алгоритм (в нем тоже есть своя прелесть  ). Но у нас упор делается именно на рациональность алгоритма, его низкую сложность, красоту построения, т.п..А вот я попробую подумать  и представить   . Это же интересно...  
_____________________________________________________________________
У меня была такая мысль. Но зачем?
Имхо программа не станет проще от того, что вместо сравнения символа с несколькими заданными символами-разделителями
 будет производиться сначала поиск разделителей (т.е. по сути опять то же сравнение, о котором говорилось только что), а затем замена, а посл снова поиск.
Хотя  ... Ведь при поиске слов мы будем обращаться к одному и тому же символу далеко не один раз (рассматриваем разные комбинации). Т.е. с этой зрения рациональнее все же заменить: вместо многократных сравнений с несколькими символами мы получим многократные сравнения с одним символом -> сложность уменьшается в разы. Кажется, я поняла!Я пыталась понять, что это здесь и здесь. Видимо, не там искала?

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

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

Вот, например, строчка: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)? Нет?


          
          

Это сообщение отредактировал(а) KasMP - 27.11.2007, 15:11

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

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

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

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

Попробую пояснить мысль подбора вариантов. Допустим, у нас вот те самые 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, если в текущей группе не было дублирования символов, и единичку в последний ненулевой бит текущей маски (в приведенном примере это третий от хвоста бит), если оно было.

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

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

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


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

Спасибо большое, теперь ясно!
Правда есть недочет: формулировка "никакие 2 из которы не имеют общих букв" подразумевает, что внутри одного слова буквы могут повторяться (т.е. склеивать слова в одну строку и только потом сравнивать нельзя). Возможно. Строки можно и нужно, просто необходимо использовать - к/р по теме "Строки".

А то, что написано в посте Akina от 28.11.2007, 18:41 приведу тогда, когда опять преподаватель начнет: "но это же просто перебор... слишком много раз бегаем по строке..." (при этом ничего более оптимального не предлагает!!)

Пожалуйста, не бросайте на произвол судьбы!!

все пытаюсь привести постановку задачи к задаче на графах.
пока "дошел" до уровня матрицы смежности.
пускай матрица определяется так: каждая ячейка {i,j} представляет собой флаг(1 или 0) - является ли слово i имеющим общие со словом j буквы(1 - если имеются, 0 - еслши не имеются). все ячейки с одинаковым номером столбца и строки - имеют значение 0(для упрощения считаем, что слово с самим собой общих букв не имеет). Тогда у нас будет матрица из 0 и 1 размерностью NxN. Удаление слова из списка - удаление строки и столбца с одинаковым номером. теперь надо удалить минимальное количество строк, чтоб оставшаяся матрица состояла из одних нулей.