2

私は、2パラメーターバージョンと3パラメーターバージョンの両方でアッカーマンのアルゴリズムを計算するシステムの機能について学習しています。mとnの値が非常に小さい場合、私のシステムはA0およびA1メソッド呼び出しから返される結果を計算して出力します。ただし、3または4を超えるものは返されず、atmを使用している端末がフリーズします。私の問題は、私のマシンが計算できるmとnの値を決定することです。

私はスタックオーバーフローをキャッチするためにいくつかのことを試みました。c++にはキャッチできるstackoverflowexceptionがないことを私は知っています。try-catchブロックは機能しません。以下のコードでは、getrlimit（）を使用してスタック制限を見つけ、メインのgStackRefにアドレスの場所を作成します。gStackLimitへのローカル変数ポインターを再帰的にチェックするcheckStackを呼び出します。

再帰メソッドに関連してスタックの使用状況をチェックするより良い方法はありますか？また、セグメンテーション違反をチェックしますか？UNIX端末で実行していることをお知らせします。 

#include <cstdlib>
#include <iostream>


#define _XOPEN_SOURCE_EXTENDED 1
#include <sys/resource.h>

int getrlimit(int resource, struct rlimit *rlp);

using namespace std;

int * gStackRef;
int gStackLimit;

void checkStack(void);

int main(int argc, char *argv[])
{
        int temp = 0;
        gStackRef = &temp;
        rlimit myl;
        getrlimit(RLIMIT_STACK, &myl);
        gStackLimit = (myl.rlim_cur / 3 * 8 / 10) ;/* modified for segment fault */
        cout << gStackLimit << "\n";
        checkStack();
}

void checkStack()
{
        int temp = 0;
        int* pVariableHere = &temp;
        size_t stackUsage = gStackRef - pVariableHere;
        printf("Stack usage: %d / %d \n", stackUsage, gStackLimit);
        if(stackUsage > gStackLimit) return;
        else checkStack();
}
4

2 に答える 2

2

ただし、3または4を超えるものは返されず、atmを使用している端末がフリーズします。

それがアッカーマン関数のポイントのようなものです。それは非常に急速に成長します。m >= 4とn >= 3、再帰的に計算している場合、死ぬA(m, n)前に関数が戻るとは思えません。

私はスタックオーバーフローをキャッチするためにいくつかのことを試みました。c++にはキャッチできるstackoverflowexceptionがないことを私は知っています。

もちろん違います。プロセスはスタックスペースが不足しています。すぐに取り壊す必要があります。

再帰メソッドに関連してスタックの使用状況をチェックするより良い方法はありますか？

再帰を使用する必要がある場合は、スタックスペースではなくヒープに割り当てられる独自のスタックデータ構造を作成して、手動で行います。これを使用して、再帰のどこにいるかを追跡します。ネストされたメソッド呼び出しによって再帰するのではなく、プッシュしてポップし、再帰しながら。

しかし、結局のところ、とにかくアッカーマンを計算するために再帰を使用するべきではありません。

于 2011-09-27T18:36:29.617 に答える
0

私はスタックオーバーフローをキャッチするためにいくつかのことを試みました。c++にはキャッチできるstackoverflowexceptionがないことを私は知っています。try-catchブロックは機能しません。以下のコードでは、getrlimit（）を使用してスタック制限を見つけ、メインのgStackRefにアドレスの場所を作成します。gStackLimitへのローカル変数ポインターを再帰的にチェックするcheckStackを呼び出します。

POSIXには、スタックオーバーフローを検出する「安全な」方法がありません。スタックオーバーフローはSIGSEGVシグナルを発生させますが、これらは一般的なセグメンテーション違反を示しているため、（一般的に）キャッチすべきではありません。これにより、プログラムがクラッシュする可能性があります。Windows環境では、-を使用してスタックオーバーフローを安全に処理できEXCEPTION_STACK_OVERFLOWますが、そのような場合、Windowsが実行しているのは、スタックの最後にガードページを配置し、SEHで通知することだけです。（SEH例外を無視した後）ガードページを使い切ると、プログラムは終了します（POSIX-landの場合と同じように）。

再帰メソッドに関連してスタックの使用状況をチェックするより良い方法はありますか？また、セグメンテーション違反をチェックしますか？UNIX端末で実行していることをお知らせします。

いいえ。あなたがしていることでさえ、未定義の振る舞いをしています。一部のマシンでは、スタックが大きくなります。一部のマシンでは、スタックが大きくなります。コンパイラーは、2つのメソッドの間に任意の量のスロップスペースを挿入できます。技術的には、コンパイラは、2つの完全に異なるメモリセグメントに配置された2つの別個のスタックがあり、それでも準拠しているようなものを実装できます。

スタックセーフな方法でAckermannを計算する場合は、ヒープから割り当てられた明示的なスタック構造を使用するか、動的計画法を使用します。

于 2011-09-27T18:37:09.463 に答える