Readln(x);L:=0; M:=1; while x > 0 do begin L:=L+1; M:= M*(x mod 8); x:= x div 8; End; Writeln(L); write(M); End. Решение: 1) для решения задачи необходимо понять, что делает эта программа; повторяя рассуждения из предыдущего примера, выясняем, что а) переменная L с каждым шагом цикла увеличивается на 1 б) переменная x на каждом шаге цикла делится на 8 и остаток отбрасывается поэтому можно сделать вывод, что в конце цикла переменная L будет равна количеству цифр введенного числа, записанного в восьмеричной системе счисления; таким образом, восьмеричная запись числа содержит ровно 3 цифры 2) выражение x mod 8 – это последняя цифра восьмеричной записи числа; на каждом шаге цикла переменная M умножается на эту величину, поэтому в результате в M будет записано произведение всех цифр восьмеричной записи введенного числа 3) по условию это произведение равно 120, то есть , где a, b и с – числа от 0 до 7 (которые в восьмеричной системе счисления записываются одной цифрой) 4) поскольку нам нужно наибольшее число, перебираем делители числа 120, начиная со старшей цифры – 7; видим, что 120 на 7 не делится, поэтому такой цифры в восьмеричной записи числа нет 5) но 120 делится на 6, поэтому старшей цифрой может быть 6 – только в том случае, когда второй сомножитель можно представить в виде произведения двух чисел в интервале 1..6 6) делим 120 на 6, получаем 20; это число представляется как произведение 5 и 4, каждое из этих чисел записывается в виде одной восьмеричной цифры, то есть, они нам подходят 7) вспомним, что нас интересует максимальное число, поэтому цифры нужно выстроить в порядке убывания: 6548 8) заметим, что мы получили число в восьмеричной системе, а ответ нужно дать в десятичной; переводим: 6548 = 6·82 + 5·81 + 4·80 = 492. 9) ответ: 492.
B8 (повышенный уровень, время – 2 мин) Тема: Кодирование чисел. Системы счисления. Что нужно знать: · принципы кодирования чисел в позиционных системах счисления ·
4 3 2 1 0 ← разряды 1 2 3 4 5N = 1·N4 + 2·N3 + 3·N2 + 4·N1 + 5·N0 · последняя цифра записи числа в системе счисления с основанием – это остаток от деления этого числа на · две последние цифры – это остаток от деления на , и т.д. Пример задания: Запись числа 6710 в системе счисления с основанием N оканчивается на 1 и содержит 4 цифры. Укажите основание этой системы счисления N. Решение: 24) поскольку запись в системе счисления с основанием N заканчивается на 1, то остаток от деления числа 67 на N равен 1, то есть при некотором целом имеем 25) следовательно, основание N – это делитель числа 66 26) с другой стороны, запись числа содержит 4 цифры, то есть 27) выпишем кубы и четвертые степени первых натуральных чисел, которые являются делителями числа 66: 28) видим, что из этого списка только для числа N = 3 выполняется условие 29) таким образом, верный ответ – 3. 30) можно сделать проверку, переведя число 67 в троичную систему 6710 = 21113 Еще пример задания: Запись числа 38110 в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N. Решение: 1) поскольку запись в системе счисления с основанием N заканчивается на 3, то остаток от деления числа 381 на N равен 3, то есть при некотором целом имеем 2) следовательно, основание N – это делитель числа 3) с другой стороны, запись числа содержит 3 цифры, то есть 4) неравенство дает (так как ) 5) неравенство дает (так как ) 6) таким образом, ; в этом диапазоне делителями числа 378 являются числа · 9, при получаем запись числа · 14, при получаем запись числа · 18, при получаем запись числа 7) наибольшим из приведенных чисел – это 18 (можно было сразу искать подбором наибольший делитель числа 378, начиная с 19 «вниз», на уменьшение) 8) таким образом, верный ответ – 18. Еще пример задания: Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 25, запись которых в системе счисления с основанием четыре оканчивается на 11? Общий подход: · вспомним алгоритм перевода числа из десятичной системы в систему с основанием (см. презентацию), из него следует, что младшая цифра результата – это остаток от деления исходного числа на , а две младших цифры – это остаток от деления на и т.д. · в данном случае , остаток от деления числа на должен быть равен 114 = 5 · потому задача сводится к тому, чтобы определить все числа, которые меньше или равны 25 и дают остаток 5 при делении на 16 Решение (через десятичную систему): 9) общий вид чисел, которые дают остаток 5 при делении на 16: где – целое неотрицательное число (0, 1, 2, …) 10) среди всех таких чисел нужно выбрать те, что меньше или равны 25 («не превосходят 25»); их всего два: 5 (при ) и 21 (при ) 11) таким образом, верный ответ – 5, 21.
Еще пример задания: Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2. Общий подход: · здесь обратная задача – неизвестно основание системы счисления, мы обозначим его через · поскольку последняя цифра числа – 2, основание должно быть больше 2, то есть · вспомним алгоритм перевода числа из десятичной системы в систему с основанием (см. презентацию), из него следует, что младшая цифра результата – это остаток от деления исходного числа на Решение: 1) итак, нужно найти все целые числа , такие что остаток от деления 23 на равен 2, или (что то же самое) (*) где – целое неотрицательное число (0, 1, 2, …); 2) сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа 3) из формулы (*) получаем , так что задача сводится к тому, чтобы найти все делители числа 21, которые больше 2 4) в этой задаче есть только три таких делителя: и 5) таким образом, верный ответ – 3, 7, 21.
Еще пример задания: Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 31 оканчивается на 11. Общий подход: · неизвестно основание системы счисления, мы обозначим его через · пока будем считать, что запись числа 31 в системе с основанием состоит из трех цифр, причем две младшие (11) нам даны, а одну (обозначим ее через ) нужно найти: 2 1 0 ← разряды 31 = k 1 1N = k·N2 + N1 + N0 = k·N2 + N + 1 · можно показать, что при большем количестве разрядов эта формула также верна, то есть, число 31 можно представить как при некотором целом ; например, для числа с пятью разрядами получаем: 4 3 2 1 0 ← разряды 31 = k4 k3 k2 1 1N = k4·N4 + k3·N3 + k2·N2 + N1 + N0 = = k·N2 + N + 1 для (из первых трех слагаемых вынесли общий множитель ) Решение: 1) итак, нужно найти все целые числа , такие что (**), где – целое неотрицательное число (0, 1, 2, …); 2) сложность в том, что и , и неизвестны, однако здесь нужно «играть» на том, что это натуральные числа 3) из формулы (**) получаем , так что задача сводится к тому, чтобы найти все делители числа 30 и отобрать только те из них, для которых уравнение (**) разрешимо при целом , то есть, – целое число 4) выпишем все делители числа 30, большие или равные 2: 2, 3, 5, 6, 10, 15, 30 5) из всех этих делителей только для 2, 3, 5 и 30 значение – целое число (оно равно соответственно 7, 3, 1 и 0) 6) таким образом, верный ответ – 2, 3, 5, 30. Еще пример задания: Укажите, сколько всего раз встречается цифра 2 в записи чисел 10, 11, 12, …, 17 в системе счисления с основанием 5. Решение: 1) переведем все указанные числа в систему счисления с основанием 5: 10 = 205, 11 = 215, 12 = 225, 13 = 235, 14 = 245, 15 = 305, 16 = 315, 17 = 325 . 2) считаем цифры 2 – получается 7 штук 3) таким образом, верный ответ – 7. Еще пример задания: Укажите наименьшее основание системы счисления, в которой запись числа 30 трехзначна. Решение: 1) обозначим через неизвестное основание системы счисления, тогда запись числа 30 в этой системе имеет вид 2) вспомним алгоритм перевода числа из системы счисления с основанием в десятичную систему: расставляем сверху номера разрядов и умножаем каждую цифру на основание в степени, равной разряду: 3) поскольку запись трехзначная, , поэтому 4) с другой стороны, четвертой цифры нет, то есть, в третьем разряде – ноль, поэтому 5) объединяя последние два условия, получаем, что искомое основание удовлетворяет двойному неравенству 6) учитывая, что – целое число, методом подбора находим целые решения этого неравенства; их два – 4 и 5: 7) минимальное из этих значений – 4 8) таким образом, верный ответ – 4. Решение (без подбора): 1) выполним п.1-4 так же, как и в предыдущем варианте решения 2) найдем первое целое число, куб которого больше 30; это 4, так как 3) проверяем второе неравенство: , поэтому в системе счисления с основанием 4 запись числа 30 трёхзначная 4) таким образом, верный ответ – 4. Еще пример задания: Укажите через запятую в порядке возрастания все десятичные числа, не превосходящие 30, запись которых в системе счисления с основанием 5 начинается на 3? Решение (вариант 1): 1) нас интересуют числа от 1 до 30 2) сначала определим, сколько цифр может быть в этих числах, записанных в системе счисления с основанием 5 3) поскольку , в интересующих нас числах может быть от 1 до 3 цифр 4) рассмотрим трехзначные числа, начинающиеся на 3 в системе с основанием 5: все они заведомо не меньше , поэтому в наш диапазон не попадают; 5) таким образом, остается рассмотреть только однозначные и двухзначные числа 6) есть всего одно однозначное число, начинающееся на 3, это 3 7) общий вид всех двузначных чисел, начинающихся на 3 в системе с основанием 5: где – целое число из множества {0, 1, 2,3,4} (поскольку система счисления имеет основание 5 и цифр, больших 4, в записи числа быть не может) 8) используя эту формулу, находим интересующие нас двузначные числа – 15, 16, 17, 18 и 19 9) таким образом, верный ответ – 3, 15, 16, 17, 18, 19. Решение (вариант 2, предложен Сенькиной Т.С., г. Комсомольск-на-Амуре): 1) нас интересуют числа от 1 до 30; сначала определим, сколько цифр может быть в пятеричной записи эти чисел 2) поскольку , в интересующих нас числах может быть не более 2 цифр (все трехзначные пятеричные числа, начинающиеся с 3, больше 30) 3) есть всего одно однозначное число, начинающееся на 3, это 3 4) выпишем все пятеричные двузначные числа, которые начинаются с 3, и переведем их в десятичную систему: 305 = 15, 315 = 16, 325 = 17, 335 = 18 и 345 = 19 5) таким образом, верный ответ – 3, 15, 16, 17, 18, 19. Еще пример задания: Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 86 оканчивается на 22. Решение (М.В. Кузнецова и её ученики): 1) запись числа 86 в системе с основанием оканчивается на 22, т.е. в разряде единиц – 2, это значит, что остаток от деления 86 на равен 2, то есть для некоторого целого имеем 2) таким образом, искомые основания – делители числа 84; остается выбрать из них те, которые соответствуют другим условиям задачи 3) среди чисел, оканчивающихся на 22 в системе счисления с основанием ,минимальное – это само число ; отсюда найдем максимальное основание: так что первый ответ: 42. 4) остальные числа, окачивающиеся в этой системе на 22, имеют не менее 3-х знаков (, …), т.е. все они больше 5) поэтому , следовательно, 6) по условию в записи числа есть цифра 2, поэтому 7) итак: , и при этом – делитель 84; возможные значения (на 5,8 и 9 число 84 не делится) 8) переводя число 86 в системы счисления с основаниями , находим, что только для основания 6 запись числа оканчивается на 22 (при делении на 3, 4 и 7 «вторые» остатки не равны 2):
9) таким образом, верный ответ: 6, 42. Еще пример задания: Найти сумму восьмеричных чисел 178 +1708 +17008 +...+17000008, перевести в 16-ую систему счисления. Найдите в записи числа, равного этой сумме, третью цифру слева. Решение: 1) Несложно выполнить прямое сложение восьмеричных чисел, там быстро обнаруживается закономерность: 178 + 1708 = 2078 178 + 1708 + 17008 = 21078 178 + 1708 + 17008 + 170008 = 211078 178 + 1708 + 17008 + 170008 + 1700008 = 2111078 178 + 1708 + 17008 + 170008 + 1700008 + 17000008 = 21111078 2) Переведем последнюю сумму через триады в двоичный код (заменяем каждую восьмеричную цифру на 3 двоичных): 100010010010010001112 3) Теперь разбиваем цепочку на тетрады (группы из 4-х двоичных цифр), начиная справа, и каждую тетраду представляем в виде шестнадцатеричной цифры 100010010010010001112 8 9 2 4 7 4) Таким образом, верный ответ (третья цифра слева): 2. Еще пример задания: Запись числа 3010 в системе счисления с основанием N оканчивается на 0 и содержит 4 цифры. Чему равно основание этой системы счисления N? Решение (1 способ, подбор): 1) запись числа 30 в системе с основанием N длиннее, чем в десятичной (4 цифры против двух), поэтому основание N меньше 10 2) это дает шанс решить задачу методом подбора, переводя в разные системы, начиная с N = 2 до N = 9 3) переводим: 30 = 111102 = 10103 = … 4) дальше можно не переводить, поскольку запись 10103 удовлетворяет условию: заканчивается на 0 и содержит 4 цифры 5) можно проверить, что при N ≥ 4 запись числа 30 содержит меньше 4 цифр, то есть не удовлетворяет условию 6) Ответ: 3. Решение (2 способ, неравенства): 1) запись числа 30 в системе с основанием N содержит ровно 4 цифры тогда и только тогда, когда старший разряд – третий, то есть 2) первая часть двойного неравенства дает (в целых числах) 3) вторая часть неравенства дает (в целых числах) 4) объединяя результаты пп. 2 и 3 получаем, что N = 3 5) заметим, что условие «оканчивается на 0» – лишнее, ответ однозначно определяется по количеству цифр 6) Ответ: 3. B9 (повышенный уровень, время – 3 мин) Тема: Графы. Поиск путей Что нужно знать: · если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть , где обозначает число путей из вершины A в некоторую вершину Q · число путей конечно, если в графе нет циклов – замкнутых путей Пример задания: На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение (1 вариант, подстановки): 1) начнем считать количество путей с конца маршрута – с города К 2) будем обозначать через NX количество различных путей из города А в город X 3) общее число путей обозначим через N 4) по схеме видно, что NБ = NГ = 1 5) очевидно, что если в город X можно приехать только из Y, Z, то NX = NY + NZ, то есть нужно сложить число путей, ведущих из A во все города, откуда можно приехать в город X 6) поскольку в K можно приехать из Е, Д, Ж или И, поэтому N = NК = NД + NЕ + NЖ + NИ 7) в город И можно приехать только из Д, поэтому NИ = NД 8) в город Ж можно приехать только из Е и В, поэтому NЖ = NЕ + NВ 9) подставляем результаты пп. 6 и 7 в формулу п. 5: N = NВ + 2NЕ + 2NД 10) в город Д можно приехать только из Б и В, поэтому NД = NБ + NВ так что N = 2NБ + 3NВ + 2NЕ 11) в город Е можно приехать только из Г, поэтому NЕ = NГ так что N = 2NБ + 3NВ + 2NГ 12) по схеме видно, что NБ = NГ = 1, кроме того, NВ = 1 + NБ + NГ = 3 13) окончательно N = 2NБ + 3NВ + 2NГ = 2·1 + 3·3 + 2·1 = 13 14) Ответ: 13. Решение (2 вариант, удобная форма записи): 1)
2) записываем для каждой вершины, из каких вершин можно в нее попасть К ИДЖЕ И Д Ж ВЕ Е Г Д БВ Г А В АБГ
3) теперь для удобства «обратного хода» вершины можно отсортировать так[‡‡], чтобы сначала шли все вершины, в которые можно доехать только из начальной точки А: Б А Г А затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки): В АБГ Е Г далее добавляем все вершины, куда можно доехать из А, Б, Г, В и Е: Д БВ Ж ВЕ на следующем шаге добавляем вершину И И Д и, наконец, конечную. вершину К ИДЖЕ именно в таком порядке мы и будем вычислять количество путей для каждой вершины 4) теперь идем по полученному списку вершин, полагая, что количество вариантов попасть в вершину равно суммарному количеству вариантов попасть в ее непосредственных предшественников. NБ = 1, NГ = 1 NВ = 1+1+1 = 3, NЕ = 1 NД = 1+3 = 4, NЖ = 3 + 1 = 4 NИ = 4, N = NК = 4 + 4 + 4 + 1 = 13 5) заметим, что вершины можно и не сортировать специально, а просто выбирать возможный порядок вычисления: проверять, какие значения известны и какие можно рассчитать с их помощью на следующем шаге 6) Ответ: 13.
1) Запишем вершины в алфавитном порядке и для каждой из них определим, из каких вершин можно в нее попасть Б А В АБГ Г А Д БВ Е Г Ж ВЕ И Д К ИДЖЕ 2) теперь определяем количество путей; сначала ставим 1 для тех вершин, в которые можно проехать только из начальной (А):
3) затем на каждом шаге добавляем те вершины, в которые можно доехать из уже добавленных в список (и из исходной точки):
4) и последние 3 шага
5) Ответ: 13. B10 (повышенный уровень, время – 3 мин) Тема: Определение скорости передачи информации при заданной пропускной способности канала. Что нужно знать: · «физический» аналог задачи:
сколько лимонада перекачается по трубе за 1 час? · любой канал связи имеет ограниченную пропускную способность (скорость передачи информации), это число ограничивается свойствами аппаратуры и самой линии (кабеля) · объем переданной информации вычисляется по формуле , где – пропускная способность канала (в битах в секунду или подобных единицах), а – время передачи Пример задания: Скорость передачи данных через ADSL-соединение равна 128000 бит/c. Через данное соединение передают файл размером 625 Кбайт. Определите время передачи файла в секундах.
Решение: 31) выделим в заданных больших числах степени двойки и переведем размер файла в биты, чтобы «согласовать» единицы измерения: 128000 бит/c = 128 · 1000 бит/с = 27 · 125 · 8 бит/с = 27 · 53 · 23 бит/с = 210 · 53 бит/с 625 Кбайт = 54 Кбайт = 54 · 213 бит 32) чтобы найти время передачи в секундах, нужно разделить размер файла на скорость передачи: 33) таким образом, ответ – 40 с.
Еще пример задания (ege.yandex.ru): Данные объемом 100 Мбайт передаются из пункта А в пункт Б по каналу связи, обеспечивающему скорость передачи данных 220 бит в секунду, а затем из пункта Б в пункт В по каналу связи, обеспечивающему скорость передачи данных 222 бит в секунду. Задержка в пункте Б (время между окончанием приема данных из пункта А и началом передачи в пункт В) составляет 24 секунды. Сколько времени (в секундах) прошло с момента начала передачи данных из пункта А до их полного получения в пункте В? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно. 1) r M18oaPX2Ob0y3j7Hcfsd+U//AwAA//8DAFBLAwQUAAYACAAAACEAN1wv4uAAAAAJAQAADwAAAGRy cy9kb3ducmV2LnhtbEyPwU7DMBBE70j8g7VI3KhTDGkbsqkQEohLELQVcHTjbRw1tkPstubvMSc4 zs5o5m25jKZnRxp95yzCdJIBI9s41dkWYbN+vJoD80FaJXtnCeGbPCyr87NSFsqd7BsdV6FlqcT6 QiLoEIaCc99oMtJP3EA2eTs3GhmSHFuuRnlK5abn11mWcyM7mxa0HOhBU7NfHQzCXoj3+Pn0obvX l11dhy9Fz7FGvLyI93fAAsXwF4Zf/IQOVWLauoNVnvUIN7ciJRHyxRRY8mcLkQ5bBDGb58Crkv// oPoBAAD//wMAUEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtD b250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAA AAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEArXvMy+EIAABrPwAADgAAAAAAAAAAAAAA AAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEAN1wv4uAAAAAJAQAADwAAAAAAAAAA AAAAAAA7CwAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAEgMAAAAAA== ">
2) переводим количество информации в биты: 100 Мбайт = 100·223 бит 3) вычисляем время передачи данных из пункта А в пункт Б: 100·223 бит/ (220 бит/с) = 100·23 с = 800 с 4) вычисляем время передачи данных из пункта Б в пункт В: 100·223 бит/ (222 бит/с) = 100·21 с = 200 с 5) общее время передачи с учетом задержки 24 с: 6) таким образом, ответ – 1024. Еще пример задания: Документ объёмом 40 Мбайт можно передать с одного компьютера на другой двумя способами: А. Сжать архиватором, передать архив по каналу связи, распаковать. Б. Передать по каналу связи без использования архиватора. Какой способ быстрее и насколько, если: · средн. скорость передачи данных по каналу связи составляет 220 бит/с; · объём сжатого архиватором документа равен 40% исходного; · время, требуемое на сжатие документа, – 10 сек., на распаковку – 2 сек? В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого. Так, например, если способ Б быстрее способа А на 50 секунд, в ответе нужно написать Б50. Единицы измерения «секунд», «сек.», «с.» к ответу добавлять не нужно. Решение: 1) переводим количество информации из Мбайтов в биты 40 Мбайт = 40 · 223 бит 2) определяем время передачи несжатого файла 3) определяем объем сжатого файла, который составляет 40% или 0,4 от объема исходного документа: 40 · 0,4 · 223 бит = 16 · 223 бит = 227 бит 4) определяем полное время передачи несжатого файла с учетом 10 секунд на упаковку и 2 секунд на распаковку: 5) видим, что передача документа способом А (с упаковкой) быстрее на 320 – 140 = 180 с 6) таким образом, ответ – А180.
|