Задача
Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.
Входные данные
Целое число [latex]N (0 < N≤ 1000)[/latex].
Выходные данные
Единственное число – количество дней.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 9 | 1 |
| 2 | 45 | 4 |
| 3 | 324 | 16 |
| 4 | 1234 | 28 |
| 5 | 213213123 | 153 |
Код программы №1 (с использованием цикла):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> #include <cmath> using namespace std; int main() { double k = 1, T = 10, N, S = 10; cin >> N; while (N > T) { S = S * 1.1; T = S + T; k++; } cout << k; return 0; } |
Решение задачи:
Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.
- Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]
Ссылки
Код программы №2(с использованием линейных вычислений):
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> #include <cmath> using namespace std; int main() { double s; cin >> s; cout << ceil (log(s / 100 + 1) / log(1.1)); return 0; } |
Решение задачи:
Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).
- Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]