目標很簡單：
找到 X1, X2, ... Xn 的幾何中間（在我的例子中 n = 3）
但是我必須撰寫自己的函式并且不能使用 pow()、exp()、log2() 等。
所以在開始編碼之前，我嘗試先用紙計算它。我使用 125 作為 (a * b * c) 的結果，因為我知道 125 的第三個根是 5
我想使用“125 e(1/n)”，但我真的被困在計算這個 exp 因為我根本不知道如何......雖然谷歌并不是真的有幫助......
這只是為了考試而學習的任務......
uj5u.com熱心網友回復：
沒有找到數字的第 n 個根的通用演算法。但是由于我們手頭有一臺計算機，我們可以使用數值近似。
我們有兩種通用方法來找到單調函式的根
- 二分法：如果你有一個值低于和一個高于，取平均值并繼續。這是一種非常穩健的方法，但它的收斂速度很慢
- 牛頓：您使用導數公式從初始猜測中找到更好的值。這個速度非常快，前提是您開始離根足夠近，但如果您從一個錯誤的猜測開始可能會很差。順便說一句，我們都知道 x -> x^n in x -> n * x^(n - 1) 的導數...
所以一個經驗法則是從二分法開始找到一個可以接受的猜測，然后用牛頓找到一個非常精確的近似值
當我們得到一些我們想要取幾何平均值的值時，我們知道結果大于最小值并且小于最大值，所以我們有了初始化二分法所需的東西。
一個可能的代碼可能是：
#include <stdio.h>
#include <stdlib.h>
#include <float.h>
// a trivial implementation for x -> x^n
double dpow(double x, int n) {
double val = 1;
int i;
for (i = 0; i < n; i ) val *= x;
return val;
}
int main() {
//double *arr;
int i, n;
printf("Enter the number of values: ");
for (;;) {
if (1 == scanf("%d", &n) && n > 1) break;
printf("Invalid input, try again\n");
int c;
while ((c = fgetc(stdin)) != EOF && c != '\n');
if (c == EOF) return 1;
}
double min = DBL_MAX, max = -DBL_MAX, a=1;
//arr = malloc(n * sizeof(*arr));
printf("Enter %d values: ", n);
for (i = 0; i < n; i ) {
double val;
for (;;) {
if (1 == scanf("%lg", &val)) break;
printf("Invalid input, try again\n");
int c;
while ((c = fgetc(stdin)) != EOF && c != '\n');
if (c == EOF) return 1;
}
a *= val;
if (min > val) min = val;
if (max < val) max = val;
}
// we want x, dpow(x, n) "close" to a, we know min <= x <= max
// first a dichotomy
double x, eps = (min max)/10.;
int nd = 0, nn = 0; // will trace the number of dich and Newton iterations
for (;;) {
nd;
x = (min max) / 2;
if (max - min < eps) {
break;
}
if (dpow(x, n) < a) min = x;
else max = x;
}
eps = x * 1e-10;
// let's go with Newton
for (;;) {
nn;
double x1 = x;
x = x1 (a - dpow(x1, n)) / n / dpow(x1, n - 1);
if (x1 - x > -eps && x1 - x < eps) break;
}
printf("sqrt%d(%g) = %g (%d dichotomy, %d Newton)\n", n, a, x, nd, nn);
return 0;
}
uj5u.com熱心網友回復：
您可以使用牛頓法計算 x 的 n 次根。
牛頓法是
y = y - f(y) / f'(y)
和
f(y) = y^n - x
這給出了以下迭代：
y = (n - 1) * y / n x / n * y^(1-n)
對于大于 x 的初始 y，此序列是收斂的（請參閱nth-root-iteration）
在純 C 中，這給出：
#include <assert.h>
#include <stdio.h>
double nthpower(int n, double x)
{
if (n < 0)
return nthpower(-n, 1 / x);
double y = 1;
for (int i = 0; i < n; i )
{
y = y * x;
}
return y;
}
int close_to_zero(double x)
{
const double eps = 1e-10;
return (-eps < x) && (x < eps);
}
double nthroot(int n, double x)
{
assert(x >= 0);
assert(n >= 0);
switch (n)
{
case 0:
return 1;
case 1:
return x;
default:
double yp, y = x;
do
{
yp = y;
y = (n - 1) * y / n x / n * nthpower(1 - n, y);
} while (!close_to_zero(yp - y));
return y;
}
}
double geometric_mean(double* x, int n)
{
double p = 1;
for (int i = 0; i < n; i )
{
p *= x[i];
}
return nthroot(n, p);
}
int main(void)
{
double x[6] = {2, 3, 4, 5, 6, 7};
printf("GM %f\n", geometric_mean(x, 0));
printf("GM %f\n", geometric_mean(x, 1));
printf("GM %f\n", geometric_mean(x, 6));
return 0;
}
列印：
通用汽車 1.000000
通用汽車 2.000000
通用汽車 4.140681
有改進的余地，例如，通過計算 xx，然后是 x^2.x^2，然后是 x^4.x^4 可以更有效地計算 n 次方......但我認為主要思想（使用牛頓法）正確說明。
uj5u.com熱心網友回復：
就像“abelenky”在他的（已洗掉）答案中寫的那樣，如果您想計算嚴格遞增函式的反函式并且您知道結果是肯定的，您也可以使用二進制搜索：
搜索n一個數的 -th rooty是該函式的反函式y=f(x, n)；因為x>0，這個函式是嚴格遞增的。
因為寫 C 代碼是為了你的功課練習，所以我不會在這里展示 C 代碼，只向你解釋原理：
在進行二分搜索之前，您必須執行兩項檢查：
- 如果數字為零，則解（根）也為零。
- 如果數字是負數，你可以計算
-root(-y, n)如果n是奇數；如果n是偶數，則沒有解決方案。
（-root(-y, n)意味著：您計算n絕對值的 -th 根y并更改結果的符號。）
現在搜索起始編號g：
double g = 1;
while(f(g) > y) { g /= 2; }
while(f(g) < y) { g *= 2; }
在n-th 根的情況下，f(x)is ，如果已知它是一個正整數pow(x, n)，您可以很容易地用一個自寫的函式（使用for回圈）替換它。n
然后執行二分查找：
double x;
int i;
for(i=0; i<60; i )
{
if(f(x g) <= y) { x =g; }
g /= 2;
}
由于double變數的精度，增加回圈運行的次數不會改變結果。如果您使用更精確的資料型別（例如long double），則需要更多回圈運行才能獲得可能的最佳結果。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/417879.html
標籤：