Курс по Python

[Munin]

Потом, наверное, со ссылочными структурами данных надо познакомиться. Какое-нибудь двоичное дерево, вставка, поиск, переборы dfs и bfs.

[kotenok gav]

У двумерных массивов есть одна особенность: нельзя их формировать как [[]*m]*n. Их надо делать как [[]*m for i in range(n)] (это использует три особенности питона, про которые я еще не рассказал) или так:

Используется синтаксис Python

mass=[]
for i in range(n):
    mass.append([]*m)

А в остальном двумерные совпадают с одномерными, за исключением того, что одномерные выглядят как [1,2,3], а двумерные как [[1,2,3],[4,5,6]].

[Munin]

arseniiv в сообщении #1319008 писал(а):

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

Это уже на непонятном мне языке. Считайте, что мои представления о массивах - на уровне паскаля.

[kotenok gav]

Munin в сообщении #1319009 писал(а):

Какое-нибудь двоичное дерево

В стандартной библиотеке питона нет такой структуры, можно сделать тремя вариантами: матрица смежности, списки смежности, класс.

[realeugene]

Munin в сообщении #1318994 писал(а):

Что плохого в этом коде?

1. $F_{10} = 55$, а не 89 https://ru.wikipedia.org/wiki/%D0%A7%D0 ... 1%87%D0%B8 Это - единственная ошибка. Остальное - это как можно улучшить.
2. Вы печатаете весь массив чисел. Так и задумано?
3. Лучше сначала резервировать массив целиком, а потом его заполнять числами. В математических алгоритмах это может дать существенную экономию.
4. Массивы вообще не нужны, если нужно вычислить одно число.
5. Числа Фибоначчи можно вычислять за логарифмическое время. Простое упражнение на использование библиотеки numpy.

[kotenok gav]

realeugene в сообщении #1319015 писал(а):

Это - единственная ошибка.

Так Munin хотел вывести все числа Фибоначчи вплоть до $F(11)$.

-- 11 июн 2018, 23:01 --

Munin в сообщении #1319013 писал(а):

Это уже на непонятном мне языке.

Для меня тоже

[Munin]

kotenok gav в сообщении #1319014 писал(а):

В стандартной библиотеке питона нет такой структуры, можно сделать тремя вариантами: матрица смежности, списки смежности, класс.

Меня интересует ссылочная структура. Видимо, класс; нужно, чтобы его объекты ссылались на его же объекты.

realeugene в сообщении #1319015 писал(а):

3. Лучше сначала резервировать массив целиком, а потом его заполнять числами.

Покажите пример.

А вообще, ведущий в теме - kotenok gav. Я попросил бы остальных знатоков не перебивать его, а только помогать.

realeugene в сообщении #1319015 писал(а):

5. Числа Фибоначи можно вычислять за логарифмическое время.

Вообще за $O(1).$ Но цель-то не вычислить число Фибоначчи. Цель - познакомиться с Python. Я пока не знаю, для чего он хорош, поэтому беру те примеры, которые мне знакомы (и не потребуют большого труда для реализации самих алгоритмов).

За fencepost counting error - спасибо, обсчитался.

[kotenok gav]

Munin в сообщении #1319018 писал(а):

нужно, чтобы его объекты ссылались на его же объекты.

Да, это класс.

Munin в сообщении #1319018 писал(а):

Покажите пример.

Используется синтаксис Python

mass=[0]*3
mass[0]=1
mass[1]=2
mass[2]=3

-- 11 июн 2018, 23:08 --

kotenok gav в сообщении #1319019 писал(а):

Да, это класс.

Точнее, можно сделать классом, чтобы потомки корня тоже были бы обьектами класса.

[realeugene]

Munin в сообщении #1319018 писал(а):

Покажите пример.

def fib(x):
    ar = [1] * x
    for i in range(2, x):
        ar[i] = ar[i-1] + ar[i-2]
    return ar

print(fib(10))

[arseniiv]

(Munin)

Munin в сообщении #1319013 писал(а):

Это уже на непонятном мне языке. Считайте, что мои представления о массивах - на уровне паскаля.

Тут не про массивы, тут про функции и инкапсуляцию. В одной функции f мы можем описать другую g, которая использует переменные, определённые в f, и вернуть её или как-то иначе отправить вовне (присвоить чему-то, куда-то положить). Тогда создаётся замыкание (closure) — используемые переменные f откладываются в некоторую область памяти, которая живёт как минимум столько, сколько живёт выданная ссылка на g, и g обращается к ней, когда использует эти переменные. Эта область может делиться между несколькими функциями, которые были определены рядом. При этом всё, что было определено вне f, никак напрямую обращаться к ней не сможет.

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

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

[kotenok gav]

arseniiv в сообщении #1319025 писал(а):

Кстати, стоит заметить, что кортежи всё-таки не массивы.

Кортежи - это (что-то там). Массивы - [что-то там].

[Munin]

kotenok gav в сообщении #1319010 писал(а):

У двумерных массивов есть одна особенность: нельзя их формировать как [[]*m]*n. Их надо делать как [[]*m for i in range(n)] (это использует три особенности питона, про которые я еще не рассказал) или так:

Используется синтаксис Python

mass=[]
for i in range(n):
    mass.append([]*m)

А в остальном двумерные совпадают с одномерными, за исключением того, что одномерные выглядят как [1,2,3], а двумерные как [[1,2,3],[4,5,6]].

То есть, получается, сделать массив $9\times 9,$ а потом "вырастить" его до $10\times 10$ не получится?

[arseniiv]

А ссылочные структуры можно делать даже весьма просто: для односвязного списка, например, просто брать пары (next, data) (и для конца использовать пустой кортеж ()) — динамическая типизация не запрещает. Обычно такое может быть полезно опять же внутри чего-то, невидимое конечному пользователю (чтобы не испортил целостность данных). Правда, не уверен, что будут какие-то преимущества перед цельными экземплярами специально для этого определённых классов.

Ну и использовать уже имеющиеся.

kotenok gav в сообщении #1319026 писал(а):

Кортежи - это (что-то там). Массивы - [что-то там].

Да, я глупость написал и уже удалил.

[Munin]

arseniiv
(замыкания, мемоизация)
Окей. Я ничего не понял, и по вашим объяснениям самостоятельно не сделаю. Можете привести пример на примере тех же чисел Фи Боначчи?

[arseniiv]

На Python — ну, могу попробовать, но я не помню имён и буду долго ковыряться в документации.

Ещё можно сказать, что не всегда нужен прям массив. Часто можно обойтись, или даже удобнее обойтись (если индексы не целые числа), словарём (dictionary), реализуется оно в современных языках эффективно или некоторым хитрым деревом или хеш-таблицей (не помню чем здесь, но это в первом приближении и не важно).