Реклама i
Стань нашим партнером - зарабатывай с нами!
| Правила | Регистрация | Пользователи | Поиск | Сообщения за день | Все разделы прочитаны |  Справка по форуму | Файлообменник |

Вернуться   Форум DWG.RU > Сообщество > Разное > Размять мозги....

Размять мозги....

Ответ
Поиск в этой теме
 
Непрочитано 21.07.2016, 07:44
#5001
Bull

Конструктор по сути (машиностроитель)
 
Регистрация: 10.10.2005
Набережные Челны (это где КамАЗ)
Сообщений: 11,391


Цитата:
Сообщение от mavik Посмотреть сообщение
Первая Сплин - "Выхода нет".
Да, сегодня с утра уже норм, вспомнил
__________________
Век живи, век учись - ...
Bull вне форума  
 
Непрочитано 01.08.2016, 08:08
#5002
T-Yoke

Артиллерист - вертолётчик. Дипломированный инженер-механик. Technologist
 
Регистрация: 29.11.2004
Где-то около Москвы
Сообщений: 16,516
Отправить сообщение для T-Yoke с помощью Skype™


Явно не моё...
Кроме "Аргентина - Ямайка 5-0", ни одну песню не узнал
__________________
«Артиллерия не токмо грохот, но и наука!» Пётр I
T-Yoke вне форума  
 
Непрочитано 12.02.2017, 11:52
#5003
Дмитррр

НЛО
 
Регистрация: 09.07.2007
Тутошние мы.
Сообщений: 6,078


Год на форум не заходил и все головоломки и головоломы исчезли

Вот практическая задача, которую сейчас думаю, как бы оптимизировать. Чтобы не путать, приведу только графический её смысл - в таком виде задача как раз представляет собой интересную головоломку.
Она из разряда "для программирования", но хотелось бы максимально её упростить.

Дано:
Есть некий график, заданный точками (Х,У) - чёрный на рисунке. Как и полагается уважающему себя графику, у каждого Х есть только один У.

Есть некая горизонтальная прямая (У=константа) - красная на рисунке.

Задача 1 (простая)
Найти площадь (жёлтая на рисунке), которая лежит над черным графиком, но под красной линией.

Задача 2 (сложная)
При заданном графике и при заданной площади найти У, которой соответствует красная линия. То есть решить задачу, обратную первой.

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

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

А можно ли точно решить или хотя бы упростить? Меня всё тенет попробовать как-то интегралы применить... И/или метод Ньютона... Но что-то не могу сообразить, как это всё в коде реализовать.

А ещё меня смущает то, что для одиночной трапеции или треугольника "задача 2" примитивна на уровне 7 класса школы. Может, есть простой способ и для нескольких трапеций и треугольников, объединённых в одну произвольную фигуру?
Миниатюры
Нажмите на изображение для увеличения
Название: Безымянный.png
Просмотров: 276
Размер:	6.5 Кб
ID:	183532  
Дмитррр вне форума  
 
Непрочитано 12.02.2017, 12:03
#5004
s7onoff


 
Сообщений: n/a


А чем плох метод последовательных приближений, кроме того, что это слишком примитивно и ничуть не красиво?)

Был бы график не дискретным, а функцией (собственно, соответствие только одной ординаты каждой абсциссе - это и есть свойство функции) - там с интегралами аналитически все бы в два счета считалось. Хотя интегралов в численных методах не бывает - там все сводится к рядам и циклам точно так же в итоге.
 
 
Непрочитано 12.02.2017, 17:48
#5005
Ильнур

КМ (+КМД), КЖ (КЖФ)
 
Регистрация: 30.05.2007
Далече
Сообщений: 25,086


Зачем так усложнять?
Все можно решить тригонометрически - куски графика ЛИНЕЙНЫ.
Т.е. все свести к площадям прямоугольников и треугольников. А это уже задача 6-го класса приходской школы. Хоть прямая, хоть обратная.
Раз уж Вы задали ломаную, то и надо ломаную рассматривать.
Или Вы условно нарисовали?
Миниатюры
Нажмите на изображение для увеличения
Название: Геометрия.jpg
Просмотров: 31
Размер:	39.4 Кб
ID:	183560  
__________________
Воскресе

Последний раз редактировалось Ильнур, 12.02.2017 в 17:55.
Ильнур вне форума  
 
Непрочитано 12.02.2017, 18:27
#5006
Дмитррр

НЛО
 
Регистрация: 09.07.2007
Тутошние мы.
Сообщений: 6,078


Цитата:
Сообщение от s7onoff Посмотреть сообщение
А чем плох метод последовательных приближений, кроме того, что это слишком примитивно и ничуть не красиво?)
Так это приводит к куче расчётов. Если бы это было нужно посчитать 1 раз, не было бы разницы, потратить 0,00001 секунду или 0,0001 секунду. Но этот блок кода прокручивается фиг_знает_сколько_раз. И весь код считаться может и несколько часов. Вот и стоит вопрос об оптимизации.

Цитата:
Сообщение от Ильнур Посмотреть сообщение
Зачем так усложнять?
Все можно решить тригонометрически - куски графика ЛИНЕЙНЫ.
Т.е. все свести к площадям прямоугольников и треугольников. А это уже задача 6-го класса приходской школы. Хоть прямая, хоть обратная.
Раз уж Вы задали ломаную, то и надо ломаную рассматривать.
Или Вы условно нарисовали?
Возможно не совсем верно сформулировал. График я нарисовал точно, но это лишь пример. График (кол-во и позиции точек) и линия меняются постоянно. И код должен способен переварить любые графики и любые прямые. И как тригонометрически рассчитать? Подскажи алгоритм. Я вот не соображу...
Дмитррр вне форума  
 
Непрочитано 12.02.2017, 18:57
#5007
Fogel

люблю мастерить
 
Регистрация: 21.01.2005
Челябинск
Сообщений: 9,897


Тоесть есть некая таблица со списком точек перегиба графика? В чем же тогда проблема? Считаете площадь трапеции (по высоте средней линии, по существу прямоугольник), считаете площадь отсекаемого треугольника/трапеции (по условию), складываете. Такое Экселю под силу легко. Обратная задача для того же Экселя, только для функции "подогнать" - сделает на раз.
И уж коли мы с Автокадом работаем - ЛИСПом строим фигуру по списку, отсекаем лишнее, свойствами смотрим площадь. Подгонку я тоже делал - условно надо было рассчитывать уровень жидкости в переворачивающемся стакане. В общем на головоломню не сильно тянет.
А вот сейчас попробуем мозги сломать, задача от NetDolphina:
Есть такое классическое упражнение по creative writing: ты должен описать выбранную тобой книгу пятью предложениями. Ровно пять, не больше и не меньше, при этом категорически запрещается раскрывать суть персонажей и сюжетные детали. Мне тут одна девочка выдала истинный шедевр жанра:
Цитата:
Что скрывается за старинным, но не имеющим особой ценности произведением искусства? Какую карьеру выбрать — заучки-ботаника или отчаянного авантюриста, искателя приключений? Что происходит за кулисами местного шоу-бизнеса? Так ли впечатляющи разрекламированные достижения биотехнологий? Тайну, связывающую эти вопросы, хранит древний нечеловеческий разум.
Fogel на форуме  
 
Непрочитано 12.02.2017, 20:33
#5008
Дмитррр

НЛО
 
Регистрация: 09.07.2007
Тутошние мы.
Сообщений: 6,078


Цитата:
Сообщение от Fogel Посмотреть сообщение
И уж коли мы с Автокадом работаем - ЛИСПом строим фигуру по списку, отсекаем лишнее, свойствами смотрим площадь. Подгонку я тоже делал - условно надо было рассчитывать уровень жидкости в переворачивающемся стакане. В общем на головоломню не сильно тянет.
Молодцы, хвалю.
Цитата:
Обратная задача для того же Экселя, только для функции "подогнать" - сделает на раз.
Я так и не понял, есть алгоритм или формула для точного решения в общем случае или нет?
Дмитррр вне форума  
 
Непрочитано 12.02.2017, 20:44
#5009
s7onoff


 
Сообщений: n/a


Ильнур, есть ведь общий случай. И площади трапеций/треугольников - вещь непостоянная - при положении линии полностью над куском графика зависимость между её положением и площадью под ней одна. Как только она опускается до треугольника - зависимость уже другая.

Всё это легко в отдельном случае и для конкретного графика, в общем случае зависимость Положение_Красной_Линии(площадь под ней) весьма заковыристая штука.
 
 
Непрочитано 12.02.2017, 21:37
#5010
Fogel

люблю мастерить
 
Регистрация: 21.01.2005
Челябинск
Сообщений: 9,897


в общем случае всё решаемо, просто надо решить на какой платформе это осуществлять. ИМХО ничего сложного тут нет
Fogel на форуме  
 
Непрочитано 13.02.2017, 05:57
#5011
Ильнур

КМ (+КМД), КЖ (КЖФ)
 
Регистрация: 30.05.2007
Далече
Сообщений: 25,086


Цитата:
Сообщение от s7onoff Посмотреть сообщение
Ильнур, есть ведь общий случай. И площади трапеций/треугольников - вещь непостоянная - при положении линии полностью над куском графика зависимость между её положением и площадью под ней одна. Как только она опускается до треугольника - зависимость уже другая. ...
Да не общий это случай - треугольник он и в Африке треугольник. Общий случай - это когда куски кривые. Вот тогда НЕОБХОДИМО притягивать высший матаппарат.
А тут, повторюсь, тривиальная задачка, арифметического уровня.
Исходная формула: S=0,5*a*b.
Далее - суммирование.
Дмитррр, твоя задача банальна, и решение получается путем рутинного суммирования.
Как тут один говорил, удочку дали, а уж рыбу сам...
__________________
Воскресе
Ильнур вне форума  
 
Непрочитано 13.02.2017, 10:35
#5012
KronSerg

Вода - моя работа
 
Регистрация: 10.11.2009
Санкт-Петербург
Сообщений: 3,639


Я ещё студентом писал программу, которая считала площадь под графиком разбивая её на прямоугольники минимальной ширины и складывая их площади, работала быстро и точно, кстати. Всё, что просил Дмитррр сделала бы легко.
__________________
Нерешаемых проблем не бывает.
KronSerg вне форума  
 
Непрочитано 13.02.2017, 11:04
#5013
s7onoff


 
Сообщений: n/a


Цитата:
Сообщение от Ильнур Посмотреть сообщение
Общий случай - это когда куски кривые. Вот тогда НЕОБХОДИМО притягивать высший матаппарат
там всё то же, только есть элемент интегрирования вместо перемножения.

Цитата:
Сообщение от Ильнур Посмотреть сообщение
А тут, повторюсь, тривиальная задачка, арифметического уровня.
Исходная формула: S=0,5*a*b.
Далее - суммирование.
Лови кусочную функцию:


Дай мне формулу нахождения такого y, при котором площадь под ним на отрезке [0;4] = S.

----- добавлено через ~2 мин. -----
Цитата:
Сообщение от KronSerg Посмотреть сообщение
Я ещё студентом писал программу, которая считала площадь под графиком разбивая её на прямоугольники минимальной ширины и складывая их площади, работала быстро и точно, кстати. Всё, что просил Дмитррр сделала бы легко.
прямая задача суперэлементарна. Решения обратной никто не дал, но все говорят "легко".

Решение обратной через прямую - это и есть метод последовательного приближения. Задаемся случайным y, вычисляем площадь, если слишком много - смотрим площадь от y/2 и т.д. НО:
Цитата:
Сообщение от s7onoff Посмотреть сообщение
А чем плох метод последовательных приближений, кроме того, что это слишком примитивно и ничуть не красиво?)
Цитата:
Сообщение от Дмитррр Посмотреть сообщение
Так это приводит к куче расчётов. Если бы это было нужно посчитать 1 раз, не было бы разницы, потратить 0,00001 секунду или 0,0001 секунду. Но этот блок кода прокручивается фиг_знает_сколько_раз. И весь код считаться может и несколько часов. Вот и стоит вопрос об оптимизации.
 
 
Непрочитано 13.02.2017, 11:22
#5014
Дмитррр

НЛО
 
Регистрация: 09.07.2007
Тутошние мы.
Сообщений: 6,078


Цитата:
Сообщение от s7onoff Посмотреть сообщение
Ильнур, есть ведь общий случай. И площади трапеций/треугольников - вещь непостоянная - при положении линии полностью над куском графика зависимость между её положением и площадью под ней одна. Как только она опускается до треугольника - зависимость уже другая.

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

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


Цитата:
Сообщение от Fogel Посмотреть сообщение
в общем случае всё решаемо, просто надо решить на какой платформе это осуществлять. ИМХО ничего сложного тут нет
На любой. К примеру Дельфи.

Цитата:
Сообщение от Ильнур Посмотреть сообщение
Дмитррр, твоя задача банальна, и решение получается путем рутинного суммирования.
Да? И вторая тоже? Как?
Цитата:
Сообщение от KronSerg Посмотреть сообщение
Я ещё студентом писал программу, которая считала площадь под графиком разбивая её на прямоугольники минимальной ширины и складывая их площади, работала быстро и точно, кстати. Всё, что просил Дмитррр сделала бы легко.
Молодец, что писал. Подскажи, как получить точное решение второй задачи.
Дмитррр вне форума  
 
Непрочитано 13.02.2017, 11:44
#5015
KronSerg

Вода - моя работа
 
Регистрация: 10.11.2009
Санкт-Петербург
Сообщений: 3,639


В общем случае, не зная заранее закономерностей, обратная задача решается только методом последовательных приближений, но раз у тебя функция с известными экстремумами и линейными участками, то можно заставить программу пробежаться по экстремумам, найти два, между которыми лежит искомая площадь, ответ обратной задачи вычислить линейным уравнением.
__________________
Нерешаемых проблем не бывает.
KronSerg вне форума  
 
Непрочитано 13.02.2017, 11:52
#5016
s7onoff


 
Сообщений: n/a


Цитата:
Сообщение от KronSerg Посмотреть сообщение
раз у тебя функция с известными экстремумами и линейными участками, то можно заставить программу пробежаться по экстремумам, найти два, между которыми лежит искомая площадь
кто сказал, что она будет лежать между ними? Линия может быть сильно выше графика.
 
 
Непрочитано 13.02.2017, 11:54
#5017
Дмитррр

НЛО
 
Регистрация: 09.07.2007
Тутошние мы.
Сообщений: 6,078


Цитата:
Сообщение от KronSerg Посмотреть сообщение
В общем случае, не зная заранее закономерностей, обратная задача решается только методом последовательных приближений, но раз у тебя функция с известными экстремумами и линейными участками, то можно заставить программу пробежаться по экстремумам, найти два, между которыми лежит искомая площадь, ответ обратной задачи вычислить линейным уравнением.
Вот тоже пришёл к такому выводу. Придётся расставить по порядку все У графика (это дась опять же кусочную функцию площади от высоты линии), найти нужный отрезок и попробовать выразить из него линейную зависимость (а скорее, просто интерполировать между нужными экстремумами).
Код не малый получится, но считать должно быстрее, чем последовательными приближениями. А главное, точно.
Дмитррр вне форума  
 
Непрочитано 13.02.2017, 12:16
#5018
KronSerg

Вода - моя работа
 
Регистрация: 10.11.2009
Санкт-Петербург
Сообщений: 3,639


Цитата:
Сообщение от s7onoff Посмотреть сообщение
кто сказал, что она будет лежать между ними? Линия может быть сильно выше графика.
Можно и такой частный случай предусмотреть, добавить прямоугольник сверху не сложно.
Цитата:
Сообщение от Дмитррр Посмотреть сообщение
Придётся расставить по порядку все У графика (это дась опять же кусочную функцию площади от высоты линии), найти нужный отрезок и попробовать выразить из него линейную зависимость (а скорее, просто интерполировать между нужными экстремумами).
Код не малый получится, но считать должно быстрее, чем последовательными приближениями. А главное, точно.
Да, должно получиться, максимальное количество подсчётов площади будет равно половине количества экстремумов. Результат интерполяции можно смело считать точным ответом, т.к. сумма линейных функций это линейная функция.
__________________
Нерешаемых проблем не бывает.
KronSerg вне форума  
 
Непрочитано 13.02.2017, 12:36
#5019
Дмитррр

НЛО
 
Регистрация: 09.07.2007
Тутошние мы.
Сообщений: 6,078


Цитата:
Сообщение от KronSerg Посмотреть сообщение
максимальное количество подсчётов площади будет равно половине количества экстремумов
Почему? Если каждая точка начального графика будет иметь уникальный игрек, то отрезков получится N-1/
Дмитррр вне форума  
 
Непрочитано 13.02.2017, 12:38
#5020
KronSerg

Вода - моя работа
 
Регистрация: 10.11.2009
Санкт-Петербург
Сообщений: 3,639


Так сортируешь же экстремумы по игреку, считаешь первый и центральный, откидываешь ненужную половину и т.д.
__________________
Нерешаемых проблем не бывает.
KronSerg вне форума  
Ответ
Вернуться   Форум DWG.RU > Сообщество > Разное > Размять мозги....

Размещение рекламы
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск