Новости

31.01.2023

Книга «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).

image


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

image


Вы можете выразить число 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).

image


Вот как выглядит равенство для числа 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 шагов. Линейный код — это неплохо, но существует более удачный способ решения данной задачи.

Об авторе
Кори Альтхофф — писатель, программист и лектор. Его первая книга The Self-Taught Programmer («Программист-самоучка») была переведена на семь языков, а после ее публикации в обиход вошло понятие программист-самоучка. Сайт Book Authority назвал The Self-Taught Programmer одной из величайших книг по программированию всех времен, а The Next Web включил ее в топ-10 книг, которые помогут стать отличным программистом. Более 200 тысяч разработчиков состоят в сообществе программистов-самоучек, собранном Кори Альтхоффом через популярную группу на Facebook, через блог, новостную рассылку и курсы на платформе Udemy. Кори живет в Калифорнии с женой и дочерью.
О научном редакторе
Доктор Ханну Парвиайнен — астрофизик, изучающий планеты за пределами нашей Солнечной системы, сотрудник Канарского института астрофизики — одного из ведущих астрофизических институтов в мире, в котором находится крупнейший из существующих оптических телескопов. Ханну Парвиайнен несколько лет был аспирантом-исследователем в Оксфордском университете. Среди ключевых тем его работ — научные вычисления и современные численные методы. Имеет более 20 лет опыта программирования на языке Python.


Подробнее с книгой можно ознакомиться в нашем каталоге.


Комментарии: 0

Пока нет комментариев


Оставить комментарий






CAPTCHAОбновить изображение

Наберите текст, изображённый на картинке

Все поля обязательны к заполнению.

Перед публикацией комментарии проходят модерацию.