Подготовка к контрольной
Темы идут в том же порядке, что и типы заданий демо-варианта: перевод чисел, действия в системах, логика, поисковые запросы, слова и двоичная запись.
Пройдено заданий: 0
Системы счисления
Позиция считается справа налево с нуля. Цифра умножается на основание в этой степени. Буквы: A=10, B=11, C=12, D=13, E=14, F=15. Цифра всегда меньше основания: в восьмеричной системе нет 8 и 9.
То же число в развёрнутой записи: 1·2⁵ + 0·2⁴ + 1·2³ + 1·2² + 0·2¹ + 1·2⁰. Нулевые слагаемые можно пропускать.
Переведи в десятичную
Из десятичной — делим на основание
Остатки записывают снизу вверх. Для дроби дробную часть умножают на основание и берут целые части.
Триады и тетрады
Так переводят без десятичной системы, потому что 8 = 2³ и 16 = 2⁴. Одна восьмеричная цифра — ровно 3 бита, одна шестнадцатеричная — ровно 4.
| Цифра | Триада | Тетрада |
|---|---|---|
| 0 | 000 | 0000 |
| 1 | 001 | 0001 |
| 2 | 010 | 0010 |
| 7 | 111 | 0111 |
| A | — | 1010 |
| C | — | 1100 |
| F | — | 1111 |
Группы отсчитывают от запятой в обе стороны. Неполную группу у целой части дополняют нулями слева, у дробной — справа.
Чему равно 1011102?
Чему равно 12013?
Число 47 в некоторой системе записано как 65. Найди основание.
Сложение, вычитание, умножение и деление
Столбик такой же, как в десятичной системе. Перенос появляется, когда сумма цифр в разряде не меньше основания: в двоичной при сумме 2, в восьмеричной при сумме 8, в шестнадцатеричной при сумме 16.
4568 + 2378 по разрядам. 6+7 = 15₁₀ = 1·8+7, пишем 7 и перенос 1. 5+3+1 = 9₁₀ = 1·8+1, пишем 1 и перенос 1. 4+2+1 = 7. Ответ 7158.
Умножение 11012 · 1102. Это 13 · 6. Сдвигами: 1101·10₂ = 11010, ещё сдвиг 110100. Сумма 11010 + 110100 = 10011102. Проверка: 13·6 = 78, а 64+8+4+2 = 78.
1110112 + 11012. В десятичной системе это 59 + 13 = 72.
4568 + 2378
B5E16 + 2A716
11012 · 1102. Ответ запиши двоичным числом без основания.
Наибольшее число, при котором высказывание истинно или ложно
Сначала переведи связки в условия на x, и только потом ищи наибольшее число.
- ИЛИ ложно только когда ложны обе части сразу.
- НЕ (условие) ложно, когда само условие истинно. Двойное отрицание снимается.
- И истинно только когда истинны обе части.
Обе части ложны: x не больше 95, и «x не кратно 14» тоже ложно, то есть x делится на 14. Подходят 14, 28, …, 84. Наибольшее — 84. Число 98 уже больше 95, первая часть становится истинной, и всё ИЛИ тоже истинно.
Сколько чисел в промежутке
Сначала оба конца переводят в десятичную систему. Потом смотрят, входит ли граница. Для чётных чисел берут ближайшее подходящее внутри промежутка.
Пример из того же типа: 10010112 ≤ x < C4₁₆. Слева 64+8+2+1 = 75, справа 12·16+4 = 196. Чётные от 76 до 194 включительно. Их (194 − 76) / 2 + 1 = 60. Единицу в конце прибавляют, потому что оба конца входят.
Наибольшее натуральное x, для которого ложно: (x > 40) ИЛИ НЕ (x кратно 9).
Наибольшее натуральное X, для которого ложно: ((X < 8) И (X ≥ 2)) ИЛИ НЕ (X < 12).
Поисковые запросы
Каждый круг — страницы, где есть одно слово. Знак | берёт всё, что попало хотя бы в один круг. Знак & берёт только общую часть. Страницы с обоими словами нельзя считать дважды: в сумме двух кругов они уже вошли два раза, поэтому пересечение вычитают.
Отсюда же находят неизвестное: |B| = |A | B| − |A| + |A & B|. Проверка: пересечение не больше каждого круга, объединение не меньше каждого.
Если слово C есть в каждом запросе, задачу сводят к двум кругам внутри C: |C & (A | B)| = |C & A| + |C & B| − |C & A & B|.
Марс & Юпитер — 274, Юпитер & (Марс | Сатурн) — 467, все три — 108. Сколько страниц у «Юпитер & Сатурн»?
Слова в алфавитном порядке
Слова одной длины в алфавитном порядке — это числа в системе, где основание равно числу букв. Буквам дают коды с нуля, в порядке алфавита.
Алфавит А, И, С, Т, У: А=0, И=1, С=2, Т=3, У=4. Всего четырёхбуквенных слов 5⁴ = 625. Первое слово АААА имеет код 0, поэтому место в списке на 1 больше кода.
Слово СТУТ. Код 2·5³ + 3·5² + 4·5¹ + 3·5⁰ = 2·125 + 3·25 + 4·5 + 3 = 348. Место: 348 + 1 = 349.
134-е место — это код 133. 133 = 1·125 + 0·25 + 1·5 + 3, буквы И, А, И, Т. Слово ИАИТ.
Какое слово стоит на 134-м месте в том же списке?
Таблицы истинности и упрощение
Импликация A → B читается «если A, то B». Она ложна в одном случае: слева 1, справа 0. Это то же самое, что ¬A ∨ B.
| A | B | A → B | A ∧ B | A ∨ B |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Цепочку без скобок считают справа налево: A → B → C означает A → (B → C). Она равна 0 только в одном наборе: все переменные, кроме последней, равны 1, а последняя равна 0. Остальные наборы дают 1.
Для семи букв A…G это 128 − 1 = 127. Если скобки поставить слева, ответов будет другое число, поэтому на контрольной важен именно правый порядок.
Как упрощать
Одинаковые множители выносят. X ∧ Y ∧ Z ∨ ¬X ∧ Y ∧ Z = Y ∧ Z ∧ (X ∨ ¬X) = Y ∧ Z, потому что X ∨ ¬X всегда истинно.
Вторая типичная склейка: (X ∨ Y ∨ Z) ∧ (X ∨ Y ∨ ¬Z) = X ∨ Y. Дальше (X ∨ Y) ∧ (X ∨ Y) остаётся X ∨ Y.
Сколько решений у A → B → C → D = 1?
Упрости X ∧ Y ∧ Z ∨ ¬X ∧ Y ∧ Z.
Сколько единиц в двоичной записи
Большое число не переводят делением. Его собирают из степеней двойки: у 2k в двоичной записи одна единица и k нулей, у 2k − 1 ровно k единиц подряд.
Сначала маленький образец. 2⁶ + 2⁴ − 1 = 64 + 16 − 1. Число 2⁴ − 1 — это четыре единицы. Они стоят в младших разрядах и не задевают шестой бит. Вместе пять единиц: 10011112.
4²⁰²⁰ + 2²⁰¹⁷ − 15. Это 2⁴⁰⁴⁰ + 2²⁰¹⁷ − 2⁴ + 1. Кусок 2²⁰¹⁷ − 2⁴ даёт единицы с 4-го бита по 2016-й: их 2013. Плюс единица от «+ 1» и единица от 2⁴⁰⁴⁰. Всего 2015. Старшая степень далеко, разряды не сливаются.
4²⁵⁵ + 2²⁵⁵ − 255. Это 2⁵¹⁰ + 2²⁵⁵ − 2⁸ + 1. Между 8-м и 254-м битом 247 единиц, ещё одна в нулевом бите и одна в 510-м. Всего 249.
Сколько единиц в двоичной записи числа 210 + 24 − 1?
Короткие вопросы по всем типам
658 в десятичной системе
11011,11012 через триады
Сколько чётных целых чисел на отрезке от 102 включительно до 2010 не включая 20? То есть 2 ≤ x < 20.
Запросов «пирожное | выпечка» — 14200, «пирожное» — 9700, пересечение — 5100. Сколько страниц по слову «выпечка»?
Сколько всего четырёхбуквенных слов из алфавита А, И, С, Т, У?
Пробная контрольная
Десять вопросов по типам демо-варианта. Подсказок нет, в конце будет счёт.
Что держать под рукой
| Приём | Как делать |
|---|---|
| В десятичную | Сумма цифра × основаниепозиция |
| Из десятичной | Делить на основание, остатки снизу вверх |
| 2 → 8 | Группы по 3 бита от запятой |
| 2 → 16 | Группы по 4 бита от запятой |
| 8 или 16 → 2 | Каждую цифру заменить триадой или тетрадой |
| Найти основание | Приравнять запись к десятичному значению |
| A | B | |A| + |B| − |A & B| |
| Слова | Система с основанием = размер алфавита, место = код + 1 |
| A → B → … → Z = 1 | 2ⁿ − 1 решений |
| Степени | 4ⁿ = 22n. У 2k одна единица, у 2k − 1 ровно k единиц |
| ИЛИ ложно | Только когда ложны обе части. НЕ снимают и смотрят условие |
| Чётные в промежутке | Сначала оба конца в десятичную, потом (последнее − первое) / 2 + 1 |
Карточки
Нажми на карточку, чтобы открыть ответ.