Этот конспект не сохранится

Закроешь вкладку — потеряешь. Зарегистрируйся — и он будет в библиотеке навсегда.

Telegram

Ваш конспект

YouTubeАлгоритмы на Python 3. Лекция №3

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

Ключевые тезисы:

  • Система счисления — способ кодирования чисел.
  • Цифра — символ для записи числа.
  • Число — абстрактная величина, не зависящая от способа записи.
  • Позиционные системы основаны на степенях (разряд = степень основания).

🔢 Эволюция систем счисления

Унарная система

  • Основа: одна цифра (например, палочка |).
  • ✅ Удобна для сложения (простое объединение символов).
  • ❌ Неудобна для записи больших чисел и операций умножения/деления.

Египетская и римская системы

  • Модификации унарной системы с дополнительными символами для сокращения записи (например, V=5, X=10).
  • Остаются непозиционными.

Вавилонская шестидесятеричная система

  • Первая позиционная система (основание 60).
  • Наследие: 60 минут в часе, 60 секунд в минуте.

Индийская (арабская) система

  • Ключевое изобретение — цифра 0.
  • Десятичная система (основание 10) стала общепринятой.

🎯 Позиционные системы счисления

Общий принцип
Число раскладывается по разрядам, где каждая цифра умножается на основание в степени позиции:
1234 = 1*10³ + 2*10² + 3*10¹ + 4*10⁰

Основание системы

  • Определяет количество допустимых цифр (от 0 до основание-1).
  • Пример для пятеричной системы: цифры 0,1,2,3,4.

💻 Двоичная система и её родственники

Двоичная система (основание 2)

  • Цифры: 0 и 1.
  • Бит — двоичный разряд (информационная ёмкость).
  • Операции:
    • Сложение: 0+0=0, 0+1=1, 1+1=10 (перенос).
    • Умножение: тривиальная таблица (0*0=0, 1*1=1).

🔗 Связь между системами

  • Четверичная (4): одна цифра кодирует два двоичных разряда (диаду).
    • 00=0, 01=1, 10=2, 11=3.
  • Восьмеричная (8): одна цифра кодирует три двоичных разряда (триаду).
    • 000=0, 001=1, ..., 111=7.
  • Шестнадцатеричная (16): одна цифра кодирует четыре двоичных разряда (тетраду).
    • Цифры: 0-9, затем A=10, B=11, C=12, D=13, E=14, F=15.

🎯 Практическое применение

  • В программировании (особенно низкоуровневом) используют шестнадцатеричную запись, так как она компактно представляет байты (1 байт = 2 hex-цифры).

⚙️ Перевод между системами

Быстрый перевод через двоичную систему
Пример: из восьмеричной в четверичную.

  1. Каждую восьмеричную цифру заменить на три двоичных.
  2. Сгруппировать двоичные разряды справа налево по два (для четверичной).
  3. Каждую группу заменить на одну четверичную цифру.

Схема Горнера
Интеллектуальный способ вычисления значения числа по его цифрам слева направо:
1234₅ = (((1*5 + 2)*5 + 3)*5 + 4)

Перевод из десятичной в произвольную систему (делением)
Чтобы получить цифры числа в системе с основанием b:

  1. Делим исходное число на b.
  2. Остаток — младшая цифра.
  3. Целая часть частного становится новым числом.
  4. Повторяем шаги 1-3, пока частное не станет нулём.
  5. Цифры выписываются в порядке от последнего остатка к первому.

🐍 Работа с системами счисления в Python

Литералы для разных систем

x = 0b1111    # Двоичная (binary)
x = 0o777     # Восьмеричная (octal)
x = 0xFA0D    # Шестнадцатеричная (hexadecimal)

Преобразование числа в строку-представление

x = 127
bin(x)  # -> '0b1111111'
oct(x)  # -> '0o177'
hex(x)  # -> '0x7f'

Преобразование строки в число с произвольным основанием (до 36)

x = int('Z3', base=36)  # Основание 36 (цифры 0-9, A-Z)

Алгоритм извлечения цифр числа (реализация делением)

x = int(input())
base = 7
while x > 0:
    digit = x % base      # Получаем младшую цифру
    print(digit, end='') # Печатаем без перевода строки
    x //= base           # Отбрасываем младшую цифру

🔄 Однопроходные алгоритмы

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

Примеры аккумуляторов и правил обновления:

  • Подсчёт элементов (n): n += 1
  • Сумма (s): s += x
  • Произведение (p): p *= x (начальное значение p = 1)
  • Максимум (m): m = max(m, x) или if x > m: m = x
  • Поиск элемента (found): found = found or (x == target)

Начальные состояния

  • Для пустой последовательности: сумма = 0, произведение = 1, счётчик = 0, максимум не определён, флаг поиска = False.

Выводы:

  • Исторически системы счисления эволюционировали от простых унарных к мощным позиционным системам.
  • Позиционность — ключевой принцип, позволяющий компактно записывать числа и выполнять арифметические операции.
  • В информатике двоичная система фундаментальна, а шестнадцатеричная — удобный инструмент для человека.
  • Понимание перевода между системами и работы с разрядами критически важно для программирования.