Задача
Спортсмен в первый день пробежал 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]
У Вас есть орфографические ошибки, и запятых тоже не хватает.
Переменные и формулы следует оформлять в окружении Latex. Например, $N$, $T=10$ .
Дроби оформляют так — $S=\frac{a+b}{c+d}$
Все исправил.
Так же, хочу заметить, что я привел решение с использованием циклов потому, что мне кажется, что задача с помощью них решается легче, да и сама программа работает чуть быстрее.
Т.е. по Вашим измерениям 3000 операций в варианте с циклом работают быстрее? Всё может быть.
Хорошо. Пожалуйста, познакомьтесь, с этой функцией и измерьте время работы в обоих случаях.
Я не совсем правильно сформулировал. Чуть быстрее среднее время срабатывания задачи на eolymp.
Вы так и не исправили отступы в коде
У вас странная формула для основного свойства логарифмов в правой части. И в ней также не использовали команду для логарифма $\log$
Ваня, Вам скопировать ещё раз те замечания, которые Вы не исправили или сами найдете?
Поздновато Вы взялись за первое задание. Такими темпами можно до экзамена не успеть.
Извиняюсь за то, что поздно взялся за задание. Я исправил все, что говорили вы и Евгения Викторовна. Сейчас должно быть все нормально.
Странно. Я наверное пишу мелкими буквами 🙂
Давайте не будем исправлять сразу много замечаний.
1. Найдите строку с номером 13 в Вашем первом коде.
2. Установите курсор перед закрывающей фигурной скобкой.
3. Умелой манипуляцией клавишами Backspace и пробела добейтесь, чтобы фигурная скобка оказалась строго над первой буквой «с» в следующей 14-й строке.
Если не будет получаться, свяжитесь со мной на Facebook — будем работать над этой проблемой вместе. Или обратитесь за консультацией к однокурсникам.
Если вдруг всё быстро получится, переходите к следующему замечанию. Скопирую его сюда. Пожалуйста, познакомьтесь, с этой функцией и измерьте время работы в обоих случаях. Можно это делать только для $N=1000.$
Эх, жалко я свой комментарий не успел сохранить перед очередным падением сервера. Я пытался написать, что со временем работы программы уже разобрался. Оказалось, что для указанных значений цикл будет работать всего несколько десятков раз. Это вполне соизмеримо с вычислением логарифма разложением в ряд. Конечно, при росте $N$ циклический алгоритм будет работать всё дольше, а время работы логарифмического останется постоянным.
Но не важно. Оставляем оба варианта. Больше баллов будет 🙂
Продолжаем работать над отступами в первом коде. Переходим к строке №9. Поскольку цикл начинается сразу после окончания ввода данных, while должен начинаться строго под cin.
Очень хорошо!
Теперь расставьте отступы в своём коде на ideone.com
Хорошо, принято.
Хотел поругать за слово «приплюсовывать», но оказалось он даже в словаре Ушакова есть. Хотя везде помечено, как разговорное. Лучше заменить на что-то соответствующее стилистике текста. Например, «увеличивать на».