Интернет-журнал "Домашняя лаборатория", 2007 №1

Ответ к упражнению

Для того, чтобы выполнить упражнение вам необходимо изменить код функции OnMouseMove следующим образом:

void CDrawDlg::OnMouseMove(UINT nFlags, CPoint point)

{

// TODO: Add your message handler code here and/or call default

////////Мой код начинается здесь///////////

if((nFlags 8l MK_LBUTTON)==MK_LBUTTON)

{

CCIientDC dc(this);

// dc.SetPixel(point.x, poi nt.y, RGB(123,211,98));

CPen NewPen(PS_SOLID, 5, RGB(255,0,0);

dc.SelectObject(&NewPen);

dc.MoveTo(m_PrevX, m_PrevY);

dc.LineTo(point.x, point.y);

m_PrevX=poi nt.x;

m_PrevY=poi nt.y;

}

////////Мой код заканчивается здесь///////////

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 < log₂ ε => m > -log₂ ε - 1 = log₂(1/ε) - 1.

Таким образом для достижения точности ε мы должны затратить по меньшей мере

I₂(ε) = log₂ (1/ε) — 1 (1)

бит информации.

2. Разложим теперь наше число α в цепную дробь:

и возьмем в качестве представления числа α последовательность {а₁, а₂…., а_n}, обрезая цепную дробь на n-м члене, т. е. беря n-ю подходящую дробь (поскольку α € (0,1), то, очевидно, а₀ = 0).

Известно, что для записи числа α_i, — требуется в среднем log₂ α_i — бит, и значит для хранения последовательности {а₁, а₂…., а_n} этих бит потребуется по меньшей мере

I_с = Σⁿ_i=1 log₂ a_i = log₂ Пⁿ_i=1a_i

(2)

Остается связать данное количество информации с потребной точностью представления числа α. Этим мы и займемся.

Известно (см. [1], стр. 40, формула (30)), что подходящая дробь

построенная по числу а, приближает его с точностью 1/q²_n:

|α — (p_n/q_n)| < 1/q²_n

Поэтому для приближения α с точностью ε достаточно соблюдения условия

1/q²_n < ε => q_n > 1/√ε

Остается получить оценку сверху для q_n, причем требуется оценить q_n величиной, связанной с I_c. Сделаем это.

Для знаменателей q_n подходящих дробей справедливо рекуррентное соотношение (см. [1], стр. 11, формула (7))

q_к = a_кq_к-1 + a_кq_к-2,

причем по определению полагается q_-1 = 0, q₀ = 1. Тогда q₁ = а₁, q₂ = a₂a₁ + 1, q₃ = a₃a₂a₁ + a₃ + a₁ и т. д.

Лемма. Для знаменателей q_n верна оценка q_n <= 2^n-1π_n, где π_n= Пⁿ _i=1= a_i.

Доказательство (методом мат. индукции). Для n = 1 утверждение верно, ибо q₁ = а₁. Предположим, что оценка верна для всех k и n. Тогда

поскольку выражение в круглых скобках не превосходит единицы ибо а_n >= 1, а_n+1 >= 1. Лемма доказана.

Опираясь теперь на лемму, заключаем, что для аппроксимации числа α с точностью ε должно быть:

1/√ε < q_n =< 2^n-1Пⁿ_i-1 a_i

Следовательно, используя (2), находим:

Таким образом, учитывая (1), получаем соотношение:

I_c(ε) >= (1/2)∙I₂(ε) - n + 3/2

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

С другой стороны, очевидно, q_n >= Пⁿ _i=1 a_i (доказывается тоже индукцией), поэтому если

1/q²_n < ε < 1/q²_n-1

то

q_n-1 < 1/√ε < q_n

(5)

и, значит

Поэтому,

I_c(ε) <= 1/2∙I₂(ε) + 1/2 + log₂ a_n

Если принять, что 1/q²_n < ε, то оценка упрощается:

I_c(ε) <= 1/2∙I₂(ε) + 1/2

Таким образом видим, что теоретическая нижняя граница для I_c(ε) — объема данных, потребных для хранения вещественного числа а, оценена нами как сверху (формулы (6) и (6’)), так и снизу (формула (4)). Поэтому в случае больших объемов информации (I_c(ε) —> оо) представление числа в виде цепной дроби требует примерно вдвое меньшего количества бит, т. е. достигаемое сжатие — порядка 50 %.