Добрый день. Может кто-нибудь сказать или показать , как на С++ можно получить кубический корень от числа N? Спасибо.
→ Обратите внимание
До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 06.11.2024 00:07:21 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Например возведением в степень 1/3: pow(x, 1./3);
бинпоиском
Бинарный поиск для монотонных функций. Кубическим корнем из числа x называется такое число y, что y^3 = x. Сформулируем задачу так: для данного вещественного числа x (x ≥ 1) найти кубический корень с точностью не менее 5 знаков после точки. Функция при x ≥ 1, ограничена сверху числом x, а снизу единицей. Таким образом, за нижнюю границу мы выбираем 1, за верхнюю само число x. После этого делим текущий отрезок пополам, возводим середину в куб и если куб больше x, то заменяем верхнюю грань, иначе нижнюю. Код будет выглядеть следующим образом: r = x ; l = 1 ; while (fabs(l-r)>eps) { m = ( l+r ) /2 ; if (m*m*m<x) l=m ; else r=m ; } Для того чтобы пользоваться функцией fabs, необходимо подключить библиотеку math.h.
Бинпоиск в таких случаях работает долго, уточняя по одной цифре в двоичном разложении за раз. Лучше уж итерационный метод, например Ньютона:
Ищем корень кубический из A , в качестве x0 берём что-то приближённое. Итерационный метод возводит точность в квадрат, а не умножает на 2, как бинпоиск.
Удивляюсь. Я воспринял исходный вопрос как то, что автор не знает pow. Или не слышал о log/exp. Или не подозревает, что извлечь корень кубический, это то же самое, что возвести в степень 1.0/3.
А тут такие серьёзные люди предлагают алгоритмические методы решения задачи.
Вопрос же был не «как получить кубический корень», а «как на С++ можно получить кубический корень».
Может, правда, вопрос был об очень большом целом N, но, тогда действительно только дихотомия и длинное умножение, думаю.
Разве в длинной арифметике не лучше итерационным с делением?
А разве он будет сходиться на целых числах? Да и писать длинное деление как-то не клево. А вот в вещественной... Хотя тут уже без BigDecimal печально...
Будет выдаваться результат с точностью до +-1, а уж три значения можно и проверить.
Да, согласен. Там же только делить на 2 надо, а это за O(N).
UPD. Не правильно воспринял. Можно же сделать дихотомию без длинного умножения, только с делением на 2, что за O(N). Любое другое длинное деление не на заранее известную константу, действительно напрягает.
Так возведение в квадрат идёт за O(N2) , как и длинное деление. Где здесь лучше?
Длинное деление очень просто пишется в варианте N^2 * log2(base). В "кнутовском" варианте за O(n^2) код сложнее, как и сама идея, но для кого-то может быть тоже не сложно пишется.
cbrt(n), не?