© К. Поляков, 2009-2012 B4 (базовый уровень, время – 2 мин) Тема: Анализ последовательностей, системы счисления. Что нужно знать: русский алфавит принципы работы с числами, записанными в позиционных системах счисления Пример задания: Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 240-м месте от начала списка. Решение (1 способ, перебор с конца): подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв; очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 33=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ) аналогично можно показать, что есть всего 35 = 243 слова из 5 букв очевидно, что последнее, 243-е слово – это УУУУУ далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е) Ответ: УУУОУ. -
Возможные ловушки и проблемы: хорошо, что требовалось найти слово, которое стоит близко к концу списка; если бы было нужно, скажем, 123-е слово, работы было бы значительно больше | ^ по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) выпишем начало списка, заменив буквы на цифры: 1. 00000 2. 00001 3. 00002 4. 00010 …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления переведем 239 в троичную систему: 239 = 222123 заменяем обратно цифры на буквы: 22212 УУУОУ Ответ: УУУОУ. -
Возможные ловушки и проблемы: нужно помнить, что нумерация в задаче начинается с 1, а числа в троичной системе – с нуля, поэтому для получения 240-го элемента списка нужно переводить в троичную систему число 240-1 = 239. | Решение (3 способ, закономерности в чередовании букв, И.Б. Курбанова): подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв:
1 | А | А | А | А | А | 2 | А | А | А | А | О | 3 | А | А | А | А | У | 4 | А | А | А | О | А | … | … | … | … | … | … | ... |
|
|
|
|
| … |
|
|
|
|
| 240 | У | У | У | О | У | 241 | У | У | У | У | А | 242 | У | У | У | У | О | 243 | У | У | У | У | У | 35 = 243 слова; 240-ое место – четвертое с конца; так как слова стоят в алфавитном порядке, то первая треть (81 шт) начинаются с «А», вторая треть (тоже 81) – с «О», а последняя треть – с «У», то есть первая буква меняется через 81 слово аналогично: 2-я буква меняется через 81/3 = 27 слов; 3-я буква – через 27/3 = 9 слов; 4-я буква – через 9/3 = 3 слова и 5-я буква меняется в каждой строке. из этой закономерности ясно, что на первой позиции в искомом слове будет буква «У» (последние 81 букв); на второй – тоже буква «У» (последние 27 букв); на третьей – тоже буква «У» (последние 9 букв); на четвертой – буква «О» (т.к. последние три буквы «У», а перед ними 3 буквы «О»)% на пятой – буква «У» (т.к. последние 3 буквы чередуются «А», «О», «У», а перед ними такая же последовательность). Ответ: УУУОУ. ^ Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААЛ 4. ААААО 5. ААААШ 4. АААКА …… На каком месте от начала списка стоит слово ШКОЛА? Решение: по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А 0, К 1, Л 2, О 3 и Ш 4 слово ШКОЛА запишется в новом коде так: 413205 переводим это число в десятичную систему: 413205 = 454 + 153 + 352 + 251 = 2710 поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда… Ответ: 2711. -
^ : нужно помнить, что список в задании начинается с 1, а числа в троичной системе – с нуля, поэтому для получения N-ой по счёту цепочки нужно переводить в троичную систему число N-1. | ^ Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка: 1. УУУУУ 2. УУУУО 3. УУУУА 4. УУУОУ …… Запишите слово, которое стоит на 240-м месте от начала списка. Решение (2 способ, троичная система, идея М. Густокашина): по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию) выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У ? 0, О ? 1, А ? 2): 1. 00000 2. 00001 3. 00002 4. 00010 …… это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д. тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления переведем 239 в троичную систему: 239 = 222123 заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок (0 ? У, 1 ? О, 2 ? А): 22212 АААОА Ответ: АААОА. ^ Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 101-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 125-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 170-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Запишите слово, которое стоит на 210-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 4. АААКА …… Запишите слово, которое стоит на 150-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 4. АААКА …… Запишите слово, которое стоит на 250-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 4. АААКА …… Запишите слово, которое стоит на 350-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 4. АААКА …… Запишите слово, которое стоит на 450-м месте от начала списка. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Укажите номер первого слова, которое начинается с буквы У. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Укажите номер слова ОАОАО. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Укажите номер слова УАУАУ. Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААО 3. ААААУ 4. АААОА …… Укажите номер первого слова, которое начинается с буквы О. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер первого слова, которое начинается с буквы У. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер первого слова, которое начинается с буквы К. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова РУКАА. Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 1. ААААА 2. ААААК 3. ААААР 4. ААААУ 5. АААКА …… Укажите номер слова УКАРА. Все 5-буквенные слова, составленные из букв К, О, Р, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ККККК 2. ККККО 3. ККККР 4. КККОК …… Запишите слово, которое стоит под номером 238. Все 5-буквенные слова, составленные из букв И, О, У, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ИИИИИ 2. ИИИИО 3. ИИИИУ 4. ИИИОИ …… Запишите слово, которое стоит под номером 240. Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. Вот начало списка: 1. АААА 2. АААМ 3. АААР 4. АААТ …… Запишите слово, которое стоит на 250-м месте от начала списка. Все 5-буквенные слова, составленные из букв Р, О, К, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ККККК 2. ККККО 3. ККККР 4. КККОК …… Запишите слово, которое стоит под номером 182.
|