Алгоритмы на Python 3; массивы (тип list)

Алгоритмы на Python 3. Лекция №5 Массивы (тип list) Массив - это такой способ доступа к данным, когда у вас есть одно имя и сразу много данных, то есть у вас есть какое-то имя А  1/ 2/ 3/ 4/ 5 -объекты данные обыкновенно хранящиеся в массиве имеют одинаковый тип. То есть, у вас есть объекты, заключенные в массив, вот эти объекты каждый из них является индивидуальным объектом. Это конкретные объекты, хранящиеся в массиве, как в некотором контейнере в которой как элементы хранятся целые числа. Весь этот массив имеет тип list, а вот хранящиеся в нем элементы не имеют собственных имен, но доступиться к ним можно. Каждый из них имеет тип int. Как создать конкретно такой вот массив: А = [1,2,3,4,5] Что можно делать с массивом? Поскольку он является вполне таким «контейнером» первое и самое интересное что можно с ним сделать: это перебрать контейнер по порядку для этого не надо практически ничего, из-за того что в Python очень удобны для этого цикл (for) for x in A: print (x) Можно распечатать и весь контейнер целиком print А, он так и распечатает в квадратных скобках через запятую все элементы. Если же хочется последовательно доступаться по элементно, то надо понимать следующее: что в этом случае возникает на каждой операции альтернативное имя Х, которое ссылается на те же самые элементы. То есть, альтернативное имя Х добавочное, но это уже имя конкретного объекта. Если вместо Х или вдобавок к нему напечатать еще и type x, то увидим что там класс int.(Каждое из них целое число) В то же время, если спросить какой type А, то он вернет List- это список. Поговорим о модели данных в языке python Как хранятся собственно данные? Оказывается, в python есть изменяемые типы и неизменяемые. Вот есть такой объект как единичка типа int, а теперь представьте себе что я говорю: «единичка измени свое значение на двойку»,но всё же не могу так сказать т.к она константа. Так вот для целых,дробных чисел и вообще для других чисел принято следующее правило: они являются константами, то есть константный тип неизменяемый. Инструкция х+=1 расшифровывается следующим образом, она расшифровывается, то есть эквивалентно следующий х=х+1 Как вычисляется это? Это вычисляется так,в начале посчитать результат: А  1/ 2/ 3/ 4/ 5 Х «+» 2 1 У меня есть объект единичка, есть еще один объект единичка временный, который сожрет сборщик мусора, как только вы числится вот это выражение. У меня эти два объекта порождают целое число, они порождают при помощи операции «+» объект 2 и после этого происходит x равно, то есть присваивания в python- это связывание имени и объекта и у меня имя x отвязываетcя от старого объекта и связывается с новым объектом. После чего, временный объект необходимый для вычисления удаляется и остается что x ссылается на объект 2 после этого благополучно происходит print x распечатывается (x) и что (x) на следующей итерации имя (х) не исчезает, но начинает ссылаться на другой объект временный. На него ссылок больше нет, приходит так называемый сборщик мусора и съедает этот временный объект. Идея в том, что есть имена, а есть объекты А как же нам изменить сам массив, вот сами элементы, хранящиеся в нем? хотелось бы их как-то поменять ну Давайте, например, поставим задачу: возвести каждый элемент в квадрат. Так чтобы к самой ссылке, вот оказывается очень просто. Для этого мне требуется доступаться к элементу по индексу. У массива у каждого элемента предусмотрен индекс, причем эти индексы идут от нуля. То есть у первого элемента индекс 1. Вот у массива нулевой элемент- это первый. Так вот я сейчас при помощи k пробегусь по диапазону от нуля до четырех. for k in range (5) range функция мне сгенерирует арифметическую прогрессию старт-стоп степ. Когда пишу range 5 это то же самое как,если написать range (0,5,1) :начать с нуля, стоп 5 не достигаемый и шаг единичка. Но можно просто написать range 5 и понятно, что это значит от 0 до 4. Итак, перебираю индексы по порядку от нуля до четырех. Вот теперь у меня нет никакого дополнительного имени x которая является, на самом деле есть у меня этот k, но это всего лишь у меня номерок, то есть это индексная переменная, и она постепенно там тикает 0,1,2 И я этой индексной переменной пользуюсь для того, чтобы сам список менять. Возникает вопрос: «А как бы мне создать массив по длиннее?» Если я хочу создать массив размером 100,1 000,1 000 000 целых чисел. Как его создать? Как мне его заполнить? Для этого можно воспользоваться следующим синт. Я могу взять и сказать: «нулевое значение хочу размножить там в столько раз в сколько мне надо.» Дальше возникает следующий вопрос: создал массив размером 1000, потому что мне поставили задачу. Сейчас я хочу ввести переменную, которая будет хранить уровень реальной заполненности в этом массиве. То есть сейчас там хранится 0 элементов. Я введу это словом top верхушечку. Вот верхушка сейчас на нуле Top указывает на индекс 0. она говорит там 0 элементов. Заодно top указывает, что фактически первый элемент куда нужно копировать. Что делаю я: считываю число x Дальше пока у меня этот x не равен нулю. Что я буду делать? То есть я получил х значит, мне впихнуть его нужно в массив куда? Естественно по указателю топ, то есть я ровненько в топовое место кладу то число, которое мне пришло. Я говорю А от top, где топ это уровень заполненности, равно x Но я же туда положил реальное число, допустим там 1,2,3,4,5 вводятся, а потом 0 1 2 3 4 5 0 на входе Каждая в отдельной строке. Но top должен сказать, теперь там один элемент хранится, то есть топ я должен увеличить. top+=1 Ну и считываю следующий х туда Х=int (input (1) Таким образом, я организовал считывание и теперь у меня два эффекта: У меня в самом массиве разложены все числа последовательно, а заодно top = 5, то есть количеству реально хранимых чисел. И я могу дальше теперь уже не циклом while, который имеет непредсказуемое количество операций, а теперь вывести числа задом наперёд. Я могу как for обычным. Я запускаю цикл for k который пробегает индексы в диапазоне for k in rang начиная с top – 1, потому что у меня если там пять элементов, то максимальный заполненный индекс – 4. Я ж с 0 начал, с 0 по 4 у меня они хранятся. Поэтому for k in rang (4;-1;-1) начиная от 4- это старт, 0 должен быть достигнут поэтому 0 стопом быть не может -1-стоп, и шаг -1. Теперь я распечатываю: print ( A[k] ) То есть, при помощи дополнительной переменной я могу контролировать реальный уровень заполненности в массиве. Простые алгоритмы 1. Копирование массива Допустим в моей задачке будет заранее известен размер массива. В первой строке вводится размер массива то, сколько элементов будет введено, а потом уже их надо запоминать и так далее. Итак, вот мне уже известен размер массива, я создаю два массива: Допустим А мне ввели из клавиатуры, ну каким образом мне считать массив А? Итак, что я сейчас делаю?- я создал два, я заполню А разумными числами. Как мне скопировать из А в В? я Давайте сейчас напишу здесь С=А Имена в питоне создаются методом присваивания в них. Что у меня сейчас происходит: у меня (А) создался, как контейнер, содержащий нули в объеме 1000 штук (В) создался как контейнер, содержащий нули в объеме 1000 штук. А как создался (С)? Никакой операции создания нового объекта не происходит. Это значит, что (С) всего лишь является ссылкой на тот же самый (А) А если я хочу создать новый список, и запустить этот процесс автоматический, т.е. создать копию? (С) в данном случае это второе имя того же самого объекта, а учитывая что списки являются изменяемыми, то если я изменю теперь А нулевому положу какое-нибудь значение 777, то я легко обнаружу, что С нулевой у меня кто?- 777 Не единичка, которая туда вначале была с клавиатуры, а вот то есть имя у меня может существовать сколько угодно имен, одного и того же объекта. Если объект является изменяемым, то у меня могут происходить внезапное изменение самого объекта. А как же мне все-таки вернуться к тому, чтобы сделать полный дубликат того списка, который есть и покороче. Чтоб не писать, тоже самое что для (В) сделано. Есть такая возможность: сотвори ко мне список на основе списка (А) С = list (А) Я вызываю явным образом конструктор списка, и он создаст новый список (копию списка) Значит у нас с вами линейный поиск массива. Я создам функцию, которая будет называться array_search Я ей буду передавать массив, я буду передавать размер массива, и я буду передавать то есть размер, в котором я буду собственно искать диапазон поиска, и я буду передавать собственно Х-искомое число. Надо сказать, что в питоне, начиная с некоторой версии я могу упоминать типы, то есть я могу тут писать, какой тип там ожидается. Могу писать,чтобы подразумевалось, что там у меня будет: А-list N-int (это целое число) Х- int (это целое число Это заголовок моей функции. Документ строка, что делает эта функция?- ```Осуществляет поиск числа Х в массиве А в диапазоне от 0 до N-1 индекса включительно, то есть по N не включительно. Дальше возникает вопрос о том, что она возвращает, если она нашла элемент, что она по-хорошему должна вернуть его местоположение(этаж, индекс) И так, возвращает индекс элемента Х в массиве А. А если там нет такого элемента, что ей возвращать? Ноль- это законный этаж, он первым элементом там находится. -1 вот хорошая мысль возвращать -1. Или -1, если такого нет. Вот я сейчас сформулировал некий договор и пока что оставлю pass Это функция пустышка, это махинатор, который как раз ничего не делает пока что. Я начну им пользоваться в начале, то есть я сейчас напишу маленький тест, который будет эту функцию тестировать, я увижу сразу что тест мой заваливается (не то что я ожидаю на самом деле), но потом я уже реализую, и когда реализую правильно, то мои тесты начнут проходить. Напишу результаты тестирования, но каким же образом? Оформим это: Она ничего не возвращает, она просто напечатает результат. Вот что она будет делать: она создает список(я прям сразу создам список 1 2 3 4 5) Я получаю значение, которое вернет array research Давайте назовем его М. Что я буду искать?-я буду искать в списке Что делаю сейчас: Array research A1 я говорю что там пять элементов, и я буду искать число 8. Давайте вначале проверим действительно негативный случай. Что я теперь говорю: если у меня m равно минус 1, то в этом случае я скажу, что у меня тест один –ok А иначе что я скажу: тест 1 фэйл. Вот я и написал метро тестирование Теперь дальше я второй тест сделаю с А2, поскольку оно будет очень похоже я сделаю copy & paste. Значит второй тест я сделаю массив -1 -2 -3 -4 -5, 5 элементов по-прежнему я буду искать -3. Соответственно у -3 какой должен быть, что был ok?- индекс должен быть 2. Давайте допишем документ строку хотя бы. Что мы напишем: Вот три теста у меня будет ну и соответственно я среди пяти элементов, еще элемент 10 и индекс это 0. Ниже по тексту напишу, что тест aray_search. Запускаем и обнаруживаем, что у нас программа заваливается с ошибкой выполнения. Дело в том, что функция возвращает мне в этом случае специфическую переменную нан нан type, a это специфическое ничего. Значит я сейчас все-таки напишу заместо pass - return-1. Пусть она всегда возвращает и окажется что, возможно некоторые тесты случайно прошли. Но реально функция будет работать, когда пройдут все. Я сделаю следующим образом: я буду перебирать индексы в диапазоне от 0 до N не включительно, если у меня А[k] окажется равным Х, в этом случае я сразу могу выходить, возвращая индекс k. Алгоритм обращения массива Я сейчас напишу примерно также, только быстренько с меньшим количеством комментариев. У нас будет функция, которая будет инвертировать сам массив Обратите внимание, что эта функция должна будет менять массив в самом себе. Значит у меня А предполагает список, N предполагает целое число, значит обращение массива то есть у меня задом наперед. Значит его поворот в рамках индексов от 0 до N-1 Сейчас я буду еще проще чем в прошлый раз тестировать, я не буду создавать отдельный список, я его буду совать ей прям вот в аргумент функции. В общем я туда скопирую несколько этих и дальше я сейчас буду запускать этот тест файл сюда. Значит что у меня получается, если у меня А1 равен 5 4 3 2 1, то ok. Итак, я предполагаю, что после вызова функции invert_array(А, 5) указываю 5 как количество элементов в нем хранящихся. Второй пример: заполню его нулями и сделаю четное количество элементов 10. Мы написали тестирование, запускаем, смотрим результат Собственно, тест 1, тест 2 ничего не разворачивает. Так, а теперь давайте с вами напишем обращение массива. Очевидно, если у меня было два массива, то я могу вместо копирования из A[K] в B[K], я могу копировать в B[K] из А[N-K-1] ,откуда возникает N1,то есть я буду копировать элементы как бы накрест. вот так произойдет зеркальное копирование. Вот таким вот образом: А теперь я пишу туда то, что у меня заготовлено для копирования массива, только в обратном порядке Запускаем: Произошло, что у меня элементы А перетирают элементы А Мне надо менять элементы местами. Для этого я воспользуюсь алгоритмом обмена двух переменных значениями. У нас вот эти 2 элемента надо поменять местами. Как я это сделаю, я говорю Запускаем тест файл в чем проблема ?- в том, что мы в начале меняем 0 с четвертым потом первый. Мне нужно было на серединке остановиться. Для этого мне нужно что N пополам на цело с отбрасыванием остатка чтобы даже двойку с двойкой не менять местами поэтому N пополам с отбрасыванием остатка и не включать в диапазон, но это будет выглядеть очень просто. Но надо сказать, что обмен двух переменных местами в таком виде когда это x y он выглядит нормально. Так, добавление элемента в конец и начало массива мы в принципе сделали. Теперь таких алгоритмов не совсем учебных циклический сдвиг. Решето Эратосфена Циклический сдвиг- эта операция преобразования элементов массива, причем она бывает разной. Циклический сдвиг бывает влево, а бывает вправо. Что делает сдвиг влево: элементы я сейчас их совпадающими собственными индексами заложу 0 1 2 3 4 я беру и сдвигаю их, а нулевой элемент я отправляю к 4 Вот этот ноль мне нужно вначале куда-нибудь выложить во временную переменную, которую я назову tmp, затем поверх него скопирую, а затем я осуществляю следующую операцию. Эти ящики как бы, подтягивая на себя, и шагаю индексом. Копирование происходит из следующего элемента в предыдущий, но само движение грузчика происходит слева направо. Циклический сдвиг вправо должен логично действовать ровно наоборот. копирование будет из предыдущего в следующий, а грузчик двигается справа-налево. То есть циклический сдвиг влево осуществляется при пробегании индексов в прямом порядке, а циклический сдвиг вправо в обратном порядке. Циклический сдвиг влево Массив А уже есть в нем N элементов я перебираю k в диапазоне N минус 1, то есть у меня N минус 1 не достигается, у меня N минус 2 достигается то есть k переберет 0 1 2 3 индексы для данного массива. 4 он не будет, потому что я буду одновременно работать здесь сразу с двумя, а именно ему говорить что A[k] присваиваю значения k + 1 В конце что я делаю в самый последний элемент с индексом N минус 1 я кладу tmp. A[N-1] = tmp Циклический сдвиг вправо В этом случае я выкладываю в переменную tmp последний элемент, затем я пробегаю индексами в диапазоне от N минус 2 до 0 включительно. Значит -1 является с топом и минус один шаг. Я делаю A[k+1 кладу значения A[k] ровно наоборот. Потом положить в А нулевой старое значение n минус 1 которое сохранено во временной переменной. В решете эратосфена не требуется использовать операцию умножения. я возможно успею на В решете эратосфена мы будем хранить по сути ложь и истину. Дальше что я делаю: обратите внимание что в этом случае я присваиваю в элементы, и поэтому я каскадным равенством туда имею полное право запихать 0 falls. Теперь я беру и для каждого значения Значит,если у меня A[k] является правдой,то значит это число простое. Я буду все кратные ему, соответственно пробегу вперед с шагом равным собственно его индексу, и отмечаю у них у всех что они уже не являются простыми. If A[k]: Итак, если он простое число, то я запускаю цикл,в котором я теперь уже вторым индексом М начну бежать в диапазоне, начиная от 2*k А(м)-у нас число составное К вот этому моменту print а будет представлять из себя массив, логических значений где индексом будут соответствовать правда или ложь. Условия и правый операнд значения выражения будет равна либо тому что слева, либо тому что справа в зависимости от того истинно вот это или ложь.