Задачка для тренировки

[Phlya]

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

А про засунуть переменную - вы же там передаете строку в аргументе, когда создаете матрицу! Конечно питон туда не подставит переменную - откуда он знает, что Вы там имеете в виду? Но если Вы почитаете про string formatting, то, скорее всего, сможете ршеить эту проблему. Ну, а при создании array'а вы пишете это не в виде строки, а в виде списка, где один из элементов - переменная. Так что тут NumPy ни при чем =)

[obgorelyi]

То есть ты мне предлагаешь использовать при объявлении матрицы str(<имя_переменной>). Еще один костыль в копилку .

По поводу, СЛАУ. Сложную систему (8x8) я решал тем же методом, что и простую систему уравнений(2x2) (можешь сам убедиться). Простую систему уравнений решил правильно, сложную нет (кстати, я такую чачу и у других библиотек встречал , например для языка С++), поэтому я предпочитаю специализированный софт, для научных вычислений).

Что касается преобразования, вектор-столбца в вектор-столбец, то как я понял, строка находится в (), могли бы тогда использовать другие символы для того, чтобы строку от значения отделить.

Говоря проще, мне не понравилось, что для работы с NumPy нужно использовать туеву хучу костылей.

И кстати, откуда инфа, что кто-то использует это в научных вычислениях (наверно гуглить разучился, я лишь нашел обзор Nasa, но там о точности вычислений ни слова, только на время засекают, видать их точность не особо волнует)?

Кстати Gap, вообще медным тазом накрылся, при попытке инвертировать матрицу 8x8 (ту же самую). Хотя по сути над ним работали несколько европейских вузов.

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

[Phlya]

Это не костыль, а следование правилам Питона.
Кстати, а слабо по-другому эту матрицу описать и все? Пример из документации:

Код: [Выделить]

>>> np.matrix([[1, 2], [3, 4]])
matrix([[1, 2],
        [3, 4]])
Чуть дольше может быть, я понимаю, но можно просто подставить переменную.

Насчет применения, попробуйте поискать не по NumPy, а по SciPy, которая, используя первый, дает кучу возможностей именно научного приложения. То что их используют, я знаю точно.



Пользователь решил продолжить мысль 14 Июня 2013, 12:36:52:http://mail.scipy.org/pipermail/scipy-user/2007-October/014023.html - почитайте тему, там есть несколько ссылок.

[obgorelyi]

Прошу прощения, пересмотрел результаты Octave она ошиблась в 4-х значениях из 8-ми (тоже плохо).

В тех поддержке написали, что матрица вырожденная, и нужно использовать псевдоинвертирование, возникает вопрос, а почему решатель это не проверяет сам (вырожденная матрица или нет)?
С учетом этого, результат полностью соответствует результату Octave (тоже 4 ошибки из 8-ми).

Вот код (виноват не на той странице смотрел способы объявления матриц до этого, зря бухтел , просто первое мнение было отрицательным исключительно из-за ввода матриц, посмотрев листинг поймете):

Код: [Выделить]

from numpy import *

# Мне лично не нравится матрица в одну строку :)
A = matrix([[  1,   2,   3,   4,   5,   6,   7,   8], [  8,   3,   5,   6,   9,  13,  19,  47], [ 10,  20,  30,  40,  50,  60,  70,  80], [ 11,  12,  13,  14,  15,  16,  17,  18], [ 21,  22,  23,  24,  25,  26,  27,  28], [ 31,  32,  43,  54,  65,  26,  47,  68], [ 11, 223,  43,  54,  65,  36,  87,  28], [ 31,  52,  73,   4,  95,  66,  47,  38]])
print("A\n"+str(A))

F = matrix([[12], [13], [24], [56], [68], [36], [96], [45]])
print("F\n"+str(F))

A1 = linalg.pinv(A)

X = A1*F
print("X\n"+str(X))

res = A*X

print("res\n"+str(res))
Вот вывод в консоли:

Код: [Выделить]

A
[[  1   2   3   4   5   6   7   8]
 [  8   3   5   6   9  13  19  47]
 [ 10  20  30  40  50  60  70  80]
 [ 11  12  13  14  15  16  17  18]
 [ 21  22  23  24  25  26  27  28]
 [ 31  32  43  54  65  26  47  68]
 [ 11 223  43  54  65  36  87  28]
 [ 31  52  73   4  95  66  47  38]]
F
[[12]
 [13]
 [24]
 [56]
 [68]
 [36]
 [96]
 [45]]
X
[[ 3.17254065]
 [ 0.52286728]
 [ 0.54926688]
 [ 0.57066366]
 [-2.15843936]
 [ 1.59872139]
 [-0.19017315]
 [-0.38007186]]
res
[[  2.5770751 ]
 [ 13.        ]
 [ 25.77075099]
 [ 39.43083004]
 [ 76.28458498]
 [ 36.        ]
 [ 96.        ]
 [ 45.        ]]
Правда увы результат все равно не идеал .

Честно даже смешно, как то. Как из всех возможных матриц, я набрал матрицу у которой детерминант равен 0 (вырожденная матрица). Вот вечно мне так не везет .

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

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

[rootv]

Есть одна задачка, вроде бы и легкая, но меня она постоянно заставляет задуматься.

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

Чем интересна задачка для меня - много ассоциаций, много уровней.
По ассоциациям -
напоминает "радар"(луч бегает по кругу) или стрелковую мишень (с кольцами). Но и там и там могут быть "неровности". Что тогда?
Камень брошенный на чистую воду дает правильные круги... а если это система каналов (или лабиринт)? Как будет распространяться волна?
А если камень бросить не в центр?

По уровням -
Похоже есть 3 направления решения:
1. Математический - вычисление любого элемента матрицы по формуле.
Плюсы: Нет необходимости рассчитывать всю матрицу. Нет необходимости изобретать сложный алгоритм.
Спорно: Вопрос преимущества в скорости при необходимости расчета всей матрицы остается спорным.
Минусы: Сама формула может быть достаточно сложной. Необходимость модификации формулы при введении дополнительных условий (например, "островов"). В некоторых случаях (реальных) формула вообще может не существовать.

2. Алгоритмический - создание алгоритма последовательного обхода, соответствующего условию задачи.
Плюсы: Можно не знать математики. Работает "на любой местности".
Спорно: При "легком" алгоритме может быть быстрее математического варианта (если нужно заполнить всю матрицу)
Минусы: нельзя сразу вычислить значение нужного элемента.

3. Комбинированный - по формуле вычисляются отдельные элементы, а остальные заполняются по алгоритму (так, наверное, проще с математикой и логикой алгоритма будет)

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

3. Матрица разбивается диагоналями на 4 сектора. Определяется значение на диагоналях (достаточно очевидная мат.формула). Остальное "интерполируется".

2. Матрица заполняется нулями (признак ненумерованности ячейки). Задается начальная точка (х,у) и ее значение "1". Задается первоначальные шаги (step_x, step_y) - это не для циклов, диапазон - [-1,0,+1]. Задается направление движения.
Дальше пишем маленькую функцию изменения значений шагов (step_x, step_y) в зависимости от направления "вращения" и "заполненности" правого(или левого) кандидата  для определения индексов следующей ячейки.

Запускаем цикл нумерации из первоначальной точки, внутри которого определяем индексы следующей ячейки...

(можно модифицировать для любой начальной точки, любого направления и любой матрицы, даже криволинейной)

Может чего забыл в какую-то "ячейку" вписать - уточняйте.

Еще возникает ассоциация с "физиками"(математиками) и "лириками"(алгоритмиками).
По традиции "физикам" кажется их позиция важнее.
Кстати, тут есть и параллель с мужским и женским отношением к жизни, детям, друг к другу...

[obgorelyi]

Есть одна задачка, вроде бы и легкая, но меня она постоянно заставляет задуматься.

Сообщение дилетанта (кроме первой части первого поста не понял ничего).

Я и не отрицал, что я дилетант .

Чем интересна задачка для меня - много ассоциаций, много уровней.
По ассоциациям -
напоминает "радар"(луч бегает по кругу) или стрелковую мишень (с кольцами). Но и там и там могут быть "неровности". Что тогда?
Камень брошенный на чистую воду дает правильные круги... а если это система каналов (или лабиринт)? Как будет распространяться волна?
А если камень бросить не в центр?

Здесь не совсем круги, круги выделял я, ибо мне так проще. С ровными кругами гораздо проще, чем со спиралью (которая в исходной задаче, что математически, что алгоритмически, что комбинаторно, как вы написали).

Кстати, по поводу исходной задачи, решения два я привел, а математическое ArcFi привел. Математическое решение сам пока не рассматривал, по той причине, что для этого метода придется, взять листок бумаги и ручку и расписать все, ибо без этого я не пойму (в баше я не силен, поэтому не все операции мне понятны в программе ArcFi, да и меня интересовало изначально минимальное количество циклов) .

P.S. Спасибо за новые задачки (правда их я уже скорее с графикой делать буду):
Конкретно, я говорю:
Задачка про радар (это можно будет сделать, как элемент игры).
Задачка про волны (вы тут еще не добавили интерференцию от двух источников). По поводу лабиринта, то там у каждой точки (если рассматривать все дискретно) образуется новый источник волн и еще нужно учесть, что волны в реальном мире затухающие, без затухания (сил сопротивления), земля постоянно бы тряслась, а на море был бы вечный шторм .

[rootv]

Есть одна задачка, вроде бы и легкая, но меня она постоянно заставляет задуматься.

Сообщение дилетанта (кроме первой части первого поста не понял ничего).

Я и не отрицал, что я дилетант .

Да нет - это я дилетант!
(Вот даже Ubuntu пока не могу установить)
Когда-то в 80-х еще была интересная для меня в то время задачка - расчет разгона ветровых волн (высоты и направления) на реальном закрытом водоеме.
Основной трудно учитываемый фактор - рельеф дна. На глубине - почти не влияет, да и рельеф обычно на глубине достаточно монотонно меняется. А на подходе к берегу начинается карусель... Матрица данных по глубинам была главной проблемой. Должна покрывать большую площадь, но детальность нужна очень высокая только в 5% площади... А памяти тогда практически не было... Как создать такую матрицу?  Наверное, есть и такие инструменты... но интереснее изобрести велосипед...

[Jack Sparrow]

Да, тут дилетанты для дилетантов пишут. Вот, например, доработал немного свой класс:

(Нажмите, чтобы показать/скрыть)

Код: (Python) [Выделить]

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 2D Матрица, эмуляция двухразмерного массива

class Matrix:
    """2D матрица."""
   
    def __init__(self, x = 3, y = 3, default = ''):
        # Параметры x и y задают размер матрицы по умолчанию
        self._matrix = [[default for row in range(x)] for col in range(y)]
   
    def __str__(self):
        """Выводит содержание матрицы в строковом виде.
           Начало координат - в левом нижнем углу."""
        res = []
        # Цикл меняет порядок элементов списка на обратный. Это позволяет получить
        # начало координат в левом нижнем углу (без этого было в левом верхнем).
        i = len(self._matrix) - 1
        while i >= 0:
            res.append(str(self._matrix[i]))
            i -= 1
       
        # Возвращаем результат, удаляя квадратные скобки
        return '\n'.join(res).replace('[','').replace(']','')
   
    def get(self, x, y):
        # Получить значение ячейки
        return self._matrix[y][x]
   
    def set(self, x, y, value):
        # Установить значение ячейки (row, col)
        self._matrix[y][x] = value


class Snake(Matrix):
    """Реализация класса Matrix для того, чтобы вывести числовую "змейку"."""
   
    def __init__(self, x=3, y=3, default=0):
        # Параметры x и y задают размеры матрицы по умолчанию.
        # Если x не равен y, или x и y - четные числа, выводится сообщение об ошибке.
        if x != y or x % 2 == 0 or y % 2 == 0:
            raise ValueError ('x и y должны быть нечетными числами и равными друг другу')
        else:
            self._matrix = [[default for row in range(x)] for col in range(y)]


Класс Matrix это просто матрица с методами set и get. А класс Snake наследуется от Matrix. Я хочу его приспособить для рисования змейки, а там, возможно, будут методы, которые не совсем нужны где-то еще. Поэтому чтобы не перегружать Matrix, лучше, думаю, все спецметоды переместить в Snake.
Например, в Snake проверяется, имеет ли матрица правильный размер (т.е. квадрат из нечетных чисел).

Код: (Python) [Выделить]

t = Snake(6,7,0)выдаст ошибку. А с классом Matrix такого не произойдет. В Snake можно добавить атрибут для отслеживания текущей ячейки, а также методы типа left, up, right и down для передвижения и увеличения текущего числа. Подразумевается, что тут идем не методом математических формул, а больше алгоритмически.

[rootv]

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

Изначально заполняем таблицу нулями.
Задаем начальные дельты для изменения текущих индексов (например d_x=0, d_y=-1).
Каждая дельта должна будет "вращаться" по кругу, например: 1,0,-1,0,1,0,-1,0,1..., короче, sin()

Дальше делаем один цикл от 25 до 1.
Присвоив очередное значение ячейке, изменяем индексы.
Если по новым индексам ячейка существует и значение ==0, уходим на новый виток цикла, если нет - возвращаем индексы, изменяем d_x и d_y в направлении вращения, снова изменяем индексы и уходим на новый виток цикла.

Вот и все.
(но это слишком уж частный случай, лучше делать алгоритм из центра или из любой точки для любой неправильной матрицы, чтобы змейка огибала любые "неровности" в матрице.
Механизм тот же, но изменение индексов всегда должно стремиться загнуть змейку - если такое направление невозможно - откат индексов и откат дельт для индексов...
Но должна быть еще и проверка "откатившегося" направления - если оно закрыто, то и здесь откат индексов и откат дельт для индексов... Если после проверки 3 направлений движения опять получаем откат, то - тупик...
Здесь два варианта - конец задачи или возврат до последней точки, имеющей открытое направление)

Ну, вроде обхода лабиринта.
Это была первая моя программка на Си. Таким способом думал найти кратчайший маршрут. Оказалось все проще...

[Phlya]

Да, я тоже придумал про рисование снаружи внутрь, что это должно оказаться проще =)

[obgorelyi]

to Jack Sparrow: мне почему-то кажется, что ваш класс Matrix скоро выльется в аналог NumPy, а то и вообще аналог Matlab.
to rootv: Я вообще под Fedora 18 сижу. Решил просто попробовать вот и осел (тут слово осел, а не осёл ) . Кстати, расскажите подробнее про вашу задачку в 80-х, насколько я знаю механика жидкостей, это вообще дело темное, так как приходится иметь дело с тензорной алгеброй. И также про обход лабиринта я не совсем понял, если рассматривать процесс поиска выхода со стороны человека, то тут только методом проверки направлений (если сам внутри лабиринта. Тут уж поверьте, один раз оказался на лесной развилке с 4-мя вариантами пути. Повезло выбрать правильный , иначе бы замерз, дело зимой было. )
Интересно насколько проще все оказалось, можете поведать? Может этот же метод и в обычной жизни (если потерялся) применим.

Еще кстати, раз уж тут другие задачки пошли, стояла передо мной где-то год назад, задача построения внутреннего и внешнего контуров:
известны координаты замкнутого контура, нужно обойти этот контур снаружи и изнутри на некотором расстоянии. (Расстояние задается пользователем). Все кривые контура интерполируются прямыми. (так проще).
Я эту задачу решал с помощью биссектрис. То есть брал 3 точки, строил угол, находил биссектрису, и строил прямые параллельные, прямым контура. Далее о том, что прямые принадлежат одному контуру, узнавал по точке пересечения с биссектрисой.
И сейчас описывая, это я понял, как я могу улучшить алгоритм, ибо дальше я снова запускал перебор координат внутреннего и наружного контура искал максимумы и минимумы по координатам X,Y (поиск максимумов и минимумов нужно засунуть в построение контуров).
Также нужно учесть, что внутренний контур не должен пересекаться с внешним. Например если контур похож на тень песочных часов, то в районе горлышка высока вероятность нарушения этого ограничения, в таких случаях должна выдаваться ошибка.

[rootv]

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

Руководитель дал формулу для изменений движения волны (развитие, угасание, изменение направления). Надо было построить модель. Для модели нужна была специфическая сетка с переменной "плотностью" исходных данных (на перегибах профиля дна шаг сетки должен быть чаще). Шаг расчетов - постоянный.
От сетки-матрицы пришлось отказаться и идти по пути либо задания изобат глубин, либо задания отдельных профилей (это более экономно), что обеспечивало бы минимальный объем памяти для исходных данных. Для получения значений в любой точке(х,у) между узлов нужен был очень быстрый алгоритм, способный понять, к каким узлам относится точка(х,у) и правильно проинтерполировать.
Как решил - уже не помню, но ситауция казалось бы распространенная... наверное, есть готовые решения (по крайней мере сейчас)?

Но там же возникала еще одна интересная задачка.
Сокурснице для диплома надо было просто изобрести что-то новое в интерполяции...
Почесал затылок и "изобрел" механизм, схожий с поведением пленки мыльного пузыря - форму поверхности определяют силы поверхностного натяжения (силы между соседними точками пленки) и объем внутри.
(В конце обозвал "потенциальным" исчислением по аналогии с диф.исчислением)

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

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

про обход лабиринта я не совсем понял, если рассматривать процесс поиска выхода со стороны человека, то тут только методом проверки направлений (если сам внутри лабиринта. Тут уж поверьте, один раз оказался на лесной развилке с 4-мя вариантами пути. Повезло выбрать правильный , иначе бы замерз, дело зимой было. )
Интересно насколько проще все оказалось, можете поведать? Может этот же метод и в обычной жизни (если потерялся) применим.

Если "со стороны человека", то да - остается перебор... Но человек все же сумеет кое-что соптимизировать... Программа таким способом будет считать годы.
Метод поиска кратчайшего маршрута тот же (я так полагаю), что и алгоритм поиска кратчайшего пути к нужному документу в сети. (для человека в лесу он не годится - иначе ему придется рассыпаться на части). Напоминает круги от брошенного в воду камня. Движение идет одновременно во всех направлениях. Кроме основного решения алгоритм дает еще один очень ценный эффект.
Больше сказать не могу - на этом сейчас пытаюсь построить уникальный в своем роде транспортный сервис.

стояла передо мной где-то год назад, задача построения внутреннего и внешнего контуров

А где-бы это могло применяться? Дизайн?

[obgorelyi]

стояла передо мной где-то год назад, задача построения внутреннего и внешнего контуров

А где-бы это могло применяться? Дизайн?

Станки с Числовым Программным Управлением (ЧПУ). Это нужно для учета формы инструмента (увы, но фрезы и резцы, тоже занимают место ).

[rootv]

Это нужно для учета формы инструмента (увы, но фрезы и резцы, тоже занимают место ).

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

А так метод вроде нормальный.

(Была мысль смоделировать "интерференцию", когда точки исходной кривой будут излучателями... но все опять свелось к биссектрисам)

[obgorelyi]

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

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

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