Добрый день. Может кто-нибудь сказать или показать , как на С++ можно получить кубический корень от числа N? Спасибо.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3312 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 9 | maroonrk | 132 |
| 10 | Proof_by_QED | 131 |
Например возведением в степень 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), не?