Корень 3-ей степери на си шарп без sqrt и math.pow.
В задаче по программированию есть часть задания , где нужно найти корень 3-ей степени из числа , а я хз как его найти. Предпологаю что есть схемка похожая по типу нахождения квадратного корня.
Это для квадратного корня
using System;
public class Test
{
public static void Main()
{
int pref = 49;
int kd = 0;
int k=1;
while (pref>0)
{
pref-=k;
kd++;
k+=2;
}
Console.WriteLine(kd);
}
}
Целочисленный корень или вещественный?
Если вещественный, то корень ищется так: https://ru.wikipedia.org/wiki/Алгоритм_нахождения_корня_n-ной_степени
Если целочисленный, то проще использовать бинарный поиск. Что-то вроде такого (на C, но C# не сильно отличается):
int icbrt(int n) {
int l = 0, r = n;
while (l < r) {
int m = (l + r) / 2;
if (m * m * m < n) {
l = m + 1;
} else if (m * m * m > n) {
r = m - 1;
} else {
return m;
}
}
return l;
} Если только с этими ограничениями, то так:
public static double Root3(double x) => Math.Exp(1d / 3d * Math.Log(Math.Abs(x))) * Math.Sign(x);
Как видишь, ни sqrt, ни pow тут нет.
Если вообще нельзя использовать Math, то экспоненту и логарифм можно сделать самому через Тейлора, а как сделать Abs и Sign, надеюсь, ты и сам догадаешься...
Алгоритм довольно примитивный (основанный на представлении квадрата числа в виде суммы последовательных нечётных чисел), сходится медленно, за O(√x). Можно, конечно, поискать, как раскладывается куб, но зачем? Проще применить бинарный поиск, он сходится за логарифм. Или разложи кубический корень в ряд Тейлора, но у него быстрая сходимость только финально, поэтому сначала надо будет найти достаточно точное приближение.
Вот пример для бинарного поиска на положительных числах (если нужны отрицательные, пошамань с подбором границ и с проверкой условия, поставь отладочную печать, чтобы понять, как работает).
using System;
class Test {
static void Main() {
const double eps = 1e-9;
double cube = double.Parse(Console.ReadLine());
double l = cube >= 1 ? 1 : 0,
r = cube >= 3 ? cube / 2.0 : cube;
while (r - l > eps) {
double m = (l + r) / 2.0;
if (m * m * m > cube) r = m;
else l = m;
}
Console.WriteLine((l + r) / 2.0);
}
} Константа eps регулирует точность.
Если надо в целых числах, то подмени типы, а точность должна быть 1, ближе не подберёшь.
Вариант 1 (итеративно):
using System;
public class CubeRoot
{
private const double Tolerance = 0.0001;
public static double CalculateCubeRootIterative(double number)
{
if (double.IsNaN(number) || double.IsInfinity(number))
return double.NaN;
double low, high;
if (number >= 0)
{
low = 0;
high = number;
}
else
{
low = number;
high = 0;
}
while (high - low > Tolerance)
{
double mid = low + (high - low) / 2;
double cube = mid * mid * mid;
if (Math.Abs(cube - number) < Tolerance)
{
return mid;
}
else if (cube > number)
{
high = mid;
}
{
low = mid;
}
}
return low;
} Вариант 2 (рекурсивно):
public static double CalculateCubeRootRecursive(double number, double low, double high)
{
// Если число не число (NaN) или бесконечность, то и корень будет не числом
if (double.IsNaN(number) || double.IsInfinity(number))
return double.NaN;
if (high - low <= Tolerance)
{
return low;
}
double mid = low + (high - low) / 2;
double cube = mid * mid * mid;
if (Math.Abs(cube - number) < Tolerance)
{
return mid;
}
else if (cube > number)
{
return CalculateCubeRootRecursive(number, low, mid);
}
else
{
return CalculateCubeRootRecursive(number, mid, high);
}
}
public static double CalculateCubeRootRecursive(double number)
{
if (number >= 0)
{
return CalculateCubeRootRecursive(number, 0, number);
}
else
{
return CalculateCubeRootRecursive(number, number, 0);
}
}
public static void Main(string[] args)
{
// Проверим, как это все работает:
double[] numbers = { 27, -8, 125, 0.125, 0, 10, -2, 1000, -1000, 1.7, double.NaN, double.PositiveInfinity, double.NegativeInfinity };
Console.WriteLine("Кубический корень:\n");
foreach (double number in numbers) {
double rootIterative = CalculateCubeRootIterative(number);
double rootRecursive = CalculateCubeRootRecursive(number);
Console.WriteLine($"Число: {number}, Итеративный корень: {rootIterative}, Рекурсивный корень: {rootRecursive}");
}
Console.WriteLine("\n");
Console.WriteLine("Производительность:\n");
int iterations = 1000000;
double numberTest = 64.0;
var swIterative = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < iterations; i++)
CalculateCubeRootIterative(numberTest);
swIterative.Stop();
var swRecursive = System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < iterations; i++)
CalculateCubeRootRecursive(numberTest);
}
}