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

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

Арифметические алгоритмы

Представление целых чисел в памяти ЭВМ

Числа с плавающей точкой

Алгебра логики

Основные операции и законы

СДНФ

Классические логические схемы

Поразрядные операции

Программирование

Полезные ссылки

Грамматика языка Python

Ввод-вывод

Ввод данных

Наиболее простой способ считать данные от пользователя — воспользоваться побочным эффектом вычисления формулы input().

Функция input неким (ОС-специфичным) способом запрашивает у пользователя строчку текста и выдаёт её в качестве своего результата. Тип данных результата — текст. Если его нужно интерпретировать как число, нужно к нему применить функцию int.

Очень часто требуется разбить строчку на отдельные слова. В этом помогает метод текстовых данных .split() и множественное присваивание. Например, чтобы считать из строчки два числа, можно воспользоваться конструкцией

a, b = input().split()
a, b = int(a), int(b)

Ровно так же можно считать и три (и любое другое количество) числа:

a, b, c = input().split()
a, b, c = int(a), int(b), int(c)

К сожалению, так нельзя считать одно число. Если хочется совсем универсального шаблона, можно воспользоваться следующим:

a, b, *_ = input().split()  
## все остальные слова текста, кроме первых двух, оказываются в переменной _
a, b = int(a), int(b)

Ровно эта же конструкция отлично работает и для одного числа:

a, *_ = input().split()
a = int(a)

Напоследок скажем о том, что если нужно считать весь поданный на вход программе текст, можно воспользоваться формулой sys.stdin.read(), предварительно дав команду import sys. Отметим, что при вводе данных с клавиатуры способ завершения ввода является ОС-специфичным. Обычно работает клавишесочетание Ctrl-D (возможно, двойное), или же Ctrl-Z, Enter.

Вывод данных

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

Её поведением можно управлять при помощи именованных входов sep и end. По умолчанию формула print(1,2,3) эквивалентна print(1,2,3,sep=' ',end='\n'). Вход sep управляет разделителем отдельных единиц данных, вход end — завершающим текстом.

Например, чтобы напечатать числа 1, 2, 3 через запятые, завершив печать точкой с переходом на новую строку, можно воспользоваться формулой

print(1, 2, 3, sep = ',', end = '.\n')

Условия и арифметика

Циклы

Функции

Рекуррентные соотношения

Почти все математические модели дискретных объектов определяются при помощи рекуррентных соотношений — уравнений на значения функций от различных наборов аргументов.

Например, сумма двух натуральных чисел в математике определена так (в терминах примитивных операций «ноль» \(0\) и «инкремент» \(S\)):

\[ \begin{aligned} a + 0 & = a \\ a + s(n) & = s(a + n) \end{aligned} \]

Естественно, в программировании (которое является разделом математики, находящемся на стыке дискретной математики и абстрактной алгебры) тоже многие объекты и алгоритмы определяются именно в терминах рекуррентных соотношений.

Цифры числа

Приведём простой пример: цифры натурального числа можно получить следующим образом (без использования встроенной функции str)

def digits(n):
  if n == 0: return '0'
  if n == 1: return '1'
  if n == 2: return '2'
  if n == 3: return '3'
  if n == 4: return '4'
  if n == 5: return '5'
  if n == 6: return '6'
  if n == 7: return '7'
  if n == 8: return '8'
  if n == 9: return '9'
  return digits(n//10) + digits(n%10)

Здесь по сути написано, что цифры числа \(n\) — это (в случае, если оно больше 9) цифры его неполного частного при делении на 10, за которыми следует последняя цифра, полностью определяемая остатком числа по модулю 10.

Аналогично можно получить, например, двоичные цифры:

def bin_digits(n):
  if n == 0: return '0'
  if n == 1: return '1'
  return bin_digits(n//2) + bin_digits(n%2)

Конечно, то же самое можно получить и при помощи цикла:

def bin_digits(n):
  if n == 0: return '0'

  result = ''

  while n > 0:
    if n % 2 == 0: digit = '0'
    else:          digit = '1'

    result = digit + result
    n = n // 10

  return result

Но рекуррентное соотношение в данном случае выглядит гораздо проще. Единственная тонкость — для каждого рекуррентного соотношения требуется доказательство (по индукции) того, что оно вообще когда-либо завершает работу. Впрочем, цикл while в этом плане не сильно лучше.

Унарная запись числа

Для разнообразия приведём пример рекуррентной функции, которая не имеет результата работы, а интересна только своим побочным эффектом.

def print_unary(n):
  if n == 0: print()
  else: print('|', end=''); print_unary(n-1)

Последовательность

Всё вышеперечисленное легко реализовать циклами. Приведём пример функции, которую циклом заменить проблематично (хотя, вообще говоря, есть достаточно простой механический способ замены произвольного рекуррентного соотношения на цикл):

def print_reversed_sequence():
  n = int(input())

  if n == 0: return

  print_reversed_sequence()
  print(n)

Эта функция разворачивает последовательность чисел, поступившую на вход программы от пользователя. На первый взгляд кажется, что алгоритм, осуществляющий разворот последовательности, должен иметь доступ к какому-нибудь механизму хранения данных. Так и есть — функции сами по себе являются одним из таких механизмов.

Упражнения

Во всех этих упражнениях запрещается использовать циклы while и for.

  1. Напишите функцию, печатающую троичную запись натурального числа.

  2. Напишите функцию print_reciprocal_digits(n,k), печатающую k цифр после запятой числа, обратного целому положительному n.

  3. Напишите функцию print_square(n), печатающую квадратик \(n\times n\). Запрещается использовать умножение текста на число.

  4. Напишите функцию C(n,k), печатающую соответствующий биномиальный коэффициент.