CDialog::OnMouseMove(nFlags, point);
}
Вы создали и выполнили программу Draw.exe, с помощью которой вы можете рисовать, путем передвижения мыши, при нажатой ее левой кнопки. Также вы познакомились с функцией OnMouseMove, которая выполняется при передвижении мыши, и с функцией OnLButtonDown — при нажатии на левую кнопку мыши.
Вы закончили третий урок!
МАТЕМАТИЧЕСКИЙ ПРАКТИКУМ
Задачи с решениями
Ведет Данила Мастер
1. Положим, что мы хотим приблизить вещественное число α € £(0,1) с точностью ε т. е. подобрать с помощью некоторого изображающего аппарата рациональное число — так чтобы p/q
| α — (p/q)|< ε
Воспользуемся для этого двумя изображающими аппаратами, именно систематическими (двоичными) дробями с одной стороны и цепными (непрерывными) дробями — с другой, и оценим потребные для хранения числа а количества информации при каждом из способов представления.
Случай систематических дробей хорошо известен. При разложении числа в двоичную дробь длины m, т. е. при использовании m значащих бит для мантиссы погрешность приближения числа α составит — (1/2)∙2-m = 2-m-1. Поэтому для достижения потребной точности ε мы должны иметь
2-m-1 < ε => -m - 1 < log2 ε => m > -log2 ε - 1 = log2(1/ε) - 1.
Таким образом для достижения точности ε мы должны затратить по меньшей мере
I2(ε) = log2 (1/ε) — 1 (1)
бит информации.
2. Разложим теперь наше число α в цепную дробь:
и возьмем в качестве представления числа α последовательность {а1, а2…., аn}, обрезая цепную дробь на n-м члене, т. е. беря n-ю подходящую дробь (поскольку α € (0,1), то, очевидно, а0 = 0).
Известно, что для записи числа αi, — требуется в среднем log2 αi — бит, и значит для хранения последовательности {а1, а2…., аn} этих бит потребуется по меньшей мере
Iс = Σni=1 log2 ai = log2 Пni=1ai
(2)
Остается связать данное количество информации с потребной точностью представления числа α. Этим мы и займемся.
Известно (см. [1], стр. 40, формула (30)), что подходящая дробь
построенная по числу а, приближает его с точностью 1/q2n:
|α — (pn/qn)| < 1/q2n
Поэтому для приближения α с точностью ε достаточно соблюдения условия
1/q2n < ε => qn > 1/√ε
Остается получить оценку сверху для qn, причем требуется оценить qn величиной, связанной с Ic. Сделаем это.
Для знаменателей qn подходящих дробей справедливо рекуррентное соотношение (см. [1], стр. 11, формула (7))
qк = aкqк-1 + aкqк-2,
причем по определению полагается q-1 = 0, q0 = 1. Тогда q1 = а1, q2 = a2a1 + 1, q3 = a3a2a1 + a3 + a1 и т. д.
Лемма. Для знаменателей qn верна оценка qn <= 2n-1πn, где πn= Пn i=1= ai.
Доказательство (методом мат. индукции). Для n = 1 утверждение верно, ибо q1 = а1. Предположим, что оценка верна для всех k и n. Тогда
поскольку выражение в круглых скобках не превосходит единицы ибо аn >= 1, аn+1 >= 1. Лемма доказана.
Опираясь теперь на лемму, заключаем, что для аппроксимации числа α с точностью ε должно быть:
1/√ε < qn =< 2n-1Пni-1 ai
Следовательно, используя (2), находим:
Таким образом, учитывая (1), получаем соотношение:
Ic(ε) >= (1/2)∙I2(ε) - n + 3/2
Впрочем, данная оценка довольно груба. Ее можно немного усилить.
С другой стороны, очевидно, qn >= Пn i=1 ai (доказывается тоже индукцией), поэтому если
1/q2n < ε < 1/q2n-1