Алгоритм — Нахождение квадратного корня через итерацию в переполнении стека
У меня домашнее задание, и у меня проблемы с петлями. Сначала я должен найти следующий самый высокий и самый низкий квадратные корни через петли, которые я уже могу сделать. Следующее мое задание говорит мне, что мне нужно получить приблизительное значение квадратного корня, которое я делаю, усредняя следующий самый высокий и самый низкий квадратные корни из целого числа. Затем я должен спросить пользователя о количестве десятичных разрядов точности, которые они хотят. Вот цитата из задания:
Затем следует построить цикл с контролем количества; он будет выполнен один раз для каждой из требуемых десятичных позиций; в этом примере этот цикл будет выполняться четыре раза (по одному разу для десятичных, сотых, тысячных и десятитысячных долей). Используйте счетчик, такой как decimalPosition, чтобы отслеживать, какой проход включен в цикле.
Вот где у меня проблемы, я использую цикл while, основанный на количестве десятичных позиций, которые ввел пользователь, но мой цикл не завершает цикл. Я новичок в программировании, поэтому, пожалуйста, прости меня, если это действительно просто. Вот мой код:
for (int decimalPosition = 1; decimalPosition <= decimal; decimalPosition++)
{
while (baseRoot*baseRoot > num)
{
baseRoot = baseRoot - (pow((.1),decimalPosition));
cout << fixed << setprecision(decimal) << baseRoot << endl;
}
}
вот мой вывод
Enter a number you wish to know the square root of: 8
Enter the number of decimal places of accuracy you want: 7
Find the square root of 8 to 7 decimal places:
2.6000000
2.7000000
2.8000000
2.9000000
2.9000000 square root of 8.0000000
Решение
Это называется Метод Ньютона, и его сходимость является квадратичной. Это должно помочь вам понять это.
PS — Вавилоняне обнаружили это первыми, но Ньютон получил за это кредит.
Другие решения
Чтобы ваш цикл работал, вы можете добавить инструкцию
baseRoot = baseRoot + (pow((.1),decimalPosition));
после цикла, потому что вам нужно убедиться, baseRoot больше, чем ответ перед каждой итерацией. Как это:
for (int decimalPosition = 1; decimalPosition <= decimal; decimalPosition++)
{
while (baseRoot*baseRoot > num)
{
baseRoot = baseRoot - (pow((.1),decimalPosition));
cout << fixed << setprecision(decimal) << baseRoot << endl;
}
baseRoot = baseRoot + (pow((.1),decimalPosition));
}
Теперь вы можете получить ответ 2.8284271,
Кстати, есть еще один эффективный способ называется метод деления пополам (аналог бинарного поиска) для решения такого рода проблем (связанных с Монотонная функциябез лишней математики:
double mySqrt(double x, double epsilon) {
double left = 0, right = x;
while (right - left > epsilon) {
double mid = (left + right) / 2;
if (mid * mid > x) {
right = mid;
} else {
left = mid;
}
}
return left;
}
Все просто, глупо 🙂