АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Тема №17 (время – 2 мин)

Читайте также:
  1. Тема №1 (время – 1 мин)
  2. Тема №11 (время – 3 мин)
  3. Тема №12 (время – 5 мин)
  4. Тема №14 (время – 1 мин)
  5. Тема №16 (время – 3 мин)
  6. Тема №18 (время – 2 мин)
  7. Тема №19 (время – 2 мин)
  8. Тема №2 (время – 2 мин)
  9. Тема №20 (время – 6 мин)
  10. Тема №21 (время – 2 мин)
  11. Тема №22 (время – 3 мин)

Тема: Анализ последовательностей, системы счисления.

Что нужно знать:

· русский алфавит

· принципы работы с числами, записанными в позиционных системах счисления

Пример задания:

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке.

Вот начало списка:

ААААА

ААААО

ААААУ

АААОА

……

Запишите слово, которое стоит на 240-м месте от начала списка.

Решение (1 способ, перебор с конца):

21) подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв;

22) очевидно, что есть всего 3 однобуквенных слова (А, О, У); двух буквенных слов уже 3´3=9 (АА, АО, АУ, ОА, ОО, ОУ, УА, УО и УУ)

23) аналогично можно показать, что есть всего 35 = 243 слова из 5 букв

24) очевидно, что последнее, 243-е слово – это УУУУУ

25) далее идём назад: предпоследнее слово УУУУО (242-е), затем идет УУУУА (241-е) и, наконец, УУУОУ (240-е)

26) Ответ: УУУОУ.

Возможные ловушки и проблемы: · хорошо, что требовалось найти слово, которое стоит близко к концу списка; если бы было нужно, скажем, 123-е слово, работы было бы значительно больше

Решение (2 способ, троичная система, идея М. Густокашина):

1) по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)

2) выпишем начало списка, заменив буквы на цифры:

1. 00000

2. 00001

3. 00002

4. 00010

……

3) это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.

4) тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления

5) переведем 239 в троичную систему: 239 = 222123

6) заменяем обратно цифры на буквы: 22212 ® УУУОУ

7) Ответ: УУУОУ.

Возможные ловушки и проблемы: · нужно помнить, что нумерация в задаче начинается с 1, а числа в троичной системе – с нуля, поэтому для получения 240-го элемента списка нужно переводить в троичную систему число 240-1 = 239.

Решение (3 способ, закономерности в чередовании букв, И.Б. Курбанова):

1) подсчитаем, сколько всего 5-буквенных слов можно составить из трех букв:

  А А А А А
  А А А А О
  А А А А У
  А А А О А
...          
         
  У У У О У
  У У У У А
  У У У У О
  У У У У У

35 = 243 слова; 240-ое место – четвертое с конца;

2) так как слова стоят в алфавитном порядке, то первая треть (81 шт) начинаются с «А», вторая треть (тоже 81) – с «О», а последняя треть – с «У», то есть первая буква меняется через 81 слово

3) аналогично:

• 2-я буква меняется через 81/3 = 27 слов;

• 3-я буква – через 27/3 = 9 слов;

• 4-я буква – через 9/3 = 3 слова и

• 5-я буква меняется в каждой строке.

4) из этой закономерности ясно, что

· на первой позиции в искомом слове будет буква «У» (последние 81 букв);

· на второй – тоже буква «У» (последние 27 букв);

· на третьей – тоже буква «У» (последние 9 букв);

· на четвертой – буква «О» (т.к. последние три буквы «У», а перед ними 3 буквы «О»)%

· на пятой – буква «У» (т.к. последние 3 буквы чередуются «А», «О», «У», а перед ними такая же последовательность).

5) Ответ: УУУОУ.

Еще пример задания (автор – В.В. Путилов):

Все 5-буквенные слова, составленные из 5 букв А, К, Л, О, Ш, записаны в алфавитном порядке.

Вот начало списка:

ААААА

ААААК

ААААЛ

ААААО

ААААШ

АААКА

……

На каком месте от начала списка стоит слово ШКОЛА?

Решение:

1) по аналогии с предыдущим решением будем использовать пятеричную систему счисления с заменой А ® 0, К ® 1, Л ® 2, О ® 3 и Ш ® 4

2) слово ШКОЛА запишется в новом коде так: 413205

3) переводим это число в десятичную систему:

413205 = 4×54 + 1×53 + 3×52 + 2×51 = 2710

4) поскольку нумерация элементов списка начинается с 1, а числа в пятеричной системе – с нуля, к полученному результату нужно прибавить 1, тогда…

5) Ответ: 2711.

Возможные ловушки и проблемы: · нужно помнить, что список в задании начинается с 1, а числа в троичной системе – с нуля, поэтому для получения N-ой по счёту цепочки нужно переводить в троичную систему число N-1.

Еще пример задания:

Все 5-буквенные слова, составленные из букв А, О, У, записаны в обратном алфавитном порядке. Вот начало списка:

УУУУУ

УУУУО

УУУУА

УУУОУ

……

Запишите слово, которое стоит на 240-м месте от начала списка.

Решение (2 способ, троичная система, идея М. Густокашина):

1) по условию задачи важно только то, что используется набор из трех разных символов, для которых задан порядок (алфавитный); поэтому для вычислений можно использовать три любые символа, например, цифры 0, 1 и 2 (для них порядок очевиден – по возрастанию)

2) выпишем начало списка, заменив буквы на цифры так, чтобы порядок символов был обратный алфавитный (У → 0, О → 1, А → 2):

1. 00000

2. 00001

3. 00002

4. 00010

……

3) это напоминает (в самом деле, так оно и есть!) числа, записанные в троичной системе счисления в порядке возрастания: на первом месте стоит число 0, на втором – 1 и т.д.

4) тогда легко понять, что 240-м месте стоит число 239, записанное в троичной системе счисления

5) переведем 239 в троичную систему: 239 = 222123

6) заменяем обратно цифры на буквы, учитывая обратный алфавитный порядок (0 → У, 1 → О, 2 → А): 22212 ® АААОА

7) Ответ: АААОА.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)