Форум » Кодирование и декодирование информации » Комбинаторика. Задания 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
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) Дорабатывать другие, предложенные мною коды не имеет смысла, но кто пожелает, можно сделать и это! А я остановлюсь на лаконичном, на мой взгляд, коде, предложенном Гошей Ищенко, только без красной строки
полная версия страницы