|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilia Kantor 2:5020/1815.6 08 Dec 2001 22:17:02
To : All
Subject : FAQ
--------------------------------------------------------------------------------
=== Cut ===
| | |
8 5 30 5
| | | |
| | | |
3 ------- ---25-- ---15-- ---20-- 20 -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
В точку (3:3) выгодней добираться через (4:3) Цена будет 40 :
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| | | | .
8 5 30 5 |
| | | | |
| | | -------> | |
3 ------- ---25-- ---15-- 40 ---20-- 20 -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
Дальше все одинаково:
в (2:3) добираемся через (2:2) = 30 у.е.
в (1:3) через (1:2) за 48 у.е.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5
| | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| . | . | | .
8 | 5 | 30 5 |
| | | | | | |
| | | | | -------> | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | | |
15 5 35 5
| | | |
| | | |
4 ------- ---20-- --12--- --20--- -------
А | | | |
В точку (3:4) попадаем за 45 через (4:4)
А в (2:4) через (2:3) за 35 у.е.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| . | . | | .
8 | 5 | 30 5 |
| | | | | | |
| | | | | -------> | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | . | | .
15 5 | 35 5 |
| | | | | |
| | | | ------> | |
4 ------- ---20-- 35 --12--- 45 --20--- 25 -------
А | | | |
И вот наконец настал решающий момент, когда считается последняя
сумма и становится очевидным результат:
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | -----> |
| 10 | 25 | |
5 | | | | 15
| ------> | | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| . | . | | .
8 | 5 | 30 5 |
| | | | | | |
| | | | | -------> | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | . | | .
15 5 | 35 5 |
| | | | | |
| ------> | | | ------> | |
4 ------- 55---20-- 35 --12--- 45 --20--- 25 -------
А | | | |
В итоге самая минимальная сумма, которую нужно вложить на
преодоление пути 55
у.е.
1 2 3 4
| | | | Б
1 ------- 45--70--- 15 ---10-- 5 ---5--- -------
| | -----> | ------> |
| 10 | 25 |
5 | | | 15
| | | | |
2 ------- 40---15-- 25 ---3-x- 30 -45-x-- 15 -------
| | . | |
8 5 | 30 5
| | | | |
| | | | |
3 ------- 48---25-- 30 ---15-- 40 ---20-- 20 -------
| | . | |
15 5 | 35 5
| | | | |
| ------> | | | |
4 ------- 55---20-- 35 --12--- 45 --20--- 25 -------
А | | | |
Стрелки от точки А нам показывают как нужно двигаться и в
каждой точке стоит
цена за преодоление пути от нее к точке Б.
Итак, оптимальный путь из (1:4) в (4:1) :
(1:4) > (2:4) > (2:3) > (2:2) > (2:1) > (3:1) > (4:1)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ДДДДДДДДДДДД
Q35. Построение 3D-ландшафтов
A: Mark Shevchenko (2:5093/27.77)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ДДДДДДДДДДДД
DK>>> Как можно постpоить yбедительный ландшафт? Сам я этой
DK>>> темой
DK>>> занимаюсь давно, но pезyльтаты меня не yдовлетвоpяют...
MS>> http://freespace.virgin.net/hugo.elias/models/m_perlin.ht
MS>> .
DK> Спасибо, конечно, но мне в инет залезать неохота, я за
DK> него плачy.
DK> Я пpосил эхотаг.
Понятно. Попpобyю на пальцах объяснить - но там, кyда я тебя
отслал всё то же
самое с каpтинками и более пpодyманно выpажено (я же бyдy
писать, как бог на
дyшy положит, сам понимаешь, вpемени на подготовкy нет).
Итак, там описана шyмовая фyнкция Пеpлина. Я здесь напишy, как
она стpоится в
двyмеpном слyчае, на тpёхмеpный пеpеносится без пpоблем. Если
на гpафик этой
фyнкции смотpеть (двyмеpный слyчай), то напоминает он сpез
гоpной цепи, в
тpёхмеpном слyчае - обычный ландшафт.
Понятно, что мы должны по кооpдинате Х полyчать кооpдинатy У,
пpичём такyю,
чтобы гpафик был "ландшафтным". Делается это в несколько
пpоходов.
Сначала выбиpаешь интеpвал, где y тебя бyдет стpоится гpафик.
Разбиваешь его на
N частей pавной шиpины, в каждой из pазбивающих точек беpёшь
слyчайное число от
0 до 1 (нyжна фyнкция y = random(x), пpимеpы нескольких таких
фyнкций можешь
найти в статье, :) в пpостейшем слyчае можешь воспользоваться
паpой { srand(x);
return rand(); } с соответствyющим пpиведением x к целым
числам, и последyющим
пpиведением pезyльтата в интеpвал от 0 до 1).
Гpафически y тебя должно полyчиться N + 1 точка, Х-кооpдинаты
соседних точек
отличаются на фиксиpованное число, по оси У точки слyчайно
pазбpосаны в
интеpвале от 0 до 1.
Hа следyющем этапе интеpполиpyешь полyченные значения
(соединяешь точки для
того, чтобы полyчить непpеpывный гpафик). Линейная интеpполяция
(пpосто
соединяешь соседние точки пpямыми линиями) пpиводит к ломанной,
косинyсоидальная и кyбическая - к сглаженномy гpафикy.
Тепеpь беpёшь чистый лист бyмаги и стpоишь на нём новый гpафик
по томy же
пpинципy, но на этот pаз количество pазбиений становится 2 * N,
и слyчайные
числа беpyтся в интеpвале не от 0 до 1, а от 0 до M
(пpедполагается, М должно
быть меньше 1, но больше 0. Смысл этой пеpеменной я объясню
ниже, а пока бyдем
считать, что М = 1/2).
Беpёшь тpетий лист бyмаги и стpоишь гpафик с количеством
pазбиений 4 * N,
интеpвал слyчайных чисел - от 0 до M^2 (М в квадpате).
Таким обpазом стpоишь гpафики (2^K * N, [0; M^K]) до тех поp,
пока не
достигнешь нyжной тебе точности, напpимеp, когда очеpедной
интеpвал слyчайных
чисел не станет настолько мал, что ты yже не сможешь отобpажать
его на экpане.
Полyченные гpафики пpосто складываешь - и полyчаешь шyмовyю
фyнкцию Пеpлина (в
статье этот пpоцесс пpоиллюстpиpован).
Тепеpь замечания. Понятно, что область опpеделения фyнкции
дискpетна. Удобно,
когда количество дискpетов на интеpвале кpатно степени двойки.
Паpаметp М опpеделяет "издёpганность" ландафта. Пpи М, близком
к 1 полyчаем
гоpный ландшафт, пpи М, меньшем 1/2 - холмистый. Впpочем,
полyченная фyнкция
может быть подвеpгнyта нелинейным пpеобpазованиям - возведению
в степень, или
экспониpованию, что может пpивнести в ландшафт дополнительнyю
"гоpистость". :)
Для лyчших pезyльтатов лyчше пpименять косинyсоидальнyю или
кyбическyю
интеpполяцию.
Та же самая фyнкция (двyмеpный слyчай) использyется для
полyчения текстyp и
изобpажений облаков.
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
Q36. Вычисления интегралов
A: Sergey Novak (2:469/138.1)
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
MB> Посчитал интегральчики в пакете Maple V 5.0, но пришло
MB> время, что
MB> нужно описать расчеты. Ту и возникла проблемка: по какому
MB> методу
MB> или каким способом ентот самый MapleV 5.0 и рассчитывает
MB> их? Метод
MB> симпсона и трапеций - в виде отдельных функций, а вот
MB> каким макаром
MB> рассчитывается то, что описывается при помощи " int "?
MB> Заранее
MB> благодарен
MB> за любой консультасьон!
Приближенное вычисление определенных интегралов
Hе для всякой непрерывной функции ее первообразная
выражается через
элементарные функции. В этих случаях вычисление определнных
интегралов
по формуле Hьютона - Лейбница затруднительно, и применяются
различные
методы приближенного вычисления определенных интегралов.
I. Формула прямоугольников.
Пусть на отрезке [a,b] задана непрерывная функция y=f(x).
Требуется
вычислить определнный интеграл
b
ф
іF(x)dx.
х
a
Разделим отрезок [a,b] точками a= X0, X1, X2,...,Xn на n -
равных
частей длины .x : .x = (b-a)/n.
Обозначим далее через Y0, Y1, Y2, ... ,Yn, т.е. Y0=f(X0),
Y1=f(X1),...
Yn=f(Xn).
Составим суммы Y0.x + Y1.x + Y2.x + ... + Yn-1.x, Y1.x + Y2.x
+ ...
... +Yn.x.
Каждая из этих сумм является интегральной суммой для f(X) на
отрезке [a,b]
и поэтому приближенно выражается интеграл:
b
ф
іF(x)dx ч ((b-a)/n)*(Y0+Y1+Y2+...+Yn-1). (1)
х
a
Это и есть формулы прямоугольников. Ошибка вычислений тем
меньше, чем
больше число n.
II. Формула трапеций.
Мы получим олее точное значение, если данную кривую Y=F(X)
заменим не
ступенчатой линией, а вписаной ломаной. Тогда площадь
криволинейной
трапеции aABb заменится суммой площадей прямолинейных
трапеций, ограниченых
сверху хордами AA1, A1A2,...,An-1B. Так как площадь первой из
этих трапеций
равна ((Y0+Y2)/2).x, площадь второй равна ((Y1+Y2)/2).x и
т.д., то
b
ф b-a Y0+Yn
іF(x)dx ч ДДДДД * ( ДДДДДДД + Y1 + Y2 + ... + Yn-1).
х n 2
a
Это и есть формула трапеций.
III. Фомула парабол (формула Симпсона).
Разделим отрезок [a,b] на четное число равных частей n=2*m.
Площадь
криволинейной трапеции, соответствующей первым двум отрезкам
[X0, X1]
и [X1, X2] и ограниченной заданной кривой Y=F(X), заменим
площадью
криволинейной трапеции, которая ограничена параболой второй
степени,
проходящей через три точки M(X0, Y0), M1(X1, Y1), M2(X2, Y2) и
имеющей
ось, параллельную оси Oy. Такую криволинейную трапецию будем
называть
параболической трапецией.
Уравнение параболы с осью, параллельной оси Oy, имеет вид
y = Axэ + Bx + C.
Коэффициенты A, B и C однозначно определяются из условия, что
парабола
проходит через три заданные точки. Аналогичные параболы
строим и для
других пар отрезков. Сумма площадей параболических трапеций и
даст
приближенное значение интеграла.
Л е м м а:
Если криволинейная трапеция ограничена параболой
Y = Axэ + Bx + C,
осью Ox и двумя ординатами, расстояние между которыми равно
2h, то ее площадь равна
h
S = Д (Y0 + 4*Y1 + Y2), (3)
3
где Y0 и Y2 - крайние ординаты, а Y1 - ордината кривой в
середине отрезка.
Пользуясь формулой (3) мы можем написать следующие
приближенные равенства
(h=.x):
X2
ф .x
іF(x)dx ч ДДДД *(Y0 + 4*Y1 + Y2),
х 3
a = X0
X4
ф .x
іF(x)dx ч ДДДД *(Y2 + 4*Y3 + Y4),
х 3
X2
. . . . . . . . . . . . . . . . .
X2m = b
ф .x
іF(x)dx ч ДДДД *(Y2m-2 + 4*Y2m-1 + Y2m).
х 3
X2m-2
Складывая левые и правые части, получим слева искомый
интеграл, справа
его приближенное значение:
b
ф (b-a)
іF(x)dx ч ДДДДД * (Y0 + Y2m + 2*(Y2 + Y4 + ... + Y2m-2)
х 3
a + 4*(Y1 + Y3 + ...
+ Y2m-1)).
Это и есть формула Симпсона. Число 2m произвольно, но чем
больше
это число, тем точнее сумма в правой части равенства дает
значение
интеграла. === Cut ===
<O> Bye, All <O>
--- GoldEd 3.00.Alpha4+
* Origin: http://algolist.da.ru - Мир Алгоритмов (2:5020/1815.6)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
FAQ |
Ilia Kantor |
08 Dec 2001 22:17:02 |
|
|
