Комбинаторика. Задания 8

Форум » Кодирование и декодирование информации » Комбинаторика. Задания 8 » Ответить

Комбинаторика. Задания 8

Елена_10: В задаче № 5750. (М. Байрамгулов) Ваня составляет 6-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно убрать три буквы и получить слово КОТ. Сколько различных слов может составить Ваня? Прошу уточнить условие. Что имеется ввиду? Все возможные перестановки с повторениями из 6 букв, в которых есть буквы К О Т в любом порядке или же порядок расположения этих букв важен? Ответ не сходится {from itertools import * al='КОМПЬЮТЕР' a = list(product(al, repeat=6)) b = list(permutations(al, 6)) k=0 for i in a: sl=''.join(i) #print(sl) k1=sl.find('К') k2=sl.find('О') k3=sl.find('Т') if 'К'in sl and 'О'in sl and 'Т'in sl: if k1<k2<k3: #print(sl) k=k+1 print('Размещения с повторениями ',k) for i in b: sl=''.join(i) #print(sl) k1=sl.find('К') k2=sl.find('О') k3=sl.find('Т') if 'К'in sl and 'О'in sl and 'Т'in sl: if k1<k2<k3: #print(sl) k=k+1 print('Перестановки ',k) #Ответ: 11249 # product(al, repeat=6) дает 8550 # Перестановки - permutations 10950}

Ответов - 22, стр: 1 2 All

Елена_10: (№ 5749) (М. Байрамгулов) Миша составляет 5-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно переставить буквы и получить палиндром. Сколько различных слов может составить Миша? Ответ на сайте 8649...Ответ не сходится, у меня 729 {from itertools import * al='КОМПЬЮТЕР' c=0 sl='' b = list(product(al, repeat=5)) k=0 print('Перестановки ',k) for i in b: sl=''.join(i) #print(sl) if sl[0]==sl[4] and sl[1]==sl[3]: print(sl) k=k+1 print('Количество слов ',k) }

s11kai: Елена_10 пишет: так, что в них можно переставить буквы и получить палиндром У меня тоже 729, видимо мы одинаково понимаем вопрос, но не совсем так, как его ставит автор! Может быть, что под переставить буквы нужно понимать следующее, допустим было слово ОРПОР перестановкой двух символов получим палиндром - РОПОР В таком случае, даже из любого слова, состоящего из трех разных символов, например ПРООР или ПРРОО можно построить как минимум по 2 палиндрома!

s11kai: Елена_10 пишет: порядке или же порядок расположения этих букв важен? Ответ не сходится Порядок важен! Посмотрите решение, предложенное Поляковым К.Ю., и сможете скорректировать свое решение [pre2] count = 0 from itertools import product for n in set(product( 'КОМПЬЮТЕР', repeat=6 )): n = ''.join(n) if n.find('К') >= 0 and n.rfind('Т')>= 0: for j in range(n.find('К')+1, n.rfind('Т')): if n[j] == 'О': count += 1 break print( count ) [/pre2]

s11kai: а можно и так: [pre2] ss = set() from itertools import product for n in set(product( 'КОМПЬЮТЕР', repeat=6 )): n = ''.join(n) if n.find('К') >= 0 and n.rfind('Т')>= 0: for j in range(n.find('К')+1, n.rfind('Т')): if n[j] == 'О': ss.add(n) print( len(ss) ) [/pre2]

s11kai: [pre2] ss = set() from itertools import product for n in set(product( 'КОМПЬЮТЕР', repeat=6 )): n = ''.join(n) if n.find('К') >= 0 and n.rfind('Т')>= 0: if n.find('О', n.find('К'), n.rfind('Т'))>0: ss.add(n) print(len(ss)) [/pre2]

Ж: Ответ верен, если буквы могут повторяться. Иначе верный ответ 2400 В решении Полякова (если распечатать учтенные им слова) есть такие слова: 'КОКТКК', 'ККОКТК', 'КОТККК', 'ККККОТ', 'КККОКТ', 'ККОТКК', 'КОКККТ', 'КККОТК' Буква К повторяется...

s11kai: Ж пишет: Ответ верен, если буквы могут повторяться. Иначе верный ответ 2400 В решении Полякова (если распечатать учтенные им слова) есть такие слова: 'КОКТКК', 'ККОКТК', 'КОТККК', 'ККККОТ', 'КККОКТ', 'ККОТКК', 'КОКККТ', 'КККОТК' Буква К повторяется... Пофиг, в условии оговорено, если убрать 3 буквы: 'КОКТКК', где сказано, что они не должны быть буквами К? К примеру, убираем ровно три буквы, выделенных красным, и получаем слово - КОТ

Ж: Решение с помощью регулярных выражений: [pre2] alfavit='КОМПЬЮТЕР'; spisok=[] for slova in product(alfavit,repeat=6): # ответ 2400 #for slova in permutations(alfavit,6): # ответ 11249 slovo=''.join(slova) if fullmatch('.*К.*О.*Т.*',slovo): spisok.append(slovo) print(len(spisok)) [/pre2]

s11kai: Ж пишет: alfavit='КОМПЬЮТЕР'; spisok=[] for slova in product(alfavit,repeat=6): # ответ 2400 #for slova in permutations(alfavit,6): # ответ 11249 slovo=''.join(slova) if fullmatch('.*К.*О.*Т.*',slovo): spisok.append(slovo) print(len(spisok)) запустил ваш код и вот что получил: Traceback (most recent call last): ... if fullmatch('.*К.*О.*Т.*',slovo): NameError: name 'fullmatch' is not defined

s11kai: s11kai пишет: NameError: name 'fullmatch' is not defined Код удалось запустить, после небольшой доработки: [pre2] import re alfavit='КОМПЬЮТЕР'; spisok=[] for slova in product(alfavit,repeat=6): # ответ 2400 #for slova in permutations(alfavit,6): # ответ 11249 slovo=''.join(slova) if re.fullmatch('.*К.*О.*Т.*',slovo): spisok.append(slovo) print(len(spisok)) [/pre2] Причем вместо указанного Вами ответа в 2400, он дал ответ 11249

s11kai: Елена_10 пишет: № 5750. (М. Байрамгулов) Ваня составляет 6-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно убрать три буквы и получить слово КОТ. Сколько различных слов может составить Ваня? А где здесь оговаривается, что буквы не могут повторяться? А раз нет, то и ответ = 11249

Ж: Ваня составляет 6-буквенные слова из букв слова КОМПЬЮТЕР Представьте, что вы разрезали слово на буквы и из них собираете новые слова. Там нет повторяющихся... , поэтому считаю, что формулировка неоднозначна. Это уже вопросы к русскому языку и его пониманию... Я понимаю так... Иначе, зачем в аналогичном задании 5720 все так подробно оговорено: Алина составляет пятибуквенные слова из букв слова POLYGON, причем известно, что буквы в словах могут повторяться любое количество раз или же не встречаться вовсе. Помогите Алине найти количество различных слов, являющимися палиндромами и содержащими в середине гласную букву.

s11kai: Ж пишет: поэтому считаю, что формулировка неоднозначна. Это уже вопросы к русскому языку и его пониманию... Нашел автора этого задания в ege8 от Полякова: 302) (М. Байрамгулов) Ваня составляет 6-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно убрать три буквы и получить слово КОТ. Сколько различных слов может составить Ваня? Что характерно, там стоит ответ 11249

s11kai: Ж пишет: Представьте, что вы разрезали слово на буквы и из них собираете новые слова А почему не взять "кассу" из букваря, где под каждой буквой лежит некоторое количество их копий

Ж: Возможно потому, что буквы сказали брать не из кассы, а из слова... А в слове КОМПЬЮТЕР ровно 9 букв и клонов нет... И я не оспариваю ответ, я беру на заметку, что авторы так понимают это задание. И в будущем буду учитывать их понимание. И есть же формулировки, которые эту неоднозначность не порождают: Сколько пятибуквенных слов можно составить из букв данного алфавита А, Б, В, Г, Д Вася составляет 5-буквенные слова, в которых встречаются только буквы А, Б, В, Г,

s11kai: Ж пишет: сказали брать не из кассы, а из слова Если быть точнее, то ... из букв слова КОМПЬЮТЕР... ,а раз нет иных ограничений, то и следует, что слово: КОМПЬЮТЕР задает алфавит, из которого уже и собираются интересуемые слова Ну да ладно, чего зря "ломать копья" каждый остается при своем мнении, коль с самого автора не спросить.

Гоша Ищенко: Сначала мы получаем всевозможные палиндромы из данного набора букв, потом считаем возможное количество перестановок в этих палиндромах. from itertools import * l = [''.join(i) for i in product('КОМПЬЮТЕР', repeat=3)] m = set() for i in l: s = i + i[-2] + i[-3] for j in permutations(s): s2 = ''.join(j) m.add(s2) print(len(m))

s11kai: Гоша Ищенко пишет: [pre2]from itertools import * l = [''.join(i) for i in product('КОМПЬЮТЕР', repeat=3)] m = set() for i in l: s = i + i[-2] + i[-3] for j in permutations(s): s2 = ''.join(j) #эту строку, например, можно удалить! m.add(s2) print(len(m)) [/pre2] Красивое решение, но из анализа кода, осмелюсь предположить, что это решение для задачи: "301)(М. Байрамгулов) Миша составляет 5-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно переставить буквы и получить палиндром. Сколько различных слов может составить Миша?", а не про КОТА! 302) (М. Байрамгулов) Ваня составляет 6-буквенные слова из букв слова КОМПЬЮТЕР так, что в них можно убрать три буквы и получить слово КОТ. Сколько различных слов может составить Ваня? Но, в любом случае, не бывает программного кода, который нельзя сократить хотя бы на одну строку: [pre2] from itertools import * l = [''.join(i) for i in product('КОМПЬЮТЕР', repeat=3)] m = set() for i in l: s = i + i[-2] + i[-3] for j in permutations(s): m.add(j) print(len(m)) [/pre2]

s11kai: Я тут подумал, а что если из кода убрать одну строку и она при этом выдает тот же результат, то может быть можно вообще переписать данный код в одну строку! Рассуждаем примерно так: В слове КОМПЬЮТЕР всего 9 букв, следовательно в палиндроме на первых трех местах может стоять по 9 разных символов, причем символы стоящие на первом и пятом месте, как и, второй с четвертым, должны совпадать. Стало быть, количество слов - палиндромов, можно рассчитать по формуле N = 9 * 9 * 9 В питоне эта строка может выглядеть так: print('ответ:',9*9*9) ответ: 729 Вау!!! Видим, что ответ совершенно другой! Стало быть, программа, предложенная вами дает неверный результат! или, неверны мои рассуждения

s11kai: Вот алгоритм, дающий одинаковый результат и программой, и, рассуждением! [pre2] from itertools import product m = set() for x in product('КОМПЬЮТЕР', repeat=5): s = ''.join(x) if s == s[::-1]: # если слово читается слева и справа одинаково m.add(s) # запоминаем его с учетом отсутствия совпадений print('Вариант решения №1', len(m)) print('Вариант решения №2',9*9*9) [/pre2] В связи с чем, осмелюсь предположить, что не верен именно ваш ответ, Гоша Ищенко: 8649, а правильным будет ответ - 729 Страшно конечно, а вдруг я просчитался? Поправьте, на ошибках тоже учатся!

s11kai: Гоша Ищенко! Прошу прощения, я ошибался, поскольку учитывал только палиндромы, а нужно было считать слова, из которых можно получить палиндромы Вот лоханулся,так лоханулся!

s11kai: Но мысль, о том что многострочный код можно переписать в однострочный, в данном случае была верна. Рассуждаем примерно так: • количество всех палиндромов 9*9*9 = 729 • всего разных букв 9 это означает, что есть ровно 9 палиндромов состоящих из одной буквы, т.е. 9 пятибуквенных слов, например, ККККК, ООООО, МММММ… • количество трехбуквенных палиндромов равно 729 – 9 = 720 • из трех символов ПАЛИНРОМА можно составить – КОМ, КМО, КММ, КОО => 4*3 = 12 слов • Итого слов будет: 720 * 12 + 9 = 8649 • Или в однострочном коде это будет выглядеть как-то так: print((9 * 9 * 9 – 9) * 12 + 9) Дорабатывать другие, предложенные мною коды не имеет смысла, но кто пожелает, можно сделать и это! А я остановлюсь на лаконичном, на мой взгляд, коде, предложенном Гошей Ищенко, только без красной строки

полная версия страницы