Изменяемые и неизменяемые объекты в Python (mutable and immutable).
В питоне всё, что можно положить в переменную, является объектом.
А сама переменная является ссылкой на этот объект.
a = 1
a = 2
b = a
Объекты «живут» в своём мире независимо от переменных, а переменные — один из способов обратиться извне к миру объектов.
Так в примере выше объект Целое-число-1 продолжает жить даже после того, как мы поменяли переменную a.
Объекты в питоне бывают двух значительно отличающихся сортов: изменяемые (mutable) и неизменяемые (immutable).
Неизменяемыми являются целые и действительные числа (int, float), строки (str), последовательности байтов (бинарные данные, bytes), а также кортежи, все элементы которых неизменяемы (tuple).
Напротив, списки (list), словари (dict) и множества (set) являются изменяемыми.
Что всё это значит?
Неизменяемые объекты обладают замечательным свойством: они не могут измениться в результате работы программы.
Если некоторая переменная «смотрит» на неизменяемый объект, то можно быть уверенным, что её значение не поменяется, если только ей не присвоить ссылку на другой объект.
Например, в результате выполнения кода a = 1 в переменной a хранится ссылка на объект Целое-число-1, и что бы не происходило с другими переменными, a будет всегда равно 1.
Изменяемые объекты не обладают таким постоянством.
Они скорее напоминают контейнер для хранения: контейнер остаётся на месте, а вот содержимое может сильно измениться.
Что всё это для нас значит?
Ну, например, если передать список в «чужую» функцию, то его могут испортить до неузнаваемости:
Здесь можно поиграться с этим примером и посмотреть на то, что происходит с ссылками:
Обратите внимание, при передаче списка в функцию можно модифицировать элементы списка при помощи присваиваний A[i] = ..., методов pop, append, insert и т.д.
Это не является модификацией списка, как целого, т.е. имя A по-прежнему указывает на тот же список, при этом
содержимое списка меняется.
Не всегда такое поведение является ожидаемым:
a = [1, 2, 3]
b = a
b.insert(0, 'ops')
b.pop()
print(b) # -> ['ops', 1, 2]
print(a) # -> ['ops', 1, 2]
Присваивание b = a не создает новый список,
а всего лишь делает b ссылкой на уже
существующий список.
Для того, чтобы «сохранить» старый список, нужно создавать его копию:
Метод .copy() создаёт новый список, в котором хранятся в точности те же ссылки.
Это означает, что если в списке будет лежать другой список, то копия будет на него ссылаться:
Во всех (почти) задачах этого листа основной алгоритм решения
задачи должен быть описан в виде функции,
получающей в качестве параметра список
(а также, возможно, и дополнительные параметры).
Во многих задачах этого листка (если не оговорено иное)
нельзя использовать вспомогательные списки.
A: Возрастает ли список?
Дан список. Определите, является ли он монотонно возрастающим
(то есть верно ли, что каждый элемент этого списка больше предыдущего).
Выведите YES, если список монотонно возрастает и NO в противном случае.
Решение оформите в виде функции is_ascending(A).
В данной функции должен быть один цикл while, не содержащий вложенных
условий и циклов — используйте схему линейного поиска.
1 7 9
YES
IDE
B: k-е вхождение
Дан список чисел, число \(a\) и натуральное число \(k\) .
Выведите индекс \(k\)-го по счету появления в массиве
числа \(a\). Если число \(a\) встречается в массиве менее
\(k\) раз, выведите число -1.
Решение оформите в виде функции kth_appearance(A, a, k).
Задача должна решаться за однократный проход по списку. Срезы и методы типа find использовать нельзя.
1 2 1 3 2 3 2 3 2 2
3 2
5
1 1 1 1
1 5
-1
IDE
C: Количество цифр
Дана последовательность чисел, состоящая только из чисел 1, ..., 9.
Последовательность завершается числом 0. Каждое число записано в
отдельной строке.
Подсчитайте, сколько раз в этой последовательности встречаются значения 1, 2, ..., 9.
Сохранять всю последовательность введенных чисел в списке нельзя, но можно (и нужно) хранить в списке количество цифр каждого вида.
Программа должна вывести ровно 9 чисел: количество единиц, двоек, ..., девяток в данной последовательности.
1
2
3
4
5
1
1
1
2
2
0
4 3 1 1 1 0 0 0 0
IDE
D: Противоположные элементы
Дан список чисел. Определите, есть ли в нем два противоположных
(то есть дающих в сумме 0) числа.
Если такие числа есть в списке, выведите их индексы в порядке возрастания.
Если таких чисел в списке нет, выведите одно число 0.
Срезы, операции типа in, методы типа find, index использовать нельзя.
1 2 3 -2 -4
1 3
IDE
E°: Сортировка выбором
Дан список целых чисел.
Выведите все элементы этого списка в порядке невозрастания значений.
Выведите новый список на экран.
Решите эту задачу при помощи алгоритма сортировки выбором.
Решение оформите в виде функции selection_sort(A).
В алгоритме сортировки выбором мы находим наибольший элемент
в списке и ставим его на первое место, затем находим наибольший
элемент из оставшихся и ставим его на второе место и т.д.
В этой задаче разрешается модифицировать исходный список,
в частности, удалить из списка i-й элемент
можно при помощи метода pop(i), и использовать
новый список для добавления в него элементов.
1 4 2 3 4
4 4 3 2 1
IDE
F°: Сортировка вставкой
Дан список целых чисел. Отсортируйте его в порядке
неубывания значений. Выведите полученный список на экран.
Решите эту задачу при помощи алгоритма сортировки вставкой.
Решение оформите в виде функции insertion_sort(A).
В этой задаче нельзя пользоваться дополнительным списком
и операциями удаления и вставки элементов.
В алгоритме сортировки вставкой в каждый произвольный момент
начальная часть списка уже отсортирована. В решении имеется цикл
for i in range(1, len(A)), внутри которого
в предположении, что элементы списка A[0],
A[1], ..., A[i-1]
уже отсортированы, элемент A[i]
добавляется в отсортированную часть списка.
Для этого находится позиция, в которую необходимо вставить
элемент A[i], затем осуществляется циклический
сдвиг фрагмента уже отсортированной части.
Важно, чтобы ваша реализация выполняла сортировку уже отсортированного массива за линейное время.
1 4 2 3 4
1 2 3 4 4
IDE
G°: Сортировка пузырьком
Дан список целых чисел. Отсортируйте его в порядке
невозрастания значений.
Выведите полученный список на экран.
Решите эту задачу при помощи алгоритма пузырьковой сортировки.
Решение оформите в виде функции bubble_sort(A).
В алгоритме пузырьковой сортировки осуществляется проход
по списку от начала к концу, и если два соседних элемента списка
стоят в неверном порядке, то они переставляются в правильном
порядке. В результате минимальный элемент списка окажется
на последнем месте. Повторим эту
процедуру еще несколько раз, чтобы поставить все элементы на свои места.
Вспомогательным списком пользоваться нельзя.
1 4 2 3 4
4 4 3 2 1
IDE
Функция sorted и метод sort
Функция sorted получает в качестве аргумента список, и возвращает ссылку на новый список,
содержащий те же элементы в порядке возрастания. Пример:
A = [1, 6, 2, 5, 3, 4]
B = sorted(A)
Метод sort применяется к списку и переставляет элементы списка в порядке возрастания. Пример:
A.sort()
Например, вот решение задачи про сортировку в порядке неубывания в одну строку:
У функции sorted и метода sort есть параметр reverse. Если этот
параметр установить в True, то сортировка будет выполняться в порядке невозрастания. Пример:
B = sorted(A, reverse = True)
A.sort(reverse = True)
Упражнения
H: Создание архива
Системный администратор вспомнил, что давно не делал архива пользовательских файлов.
Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.
Известно, какой объем занимают файлы каждого пользователя.
Напишите программу, которая по заданной информации о пользователях и свободному объему на архивном диске определит максимальное число пользователей, чьи данные можно поместить в архив, при этом используя свободное место как можно более полно.
Программа получает на вход в одной строке число S – размер свободного места на диске (натуральное, не превышает 10000),
и число N – количество пользователей (натуральное, не превышает 100), после этого идет N чисел - объем данных каждого пользователя (натуральное, не превышает 1000), записанных каждое в отдельной строке.
Выведите наибольшее количество пользователей, чьи данные могут быть помешены в архив.
100 2
200
50
1
100 3
50
30
50
2
IDE
I: Обувной магазин
В обувном магазине продается обувь разного размера.
Известно, что одну пару обуви можно надеть на другую,
если она хотя бы на три размера больше. В магазин пришел покупатель.
Требуется определить, какое наибольшее количество пар обуви сможет
предложить ему продавец так, чтобы он смог надеть их все одновременно.
Сначала вводится размер ноги покупателя (обувь меньшего размера он надеть не сможет), в следующей строке — размеры
каждой пары обуви в магазине через пробел. Размер — натуральное число, не превосходящее 100.
Выведите единственное число —максимальное количество пар обуви, которое сможет надеть покупатель.
60
60 63
2
35
30 40 35 42 35
2
Выведите единственное число —максимальное
количество пар обуви, которое сможет надеть покупатель.
IDE
J°: Результаты олимпиады
В олимпиаде участвовало N человек. Каждый получил определенное количество баллов, при этом оказалось,
что у всех участников — разное число баллов.
Упорядочите список участников олимпиады в порядке убывания набранных баллов.
Программа получает на вход число участников олимпиады N.
Далее идет N строк, в каждой строке записана фамилия участника, затем, через пробел, набранное им количество баллов.
Выведите список участников (только фамилии) в порядке убывания набранных баллов.
3
Ivanov 15
Petrov 10
Sidorov 20
Sidorov
Ivanov
Petrov
IDE
K: Личные дела
Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам,
а внутри класса по фамилиям.
В первой строке входных данных записано число \(N\) (\(1 \le N \le 1000\)) – количество личных дел.
Далее записано \(N\) строк, каждая из которых состоит из фамилии учащегося (строка без пробелов)
и номера класса (целое число от 1 до 11).
Нужно вывести список всех учащихся, сначала выводя номер класса, затем — фамилию учащегося.
Список должен быть отсортирован по классу, а затем по фамилии.
3
Ivanov 10
Petrov 9
Sidorov 9
9 Petrov
9 Sidorov
10 Ivanov
IDE
L: Такси
После затянувшегося совещания директор фирмы решил заказать такси,
чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколько у него сотрудников.
Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.
Директор знает, какому сотруднику сколько километров от работы до дома
(к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине).
Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор
хочет заплатить как можно меньшую сумму.
В первой строке записаны N чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании.
Во второй строке записаны N чисел — тарифы за проезд одного километра в такси.
Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.
10 20 30
50 20 30
1700
IDE
M: Сортировка дробей
В этой задаче вам нужно научиться сортировать не числа, а рациональные дроби.
Программа получает на вход \(N\) дробей: сначала задается число \(N\), потом
идет \(N\) строк, в каждой из которорых записана одна дробь. Дробь записана
в виде \(a/b\), где \(a\) и \(b\) —натуральные числа.
Программа должна вывести список этих дробей в порядке неубывания.
Если в списке есть две равные дроби \(a/b=c/d\), то раньше
выводится дробь, у которой меньше числитель.
При решении этой задачи нельзя использовать действительные числа.
Указание. Удобно отдельно хранить числитель дроби, отдельно — знаменатель.
3
4/2
2/6
1/2
2/6
1/2
4/2
IDE
N: Коньки
В 179 школе есть много коньков самых разных размеров. Школьник может надеть коньки любого размера, который не меньше
размеров его ноги. Известны размеры всех коньков и размеры ног школьников. Определите, какое наибольшее число школьников
сможет одновременно пойти покататься.
Первая строка содержит список натуральных чисел размеры коньков. Вторая строка содержит
список размеров ног школьников.
Выведите единственное число — наибольшее количество школьников, которое сможет пойти на каток.
41 40 39 42
42 41 42
2
IDE
O: Скидки
В супермаркете проводится беспрецедентная акция — «Покупая два любых товара,
третий получаешь бесплатно*», а внизу мелким шрифтом приписано
«* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».
Вася, идя в супермаркет, определился, какие товары он хочет купить, и узнал, сколько они стоят.
Помогите ему определить минимальную сумму денег, которую ему нужно взять с собой, чтобы в итоге стать счастливым обладателем этих товаров.
Программа получает на вход число N (1≤N≤1000), а затем N чисел — стоимости выбранных Васей товаров.
Все стоимости — натуральные числа, не превышающие 10000.
Выведите одно число – сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).
6
1 5 4 3 5 7
19
Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок.
5
3 15 25 8 8
51
Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка.
IDE
P: Чемпионат по стрельбе
На региональном этапе Всероссийской олимпиады школьников по информатике 23 января 2011 года предлагалась следующая задача.
Победитель школьного этапа олимпиады по информатике нашел дома в старых бумагах
результаты чемпионата страны по стрельбе из лука, в котором участвовал его папа.
К сожалению, листок с результатами сильно пострадал от времени, и разобрать фамилии
участников было невозможно. Остались только набранные каждым участником очки,
причем расположились они в том порядке, в котором участники чемпионата выполняли стрельбу.
Расспросив папу, школьник выяснил, что количество очков, которое набрал папа,
заканчивается на 5, один из победителей чемпионата стрелял раньше папы, а папин друг,
который стрелял сразу после папы, набрал меньше очков. Теперь он заинтересовался,
какое самое высокое место мог занять его папа на том чемпионате.
Будем считать, что участник соревнования занял k-е место, если ровно (k-1) участников
чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата,
занявшие первое место.
Требуется написать программу, которая по заданным результатам чемпионата определяет,
какое самое высокое место на чемпионате мог занять папа победителя школьного этапа олимпиады по информатике.
Программа получает на вход целое число n — количество участников чемпионата страны по стрельбе
(3⩽n⩽105). Далее идет n положительных целых чисел, каждое из которых не превышает 1000, —
очки участников чемпионата, приведенные в том порядке, в котором они выполняли стрельбу.
Выведите одно целое число — самое высокое место, которое мог занять папа школьника.
Если не существует ни одного участника чемпионата, который удовлетворяет, описанным выше условиям, выведите в выходной файл число 0.
7
10 20 15 10 30 5 1
6
3
15 15 10
1
3
10 15 20
0
IDE
Q: SMS-голосование
На телевизионном шоу зрители голосуют за участников шоу, отправляя SMS-сообщение с номером участника.
Определите победителя шоу на основе присланных SMS-сообщений.
Первая строка входных данных содержит количество участников шоу N.
Во второй строке содержится список номеров, присланных телезрителями, через пробел.
Программа должна вывести номер участника, набравшего наибольшее число голосов.
Если таких несколько — программа должна вывести номера всех
победителей шоу в порядке возрастания.
Неверные номера, присланные телезрителями (то есть большие чем N) необходимо игнорировать.
3
1 2 2 1 3 2 3
2
2
1 2 2 1
1 2
3
4 3 4
3
IDE
R°: Сортировка подсчетом
Дан список из N (N⩽105) элементов,
которые принимают целые значения от 0 до 100.
Отсортируйте этот список в порядке неубывания элементов. Выведите полученный список.
Решение оформите в виде функции count_sort(A), которая модифицирует передаваемый ей список.
Использовать встроенные функции сортировки нельзя.
Сортировка подсчетом устроена следующим образом.
Пусть вы заранее знаете, что ваш список может содержать только заранее известный набор значений.
Пройдя по списку от начала и до конца подсчитываем, сколько раз встретился каждый элемент.
После этого последовательно выводим возможные значения столько раз, сколько они встречались в списке.
1 3 2 3 1
1 1 2 3 3
IDE
S: Клавиатура
На региональном этапе Всероссийской олимпиады школьников по информатике в 2009 году предлагалась следующая задача.
Всем известно, что со временем клавиатура изнашивается,
и клавиши на ней начинают залипать. Конечно, некоторое время
такую клавиатуру еще можно использовать, но для нажатий клавиш
приходиться использовать большую силу.
При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий,
которое она должна выдерживать. Если знать эти величины для используемой клавиатуры,
то для определенной последовательности нажатых клавиш можно определить,
какие клавиши в процессе их использования сломаются, а какие — нет.
Требуется написать программу, определяющую, какие клавиши сломаются
в процессе заданного варианта эксплуатации клавиатуры.
Первая строка входных данных содержит целое число n (1⩽n⩽1000) —
количество клавиш на клавиатуре. Вторая строка содержит n целых чисел —
с1, с2, … , сn, где сi
(1⩽ci⩽100000) — количество нажатий,
выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1⩽k⩽100000) —
общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj
(1⩽pj⩽n) — последовательность нажатых клавиш.
Программа должна вывести n строк, содержащих информацию об исправности клавиш.
Если i-я клавиша сломалась, то i-ая строка должна содержать слово YES,
если же клавиша работоспособна — слово NO.
5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5
YES
NO
NO
NO
YES
IDE
T: Задача Иосифа Флавия
N человек, пронумерованных числами от 1 до N стоят в кругу.
Они начинают считаться, каждый K-й по счету человек выбывает из круга,
после чего счет продолжается со следующего за ним человека.
Определите номер человека, который останется в кругу последним.
Программа получает на вход числа N и K, не превосходящие 100
и должна вывести одно число от 1 до N.
5 7
4
В этом примере люди выбывают в таком порядке: 2, 5, 1, 3, остался номер 4.
IDE
U°: Слияние списков
Даны два списка A и B упорядоченных по неубыванию.
Объедините их в один упорядоченный список С (то есть он должен содержать
len(A)+len(B) элементов). Решение оформите в виде
функции merge(A, B), возвращающей новый список. Алгоритм
должен иметь сложность O(len(A)+len(B)). Модифицировать исходные списки запрещается.
Использовать функцию sorted и метод sort запрещается.
Программа получает на вход два неубывающих cписка, каждый в отдельной строке.
Программа должна вывести последовательность неубывающих чисел, полученных объединением двух данных списков.
1 5 7
2 4 4 5
1 2 4 4 5 5 7
IDE
V: Пересечение множеств
Даны два списка, упорядоченных по возрастанию (каждый список состоит из различных элементов).
Найдите пересечение множеств элементов этих списков, то есть те числа, которые являются элементами
обоих списков. Алгоритм должен иметь сложность O(len(A)+len(B)).
Решение оформите в виде функции intersection(A, B).
Функция должна возвращать список пересечения данных списков в порядке возрастания элементов.
Модифицировать исходные списки запрещается.
Программа получает на вход два возрастающих списка, каждый в отдельной строке.
Программа должна вывести последовательность возрастающих чисел,
являющихся элементами обоих списков.
1 3 4 7 9
2 3 7 10 11
3 7
IDE
W: Наибольшее произведение двух чисел
Дан список, заполненный произвольными целыми числами. Найдите в этом списке
два числа, произведение которых максимально. Выведите эти числа в порядке неубывания.
Количество чисел в списке не превосходит 100.
4 3 5 2 5
5 5
-4 3 -5 2 5
-5 -4
IDE
X★: Наибольшее произведение двух чисел
Решите предыдущую задачу для случая, когда количество чисел в списке
не превосходит 100000. Решение должно иметь сложность \(O(n)\).
Стандартной сортировкой пользоваться нельзя.
IDE
Y★: Наибольшее произведение трех чисел
В данном списке из n⩽105 целых чисел найдите три числа,
произведение которых максимально.
Решение должно иметь сложность O(n), где n - размер списка.
Выведите три искомых числа в любом порядке.
Тесты к этой задаче закрытые.
3 5 1 7 9 0 9 -3 10
9 10 9
-5 -30000 -12
-5 -30000 -12
IDE
Z★★: Ханойская сортировка
Кто-то перепутал Ханойскую головоломку и разместил диски на первом
стержне не соблюдая правила игры. Переложите эти диски так, чтобы они
оказались на одном из стержней строго в порядке возрастания номеров.
Программа получает на вход число дисков n⩽10.
Во второй строке записаны n чисел —
номера дисков на первом стержне сверху вниз.
Перемещать диск можно только в том случае,
если он кладется на диск большего номера.
Выведите последовательность перекладываний,
размещающая диски на любом стержне в порядке возрастания номеров.
Формат вывода одного перекладывания:
A B C, где A номер
перемещаемого диска (1⩽A⩽n), B —
номер стержня с которого снимается диск, C —
номер стержня на который кладется диск.
