Подтема 5 из 6
Нумерованный список
Номер слова в списке по алфавиту и слово по номеру — и ответ задачи темы.
Список как счётчик
Вернёмся к задаче темы: слова пронумерованы по алфавиту. Как связан номер со словом?
Полный список слов по алфавиту меняется как счётчик в системе счисления: заменим буквы цифрами по порядку, и номер слова — это значение записи плюс один. Для трёхбуквенных слов из АБВ: А → 0, Б → 1, В → 2, список идёт как 000, 001, 002, 010, … в троичной системе.
Если в алфавите m букв, система счисления — с основанием m. Первое слово ААА — это 000 = 0, а его номер — 1.
Номер слова
Номер слова — это сколько слов стоит раньше него, плюс один. Для слова БАВБ из четырёхбуквенного списка АБВ: раньше идут 27 слов на А; слов на Б со второй буквой меньше А нет; слов БАА? и БАБ? — 6; и одно слово БАВА. Это и есть веса разрядов записи 1021₃.
Программа вычисляет номер без перебора: дописывает цифры справа, как при чтении числа.
alphabet = 'АБВ'word = 'БАВБ'base = len(alphabet)value = 0for letter in word: digit = alphabet.index(letter) value = value * base + digit print(value + 1)Слово по номеру
Слово по номеру находят обратным ходом: вычесть единицу, перевести в систему счисления делением, заменить цифры буквами. Пятидесятое четырёхбуквенное слово из АБВ: 50 − 1 = 49.
- Переводим 49 в систему с основанием 3. Цифры записи появятся справа налево.
- 49 = 3 · 16 + 1. Остаток 1 — цифра разряда 3⁰, дальше работаем с частным 16.
- 16 = 3 · 5 + 1. Остаток 1 — цифра разряда 3¹, дальше работаем с частным 5.
- 5 = 3 · 1 + 2. Остаток 2 — цифра разряда 3², дальше работаем с частным 1.
- 1 = 3 · 0 + 1. Остаток 1 — цифра разряда 3³, частное 0 — перевод закончен.
- Готово: 49 = 1211₃. Первый найденный остаток стоит справа, последний — слева.
49 = 1211₃ → БВББ. Начальные нули терять нельзя: пятое слово — 4 = 11₃ = 0011₃ → ААББ, ведь нули — это первые буквы алфавита.
alphabet = 'АБВ'length = 4number = 50base = len(alphabet)value = number - 1word = ''for i in range(length): digit = value % base word = alphabet[digit] + word value = value // base print(word)Порядок алфавита
Буквы записывают по алфавиту сами: product идёт в порядке входной строки. В задаче темы буквы перечислены как Т, О, Р, К, А, а по алфавиту это 'АКОРТ': А → 0, К → 1, О → 2, Р → 3, Т → 4. С product('ТОРКА', repeat=5) список начался бы с ТТТТТ, и все номера были бы другими.
Со словами, начинающимися одинаково, удобно работать блоками: слова на А занимают номера 1–625, на К — 626–1250, и так далее.
Номер и счётчик
В нумерованном списке номер и количество подходящих слов — разные переменные: номер растёт на каждом слове полного списка, счётчик — только на подходящих.
Номер даёт enumerate(..., start=1): он приписывает каждому слову его номер, начиная с 1. Условие «нечётный номер» — number % 2 == 1. Вот программа для задачи темы:
from itertools import product count = 0for number, letters in enumerate( product('АКОРТ', repeat=5), start=1): word = ''.join(letters) if ( word[0] != 'А' and word.count('О') == 2 and 'ОО' not in word and number % 2 == 1 ): count += 1print(count)Из 336 подходящих по буквам слов нечётные номера у 168. Это ответ задачи темы.
Первое и последнее
Первое подходящее слово находят с остановкой, последнее — запоминая каждый новый подходящий номер. Посмотри по шагам, как запоминается последний номер в маленьком списке АА, АБ, БА, ББ:
from itertools import product last_number = Nonefor number, letters in enumerate( product('АБ', repeat=2), start=1): word = ''.join(letters) if word.count('А') == 1: last_number = number print(last_number)Для задачи темы: первое подходящее слово — номер 683 (КАОКО), последнее — номер 3073 (ТТОТО).
from itertools import product first = Nonelast = Nonefor number, letters in enumerate( product('АКОРТ', repeat=5), start=1): word = ''.join(letters) if ( word[0] != 'А' and word.count('О') == 2 and 'ОО' not in word and number % 2 == 1 ): if first is None: first = (number, word) last = (number, word)print(*first)print(*last)None значит «пока не найдено»: первое запоминаем один раз, последнее перезаписываем при каждом подходящем слове.
Полный и новый список
Формула «запись + 1» верна только для полного списка. Если неподходящие слова удалили и оставшиеся пронумеровали заново, новый номер — это счётчик подходящих слов.
Поэтому при поиске номеров в полном списке нельзя сокращать алфавит: удалённая буква изменит нумерацию.
Итого
- Номер словабуквы → цифры по алфавиту, номер = запись + 1
- Слово по номеруномер − 1 в систему счисления, нули не терять
- Алфавитзаписать буквы по порядку самому
- Номер и счётчик
enumerate(..., start=1)и отдельныйcount - Первое, последнеезапомнить один раз; перезаписывать каждый раз
Проверьте себя
Ответь сначала сам, потом открой ответ.
АБВ записаны по алфавиту с номерами от 1. Какой номер у слова ВАБВ?ОтветСкрыть ответ
ОтветСкрыть ответ
АВАБ: 20 − 1 = 19 = 0201₃, начальный ноль — это буква А.product, чтобы номера шли по алфавиту?ОтветСкрыть ответ
'АКОРТ': product идёт в порядке входной строки, поэтому буквы записывают по алфавиту сами.count?ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Номер слова ВАБВ
Все четырёхбуквенные слова из АБВ записаны по алфавиту с номерами от 1. Какой номер у слова ВАБВ?
Введите число.
Подсказка
Запись в троичной системе плюс один.
Решение
Буквы А, Б, В — цифры 0, 1, 2. ВАБВ ↔ 2012₃ = 2 · 27 + 0 · 9 + 1 · 3 + 2 = 59, номер на единицу больше: 60.
Решение программой
alphabet = 'АБВ'word = 'ВАБВ'digits = ''.join(str(alphabet.index(c)) for c in word)print(int(digits, 3) + 1)Ответ: 60
Номер слова ГАББА
Все пятибуквенные слова из АБВГ записаны по алфавиту и пронумерованы с 1. Какой номер у слова ГАББА?
Введите число.
Подсказка
Запись в четверичной системе плюс один.
Решение
Буквы А, Б, В, Г — цифры 0–3. ГАББА ↔ 30110₄ = 3 · 256 + 0 + 16 + 4 + 0 = 788, номер 789.
Решение программой
alphabet = 'АБВГ'word = 'ГАББА'digits = ''.join(str(alphabet.index(c)) for c in word)print(int(digits, 4) + 1)Ответ: 789
Слова разной длины
Коды длины от 1 до 3 из букв А, Б, В записаны так: сначала по алфавиту все однобуквенные, затем двухбуквенные, затем трёхбуквенные. Под каким номером стоит код ВВ?
Введите число.
Подсказка
Сначала идут все однобуквенные.
Решение
Сначала идут 3 однобуквенных кода. Среди двухбуквенных ВВ ↔ 22₃ = 8 — девятый. Номер 3 + 9 = 12.
Решение программой
print(3 + int('22', 3) + 1)Ответ: 12
Слово под номером 20
В том же списке какое слово имеет номер 20?
Введите слово заглавными буквами.
Подсказка
Номер минус один — в троичную систему.
Решение
20 − 1 = 19 = 0201₃ — начальный ноль сохраняем. Цифры 0, 2, 0, 1 — буквы А, В, А, Б.
Решение программой
alphabet = 'АБВ'n = 20 - 1word = ''for _ in range(4): word = alphabet[n % 3] + word n //= 3print(word)Ответ: АВАБ
Слово под номером 500
В том же списке какое слово стоит под номером 500?
Введите слово заглавными буквами.
Подсказка
Начальные нули терять нельзя.
Решение
500 − 1 = 499 = 13303₄. Цифры 1, 3, 3, 0, 3 — буквы Б, Г, Г, А, Г.
Решение программой
alphabet = 'АБВГ'n = 500 - 1word = ''for _ in range(5): word = alphabet[n % 4] + word n //= 4print(word)Ответ: БГГАГ
Слово под номером 700
Все 5-буквенные слова, составленные из букв К, О, Т, Ы, записаны в алфавитном порядке и пронумерованы, начиная с 1. Какое слово стоит под номером 700?
Введите слово заглавными буквами.
Подсказка
Алфавит: К, О, Т, Ы.
Решение
По алфавиту буквы идут К, О, Т, Ы — цифры 0–3. 700 − 1 = 699 = 22323₄: цифры 2, 2, 3, 2, 3 — буквы Т, Т, Ы, Т, Ы.
Решение программой
alphabet = 'КОТЫ'n = 700 - 1word = ''for _ in range(5): word = alphabet[n % 4] + word n //= 4print(word)Ответ: ТТЫТЫ
Первое слово на В
В списке четырёхбуквенных слов из АБВ под каким номером первое слово, начинающееся с В?
Введите число.
Подсказка
Перед ним все слова на А и Б.
Решение
Перед первым словом на В стоят все слова на А и на Б, по 3³ = 27: 2 · 27 = 54. Номер 55.
Решение программой
print(2 * 3 ** 3 + 1)Ответ: 55
Номер слова ТОК
Все трёхбуквенные слова из букв Т, О, К записаны в алфавитном порядке и пронумерованы с 1. Под каким номером стоит слово ТОК?
Введите число.
Подсказка
Сначала запиши алфавит по порядку.
Решение
По алфавиту буквы идут К, О, Т — цифры 0, 1, 2. ТОК ↔ 210₃ = 21, номер 22.
Решение программой
alphabet = 'КОТ'word = 'ТОК'digits = ''.join(str(alphabet.index(c)) for c in word)print(int(digits, 3) + 1)Ответ: 22
Номер слова РУДАР
Все 5-буквенные слова, составленные из букв Р, У, Д, А, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером стоит слово РУДАР?
Введите число.
Подсказка
Алфавит по порядку: А, Д, Р, У.
Решение
По алфавиту буквы идут А, Д, Р, У — цифры 0–3. РУДАР ↔ 23102₄ = 512 + 192 + 16 + 0 + 2 = 722, номер 723.
Решение программой
alphabet = 'АДРУ'word = 'РУДАР'digits = ''.join(str(alphabet.index(c)) for c in word)print(int(digits, 4) + 1)Ответ: 723
Первое слово на Й
Все 6-буквенные слова, составленные из букв М, А, Й, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером стоит первое слово, которое начинается с буквы Й?
Введите число.
Подсказка
По алфавиту А < Й < М.
Решение
По алфавиту А < Й < М, поэтому перед словами на Й стоят все 3⁵ = 243 слова на А. Первое слово на Й — номер 244.
Решение программой
print(3 ** 5 + 1)Ответ: 244
Чётные номера с одной А
Все трёхбуквенные слова из АБВГ записаны по алфавиту и пронумерованы с 1. Сколько слов с ровно одной А имеет чётный номер? Повторения разрешены.
Введите число.
Подсказка
Номер и количество хранятся раздельно.
Решение
Алфавит из четырёх букв, номер чётный, когда последняя буква — Б или Г (цифры 1 и 3). А стоит на одном из первых двух мест, оставшееся место — одна из трёх букв: 2 · 2 · 3 = 12.
Решение программой
from itertools import product count = 0for number, letters in enumerate( product('АБВГ', repeat=3), start=1): word = ''.join(letters) if number % 2 == 0 and word.count('А') == 1: count += 1print(count)Ответ: 12
Нечётные номера с одной А
В том же списке сколько слов с ровно одной А имеют нечётный номер?
Введите число.
Подсказка
Номер увеличивается для каждого слова полного списка.
Решение
Основание 3 нечётное: номер нечётный, когда сумма цифр чётна, то есть букв Б чётное число — ноль или две. Место А — 4 способа; три другие буквы — все В (1 способ) или ровно две Б (3 способа): 4 · (1 + 3) = 16.
Решение программой
from itertools import product count = 0for number, letters in enumerate( product('АБВ', repeat=4), start=1): word = ''.join(letters) if number % 2 == 1 and word.count('А') == 1: count += 1print(count)Ответ: 16
Количество слов с чётными номерами
Все 6-буквенные слова, составленные из букв С, И, Н, Е, Л, записаны в алфавитном порядке и пронумерованы. Определи количество слов с чётными номерами, которые содержат не менее двух букв Е и не содержат двух букв Н, стоящих рядом.
Введите число.
Подсказка
Алфавит по порядку: Е, И, Л, Н, С.
Решение
Алфавит по порядку — Е, И, Л, Н, С. Программа хранит номер и счётчик раздельно: номер растёт на каждом слове, счётчик — на словах с чётным номером, не менее чем двумя Е и без НН. Получается 2440.
Решение программой
from itertools import product count = 0for number, letters in enumerate( product('ЕИЛНС', repeat=6), start=1): word = ''.join(letters) if ( number % 2 == 0 and word.count('Е') >= 2 and 'НН' not in word ): count += 1print(count)Ответ: 2440
Первое слово без А
Все четырёхбуквенные слова из АБВ записаны по алфавиту и пронумерованы с 1. Под каким номером первое слово, в котором нет буквы А?
Введите число.
Подсказка
Первое подходящее — с остановкой.
Решение
Первое слово без А — ББББ ↔ 1111₃ = 40, его номер 41.
Решение программой
from itertools import product for number, letters in enumerate( product('АБВ', repeat=4), start=1): word = ''.join(letters) if 'А' not in word: print(number) breakОтвет: 41
Последнее слово с двумя В
В том же списке под каким номером последнее слово с ровно двумя буквами В?
Введите число.
Подсказка
Последнее — запоминай каждый новый подходящий номер.
Решение
Последнее слово с ровно двумя В — ВВББ ↔ 2211₃ = 76, номер 77.
Решение программой
from itertools import product last = Nonefor number, letters in enumerate( product('АБВ', repeat=4), start=1): word = ''.join(letters) if word.count('В') == 2: last = numberprint(last)Ответ: 77
Последнее слово с нечётным номером
Все 5-буквенные слова, составленные из букв К, Р, О, Т, А, записаны в алфавитном порядке и пронумерованы. Под каким номером в списке стоит последнее слово с нечётным номером, которое не начинается с буквы А и содержит ровно две буквы О?
Введите число.
Подсказка
Алфавит по порядку: А, К, О, Р, Т.
Решение
Алфавит по порядку — А, К, О, Р, Т. Программа перебирает пронумерованный список, проверяет нечётность номера, первую букву и две О и запоминает последний подходящий номер — 3113.
Решение программой
from itertools import product last = Nonefor number, letters in enumerate( product('АКОРТ', repeat=5), start=1): word = ''.join(letters) if ( number % 2 == 1 and word[0] != 'А' and word.count('О') == 2 ): last = numberprint(last)Ответ: 3113
Первое слово с чётным номером
Все 5-буквенные слова, составленные из букв М, Е, Л, К, А, записаны в алфавитном порядке и пронумерованы. Под каким номером стоит первое слово с чётным номером, которое не начинается с букв А или Е и содержит не менее двух букв Л?
Введите число.
Подсказка
Первое найденное — с остановкой.
Решение
Алфавит по порядку — А, Е, К, Л, М. Программа останавливается на первом слове с чётным номером, которое не начинается с А или Е и содержит не менее двух Л, — номер 1294.
Решение программой
from itertools import product for number, letters in enumerate( product('АЕКЛМ', repeat=5), start=1): word = ''.join(letters) if ( number % 2 == 0 and word[0] not in 'АЕ' and word.count('Л') >= 2 ): print(number) breakОтвет: 1294
Номер в сокращённом списке
Из четырёхбуквенных слов из АБВ оставили только слова без двух одинаковых букв подряд и пронумеровали их заново по алфавиту, начиная с 1. Какой номер получило слово БАБА?
Введите число.
Подсказка
Новый список нумеруют заново — номер растёт только у оставленных слов.
Решение
В новом списке перед БАБА стоят только слова на А без одинаковых соседей: 2 · 2 · 2 = 8. Поэтому её новый номер 9.
Решение программой
from itertools import product number = 0for letters in product('АБВ', repeat=4): word = ''.join(letters) if any(word[i] == word[i + 1] for i in range(3)): continue number += 1 if word == 'БАБА': print(number)Ответ: 9