Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [Алгоритм] Строки: найти макс.набор слов,

Автор: KasMP 26.11.2007, 17:53

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

Автор: JackYF 26.11.2007, 18:33

Цитата(KasMP @  26.11.2007,  17:53 ) Нельзя использовать массивы. Круто. А что можно? строка - не массив?    В общем, идея дубового решения такова (очень похожа на идею решения задачи на графах, правда, какой, не помню ): 1. Выделить все слова из строки. 2. Из каждого слова сформировать набор, пока состоящий из этого слова. 3. Затем, для каждой группы и для каждого другого слова сравнить его набор букв с набором букв слов из группы, если не совпали, добавить в группу. После этого этапа мы будем иметь группы из одного слова и группы из двух. Группы из одного слова нам уже не нужны, забиваем на них. 4. Повторяем процедуру №3, вычёркиваем все группы, состоящие уже из двух слова, оставляем только трёхсловные группы. 4+. И так далее, пока нечего будет добавлять к группам. 5. Пройтись по группам, подсчитать количество слов в группах. Как это дело организовать "без массивов", я не очень себе представляю. Массив - одна из базовых структур языка программирования, без них как без ног...

Автор: Akina 26.11.2007, 18:39

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

Автор: KasMP 26.11.2007, 23:54

Цитата(JackYF @  26.11.2007,  18:33 ) Круто. А что можно? строка - не массив? Я не спорю, строка - разновидность массива  ... Но дословно было сказано именно так  . Цитата(JackYF @  26.11.2007,  18:33 ) В общем, идея дубового решения такова (очень похожа на идею решения задачи на графах, правда, какой, не помню smile): Спасибо за дубовый алгоритм (в нем тоже есть своя прелесть  ). Но у нас упор делается именно на рациональность алгоритма, его низкую сложность, красоту построения, т.п.. Цитата(JackYF @  26.11.2007,  18:33 ) Как это дело организовать "без массивов", я не очень себе представляю. Массив - одна из базовых структур языка программирования, без них как без ног...  А вот я попробую подумать  и представить   . Это же интересно...   _____________________________________________________________________ Цитата(Akina @  26.11.2007,  18:39 ) Для начала поменяй все символы-разделители на, скажем, пробелы. У меня была такая мысль. Но зачем? Имхо программа не станет проще от того, что вместо сравнения символа с несколькими заданными символами-разделителями  будет производиться сначала поиск разделителей (т.е. по сути опять то же сравнение, о котором говорилось только что), а затем замена, а посл снова поиск. Хотя  ... Ведь при поиске слов мы будем обращаться к одному и тому же символу далеко не один раз (рассматриваем разные комбинации). Т.е. с этой зрения рациональнее все же заменить: вместо многократных сравнений с несколькими символами мы получим многократные сравнения с одним символом -> сложность уменьшается в разы. Кажется, я поняла! Цитата(Akina @  26.11.2007,  18:39 ) байтовую маску Я пыталась понять, что это http://www.google.ru/search?hl=ru&q=байтовая+маска и http://ru.wikipedia.org/wiki/байтовая_маска. Видимо, не там искала?

Автор: Akina 27.11.2007, 10:06

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

Автор: KasMP 27.11.2007, 15:03

А если не доходит, как реализовать это на паскале, то лучше создать новую тему (чтобы был порядок) или можно продолжить здесь (чтобы не забивать форум)?  Цитата(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)? Нет?

Автор: GIK 27.11.2007, 16:07

Яб сделал так: 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) Все вроде...

Автор: KasMP 27.11.2007, 18:35

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

Автор: Akina 27.11.2007, 18:57

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

Автор: GIK 28.11.2007, 12:46

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

Автор: SaDFromSpb 28.11.2007, 17:59

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

Автор: Akina 28.11.2007, 18:41

Цитата(SaDFromSpb @  28.11.2007,  18:59 ) Вроде как, это задача на NP-полноту, то есть самое оптимальное решение может быть достигнуто только полным перебором.  Верно. Впрочем, при правильном построении программы (в данном случае это может быть например перестроение слов с сортировкой их символов + сортировка слов по длине) количество отбрасываемых вариантов может гарантированно составлять более половины возможных. Цитата(SaDFromSpb @  28.11.2007,  18:59 ) Чтобы утверждать наверняка, нужно это четко доказать. Достаточно того, что вероятность наличия какого-либо символа в каком-либо слове не может быть рассчитана на основании знания части или всех остальных слов. Т.е. каждое из слов полностью независимо. Впрочем, можно доказать, что ПОЛНОГО перебора в общем случае нет - количество слов в группе заведомо не больше количества символов в алфавите, но на суть это не влияет.

Автор: KasMP 2.12.2007, 15:58

Цитата(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 приведу тогда, когда опять преподаватель начнет: "но это же просто перебор... слишком много раз бегаем по строке..." (при этом ничего более оптимального не предлагает!!)

Автор: KasMP 9.12.2007, 10:46

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

Автор: skyboy 15.12.2007, 14:46

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

Автор: KasMP 16.12.2007, 08:19

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

Автор: SelenIT 16.12.2007, 12:30

Если попытаться подойти с другой стороны - для каждой буквы алфавита посчитать количество слов в строке, в которых она встречается, а потом оставить слова только из тех букв, для которых это количество равно единице? Без массивов, конечно, такое сделать трудно... Upd.: пришла идея алгоритма. Всего используем 4 строки - исходная, полный алфавит, вспомогательная и результат (две последние изначально пусты). Этап первый. Берем первую букву алфавита и ищем ее в исходной строке. Нашли - добавляем ее во вспомогательную строку и продолжаем анализировать исходную. Если после обнаружения этой буквы в исходной строке встретился символ не из алфавита, а потом, спустя сколько-то символов, опять эта буква - это значит, что она повторяется как минимум в двух словах и нам не подходит - удаляем ее из вспомогательной строки и переходим к следующей букве алфавита. В конце первого этапа вспомогательная строка будет состоять исключительно из букв, встречающихся лишь в одном слове. Этап второй. Берем исходную строку и ищем слова, состоящие исключительно из букв вспомогательной строки. Нашли - копируем посимвольно в результат и добавляем пробел. Когда исходная строка пройдена до конца, удаляем из результата лишний концевой пробел и выводим его (результат). Upd 2 [obsoleted by Upd. 3] Upd 3: не... вроде, померещилось, "походу" все верно)

Автор: skyboy 16.12.2007, 14:12

Цитата(SelenIT @  16.12.2007,  11:30 ) для каждой буквы алфавита посчитать количество слов в строке, в которых она встречается, а потом оставить слова только из тех букв, для которых это количество равно единице? Цитата ложка ложка ложка каждая буква встречается трижды. но из строки можно выбрать множество слов(одно слово), для которого(множества) буквы повторяться не будут. Добавлено через 26 секунд Цитата(KasMP @  16.12.2007,  07:19 ) гм... интересно. не. слишком заумно. кроме того, алгоритм так и не сформировался. думаю.

Автор: SelenIT 16.12.2007, 14:35

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

Автор: KasMP 16.12.2007, 15:20

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

Автор: SelenIT 16.12.2007, 15:56

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

Автор: powerfox 16.12.2007, 16:02

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

Автор: KasMP 16.12.2007, 17:29

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

Автор: powerfox 16.12.2007, 18:18

Цитата(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; Главное, нормально написать инициализацию новых элементов (не забыть о выделении памяти).

Автор: KasMP 16.12.2007, 20:35

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

Автор: KasMP 20.12.2007, 16:46

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

Автор: GoshaNahui 20.12.2007, 18:01

дак с массивами то всё просто. тогда перебираешь с рекурсией и всё а поотом мы сделаем с масивами а потом и без них! то-то она рада будет Добавлено через 2 минуты и 58 секунд дак с массивами то всё просто. тогда перебираешь с рекурсией и всё а поотом мы сделаем с масивами а потом и без них! то-то она рада будет

Автор: skyboy 20.12.2007, 18:37

Цитата(KasMP @  20.12.2007,  15:46 ) так вот, преподаватель сдалась и разрешила использовать массивы!!!!!! лучше бы она сдалась и поставила оценку только за реализацию анализа   теперь бы придумать алгоритм получения пустого графа за минимальное количество шагов... ни у кого нет подборки алгоритмов трансформации графа?

Автор: Akina 20.12.2007, 18:50

Цитата(KasMP @  16.12.2007,  16:20 ) непонятно, как отличить два слова, одно из которых имеет две одинаковы буквы ("паскаль", "мяч") от двух слов, имеющих общие буквы ("мяч", "грач"), Вообще-то если В ОДНОМ СЛОВЕ разрешены повторы - текст должен пройти предобработку, которая их уберет (грубо - превратит каждое слово в набор уникальных для этого слова символов), и плевать что смысл слова потеряется, для задачи он как раз нахрен не нужен, ибо исходный массив не трогается, а мыв оперируем не словом, а его позицией в исходном тексте для его идентификации (во блин завернул!). В условиях запрета на массивы это пришлось бы делать с каждым словом в процессе обработки. Но не суть. Т.е. тот же "паскаль" превращается хоть в "паскль", хоть в "скальп" - неважно, на поиск совпадающих символов это никак не влияет. Добавлено через 1 минуту и 11 секунд Цитата(skyboy @  20.12.2007,  19:37 ) теперь бы придумать алгоритм получения пустого графа за минимальное количество шагов...  Не факт, что это будет оптимальный для задачи граф :( Добавлено через 6 минут и 5 секунд Цитата(SelenIT @  16.12.2007,  15:35 ) что делать с повторяющимися словами, непонятно По-любому в результирующий оптимальный набор войдет только одно из них (или ни одного). Но если войдет - пофиг какое, задача найти один любой оптимум, а не все существующие оптимумы.

Автор: KasMP 20.12.2007, 19:52

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

Автор: Akina 21.12.2007, 13:21

Так... ну тебе же разрешили массивы! Значит, сразу это используй. Первые этапы работы: 0) Получение копии исходной строки (чтобы не пакостить ее) 1) Замена на пробелы всех других возможных разделителей 2) Разбивка полученной строки в массив по разделителю-пробелу (Split) - в каждом элементе массива получается 1 слово 3) Обработка этого массива с выбрасыванием не-слов и со сжатием слов (удалением дублирующихся в слове символов) А дальше уже любым способом организуй перебор (да хоть полным перебором вариантов сочетаний). Сделай отдельной функцией проверку на существование повторяющихся символов - так будет удобнее. В общем, начинай создавать код. А мы заодно поймем. на каком языке программирования ты делаешь работу

Автор: KasMP 22.12.2007, 11:18

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)