3 / 3 / 0
Регистрация: 20.06.2015
Сообщений: 20
|
|
1 | |
Усложненная задача на перестановки букв в слове21.06.2015, 11:50. Показов 3829. Ответов 10
Метки нет (Все метки)
Добрый день! Посчастливилось столкнуться с такой задачей:
"Cкoлькo paзличныx cлoв мoжнo cocтaвить из букв cлoвa «ЭKCЦEHTPИCИTET», ecли кaждoe cлoвo coдepжит poвнo oднo из пoдcлoв PИC, ЦИHK и TECT". Возможно, задача может показаться простой и тривиальной, но в формулировке задачи заложено много подводных камней, которые делают процесс решения далеко не однозначным. Реально ли в данном случае проверить результат, смоделировав задачу на языке программирования или в матпакете?
0
|
21.06.2015, 11:50 | |
Ответы с готовыми решениями:
10
Способы перестановки букв в слове Симфония Напишите программу циклической перестановки букв в слове X так, что i буква слова становится (i+1), а последняя - первой Усложненная задача - Найти силу торможения Усложненная задача открытия файла в папке |
2525 / 1751 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
|
|
21.06.2015, 16:47 | 2 |
Не вижу проблемы. Сначала найти кол-во перестановок, дающих подслово РИС, затем отдельно для ЦИНК, затем для ТЕСТ, Затем ЦИНК и РИС, РИС и ТЕСТ, ЦИНК и ТЕСТ, затем ЦИНК и ТЕСТ И РИС и метод включений-исключений подрубаем и получаем требуемое.
Добавлено через 40 секунд Кстати где?
0
|
3 / 3 / 0
Регистрация: 20.06.2015
Сообщений: 20
|
|
21.06.2015, 17:14 [ТС] | 3 |
Они обнаружатся, если провести вычисления и затем проверить результат. Кстати, как его можно проверить в каком-нибудь матпакете типа Matlab или Mathematica? Само условие, на мой взгляд, неоднозначно и допускает несколько трактовок, и результаты, соответственно, будут разными. Поэтому я бы начал с построения какой-либо модели. Попробуйте сами провести выкладки и получить результат хотя бы для одного подслова РИС (т.е. слово содержит РИС и не содержит ни ЦИНК, ни ТЕСТ), и увидите, что все не так однозначно.
0
|
2525 / 1751 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
|
|
21.06.2015, 17:23 | 4 |
Мда... Это тяжело... Пусть A - множество слов, содержащих РИС, B - ЦИНК, C - ТЕСТ. И РИС и ЦИНК содержат слова из , и РИС и ТЕСТ , все слова - , тогда кол-во слов, содержащих только РИС - . Все очень даже однозначно.
0
|
3 / 3 / 0
Регистрация: 20.06.2015
Сообщений: 20
|
|
21.06.2015, 17:43 [ТС] | 5 |
Я с вами согласен – это действительно не так просто, как кажется, иначе я бы не стал размещать здесь эту задачу. Даже результаты вычисления можностей множеств A, B и C могут не совпасть с результатами проверки, отсюда и желание провести независимую экспертизу. Быстро набросать модель для проверки мне не удалось, поэтому я и обратился на форум. Попробуйте сами провести вычисления и проверить результат, если это у вас получится. Это обычная задача из сборника типовых расчетов, поэтому я тоже не ожидал от нее никаких подвохов.
0
|
2525 / 1751 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
|
|
22.06.2015, 02:33 | 6 |
Сложность заключается в повторяющихся буквах. Можно разобраться с ними. Сделать их "различными" - проще говоря присвоить некоторый индекс, например T1, T2, T3 - искусственно ввести порядок, например ТЕСТ можно составить как Т1ЕСТ2 или Т3ЕСТ2 и т.д. Найти кол-во комбинаций, применить опять-таки принцип включений-исключений и уже на выходе исключить порядок (нужно будет разделить результат на 48=2!2!2!3!).
2
|
3 / 3 / 0
Регистрация: 20.06.2015
Сообщений: 20
|
|
22.06.2015, 14:54 [ТС] | 7 |
Сложности с повторяющимися буквами здесь как раз таки нет – нас не интересует, каким образом и из каких конкретно букв было составлено слово TECT (как Т1ЕСТ2 или как Т3ЕСТ2), потому что как только мы сформировали слово TECT (из любых подвернувшихся под руку букв), мы просто получили еще один атом – "метабукву" TECT, в дополнение к оставшимся 10 буквам, а потом просто применяем формулу перестановок с повторениями, учитывая парность букв И.
Сложность здесь в другом – она связана с повторяющимимся словами и касается именно слова TECT: оно может встречаться дважды в буквосочетании TECTECT (букв исходного слова для этого как раз достаточно) и как это сочетание обрабатывать (как одно слово, или как два) из условия задачи не ясно. Подробнее: в условии сказано "кaждoe cлoвo coдepжит poвнo oднo из пoдcлoв PИC, ЦИHK и TECT", но что именно означает выражение "poвнo oднo из пoдcлoв", не уточнено, а в данной ситуации это важно. Например, сочетание TECTECT можно рассматривать как одно подслово TECT, встречающееся два раза, и какую бы трактовку мы ни приняли, это приводит к дополнительным сложностям при определении мощности множеств. Эти сложности, конечно, вполне разрешимы, но именно это (в том числе) и я назвал "подводным камнем" в условии задачи. Второй подводный камень (с точки зрения добросовестного студента, решающего "сферическую задачу в вакууме" и не имеющего возможности уточнить условие) связан с тем, что не уточнено само понятие "слово", которое необходимо составлять из букв исходного слова ЭKCЦEHTPИCИTET, а именно: не сказано, сколько букв должно содержать это слово, т.е. должны быть использованы все 14 букв, или же слово PИC само по себе тоже подойдет – оно ведь не противоречит формулировке "cлoвo coдepжит poвнo oднo из пoдcлoв PИC, ЦИHK и TECT", т.к. содержит только слово PИC. В виду присутствия этих "камней" в русле решения мне и пришла в голову мысль построить модель задачи и проверить результат честным перебором, но почему это не удалось сделать легко и быстро, думаю, понятно. Спасибо за участие в обсуждении – мне хотелось получить свежий взгляд со стороны и проговорить все тонкие моменты вслух. Прием с нумерацией букв/слов вполне может пригоиться для разрешения коллизии со словом TECT, только немного в другом смысле.
0
|
2525 / 1751 / 152
Регистрация: 11.08.2012
Сообщений: 3,349
|
|
22.06.2015, 15:12 | 8 |
Не по теме: Хех. Я автоматически домысливаю, что кол-во букв в "слове" должно быть 14. Это уже привычка, которую на форуме выработал - достраивать условие задачи. Студенты постят частенько неполные условия, приходится врубать режим "хрустального шара" :D Вредная привычка, даа... Про "слова" видел специальную книжку, но, к сожалению, уже не вспомню автора и где её брал. *** Обобщить задачу на слова с разным кол-вом букв можно, считать только долго и нудно. Можно впрочем попробовать. *** Постановка задачи, по всей видимости, просто не корректна. А откуда такая проблема возникла?
0
|
204 / 141 / 57
Регистрация: 25.12.2014
Сообщений: 446
|
|
22.06.2015, 15:35 | 9 |
Количество слов, имеющих в составе РИС, но не содержащих ни ЦИНК, ни ТЕСТ можно подсчитать так.
Рассматриваем все разные перестановки букв ЭKCЦEHTPИTET (от РИС оставляем только букву Р). Таких слов 12!/(2!*3!), но среди них есть слова содержащие ЦИНК, их надо исключить. Для этого считаем перестановки букв ЭCЦETPTET. Их 9!/(2!*3!) А сколько слов содержат ТЕСТ? Для этого считаем перестановки букв ЭKCЦEHTPИ. Их 9! А если ТЕСТ и ЦИНК содержатся одновременно, то слов будет столько, сколько перестановок ЭCЦETP, т.е. 6! Итак, слов содержащих РИС, но не содержащих ни ЦИНК ни ТЕСТ ровно 12!/(2!*3!)-9!/(2!*3!)-9!+6! Аналогично, можно посчитать и для оставшихся двух слов.
0
|
3 / 3 / 0
Регистрация: 20.06.2015
Сообщений: 20
|
|
22.06.2015, 15:46 [ТС] | 10 |
В этом необходимости нет – если задачу удастся решить для всех 14 букв, то потом просто останется рассмотреть по тому же алгоритму все остальные возможные сочетания из меньшего количества букв, т.е. это именно долго и нудно, но совсем не сложно (чисто бухгалтерская работа).
Вот здесь соглашусь – вопросов к условию достаточно, и, как выясняется, не только самых очевидных. Не могу быть уверен, но не удивлюсь, если сам автор не предусмотрел особого случая со словом TECT, хотя это очень маловероятно, конечно. Сама задача взята из сборника типовых расчетов одного из технических вузов (название которого мы по понятным причинам здесь не будем упоминать всуе) и просто случайно подвернулась под руку. Никаких особых сложностей в ней не предполагалось. TrueTerm, не могли бы вы, пожалуйста, рассчитать, сколько уникальных слов содержат слово TECT (наряду, возможно, с другими словами из списка), чтобы мы могли сравнить наши результаты.
0
|
3 / 3 / 0
Регистрация: 20.06.2015
Сообщений: 20
|
|
25.06.2015, 08:46 [ТС] | 11 |
cmath, TrueTerm, Байт (никого не забыл?), мне-таки удалось довести решение задачи до получения ответа в явном виде и проверить результат, построив компьютерную модель, но и первое, и второе далось ценой значительных усилий, т.к. задача по количеству нюансов и возможностей, которые необходимо учесть, чем-то напоминает сад расходящихся тропок Борхеса. Если кто-то располагает достаточным запасом времени и хочет проверить свои силы, можем сверить полученные результаты. В сборник типовых расчетов задача скорее всего попала по недосмотру составителя, т.к. больше похожа на мини-курсовую по теме "Формула включений–исключений".
Добавлено через 5 минут Конкретно вот этот вот пункт не совсем верен, хотя общий подход, конечно, правильный. Для слова РИС все подсчитано верно.
0
|
25.06.2015, 08:46 | |
25.06.2015, 08:46 | |
Помогаю со студенческими работами здесь
11
Дано слово. Поменять местами первую из букв a и последнюю из букв о. Учесть возможность того, что таких букв слове может и не быть Поиск букв в слове. Напишите программу для проверки, есть ли в слове Х буква «а» Составьте программу подсчета числа тех гласных букв в слове Х, что не используются в слове Z Найти количество тех гласных букв в одном слове, что присутствуют в другом слове Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |