Книга «Computer Science для программиста-самоучки. Все что нужно знать о структурах данных и алгоритмах»

Как дела, Хаброжители?

Книги Кори Альтхоффа вдохновили сотни тысяч людей на самостоятельное изучение программирования.

Чтобы стать профи в программировании, не обязательно иметь диплом в области computer science, и личный опыт Кори подтверждает это: он стал разработчиком ПО в eBay и добился этого самостоятельно.

Познакомьтесь с наиболее важными темами computer science, в которых должен разбираться каждый программист-самоучка, мечтающий о выдающейся карьере, — это структуры данных и алгоритмы. «Computer Science для программиста-самоучки» поможет вам пройти техническое интервью, без которого нельзя получить работу в «айти».

Книга написана для абсолютных новичков, поэтому у вас не должно возникнуть трудностей, даже если ранее вы ничего не слышали о computer science.

Двоичный код

Компьютеры «мыслят» в двоичном формате. Двоичное число — число двоичной системы счисления (с основанием 2). Система счисления — система записи чисел. Для обозначения двоичных чисел используются только две цифры: 0 и 1. В двоичной системе цифра называется битом, что означает двоичный разряд.

Система счисления, которую вы используете для счета, называется десятичной (с основанием 10) и имеет 10 знаков (от 0 до 9). Основание системы счисления — это количество цифр в этой системе. Двоичная и десятичная — не единственные виды систем счисления. Есть, например, система счисления по основанию 16, которая популярна среди программистов и называется
шестнадцатеричной.

Ниже приведено несколько примеров двоичных чисел:

100
1000
101
1101

Когда вы смотрите на эти числа, вы не знаете, по какому они основанию — 2 или 10. Например, первое число 100 может быть 100 по основанию 10 или 4 по основанию 2.

Существует несколько способов для отображения числа по основанию 2. Например, программисты часто ставят b перед числом, чтобы показать, что оно по основанию 2. Вот как еще можно обозначить число по основанию 2:

100b
10002
%100
0b100

Вес разряда — это числовое значение, которое принимает цифра в зависимости от своего места в числе. У четырехзначного числа вес разряда представлен в тысячах, сотнях, десятках и единицах. К примеру, число 1452 — это одна тысяча, плюс четыре сотни, плюс пять десятков, плюс две единицы (рис. 6.1).


В десятичной системе каждый вес разряда имеет степень 10. Крайний правый вес разряда равен 10 в нулевой степени, что равно 1. Следующий вес разряда — 10 в первой степени, что равно 10. Следующий вес разряда равен 10 во второй степени (10 × 10), что равно 100. Следующий вес разряда равен 10 в третьей степени (10 × 10 × 10), что равно 1000 (рис. 6.2).


Вы можете выразить число 1452 как равенство, используя его веса разрядов:
(1 * 10 ** 3) + (4 * 10 ** 2) + (5 * 10 ** 1) + (2 * 10 ** 0) = 1452

Или представить следующим образом:
1 * 10 ** 3 = 1 * 1000 = 1000 +
4 * 10 ** 2 = 4 * 100 = 400 +
5 * 10 ** 1 = 5 * 10 = 50 +
2 * 10 ** 0 = 2 * 1 = 2
___________
1452

Двоичная система счисления работает так же, как десятичная, за исключением того, что в ней лишь две цифры — 0 и 1, а веса разрядов имеют степень 2, а не 10. Крайний правый вес разряда равен 2 в нулевой степени, что равно 1. Следующий вес разряда — 2 в первой степени, что равно 2. Следующий вес разряда равен 2 во второй степени, что равно 4 (2 × 2). Следующий вес разряда равен 2 в третьей степени, что равно 8 (2 × 2 × 2) (рис. 6.3).


Вот как выглядит равенство для числа 1101 по основанию 2:
(1 * 2 ** 3) + (1 * 2 ** 2) + (0 * 2 ** 1)
+ (1 * 2 ** 0) =

8 + 4 + 0 + 1 = 13

Или:
1 * 2 ** 3 = 1 * 8 = 8 +
1 * 2 ** 2 = 1 * 4 = 4 +
0 * 2 ** 1 = 0 * 2 = 0 +
1 * 2 ** 0 = 1 * 1 = 1
____
13

Как видите, 1101 в двоичной системе является числом 13 в десятичной.

В десятичной системе вы считаете, начиная с нуля: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. В этот момент у вас заканчиваются цифры. Чтобы представить следующее число, как вам известно, вы создаете 10, используя 2 цифры. Вы представляете 10 с помощью цифры 1, за которой следует 0.

Когда вы считаете в двоичном коде, вы также начинаете с нуля.
0

Как и в десятичной системе, следующее число 1.
1

После 1 у вас заканчиваются цифры. Это означает, что вам нужно использовать две цифры, чтобы представить число 2, так же, как вы их использовали в десятичной системе, чтобы представить число 10.

В двоичном коде вы обозначаете 2 с помощью 1 и 0:
10

Ноль означает отсутствие единиц, а 1 означает одну двойку. Как же обозначить число 3 в двоичной системе?
11

Первая справа цифра 1 означает одну единицу, а вторая справа 1 означает одну двойку. Если вы прибавите 2 к 1, то получите 3.

Следующая цифра 4 в двоичной системе выглядит следующим образом:
100

Первый 0 справа означает отсутствие единиц, второй 0 справа означает отсутствие двоек, а 1 означает одну четверку. Сложите их и получите 4.

Побитовые операторы

Обычно, когда вы программируете или оперируете числами, вы работаете с целыми числами и числами с плавающей точкой, например с такими, как 100 и 10.5. Однако бывает полезно поработать и с двоичными числами. Используя двоичные числа, можно быстро решать определенные задачи: скажем, выяснить, является ли число степенью 2.

Для работы с двоичными числами в Python можно использовать метод bin.

print(bin(16))

>> 0b1000

Когда вы печатаете bin(16), результат равен 0b10000, что в двоичной системе означает число 16. Как вы узнали ранее, 0b показывает, что число записано в двоичном формате.

Побитовый оператор — это оператор, который можно использовать в выражении с двумя двоичными числами. Например, побитовый оператор AND в Python выполняет булеву арифметику бит за битом. Если оба бита равны 1 (True), Python возвращает число 1; в противном случае Python возвращает 0 (False). Логика для каждого бита у побитового AND та же, что и для ключевого слова and в Python.

Как вы уже знаете, если вы используете ключевое слово and в Python и обе стороны выражения принимают значение True, то Python возвращает True.

print(1==1 and 2==2)

>> True

Если обе стороны принимают значение False, он возвращает False.

print(1==2 and 2==3)

>> False

Если одна сторона принимает значение True, а другая False, Python также возвращает False.

print(1==1 and 1==2)

>> False

Рассмотрим пример применения побитового AND. Допустим, у вас есть два целых числа 2 и 3. Два в двоичной системе равно 0b10, а 3 равно 0b11. Первый справа бит цифры 2 — это 0, первый справа бит цифры 3 — это 1.

10 # 2
11 # 3
——
0

Применение побитового AND к этим битам приводит к 0, потому что есть значения True и False, которые возвращают False (помните: 0 равно False, а 1 равно True). Применение побитового AND ко второму набору битов приводит к 1, так как обе цифры принимают значение True, и Python возвращает True.

10 # 2
11 # 3
——
10

В данном случае побитовая операция AND выводит 0b10, что соответствует цифре 2 в двоичном коде (вы скоро узнаете, чем это полезно).

На языке Python побитовый оператор AND — это знак амперсанда (&). Вот как вы можете применить побитовое AND к двоичным цифрам 0b10 и 0b11 на языке Python:

print(0b10 & 0b11)

>> 2

Вам не нужно использовать побитовое AND для двоичных чисел.

print(2 & 3)

>> 2

В данном случае вы применили оператор AND для десятичных чисел, но Python использует двоичные значения, определяющие 2 и 3, для выполнения операции.

В Python также есть побитовый оператор OR, который работает побитово и возвращает значение 1, когда один или оба бита принимают значение True, и возвращает False, когда оба принимают значение False: точно так же, как ключевое слово or в Python. Посмотрим, что произойдет, если вы используете побитовый оператор OR для чисел 2 и 3. Применение оператора OR для первых двух битов приводит к значению 1, потому что один из битов равен True.

10 # 2
11 # 3
——
1

Когда вы применяете побитовый оператор OR для второго набора битов, Python возвращает 1, потому что оба бита принимают значение True (1).

10 # 2
11 # 3
——
11

Как видите, результат оператора OR для чисел 2 и 3 равен 0b11, что соответствует десятичному числу 3.

На языке Python побитовый оператор OR представлен в виде вертикальной черты (|).

print(2 | 3)

>> 3

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

Рассмотрим некоторые ситуации, когда побитовые операторы бывают полезны. Вы можете использовать побитовое AND для проверки четности или нечетности числа. У четного числа, такого как 2, всегда стоит 0 в конце, тогда как число 1 всегда имеет 1 в конце (и содержит только одну двоичную цифру — 1).

10 # 2
1 # 1

Когда вы применяете побитовый оператор AND для четного числа и числа 1, Python всегда возвращает False, потому что четное число заканчивается на 0, а у числа 1 лишь одна двоичная цифра 1.

10 # 2
1 # 1
--
0

С другой стороны, когда вы применяете побитовый оператор AND для нечетного числа и числа 1, Python всегда будет возвращать значение True, потому что нечетное число заканчивается на 1, а у числа 1 лишь одна двоичная цифра 1.

11 #3
1 #1
--
1

Поскольку у числа 1 лишь одна двоичная цифра, не имеет значения, сколько двоичных цифр у числа, которое вы проверяете на четность, — одна или тысяча.

Поскольку у числа 1 лишь одна двоичная цифра, вы производите только одно сравнение: последней двоичной цифры числа и 1.

Вот как проверить, является число четным или нечетным, используя побитовый оператор AND в Python:

def is_even(n):
     return not n & 1

В функции is_even вы возвращаете not n & 1. Код n & 1 использует побитовый оператор AND для n и 1. Затем вы используете not, чтобы поменять результат на противоположный тому, каким он был бы, потому что, когда вы используете побитовый оператор AND для четного числа и 1, он возвращает False, а это означает, что число четное. В данном случае вы хотите, чтобы функция возвращала значение True для демонстрации того, что число четное, поэтому вы используете not для переключения True на False и False на True.

Побитовый оператор AND также можно использовать для определения того, является ли целое число степенью 2. Каждое число, являющееся степенью 2, имеет одну 1 в своем двоичном представлении, потому что двоичный код имеет основание 2, а это означает, что у любой степени 2 лишь одна цифра 1: например, число 8 в двоичном коде представлено как 0b1000. И наоборот, число, которое на 1 меньше степени 2, содержит только биты с 1: число 7, на 1 меньшее 8, в двоичном коде имеет вид 0b111.

Когда вы примените побитовый оператор AND для этих двух двоичных чисел, вы увидите, что весь итоговый двоичный код состоит из нулей, если первое число является степенью 2.

1000 # 8
0111 # 7
————
0000

Если число не является степенью 2, итог будет содержать как минимум одну двоичную цифру, равную 1.

0111 # 7
0110 # 6
————
0001

Вот как использовать побитовый оператор AND в Python, чтобы определить, является ли число степенью 2:

def is_power(n):
     if n & (n - 1) == 0:
            return True
     return False

Функция is_power принимает рассматриваемое число. Внутри функции вы используете оператор if, чтобы проверить, равно ли использование оператора AND для n и n – 1 нулю. Если это так, то n является степенью 2 и вы возвращаете True. В противном случае вы возвращаете False.

FizzBuzz

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

Вот в чем состоит задача FizzBuzz: написать программу, которая выводит числа от 1 до 100; если число кратно 3, вывести Fizz; если число кратно 5, вывести Buzz; если число кратно 3 и 5, вывести FizzBuzz.

Ключом к решению этой задачи является использование оператора остатка от деления, который делит два значения и возвращает остаток. Если остаток равен 0, вы понимаете, что делимое (число, которое вы делили) кратно делителю (числу, на которое делили). Например, 6 % 3 делит 6 на 3 и возвращает остаток 0.

print(6 % 3)

>> 0

Поскольку остатка нет, вы знаете, что 6 кратно 3.

Когда вы оцениваете 7 % 3, остаток есть, поэтому вы знаете, что 7 не кратно 3.

print(7 % 3)

>> 1

Чтобы решить задачу FizzBuzz, вы перебираете числа от 1 до 100 и используете оператор по модулю, проверяя, является ли число кратным 3 и 5, только 3 или только 5.

Вот как это сделать:

def fizzbuzz(n):
     for i in range(1, n + 1):
            if i % 3 == 0 and i % 5 == 0:
                   print('FizzBuzz')
            elif i % 3 == 0:
                   print('Fizz')
            elif i % 5 == 0:
                   print('Buzz')
            else:
                   print(i)

Даже если вы хотите найти числа от 1 до 100, лучше всего ввести число n вместо жесткого кодирования 100. Введение n сделает вашу программу более гибкой, если вы захотите запустить ее с другим числом. Итак, функция fizzbuzz принимает n в качестве параметра.

def fizzbuzz(n):

Для начала вы используете цикл for для перебора каждого числа от 1 до n + 1.

for i in range(1, n + 1):

Затем вы используете условный оператор с оператором остатка от деления, чтобы определить, делится ли число i и на 3, и на 5. Если это так, выводите FizzBuzz.

if i % 3 == 0 and i % 5 == 0:
     print('FizzBuzz')

Далее вы используете еще один условный оператор, чтобы проверить, делится ли число на 3. Если это так, выводите Fizz.

elif i % 3 == 0:
     print('Fizz')

Затем вы используете еще один условный оператор, чтобы проверить, делится ли число на 5. Если это так, выводите Buzz.

elif i % 5 == 0:
     print('Buzz')

Если число не делится ни на 3, ни на 5, ни на оба этих числа, выводите само число.

else:
     print(i)

Когда вы запустите программу, вы увидите следующее: числа, которые делятся на 3, например 6 и 27, заменяются на Fizz; числа, кратные 5, например 10 и 85, заменяются на Buzz; те числа, которые делятся на оба числа, например 15 и 30, заменяются на FizzBuzz.

>> 1 2 Fizz 4 Buzz Fizz 7 8...Buzz Fizz 97 98 Fizz Buzz

Вашему алгоритму требуется n шагов, поэтому он линейный. Если вы введете 100, алгоритму потребуется 100 шагов, если введете 1000, потребуется 1000 шагов. Оператор остатка от деления был ключом к решению данной задачи. Однако он может быть полезен не только на техническом интервью. Оператор остатка от деления также используется при написании реальных приложений. Например, у вас имеется текстовый файл длиной 50 000 строк, и вы можете на страницу поместить 49 строк. Сколько текста будет на последней странице? На последней странице будет 20 строк, потому что 50000 % 49 = 20. А что, если у вас база данных с 20 000 наименований и вы хотите что-то сделать с каждым вторым наименованием? Один из способов — перебирать каждый элемент и менять только элементы с четным индексом.

Наибольший общий делитель

Наибольший общий делитель — наибольшее положительное целое число, на которое делятся без остатка два или более целых числа. В этом разделе вы узнаете, как для двух целых чисел, например 20 и 12, найти их наибольший общий делитель.

Числа 20 и 12 вы можете разделить без остатка на 1, 2 и 4. Поскольку 4 — самое большое число, оно и является наибольшим общим делителем.

Делители числа 20: 1, 2, 4, 5, 10.
Делители числа 12: 1, 2, 3, 4, 6.

Один из алгоритмов для нахождения наибольшего общего делителя для двух чисел — проверка всех возможных делителей на предмет того, на какие из них без остатка делятся оба числа. Например, чтобы найти наибольший общий делитель для чисел 20 и 12, вы начинаете с деления их на 1, затем на 2, на 3 и т. д. Вам не нужно проверять числа, которые больше самого меньшего из двух чисел, потому что оно не может делиться без остатка на превышающее его число. Например, число больше 12 не разделит 12 без остатка.

Ниже представлен код на языке Python для вашего алгоритма:

def gcf(i1, i2):
     gcf = None
     if i1 > i2:
            smaller = i2
     else:
            smaller = i1
     for i in range(1, smaller + 1):
            if i1 % i == 0 and i2 % i == 0:
                   gcf = i
     return gcf

gcf(20, 12)

Функция gcf принимает в качестве параметров два целых положительных числа, для которых вы ищете наибольший общий делитель.

def gcf(i1, i2):

Внутри функции вы определяете, какое из двух целых чисел меньше, и присваиваете его значение переменной smaller, чтобы прекратить проверку делителей, дойдя до этого числа.

if i1 > i2:
     smaller = i2
else:
     smaller = i1

Затем вы используете цикл for, чтобы проверить каждый делитель от 1 до значения переменной smaller плюс 1 (чтобы проверить и наименьшее число).

for i in range(1, smaller + 1):

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

if i1 % i == 0 and i2 % i == 0:
     gcf = div

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

Однако у вашего кода есть проблема. Что, если одно из целых чисел равно 0?

print(gcf(0, 22))

>> None

Программа вернет неверный ответ, если одно из целых чисел будет равно 0. Неспособность кода справиться с числом 0 является примером граничного условия — входных данных, находящихся за пределами тех входных данных, которые ожидаемо должна была получить ваша программа. Если при вычислении наибольшего общего делителя для двух чисел одно из чисел равно 0, то наибольший общий делитель будет равен второму целому числу. Например, наибольший общий делитель для чисел 0 и 12 равен 12.

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

def gcf(i1, i2):
     if i1 == 0:
            return i2
     if i2 == 0:
            return i1

     if i1 > i2:
            smaller = i2
     else:
            smaller = i1

     for divisor in range(1, smaller + 1):
            if(i1 % divisor == 0) and (i2 % divisor == 0):
                 gcf = divisor

     return gcf

Ваша программа также не может обрабатывать отрицательные числа, поэтому в начале вам следует добавить проверку на то, что оба числа положительные.

def gcf(i1, i2):
     if i1 < 0 or i2 < 0:
            raise ValueError("Numbers must be positive.")
     if i1 == 0:
            return i2
     if i2 == 0:
            return i1

     if i1 > i2:
            smaller = i2
     else:
            smaller = i1

     for divisor in range(1, smaller+1):
            if(i1 % divisor == 0) and (i2 % divisor == 0):
                   gcf = divisor

     return gcf

Код для нахождения наибольшего общего делителя линеен, так как алгоритм решает задачу за n шагов. Линейный код — это неплохо, но существует более удачный способ решения данной задачи.


Более подробно с книгой можно ознакомиться на сайте издательства:
» Оглавление
» Отрывок

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Computer Science