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

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



НазваниеТема : Анализ последовательностей, системы счисления
Дата конвертации24.06.2012
Размер98.3 Kb.
ТипРешение

© К. Поляков, 2009-2012

B4 (базовый уровень, время – 2 мин)


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

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

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

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

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


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

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

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

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

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

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

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

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

  6. Ответ: УУУОУ.

Возможные ловушки и проблемы:

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

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

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

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

1. 00000

2. 00001

3. 00002

4. 00010

……

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

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

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

  4. заменяем обратно цифры на буквы: 22212  УУУОУ

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


Возможные ловушки и проблемы:

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

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

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


1

А

А

А

А

А

2

А

А

А

А

О

3

А

А

А

А

У

4

А

А

А

О

А













...

































240

У

У

У

О

У

241

У

У

У

У

А

242

У

У

У

У

О

243

У

У

У

У

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

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

  2. аналогично:

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

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

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

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

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

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

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

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

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

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

  1. Ответ: УУУОУ.
^

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


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

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

1. ААААА

2. ААААК

3. ААААЛ

4. ААААО

5. ААААШ

4. АААКА

……

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

Решение:

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

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

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

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

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

  2. Ответ: 2711.

^ Возможные ловушки и проблемы:

    • нужно помнить, что список в задании начинается с 1, а числа в троичной системе – с нуля, поэтому для получения N-ой по счёту цепочки нужно переводить в троичную систему число N-1.
^

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


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

1. УУУУУ

2. УУУУО

3. УУУУА

4. УУУОУ

……

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

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

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

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

1. 00000

2. 00001

3. 00002

4. 00010

……

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

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

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

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

  5. Ответ: АААОА.
^

Задачи для тренировки1:


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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

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

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

4. АААКА

……

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

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

4. АААКА

……

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

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

4. АААКА

……

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

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

4. АААКА

……

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

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Укажите номер первого слова, которое начинается с буквы У.

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Укажите номер слова ОАОАО.

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Укажите номер слова УАУАУ.

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

1. ААААА

2. ААААО

3. ААААУ

4. АААОА

……

Укажите номер первого слова, которое начинается с буквы О.

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

5. АААКА

……

Укажите номер первого слова, которое начинается с буквы У.

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

5. АААКА

……

Укажите номер первого слова, которое начинается с буквы К.

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

5. АААКА

……

Укажите номер слова РУКАА.

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

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

5. АААКА

……

Укажите номер слова УКАРА.

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

1. ККККК

2. ККККО

3. ККККР

4. КККОК

……

Запишите слово, которое стоит под номером 238.

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

1. ИИИИИ

2. ИИИИО

3. ИИИИУ

4. ИИИОИ

……

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

  1. Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. Вот начало списка:

1. АААА

2. АААМ

3. АААР

4. АААТ

……

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

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

1. ККККК

2. ККККО

3. ККККР

4. КККОК

……

Запишите слово, которое стоит под номером 182.


1 Источники заданий:

  1. Тренировочные работы МИОО 2011-2012.




Похожие:

Тема : Анализ последовательностей, системы счисления iconТема : Анализ последовательностей, системы счисления
Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке
Тема : Анализ последовательностей, системы счисления iconТема : Кодирование чисел. Системы счисления
Запись числа 6710 в системе счисления с основанием n оканчивается на 1 и содержит 4 цифры. Укажите основание этой системы счисления...
Тема : Анализ последовательностей, системы счисления iconТема : Кодирование чисел. Системы счисления
Запись числа 6710 в системе счисления с основанием n оканчивается на 1 и содержит 4 цифры. Укажите основание этой системы счисления...
Тема : Анализ последовательностей, системы счисления iconУрок 2 "Перевод чисел в различных системах счисления." Тип урока: урок изучения и закрепления новых знаний. Цели урока. Образовательная
Научить выполнять перевод чисел из десятичной системы счисления в восьмеричную систему счисления и из восьмеричной системы счисления...
Тема : Анализ последовательностей, системы счисления iconВариант 1 а) 618(10); б) 556(10); в) 129(10)
Перевести данное число из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную системы счисления
Тема : Анализ последовательностей, системы счисления iconВариант 1 а) 618(10); б) 129,25(10); а) 1111011011(2); б) 10110,011(2); в) 675,2(8); г) 94,4(16)
Перевести данное число из десятичной системы счисления в двоичную, восьмеричную и шестнадцатеричную системы счисления
Тема : Анализ последовательностей, системы счисления iconТема Системы счисления, Четность 8 часов

Тема : Анализ последовательностей, системы счисления icon* в задании 3 надо вставить любые символы, знаки…
...
Тема : Анализ последовательностей, системы счисления icon* в задании 3 надо вставить любые символы, знаки… 1,5,9,13
...
Тема : Анализ последовательностей, системы счисления iconТема : Системы счисления и двоичное представление информации в памяти компьютера

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов