Первое слово с буквы

Ещё один вопрос по тому же списку: «под каким номером идёт первое слово, которое начинается с буквы О?»

Здесь не нужно ни слово искать, ни список строить. Нужно понять только одно: сколько слов проходит до него. Номер первого нужного слова — это их количество плюс один.

Список состоит из блоков

Все слова с первой буквой К идут подряд — это блок. За ним блок на Л, потом на Н, и так далее по алфавиту. Внутри блока первая буква зафиксирована, а остальные клетки свободны, поэтому размер блока = алфавит в степени (длина − 1).

Буквы слова КЛОУН по алфавиту: К, Л, Н, О, У. До буквы О стоят три буквы — К, Л и Н. Значит, перед первым словом на О проходит три полных блока по 5⁴ = 625 слов.

3 × 625 + 1 = 1876. Само слово — ОКККК: буква О, а дальше самые ранние буквы алфавита.

Если задан префикс из двух букв

«Первое слово, которое начинается с букв ГО». Логика та же, только фиксируем не одну клетку, а две — и блоки становятся мельче.

Буквы слова ГОРКА по алфавиту: А, Г, К, О, Р. Перед буквой Г стоит одна буква (А) — это один большой блок из 5⁴. Внутри блока Г перед буквой О стоят три буквы (А, Г, К) — это три блока по 5³.

1 · 5⁴ + 3 · 5³ + 1 = 625 + 375 + 1 = 1001.

Программное решение

Блочный счёт короткий, но сбиться в нём проще простого: сколько букв идёт до нужной, входит ли она сама, прибавлять единицу или нет. Ошибка ровно на единицу — самая частая в этом типе.

Программа ниже перебирает в алфавитном порядке список слов и остановиться на первом слове, которое начинается с нужной буквы. Никаких блоков считать не надо — надо просто посмотреть.

word[0] — это первая буква слова с индексом. Как только она совпала с нужной, печатаем i + 1 (индекс с нуля, номер с единицы) и выходим командой break: слово первое (перебираем же в алфавитном порядке), дальше искать нечего, и цикл незачем крутить до конца.

Почему это эффективно: код не считает блоки — а значит, не может ошибиться на единицу там, где ошибается человек. И заодно он проверяет твою формулу: сошлось — блоки посчитаны верно, не сошлось — ищи, где потерял букву.

Результат работы программы

1876

Точно как формула 3 · 5⁴ + 1. Блочный счёт и перебор дают одно и то же — пользуйся тем, что быстрее в конкретной задаче: формулой в уме или кодом на экзамене.

Проверь себя