e-olimp 1658. Факториал

Задача

Вычислите факториал числа.

Входные данные

Одно целое число [latex]n[/latex]([latex] 0 ≤ n ≤ 20[/latex]).

Выходные данные

Выведите значение [latex]n! = 1 * 2 * 3 * … * n.[/latex]

Тесты

Входные данные Выходные данные
3 6
0 1
20 2432902008176640000

Код

Решение задачи

Для решения данной задачи используем цикл, в котором вычисляем искомый факториал.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

e-olymp 97. Числа Белла

Задача

Число Белла [latex]B_n[/latex] равно количеству разбиений множества из [latex]n[/latex] элементов на произвольное количество непересекающихся непустых подмножеств. Например, [latex]B_3 = 5[/latex], так как существует [latex]5[/latex] возможных разбиений множества [latex]\lbrace a, b, c\rbrace[/latex]: [latex]\lbrace\lbrace a\rbrace, \lbrace b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, b\rbrace, \lbrace c\rbrace\rbrace, \lbrace\lbrace a, c\rbrace, \lbrace b\rbrace\rbrace, \lbrace\lbrace a\rbrace, \lbrace b, c\rbrace\rbrace, \lbrace\lbrace a, b, c\rbrace\rbrace[/latex]. Дополнительно считаем, что [latex]B_0 = 1[/latex].
Рассмотрим определитель [latex]D_n[/latex]:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix}$$
Для заданного простого числа [latex]p[/latex] найти наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Входные данные

Каждая строка ввода содержит два целых числа [latex]n[/latex] и [latex]p[/latex] ( [latex]\;0\leq\; n,\;p \;\leq\; 10000[/latex] ). Известно, что [latex]p[/latex] – простое.

Выходные данные

Для каждой пары входных значений [latex]n[/latex] и [latex]p[/latex] в отдельной строке выведите наибольшее целое [latex]k[/latex], для которого [latex]D_n[/latex] делится на [latex]p^k[/latex].

Тесты

Входные данные Выходные данные
1 5
3 2
4 2
4 3
10000 3
0
2
5
2
24962375
18 2
465 1009
9998 9221
548 11
134
0
778
14412
1093 1093
1103 1723
3931 617
4868 6113
9534 71
1
0
10635
0
639989
617 17
42 11
0 5
11295
63
0

Код программы

 

Решение

Числа Белла обладают интересным свойством:
$$D_n = \begin{vmatrix}
B_0& B_1& B_2&\ldots& B_n\\
B_1& B_2& B_3&\ldots& B_{n+1}\\
\ldots& \ldots& \ldots& \ldots& \ldots\\
B_n& B_{n+1}& B_{n+2}&\ldots& B_{2n}
\end{vmatrix} = \prod_{i=1}^n i! $$

Воспользуемся этим свойством для решения данной задачи. Найдём степень числа [latex]p[/latex] в разложении  на простые множители. Для этого узнаем степень вхождения этого числа в каждый из факториалов. Суммой полученных значений и будет являться искомое число [latex]k[/latex].

Ссылки

Условия задачи на e-olymp
Код задачи на ideone
Число Белла на wikipedia

e-olymp 513. Проблема Николая

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

Входные данные

В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex].

Выходные данные

Вывести искомое количество способов.

Тесты

Входные данные Выходные данные
[latex]500[/latex] [latex]2001[/latex] [latex]0[/latex]
[latex]4[/latex] [latex]5[/latex] [latex]4[/latex]
[latex]4[/latex] [latex]7[/latex] [latex]3[/latex]
[latex]15[/latex] [latex]213[/latex] [latex]147[/latex]
[latex]10[/latex] [latex]3[/latex] [latex]0[/latex]

Код программы

Решение задачи

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

D2655B. Cумма ряда с заданной точностью

Задача
Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до
[latex]\varepsilon [/latex], если [latex]\sum\limits _{ n=1 }^{ \infty }{ \frac { 1 }{ (2n-1)! } } [/latex]

Тесты

Входные данные Выходные данные
Точность Кол-во взятых членов ряда Значение суммы
1 1 2 1.1666666667
2 1е-5 5 1.1752011684
3 100 1 1
4 1e-10 7 1.1752011936

Код на C++

Код на Java

Решение
Очевидно, ряд является положительным, и общий член ряда стремится к нулю. Ряд сходится по признаку Д’аламбера:
[latex] \lim\limits_{n \rightarrow \infty } \frac{ a_{n+1} }{a_{n}} = \lim\limits_{n \rightarrow \infty } \frac{ \big(2n-1\big)! }{ \big(2n+1\big)! } = \lim\limits_{n \rightarrow \infty } \frac{1}{2n \big(2n+1\big) } =0 < 1[/latex].
Оценим остаток ряда, исходя из того, что [latex]k! > \left( \frac{k}{e} \right) ^{k} , \big(k=1,2,\dots\big) [/latex]:
[latex]R_{N}<\sum\limits_{n=N+1}^\infty \left(\frac{e}{2n-1}\right)^{2n-1}\leq\sum\limits_{n=N+1}^\infty \left(\frac{e}{2N+1}\right)^{2n-1}=\left(\frac{e}{2N+1}\right)^{2N+1}\sum\limits_{i=0}^\infty \left(\frac{e}{2N+1}\right)^{2i}[/latex]
Поскольку при [latex]N\geq1[/latex] [latex]\frac{e}{2N+1}<1[/latex]:
[latex]R_{N} < \left(\frac{e}{2N+1}\right)^{2N+1}\frac{1}{1-\left(\frac{e}{2N+1}\right)^2}[/latex]

В переменной sum хранится текущее значение суммы ряда, в last — последний рассмотренный член ряда. В начале работы программы вводится требуемая точность eps. Можно заметить, что для получения [latex]n[/latex]-го члена ряда достаточно разделить предыдущий на [latex]\left(2n-2\right)\cdot\left(2n-1\right)[/latex], однако необходимо отдельно рассмотреть случай, когда [latex]n = 1[/latex]. В цикле увеличиваем [latex]n[/latex], находим значение следующего члена ряда и прибавляем к sum, пока остаток ряда не станет достаточно маленьким. Оцениваем остаток ряда при помощи функции Rn(int n). Во время её работы может потребоваться возведение числа в большую степень, делаем это по алгоритму бинарного возведения в степень.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).
Условие задачи (стр. 259)

А137е

Даны натуральные [latex] n[/latex], действительные [latex] a_{1},\ldots,a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

n a1 a2 a3 a4
Input: 4  1 2 3 4 Output: 2.00 4.00 9.00 28.00
Input: 4 0.1 0.2 0.3 0.4 Output: 1.10 2.20 6.30 24.40

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]for[/latex], от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.

Ссылка на программу.

А99

Задача: Пусть [latex]a_{1}=4[/latex], b1=v, an=2bk-1+ak-1. bk=2a^2k-1+bk-1, k=2,3…

Даны действительные u, v, натуральное n.

Найти Е от n при k=1 (ak*bk)/(k+1)!

Тесты:

N U V Результат Вывод
2 4 3 64 тест пройден
1 4 2 4 тест пройден
2 1 2 4 тест пройден
0 3 1 1 тест пройден
1 2 3 3 тест пройден

Код:

Решение:
if (M == 0) // массив
return 1; // возвращаем факториал от нуля, это 1
else // Во всех остальных случаях
return M * fact(M — 1); // делаем рекурсию.

Пишем условия и формулы:

sum = a * b / fact(k + 1);
for (k = 2; k <= n; k++) // цикл

Цикл:
t = a;
a = 2*b + a;
b = 2 * t * t + b;
sum = sum + (a * b / fact(k + 1));

код задачи в ideone: http://ideone.com/1fNmWc

А136з

Задача Вычислить: [latex]-\frac{a_1}{1!}+\frac{a_2}{2!}-…+\frac{(-1)^na_n}{n!}[/latex]

Тест

n последовательность sum(wolframalpha)
2 0 0 0
2 5 8 -1
3 5 8 12 -3
4 1 2 3 24  1
 5  0 0 0 2 3  0, 058333

Ссылка на программу:http://ideone.com/F0UyqY

Решение:
В этой задаче главное правильно расставить знаки, так  как  это повлияет на результат.Поэтому мы заводим переменную [latex]sign[/latex], которая будет следить за знаком. Далее проверяем  чётность, если элемент делиться на 2 без остатка, то он получает знак [latex]+[/latex], в противном случае [latex]-[/latex]:

Описываем факториал:

Выполняем суммирование и делим на факториал:

Вводим в [latex]input[/latex] количество элементов ([latex]n[/latex])  и сами элементы.Получаем ответ.

Ю3.37

Задача. Численно убедиться в справедливости равенства, для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]e[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex](слагаемых или сомножителей), необходимых для достижения заданной точности.

[latex]\frac {{e}^{x}-{e}^{-x}}{2} =x+\frac {{x}^{3}}{3!}+\frac {{x}^{5}}{5!} +…+\frac {{x}^{2n-1}}{(2n-1)!} +…[/latex]

x e результат Комментарий
5 0.01 0.002312 Работает
3.14 0.999 0.686728 Работает
4 0 Эквивалентно Работает

Всё просто. Считаем левую часть, считает правую часть циклом. В том же цикле ждём момента когда [latex]le-pr[/latex] будет меньше или равно заданной погрешности.

ideone

Вывод: Задача решена.

А36

Задача: Даны действительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]Проверить, выполняются ли неравенства  [latex]a<b<c[/latex].

Тесты:

Ввод Вывод Результат
a b c неравенство                     не выполнено
2 1 3 b<=a<c: нер-во a<b<c                 не выполняется неравенство                     не выполнено
1 3 2 a<=c<=b: нер-во a<b<c                 не выполняется неравенство                     не выполнено
3 1 2 b<=c<=a: нер-во a<b<c                 не выполняется неравенство                     не выполнено
3 2 1 c<=b<=a: нер-во a<b<c                 не выполняется неравенство                     не выполнено
2 3 1 c<=a<b: нер-во a<b<c                 не выполняется неравенство                     не выполнено
1 2 3 нер-во a<b<c справедливо неравенство выполнено

Код программы:

Отчет:

После ввода чисел a, b, c программа проверит их соотношения. Ввиду наличия трех сравниваемых чисел имеем 3! = 6 возможных комбинаций чисел, и только одна из них соответствует требованию. Если неравенство [latex]a<b<c[/latex] имеет место быть, то программа сообщит о его выполнении. В противном же случае консоль выдаст ответ о не выполненном неравенстве, предварительно сообщив причину.

Копия кода на сайте Ideone: ideone.com/aYmMJ2

А116е

Вычислить [latex] \prod_{i=1}^{n}{\frac{(1-x)^{i+1}+1}{((i-1)!+1)^2}} [/latex]

Числа [latex] n [/latex] и [latex] x [/latex] вводятся с клавиатуры.

n x Ответ
1 3 1.25
2 3 -2.1875
3 3 -4.13194

Вводим n и x типа int. Инициализируем переменные v=1-x и u=1 типа double. Присваем значение переменной pro, при  n=1. Запускаем цикл от 2 до n в котором увеличиваем факториал u*=i-1 и степень v*=1-x. Так цикл пройдет n раз и в конце выдаст итоговое произведение cout<< pro.

Link

Java

 

А137е(а)

Даны натуральные [latex] n[/latex], действительные [latex] a_{1}…a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

Input : 1 2 3 4 Output: 2.00 4.00 9.00 28.00
Input : 0.1 0.2 0.3 0.4 Output: 1.10 2.20 6.30 24.40

 

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]while[/latex], у которого в условии ставим:

(Работать, пока файл не закончится (конец потока)). Дальше в теле цикла описываем увеличение факториала и выводим сумму цифр из потока и факториала, в конце цикла увеличиваем [latex]i[/latex] для увеличения факториала.

Java

 

Ссылка на программу.

Ю3.36

Задача

Численно убедиться в справедливости равенства, для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]\varepsilon[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex] (слагаемых или сомножителей), необходимых для достижения заданной точности.

[latex]\frac { { e }^{ x }+{ e }^{ -x } }{ 2 } =1+\frac { { x }^{ 2 } }{ 2! } +\frac { { x }^{ 4 } }{ 4! } +\cdots+\frac { { x }^{ 2n } }{ (2n)! } +\cdots[/latex]

Тесты

   x [latex]\varepsilon[/latex] Левая часть Правая часть    n Разность Комментарий
3 0.00005 10.0676619958  10.0676598764 8 0.0000021194 Пройден
 11.33  0.0000314 41641.5114284855 41641.5114045419 19 0.0000239436 Пройден
 6 0 Погрешность равна 0, тогда правая часть стремится к левой 201.7156361225 (n=бесконечность)​  Не пройден

Код программы на C++:

В данной задаче необходимо было доказать равенство при заданном [latex]x[/latex] и [latex]\varepsilon [/latex].

Для этого вначале высчитывалось значение левой части [latex]\frac { { e }^{ x }+{ e }^{ -x } }{ 2 } [/latex] при заданном [latex]x[/latex], а далее, в цикле, высчитывалось значение правой части [latex]\frac { { x }^{ 2 } }{ 2! } +\frac { { x }^{ 4 } }{ 4! } +…+\frac { { x }^{ 2n } }{ (2n)! } +…[/latex]. В цикле программа находила последующий элемент последовательности, стоящей в правой части равенства, каждый раз умножая предыдущий элемент на [latex]\frac { { x }^{ 2 } }{ (2n-1)*(2n) } [/latex] до тех пор пока разность между левой и правой частью равенства [latex]dife=left-right[/latex]  не стала меньше заданной погрешности, заданной по модулю [latex]dife < \left|\varepsilon \right|[/latex]. После завершения цикла программа запоминает последнее значение [latex]n[/latex] и после этого выводит его на экран.

Код программы на Java

 

А114е

Задача. Вычислить [latex]\prod_{i=1}^{10}{(2+\frac{1}{i!})}.[/latex]

По условию [latex]i[/latex] у нас изменяется от [1; 10], но, чтобы полностью убедиться, что программа правильно работает, изменим интервал, на котором изменяется[latex]i[/latex], к примеру [1; n].

Тест

i f p (wolframalpha)
1 1 3
2 2 7.5
3 6 16.25
4 24 33.17708
5 120 66.630635
6 720 133.3538125486111
7 5040 266.7340841820129 
8 40320 533.4747839927034
9 362880 1066.951038098899
10 3628800 2133.902370220902

Код программы на языке С++ :

Ссылка на код программы: http://ideone.com/DEEFJd
Решение задачи сводится к нахождению произведения [latex]p[/latex]. Присваиваем [latex]p = 1[/latex], [latex]f = 1[/latex]. Далее фиксируем значение [latex]i[/latex]:

Анализируем, [latex]f [/latex] увеличивается в зависимости от [latex]i[/latex], следовательно:

Следующим шагом будет вычисление искомого произведения — каждый последующий член вычисляем и умножаем на предыдущий:

Получаем ответ.

Код программы на языке Java:

Ссылка на программу: http://ideone.com/JzB87V

А116 (б)

Даны натуральное число [latex]n[/latex], действительное число [latex]x[/latex]. Вычислить: [latex]\sum_{i=1}^{n}{(\frac{1}{i!}+\sqrt{|x|})}[/latex];

n x Ответ
2 -4 5.5
3 4 7.6666
1 4 3

Для решения этой задачи воспользуемся циклом for.  Для начала запишем квадрат модуля числа x. Далее создадим цикл для решения этой задачи. Вычислим сначала сумму факториалов, а вне цикла добавим к ней квадрат модуля x, умноженный на n.

А114в

Задача: Вычислить [latex]\sum_{i=1}^{10}{\frac{1}{i!}}[/latex].

Ответ
1.718282

C++:

Java:

Для переменных [latex]a, b[/latex] я использовала тип double, так как они они используются для вычислений и являются вещественными числами. Для переменной [latex]i[/latex] — тип int, так как [latex]i[/latex] — это целые числа от 1 до 10.

Чтобы решить задачу, воспользуемся циклом for, который работает при [latex]1\leq i\leq 10[/latex] и каждый раз прибавляет к [latex]i[/latex] единицу. Переменную [latex]i[/latex] я объявила в цикле, так как вне цикла она не нужна.

Сначала найдём [latex]a[/latex] — элемент суммы, который зависит от выбранного [latex]i[/latex]. После сложим [latex]a[/latex] и переменную [latex]b[/latex], которая обозначает сумму предыдущих элементов, a результат запишем снова в переменную [latex]b[/latex].

Когда цикл дойдёт до 11, его условие перестанет выполняться и напечатается последнее значение, присвоенное переменной [latex]d[/latex].

Эта задача на Ideone:
C++
Java