Информатика — 8 класс

Подготовка к контрольной 1 триместра: системы счисления, логика, запросы и комбинаторика

ТВОЙ ПРОГРЕСС

Подготовка к контрольной

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

Пройдено заданий: 0

ТЕМА 1

Системы счисления

Позиция считается справа налево с нуля. Цифра умножается на основание в этой степени. Буквы: A=10, B=11, C=12, D=13, E=14, F=15. Цифра всегда меньше основания: в восьмеричной системе нет 8 и 9.

1011012 = 1·32 + 0·16 + 1·8 + 1·4 + 0·2 + 1·1 = 45

То же число в развёрнутой записи: 1·2⁵ + 0·2⁴ + 1·2³ + 1·2² + 0·2¹ + 1·2⁰. Нулевые слагаемые можно пропускать.

Частая ошибка — начать степени слева. У самого правого разряда степень всегда 0, даже если число длинное.

Переведи в десятичную

Из десятичной — делим на основание

Остатки записывают снизу вверх. Для дроби дробную часть умножают на основание и берут целые части.

Триады и тетрады

Так переводят без десятичной системы, потому что 8 = 2³ и 16 = 2⁴. Одна восьмеричная цифра — ровно 3 бита, одна шестнадцатеричная — ровно 4.

ЦифраТриадаТетрада
00000000
10010001
20100010
71110111
A—1010
C—1100
F—1111

Группы отсчитывают от запятой в обе стороны. Неполную группу у целой части дополняют нулями слева, у дробной — справа.

11011,11012 → восьмеричная. Целая часть: 011 011. Дробная: 110 100. Получается 33,648. Ноль слева у целой части не пишут, ноль справа у дроби писать нужно: он меняет последнюю цифру.
Обратно, 72,258 → двоичная. 7=111, 2=010, 2=010, 5=101. Ответ: 111010,0101012. Десятичную систему для этого не открывают.

Чему равно 1011102?

Чему равно 12013?

Число 47 в некоторой системе записано как 65. Найди основание.

ТЕМА 2

Сложение, вычитание, умножение и деление

Столбик такой же, как в десятичной системе. Перенос появляется, когда сумма цифр в разряде не меньше основания: в двоичной при сумме 2, в восьмеричной при сумме 8, в шестнадцатеричной при сумме 16.

Двоичная1 + 1 = 102. В разряд пишут 0, переносят 1.
Восьмеричная6 + 7 = 15₁₀ = 178. Пишут 7, переносят 1.
ШестнадцатеричнаяE + 7 = 21₁₀ = 15₁₆. Пишут 5, переносят 1.

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. Ответ запиши двоичным числом без основания.

ТЕМА 3

Наибольшее число, при котором высказывание истинно или ложно

Сначала переведи связки в условия на x, и только потом ищи наибольшее число.

  1. ИЛИ ложно только когда ложны обе части сразу.
  2. НЕ (условие) ложно, когда само условие истинно. Двойное отрицание снимается.
  3. И истинно только когда истинны обе части.
(x > 95) ИЛИ НЕ (x кратно 14) — ложно

Обе части ложны: x не больше 95, и «x не кратно 14» тоже ложно, то есть x делится на 14. Подходят 14, 28, …, 84. Наибольшее — 84. Число 98 уже больше 95, первая часть становится истинной, и всё ИЛИ тоже истинно.

Истинное «НЕ (x > 19) И НЕ (x чётное)» — это сразу два условия: x ≤ 19 и x нечётное. Наибольшее — 19. Чётное 18 не подходит из-за второй части.

Сколько чисел в промежутке

Сначала оба конца переводят в десятичную систему. Потом смотрят, входит ли граница. Для чётных чисел берут ближайшее подходящее внутри промежутка.

Пример из того же типа: 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).

ТЕМА 5

Слова в алфавитном порядке

Слова одной длины в алфавитном порядке — это числа в системе, где основание равно числу букв. Буквам дают коды с нуля, в порядке алфавита.

Всего слов = (число букв)длина

Алфавит А, И, С, Т, У: А=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, буквы И, А, И, Т. Слово ИАИТ.

Если забыть прибавить 1, ответ будет на одно место меньше. АААА — первое слово, а не нулевое.

Какое слово стоит на 134-м месте в том же списке?

ТЕМА 6

Таблицы истинности и упрощение

Импликация A → B читается «если A, то B». Она ложна в одном случае: слева 1, справа 0. Это то же самое, что ¬A ∨ B.

ABA → BA ∧ BA ∨ B
00100
01101
10001
11111

Цепочку без скобок считают справа налево: A → B → C означает A → (B → C). Она равна 0 только в одном наборе: все переменные, кроме последней, равны 1, а последняя равна 0. Остальные наборы дают 1.

Решений «цепочка = 1» ровно 2ⁿ − 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.

В задании «какой столбец какая переменная» сначала упрощают F, потом подставляют известные 0 и 1 из строки. Перестановку, которая не даёт указанное F, вычёркивают. Буквы в ответе пишут подряд, в порядке столбцов.

Сколько решений у A → B → C → D = 1?

Упрости X ∧ Y ∧ Z ∨ ¬X ∧ Y ∧ Z.

Чтобы сопоставить столбцы фрагмента таблицы, подставь известные нули и единицы в формулу и вычеркни перестановки, которые не дают указанное F.
ТЕМА 7

Сколько единиц в двоичной записи

Большое число не переводят делением. Его собирают из степеней двойки: у 2k в двоичной записи одна единица и k нулей, у 2k − 1 ровно k единиц подряд.

4ⁿ = (2²)ⁿ = 22n

Сначала маленький образец. 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.

Если две степени попали в один и тот же бит, их нельзя просто сложить как «две единицы»: 2k + 2k = 2k+1, единица переезжает на разряд выше.

Сколько единиц в двоичной записи числа 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 = 12ⁿ − 1 решений
Степени4ⁿ = 22n. У 2k одна единица, у 2k − 1 ровно k единиц
ИЛИ ложноТолько когда ложны обе части. НЕ снимают и смотрят условие
Чётные в промежуткеСначала оба конца в десятичную, потом (последнее − первое) / 2 + 1
A → B = ¬A ∨ B
¬(A → B) = A ∧ ¬B
ПОВТОРЕНИЕ

Карточки

Нажми на карточку, чтобы открыть ответ.

1 из 11