IV. Циклическая структура управления (без индексации)

Инструментальные средства программирования: условные и составные операторы, операторы цикла, но пока никаких массивов.

IV.1. Однократные итерационные циклы

1. (Факториал.) Вычислить т = n!

2. (Одна замечательная формула.) Для заданного n вы­числить S_n = 1³+2³+ … +n³ и T_n = 1+2+ … +n и установить, имеет ли место равенство S_n = T_n². (Тождество S_n = T_n² нетрудно доказать по индукции, однако здесь программируй­те!)

3. (Приближенное вычисление определенных интегралов.) Вычислить приближенное значение I_n определенного интеграла по одной из квадратурных формул с числом шагов интегрирова­ния, равнымn. В приводимых ниже формулах ,x_i = a + ih, y_i = f (x_i).

Формула прямоугольников: I_n = h[y₀ + y₁ + … + y_n–1].

Формула трапеций: I_n = h[(y₀ + y_n)/2 + y₁ + y₂ + … + y_n–1].

Формула Симпсона (n четно):

.

Варианты задания (везде n = 100):

a) ,;

б) ,;

в) ,.

Вычислить погрешность |I – I_n| использованной приб­лиженной формулы, учитывая, что истинные значения соответ­ствующих интегралов равны соответственно

a) 1.35011...; б) ; в) .

4. (Гармонический ряд. Константа Эйлера-Маскерони.)

а) Вычислить сумму n первых членов гармонического ряда:

б) Для заданного t > 1.0 вычислить n, при котором H_n > t  H_n–1.

в) Известно, что , где0 < _n  , а  – некоторая константа, назы­ваемая константой Эйлера-Маскерони. Вычислить значение константы  с заданной точностью  . (Известно, что

 = 0.5772156649015328606065120900824024310422...).

5. (Знакопеременный ряд Грегори.)

а) Вычислить сумму n первых членов ряда Грегори

четырьмя способами: сложить члены (1) слева направо и (2) справа налево; сложить сначала отдельно положительные, а затем отрицательные члены (3) слева направо и (4) справа налево. Полученные результаты напечатать и объяснить расхож­дение в результатах (если оно имеется).

б) Если вычислять S_n способом (1), то , ког­да n  . Для заданного  = 0.0001 найти наименьшее n такое, что . (Считать, что  = 3.1415926.)

6. (Постоянная Каталана.) Вычислить приближенное зна­чение постоянной Каталана – следующей знакопеременной суммы:

,

"обрывая" суммирование:

а) на n-ом члене;

б) как только очередной член ряда становится по абсолютной величине   .

7. (Произведение Валлиса.) Положим

.

Для заданного  > 0 вычислить первое n, при котором . (Известно, что при n  .) Считать, что  = 3.1415926.

8. (Ряд Гаусса.) Положим

,

где 0 < p < q – целые числа. Известно, что

.

Вычислить E_n = |S_n(p,q) – S(p,q)| для заданных n, p, q.

9. (Некоторые интересные суммы.) Вычислить суммы

а) ;	в) ;
б) ;	г) .

(Рядом с суммами указаны их значения при n = .)

10. (Вычисление конечных сумм.) Вычислить:

а) ;	в) ;
б) ;	г) ,

где (2m)!!=2·4· …· (2m) и (2m+1)!!=1·3·5·…· (2m+1).

Указание. Здесь можно использовать схему Горнера.

Например,

11. (Вычисление конечных сумм и произведений.) Вычислить:

а) ;	в) ;
б) ;	г) .

12. (Некоторые хорошо известные разложения функций в ряд.) Вычислить приближенные значения функций, используя их разложения в ряд и суммируя члены от первого до (исключи­тельно) члена (с наименьшим номером), не превосходящего по абсолютной величине  :

а) ;	в) ,|x|<1;
б) ;	г) .

13. (Число  = 3.1415926535897932384626433832795...) Вычислить приближенное значение числа  по формуле: , где,|x|<1. При вычислении бесконечной суммы учесть только те слагае­мые, которые по абсолютной величине   = 0.0001.

14. (Вычисление конечных сумм.) Вычислить суммы, суммируя по тем k = 1,2,..., для которых t_k   :

а) ,; б),.

15. (Попадание в интервал.) Целые числа l, k, n, a₁, … , a_n определяются вводом и последовательно обрабатываются програм­мой. Вычислить, сколько введено чисел a_i, которые:

а) принадлежат интервалу (l, k];

б) кратны l и при делении на k дают в остатке 1, 2 или 3.

Другой вариант задания. Определить числа a_i явно, например: a_i=i³+7i²-15i+3, i=1,2,…,n.

16. (Минимум, максимум и сумма одновременно.) Последо­вательность вещественных чисел x₁, x₂, … определяется вводом. Вычислить минимум, максимум и сумму чисел этой по­следовательности. Считать, что x₁  0, а последним элемен­том последовательности является первое число x_n, равное нулю. При этом число x_n в вычислении минимума и максимума не участвует.

Другой вариант задания. Числа x_i задать явно, например, x_i = e^cos ix– sin ix, i = 1,2,…,n.

17. (Число перемен знака в последовательности.) Вычислить V_n – число перемен знака в последовательности 1, cos 1, cos 2, …, cos(n–1), cos n. (Интересно отметить, что n/V_n   при n  .)

18. (Ближайшее к целому.) Среди чисел ,k=1, 2, …, 40, найти ближайшее к какому-нибудь целому. Здесь a, b > 0 – заданные вещественные числа.

19. (Найти рекуррентность.) Для заданных натурального n и вещественных a  0 и b  1 вычислить:

a) (n корней);

б) (n логарифмов).

(Отметим, что x_n  x, где – корень уравнения;, гдеy – наибольший корень уравнения , приn  .)

20. (Линейные рекуррентные последовательности.) Вычис­лить значения п-ых членов последовательностей {x₀, x₁, …} и {y₀, y₁, …}, определяемых рекуррентно:

а) x₀ = a; x_k = bx_k–1+c, k = 1, 2,…;

б) x₀ =a; x₁ = b; x_k=cx_k–1+ dx_k-2, k = 2, 3, … ;

в) x₀ = x₁ = x₂ = a; x_k = bx_k–1+ cx_k-3, k = 3, 4, … ;

г) x₀ = y₀ = a, x_k = bx_k–1+ cy_k–1, y_k = dx_k–1+ ey_k–1, k = 1, 2,…;

д) x₀ = y₀ = a, x₁ = y₁ = bx₂ = y₂ = c; x_k = dx_k–1+ ey_k–2+fx_k–3, y_k = gx_k–1+ hy_k–2, k = 3, 4,…

21. (Длина кривой.) Вычислить длину кривой y = f (x) между точками A и B, выбирая в качестве её приближенного значения длину ломаной A A₁ A₂…A_n–1 B (см. рис. 4).

Указание. Длина отрезка А_i A_i+1 равна , где h = (b–a)/n, x_i = a+ih, i = 0,1,…, n. Исходные данные ( f (x), a, b, n) подобрать самостоятельно.

22. (Поиск итерационной схемы.) Для заданных x, a  0 и n  0 вычислить:

a) ; б); в); г)(s – целое).

Указания. а) Здесь y₀ = 1; y_k = b_ky_k–1 (k  1), где b₀ = 1/ax; b_k = b_k–1x² (k  1). б) ,,. в) Тропинка уже проложена. г) Здесь можно поступить так: сначала вычислитьm = n^s, а затем вычислить y_n = x^m, используя степенной алгоритм (см. задачу 1.9).

23. (Вычисление конечных сумм.) Вычислить суммы:

а) ; б) ,

суммируя по тем k = 0,1,..., для которых a  v_k  b (0 < a < b). Последовательность v₀, v₁, … определена рекуррентно: v₀ = v₁ = a; v_k = v_k–1+v_k-2 для k = 2,3,…

24. (Суммирование рядов.) Просуммировать ряды:

а) ; б)

Суммирование по n продолжать до тех пор, пока n  m или |a_n|  , где m  1 и  > 0 – заданные (нату­ральное и вещественное) числа, а a_n – n-ый член ряда.

Указание. Для вычисления b_k = cos kx и c_k = sin kx используйте следующие формулы: b₀ = 1, c₀ = 0, b₁ = cos x, c₁ = sin x; b_k = b_k–1b₁–c_k–1c₁, c_k = c_k–1b₁ + c₁b_k–1, k = 2,3,…

(Теоретические ответы: а) ; б).)

25. (Приближенное вычисление кубического корня.) Вычислить значение , используя итерационную формулу:

, n = 0,1,…,

где y₀ = x/3, если х  1; y₀ = x, если х < 1. В качестве у взять y_n+1 с наименьшим n, для которого |y_n+1–y_n|  , где  > 0 – заданное число. (Известно, что , когдаn.)

26. (Как вычислить log₂ x?) Вычислить у = log₂ x (x > 0) с заданной точностью  .

Указание. Так как log₂ x = –log₂ (1/x) и log₂ x=m+log₂ (x/2^m), то все сводится к умению вычис­лять у = log₂ x при 1  x < 2. В этом случае x = 2^y, где 0  y < 1, или для некоторых ₁, ₂, …  {0,1}. Если обозначить y_n = b₁+b₂ +…+b_n, где b_i = _i / 2ⁱ, то |y ‑ y_n|  b_n. Поэтому, если n таково, что b_n  , то y_n  log₂ x  y_n+ . Вычисление y_n и b_n можно провести по итерационной схеме: a₀ = x, b₀ = 1, y₀ = 0; ,b_k = b_(k–1)/2; y_k = y_k–1 или y_k-1 + b_k-1 соответственно при и; k = 1, 2, …

27. (Приближенное вычисление 1/x при 0 < x < 2.) Последовательности {a_k} и {b_k} заданы рекуррентно:

a₀ = 1, b₀ = 1–x; a_k = a_k-1(1+b_k–1), b_k =  (b_k–1)², k = 1,2,...

Вычислить a_n для наименьшего п, при котором b_n   ( > 0). (Для такого n имеем |a_n–1/x|   /x.)

28. (Приближенное вычисление при0<x<2.) Последовательности {a_k} и {b_k} заданы рекуррентно:

a₀ = x, b₀ = 1–x; a_k = a_k–1(1+b_k–1/2), , k = 1,2,…

Вычислить a_n для наименьшего n, при котором b_n   ( > 0). (Для такого n имеем .)

29. (Если последовательность имеет предел, то для любо­го заданного  > 0 найдется n такое, что...) Последовате­льность {x₀, x₁,…} определяется рекуррентно. Найти наименьшее n, при котором |x_n‑x_n‑1|   .

а) ; б) ;k=1,2,…; x₀ = 0.

Замечания. При n   a) , б) , где x – корень уравнения x=cos x.

30. (Метод Ньютона, или метод касательных.) Найти приближенное значение  корня уравнения f (x) = 0 по методу Ньютона.

Суть метода. Последовательное приближение к искомому решению x= из заданного промежутка (a,b) осуществля­ется по итерационной формуле

x_n = x_n–1–f (x_n–1) / f (x_n–1), n = 1,2,…

В качестве начального приближения x₀ выбирается значение z того конца промежутка (а,b), для которого f (z) f (z) > 0. Полагают  = x_n, для первого n, при котором

|x_n–x_n–1|  |f (x_n–1)/f (x_n–1)|  .

(Здесь  > 0 – некоторое заданное число, так называемая точность вычисления.) Процесс после­довательного приближения к искомому решению иллюстрируется на рис. 5.

Варианты задания (везде  = 0.0001):

а) f (x)  = x⁵–x–0.002, (a, b)=(1.0, 1.1);

б) , (a, b)=(, 2).

31. (Метод половинного деления.) Найти приближенное значение  корня уравнения f (x) = 0 с абсолютной точностью  методом половинного деления.

Суть метода. Предположим, что нам известен интервал (a, b) такой, что    (a,b) и f(a) f(b) < 0. Рассмотрим точку c =  (a+b)/2 – середину этого интервала. Если f(c) = 0, то полагаем =c (корень найден); если же  f(c)  0, то указанную процедуру повторим для того из интервалов (а,с) или (с,b), на концах которого функция f(x) меняет знак. Этот процесс повторяется до тех пор, пока длина последнего из рассматриваемых интервалов не станет  2. Его середину берем в качестве приближенного значения . Процесс стягивания интервалов к искомому решению иллю­стрируется на рис. 6.

Варианты задания (везде  = 0.0001):

a) ,;

б) , (a, b) = (0,1);

в) , (a, b) = (–3,–2), (–1,0), (0,1).

32. (Метод простых итераций.) Найти приближенное значение  корня уравнения x = f (x) методом простых итераций.

Суть метода. В процессе построения элементов числовой последовательности {x₀, x₁,…}, определяемой рекуррентно:

x_n+1 = f (x_n), n = 0,1,…; x₀ = a,

находят первое n, при котором |x_n–x_n–1|   и полагают  = x_n. Здесь  > 0 и a – заданные значения, так назы­ваемые точность вычисления и начальное приближение. Процесс последовательного приближения к искомому решению иллюстри­руется на рис. 7.

Варианты задания (везде  = 0.0001):

а) f (x)  = –ln(x+3), a = 0;

б) f (x)  =  1+9 sin(x)/2, a – любое;

в) f (x)  = x⁵–0.2, a = –1.0, 0.0 и 1.0.

33. (Requla false.–Метод ложного положения, или ме­тод секущих.) Найти приближенное значение  корня уравнения f (x) = 0 по методу секущих.

Суть метода. Выбирают два начальных приближения x₀ и x₁ так, чтобы f (x₀) f (x₁) < 0, и строят последовательные приближения

, n =1,2,…

В качестве z каждый раз выбирают x_k (с k < n) так, чтобы f (x_n) f (z) < 0 (это обеспечивает локализацию  между x_n и z). Наконец, в качестве значения  берут x_n для пер­вого n, при котором |x_n+1 – x_n|   . Процесс последовате­льного приближения к искомому решению иллюстрируется на рис. 8.

Указание. Исходные данные взять из задачи 31.