0

反復関数と再帰関数に問題があります。反復関数があり、それを再帰関数に変換する必要があります。私のコードについてアドバイスをいただけますか? どうもありがとう

コードは、再帰を使用して、データ ポイントの配列が凹関数に対応するかどうかを判断することです。

反復バージョンのコードは次のとおりです。

bool isConcave(double a[], int n)
{
int slope = 1;
bool concave = true;

for (int i = 1; i < n && concave; i++)
{
    double delta = a[i] - a[i-1];

    if (slope > 0)
    {
        if (delta < 0)
            slope = -1;
    }
    else if (delta > 0)  
        concave = false; // slope == -1 and delta > 0
}
return concave;
}

そして、これが動作しない私の再帰バージョンのコードです:

bool isConcave_r(double a[], int n, int& slope)  
{
//Implement this function using recursion
double delta = a[n] - a[n-1];
bool concave = true;

if (n == 0)
    return false;
if (slope > 0)
{
    if (delta < 0)
    {
        slope = -1;
    }
    else
        concave = true;
}else
    return 0;

//dummy return statement
return isConcave_r(a, n, slope);

}
4

2 に答える 2

0

最善/最もクリーンな方法である必要はありませんが、任意のループを置き換えることができます

for (int i = 0; i != N; ++i) {
    body(i, localVars);
}

に

void body_rec(int N, int i, LocalVars& localVars)
{
    if (i == N) return;
    body(i, localvars);
    body_rec(N, i + 1, localVars);
}

また

int body_rec(int N, int i, LocalVars& localVars)
{
    if (i == N) return localVars.res; // or any correct value
    body(i, localvars);
    if (localVars.end) { // break the "loop", and so stop the recursion.
        return localVars.res; // or any correct value
    }
    return body_rec(N, i + 1, localVars);
}

したがって、あなたの場合、slope再帰に渡すのを忘れています。

[編集]

完全なソリューション:

bool isConcave_r(int N, int i, double a[], int slope)
{
    if (i >= N) return true;

    const double delta = a[i] - a[i-1];

    if (slope > 0) {
        if (delta < 0) {
            slope = -1;
        }
    }
    else if (delta > 0) {
        return false;
    }
    return isConcave_r(N, i + 1, a, slope);
}

bool isConcave(double a[], int n)
{
    int i = 1;
    int slope = 1;
    return isConcave_r(n, i, a, slope);
}

また、名前が「正しくない」ように見えることに注意してください。「曲線」が凹状であるかどうかを確認しないでくださいdelta == 0。具体的に説明する必要がある場合...

于 2013-10-15T10:47:04.483 に答える
0

In the iterative version of your program, the computation moves from 1 to n-1, but in the recursive version computation moves form n-1 to 1. So, instead of tail recursion, use head recursion. And slope should be static variable. So, declare slope as static variable. It will work.

于 2013-10-15T10:57:51.903 に答える