В алфавите языке племени «тумба-юмба» четыре буквы: «K», «L», «M» и «N». Нужно вывести на экран все возможные слова, состоящие из n букв (n>1), в которых вторая буква «K». Подсчитайте количество таких слов.
Сейчас я могу только перебрать все возможные варианты :/
def TumbaWords(word, alphabet, n): if n < 1: print(word) return for c in alphabet: TumbaWords(word+c, alphabet, n — 1) x = list(word) n = int(input()) TumbaWords(«»,»KLMN», n)
Отслеживать
25.1k 7 7 золотых знаков 30 30 серебряных знаков 46 46 бронзовых знаков
задан 26 дек 2019 в 14:47
Mikey_mouse Mikey_mouse
179 6 6 серебряных знаков 17 17 бронзовых знаков
Каков будет вопрос?
26 дек 2019 в 14:51
Вам точно нужна рекурсия? В питоне она довольно ограниченная по глубине. Лучше как-то через циклы решить. Да и вообще данная задача решается скорее алгебраически, а не перебором.
26 дек 2019 в 15:05
26 дек 2019 в 15:15
26 дек 2019 в 15:17
количество = 4 * 1 * 4 * . всего n сомножителей . * 4 . Другими словами 4**(n — 1)
26 дек 2019 в 17:25
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Решение без рекурсии
Поскольку нужно не посчитать их количество, а вывести на экран, сделать это действительно можно только перебором. Но перебирать второй символ бессмысленно, потому количество вариантов для перебора сокращается сразу вчетверо. Могу предложить такой вариант:
Python #18 Обработка символьных строк
n = int(input(‘N > ‘)) alphabet = [‘K’, ‘L’, ‘M’, ‘N’] res = [‘KK’, ‘LK’, ‘MK’, ‘NK’] def extend(d: dict, alphabet: dict) -> dict: return [item + a for item in d for a in alphabet if type(a) == type(‘a’)] if n > 2: for i in range(n-2): res = extend(res, alphabet) print(res) print(‘Всего слов’, len(res))
N > 5 [‘KKKKK’, ‘KKKKL’, ‘KKKKM’, ‘KKKKN’, ‘KKKLK’, ‘KKKLL’, ‘KKKLM’, ‘KKKLN’, ‘KKKMK’, ‘KKKML’, ‘KKKMM’, ‘KKKMN’, ‘KKKNK’, ‘KKKNL’, ‘KKKNM’, ‘KKKNN’, ‘KKLKK’, ‘KKLKL’, ‘KKLKM’, ‘KKLKN’, ‘KKLLK’, ‘KKLLL’, ‘KKLLM’, ‘KKLLN’, ‘KKLMK’, ‘KKLML’, ‘KKLMM’, ‘KKLMN’, ‘KKLNK’, ‘KKLNL’, ‘KKLNM’, ‘KKLNN’, ‘KKMKK’, ‘KKMKL’, ‘KKMKM’, ‘KKMKN’, ‘KKMLK’, ‘KKMLL’, ‘KKMLM’, ‘KKMLN’, ‘KKMMK’, ‘KKMML’, ‘KKMMM’, ‘KKMMN’, ‘KKMNK’, ‘KKMNL’, ‘KKMNM’, ‘KKMNN’, ‘KKNKK’, ‘KKNKL’, ‘KKNKM’, ‘KKNKN’, ‘KKNLK’, ‘KKNLL’, ‘KKNLM’, ‘KKNLN’, ‘KKNMK’, ‘KKNML’, ‘KKNMM’, ‘KKNMN’, ‘KKNNK’, ‘KKNNL’, ‘KKNNM’, ‘KKNNN’, ‘LKKKK’, ‘LKKKL’, ‘LKKKM’, ‘LKKKN’, ‘LKKLK’, ‘LKKLL’, ‘LKKLM’,’LKKLN’, ‘LKKMK’, ‘LKKML’, ‘LKKMM’, ‘LKKMN’, ‘LKKNK’, ‘LKKNL’, ‘LKKNM’, ‘LKKNN’, ‘LKLKK’, ‘LKLKL’, ‘LKLKM’, ‘LKLKN’, ‘LKLLK’, ‘LKLLL’, ‘LKLLM’, ‘LKLLN’, ‘LKLMK’, ‘LKLML’, ‘LKLMM’, ‘LKLMN’, ‘LKLNK’, ‘LKLNL’, ‘LKLNM’, ‘LKLNN’, ‘LKMKK’, ‘LKMKL’, ‘LKMKM’, ‘LKMKN’, ‘LKMLK’, ‘LKMLL’, ‘LKMLM’, ‘LKMLN’, ‘LKMMK’, ‘LKMML’, ‘LKMMM’, ‘LKMMN’, ‘LKMNK’, ‘LKMNL’, ‘LKMNM’, ‘LKMNN’, ‘LKNKK’, ‘LKNKL’, ‘LKNKM’, ‘LKNKN’, ‘LKNLK’, ‘LKNLL’, ‘LKNLM’, ‘LKNLN’, ‘LKNMK’, ‘LKNML’, ‘LKNMM’, ‘LKNMN’, ‘LKNNK’, ‘LKNNL’, ‘LKNNM’, ‘LKNNN’, ‘MKKKK’, ‘MKKKL’, ‘MKKKM’, ‘MKKKN’, ‘MKKLK’, ‘MKKLL’, ‘MKKLM’, ‘MKKLN’, ‘MKKMK’, ‘MKKML’, ‘MKKMM’, ‘MKKMN’, ‘MKKNK’, ‘MKKNL’, ‘MKKNM’, ‘MKKNN’, ‘MKLKK’, ‘MKLKL’, ‘MKLKM’, ‘MKLKN’, ‘MKLLK’, ‘MKLLL’, ‘MKLLM’,’MKLLN’, ‘MKLMK’, ‘MKLML’, ‘MKLMM’, ‘MKLMN’, ‘MKLNK’, ‘MKLNL’, ‘MKLNM’, ‘MKLNN’, ‘MKMKK’, ‘MKMKL’, ‘MKMKM’, ‘MKMKN’, ‘MKMLK’, ‘MKMLL’, ‘MKMLM’, ‘MKMLN’, ‘MKMMK’, ‘MKMML’, ‘MKMMM’, ‘MKMMN’, ‘MKMNK’, ‘MKMNL’, ‘MKMNM’, ‘MKMNN’, ‘MKNKK’, ‘MKNKL’, ‘MKNKM’, ‘MKNKN’, ‘MKNLK’, ‘MKNLL’, ‘MKNLM’, ‘MKNLN’, ‘MKNMK’, ‘MKNML’, ‘MKNMM’, ‘MKNMN’, ‘MKNNK’, ‘MKNNL’, ‘MKNNM’, ‘MKNNN’, ‘NKKKK’, ‘NKKKL’, ‘NKKKM’, ‘NKKKN’, ‘NKKLK’, ‘NKKLL’, ‘NKKLM’, ‘NKKLN’, ‘NKKMK’, ‘NKKML’, ‘NKKMM’, ‘NKKMN’, ‘NKKNK’, ‘NKKNL’, ‘NKKNM’, ‘NKKNN’, ‘NKLKK’, ‘NKLKL’, ‘NKLKM’, ‘NKLKN’, ‘NKLLK’, ‘NKLLL’, ‘NKLLM’, ‘NKLLN’, ‘NKLMK’, ‘NKLML’, ‘NKLMM’, ‘NKLMN’, ‘NKLNK’, ‘NKLNL’, ‘NKLNM’, ‘NKLNN’, ‘NKMKK’, ‘NKMKL’, ‘NKMKM’, ‘NKMKN’, ‘NKMLK’, ‘NKMLL’, ‘NKMLM’,’NKMLN’, ‘NKMMK’, ‘NKMML’, ‘NKMMM’, ‘NKMMN’, ‘NKMNK’, ‘NKMNL’, ‘NKMNM’, ‘NKMNN’, ‘NKNKK’, ‘NKNKL’, ‘NKNKM’, ‘NKNKN’, ‘NKNLK’, ‘NKNLL’, ‘NKNLM’, ‘NKNLN’, ‘NKNMK’, ‘NKNML’, ‘NKNMM’, ‘NKNMN’, ‘NKNNK’, ‘NKNNL’, ‘NKNNM’, ‘NKNNN’] Всего слов 256
UPD: рекурсивное решение
Но если рекурсия не является обязательной, лучше использовать вариант выше
Строки в с++. Нуль терминатор. Что такое строка в с++. char c++ массив. С++ Для начинающих. Урок #60
n = int(input(‘N > ‘)) alphabet = [‘K’, ‘L’, ‘M’, ‘N’] res = [‘KK’, ‘LK’, ‘MK’, ‘NK’] def extend(d: dict, alphabet: dict, l: int) -> dict: if len(d[0]) >= l: return d return extend([item + a for item in d for a in alphabet if type(a) == type(‘a’)], alphabet, l) res = extend(res, alphabet, n) print(res) print(‘Всего слов’, len(res))
N > 5 [‘KKKKK’, ‘KKKKL’, ‘KKKKM’, ‘KKKKN’, ‘KKKLK’, ‘KKKLL’, ‘KKKLM’, ‘KKKLN’, ‘KKKMK’, ‘KKKML’, ‘KKKMM’, ‘KKKMN’, ‘KKKNK’, ‘KKKNL’, ‘KKKNM’, ‘KKKNN’, ‘KKLKK’, ‘KKLKL’, ‘KKLKM’, ‘KKLKN’, ‘KKLLK’, ‘KKLLL’, ‘KKLLM’, ‘KKLLN’, ‘KKLMK’, ‘KKLML’, ‘KKLMM’, ‘KKLMN’, ‘KKLNK’, ‘KKLNL’, ‘KKLNM’, ‘KKLNN’, ‘KKMKK’, ‘KKMKL’, ‘KKMKM’, ‘KKMKN’, ‘KKMLK’, ‘KKMLL’, ‘KKMLM’, ‘KKMLN’, ‘KKMMK’, ‘KKMML’, ‘KKMMM’, ‘KKMMN’, ‘KKMNK’, ‘KKMNL’, ‘KKMNM’, ‘KKMNN’, ‘KKNKK’, ‘KKNKL’, ‘KKNKM’, ‘KKNKN’, ‘KKNLK’, ‘KKNLL’, ‘KKNLM’, ‘KKNLN’, ‘KKNMK’, ‘KKNML’, ‘KKNMM’, ‘KKNMN’, ‘KKNNK’, ‘KKNNL’, ‘KKNNM’, ‘KKNNN’, ‘LKKKK’, ‘LKKKL’, ‘LKKKM’, ‘LKKKN’, ‘LKKLK’, ‘LKKLL’, ‘LKKLM’,’LKKLN’, ‘LKKMK’, ‘LKKML’, ‘LKKMM’, ‘LKKMN’, ‘LKKNK’, ‘LKKNL’, ‘LKKNM’, ‘LKKNN’, ‘LKLKK’, ‘LKLKL’, ‘LKLKM’, ‘LKLKN’, ‘LKLLK’, ‘LKLLL’, ‘LKLLM’, ‘LKLLN’, ‘LKLMK’, ‘LKLML’, ‘LKLMM’, ‘LKLMN’, ‘LKLNK’, ‘LKLNL’, ‘LKLNM’, ‘LKLNN’, ‘LKMKK’, ‘LKMKL’, ‘LKMKM’, ‘LKMKN’, ‘LKMLK’, ‘LKMLL’, ‘LKMLM’, ‘LKMLN’, ‘LKMMK’, ‘LKMML’, ‘LKMMM’, ‘LKMMN’, ‘LKMNK’, ‘LKMNL’, ‘LKMNM’, ‘LKMNN’, ‘LKNKK’, ‘LKNKL’, ‘LKNKM’, ‘LKNKN’, ‘LKNLK’, ‘LKNLL’, ‘LKNLM’, ‘LKNLN’, ‘LKNMK’, ‘LKNML’, ‘LKNMM’, ‘LKNMN’, ‘LKNNK’, ‘LKNNL’, ‘LKNNM’, ‘LKNNN’, ‘MKKKK’, ‘MKKKL’, ‘MKKKM’, ‘MKKKN’, ‘MKKLK’, ‘MKKLL’, ‘MKKLM’, ‘MKKLN’, ‘MKKMK’, ‘MKKML’, ‘MKKMM’, ‘MKKMN’, ‘MKKNK’, ‘MKKNL’, ‘MKKNM’, ‘MKKNN’, ‘MKLKK’, ‘MKLKL’, ‘MKLKM’, ‘MKLKN’, ‘MKLLK’, ‘MKLLL’, ‘MKLLM’,’MKLLN’, ‘MKLMK’, ‘MKLML’, ‘MKLMM’, ‘MKLMN’, ‘MKLNK’, ‘MKLNL’, ‘MKLNM’, ‘MKLNN’, ‘MKMKK’, ‘MKMKL’, ‘MKMKM’, ‘MKMKN’, ‘MKMLK’, ‘MKMLL’, ‘MKMLM’, ‘MKMLN’, ‘MKMMK’, ‘MKMML’, ‘MKMMM’, ‘MKMMN’, ‘MKMNK’, ‘MKMNL’, ‘MKMNM’, ‘MKMNN’, ‘MKNKK’, ‘MKNKL’, ‘MKNKM’, ‘MKNKN’, ‘MKNLK’, ‘MKNLL’, ‘MKNLM’, ‘MKNLN’, ‘MKNMK’, ‘MKNML’, ‘MKNMM’, ‘MKNMN’, ‘MKNNK’, ‘MKNNL’, ‘MKNNM’, ‘MKNNN’, ‘NKKKK’, ‘NKKKL’, ‘NKKKM’, ‘NKKKN’, ‘NKKLK’, ‘NKKLL’, ‘NKKLM’, ‘NKKLN’, ‘NKKMK’, ‘NKKML’, ‘NKKMM’, ‘NKKMN’, ‘NKKNK’, ‘NKKNL’, ‘NKKNM’, ‘NKKNN’, ‘NKLKK’, ‘NKLKL’, ‘NKLKM’, ‘NKLKN’, ‘NKLLK’, ‘NKLLL’, ‘NKLLM’, ‘NKLLN’, ‘NKLMK’, ‘NKLML’, ‘NKLMM’, ‘NKLMN’, ‘NKLNK’, ‘NKLNL’, ‘NKLNM’, ‘NKLNN’, ‘NKMKK’, ‘NKMKL’, ‘NKMKM’, ‘NKMKN’, ‘NKMLK’, ‘NKMLL’, ‘NKMLM’,’NKMLN’, ‘NKMMK’, ‘NKMML’, ‘NKMMM’, ‘NKMMN’, ‘NKMNK’, ‘NKMNL’, ‘NKMNM’, ‘NKMNN’, ‘NKNKK’, ‘NKNKL’, ‘NKNKM’, ‘NKNKN’, ‘NKNLK’, ‘NKNLL’, ‘NKNLM’, ‘NKNLN’, ‘NKNMK’, ‘NKNML’, ‘NKNMM’, ‘NKNMN’, ‘NKNNK’, ‘NKNNL’, ‘NKNNM’, ‘NKNNN’] Всего слов 256
Источник: ru.stackoverflow.com
Рекурсивный перебор — Free Pascal
попарно различных символов (буквы латинского алфавита и цифры). Требуется вывести все перестановки символов данной строки в алфавитном порядке.
IOX IXO OIX OXI XIO XOI Внимание: перебор должен быть РЕКУРСИВНЫМ и понятным. Если что, напишите с комментариями.
Код к задаче: «Рекурсивный перебор»
Листинг программы
var s:string; // строка символов used:array[0..10] of boolean; // метка того, использовали ли мы элемент под номером i в перестановке a:array[0..10] of longint; // текущая перестановка i,n,j:longint; // n — длина строки, i,j — счетчики ch:char; procedure dfs(v:longint); // процедура генерации var i:longint; // счетчик begin if (v=n+1) // если перестановка сгенерирована then begin for i:= 1 to n do write(s[a[i]]); // то выводим ее посимвольно writeln; exit; end; for i:= 1 to n do // иначе ищем элемент, который мы поставим на v-ое место if used[i] then // если элемент не использован begin a[v]:=i; // то ставим его на v-ое место used[i]:=false; // метим, что это элемент мы брали dfs(v+1); // переходим на следующую позицию used[i]:=true; // откат обратно end; end; begin readln(s); // ввод строки n:=length(s); // длина строки for i:= 1 to n-1 do for j:= 1 to n-i do if (s[j]>s[j+1]) // это сортировка символов строки, потому что перестановки генерируются в алфавитном порядке then begin ch:=s[j]; s[j]:=s[j+1]; s[j+1]:=ch; end; for i:= 1 to n do used[i]:=true; // обнуление dfs(1); // запуск рекурсии end.
Источник: studassistent.ru
Уроки 52 — 54
Символьные строки. Функции для работы с символьными строками
§66. Символьные строки
1. Напишите программу, которая во введённой символьной строке заменяет все буквы «а» на буквы «б» и наоборот, заглавные — на заглавные, строчные — на строчные. При вводе строки ‘абсАБС’ должен получиться результат ‘басБАС’.
2. Введите символьную строку и проверьте, является ли она палиндромом (палиндром читается одинаково в обоих направлениях, например: «казак»).
3. Введите адрес файла и «разберите» его на части, разделённые знаком «/». Каждую часть выведите в отдельной строке.
4. Введите строку, в которой записана сумма натуральных чисел, например ‘1+25+3’. Вычислите это выражение.
5. Введите с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Выведите инициалы и фамилию. Например, при вводе строки ‘Иванов Пётр Семёнович’ должно получиться ‘П.С. Иванов’.
6. Разберитесь, как работает ещё одна функция замены:
Приведите пример входных данных, при которых эта функция работает неправильно.
7. Напишите рекурсивную версию процедуры replaceAll. Сравните две версии. Какую из них вы рекомендуете выбрать и почему?
8. Напишите функцию, которая изменяет в имени файла расширение на заданное (например, на bak). Функция принимает два параметра: имя файла и нужное расширение. Учтите, что в исходном имени расширение может быть пустым.
9. Напишите функцию, которая определяет, сколько раз входит в символьную строку заданное слово.
10. С клавиатуры вводится число N, обозначающее количество футболистов команды «Бублик», а затем — N строк, в каждой из которых — информация об одном футболисте в таком формате:
Данные разделяются одним пробелом. Нужно подсчитать, сколько футболистов, родившихся в период с 1998 по 2000 г., не забили мячей вообще.
11. В условиях задачи 10 определите фамилию и имя футболиста, забившего наибольшее число голов, и количество забитых им голов.
12. В условиях задачи 10 выведите в алфавитном порядке фамилии и имена всех футболистов, которые забили хотя бы один гол. В списке не более 100 футболистов.
13. Измените программу рекурсивного перебора так, чтобы длину слова можно было ввести с клавиатуры.
14. Выведите на экран все слова из К букв, в которых буква «Ы» встречается более 1 раза, и подсчитайте их количество.
15. Выведите на экран все слова из К букв, в которых есть одинаковые буквы, стоящие рядом (например, «ЫШШО»), и подсчитайте их количество.
16. В языке племени «тумба-юмба» запрещено ставить две гласные буквы подряд. Выведите все слова длины К, удовлетворяющие этому условию, и найдите их количество.
*17. Напишите программу перебора слов заданной длины, не использующую рекурсию. Попробуйте составить функцию, которая на основе некоторой комбинации вычисляет следующую за ней.
*18. Перестановки. К вам пришли К гостей. Напишите программу, которая выводит все перестановки — способы посадить их за столом. Гостей можно обозначить латинскими буквами.
Следующая страница §66. Символьные строки
Cкачать материалы урока
Источник: xn—-7sbbfb7a7aej.xn--p1ai