質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • C++

    3443questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • セグメンテーション違反

    4questions

    セグメンテーション違反とは、ソフトウェア実行時に発生するエラーのひとつであり、許可されていないメモリにアクセスしたときに起きます。しばしば、ポインタの不適切な使用、またはバッファオーバーフローによって起こります。

セグメンテーションエラーが消えない

解決済

回答 7

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,682

waya

score 14

引数nから値を求める簡単なプログラムを作成しましたが、
以下のプログラムでセグメンテーション違反がでます。
大きな数字の用いた時にコアダンプが生じます。
lldbを用いてデバッグしたところ、
func関数の返り値のところでbreakしていました。
ここまではわかったのですが、ここから先の解決方法がわかりません。
ご回答よろしくおねがいいたします。

#define ffor(i,a,b) for (int i=(a);i<(b);i++)
#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#define SIZE 10000001
#define MOD 1000000007
#define INF 100000000
using namespace std;

int memo[SIZE];
int s = 10007;
int func(int n){
    if(n == 3) return 1;
    if(n <= 2) return 0;
    if(memo[n] != 0) return memo[n];

    return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s;
}

int main(){
    int n;
    cin >> n;

    cout << func(n) << endl;

    return 0;
}

追記
記入不足があり申し訳有りません。
SIZE以上の入力が出た時にコアダンプが出るという点は承知しております。
入力値が10^4程度だとエラーが出ないのですが、10^6くらいの値からエラーが出ます。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 7

checkベストアンサー

+2

今回の場合は再起呼び出し回数が多すぎることが最初の原因なので、そっちのパッチが大事かなと思います。コールスタックは有限なので…数字を増やすとリニアに呼び出し回数が増えるタイプの再帰呼び出しは考え方を変えないといけないかなと。

幸い、今回の設計の場合は隙間なくnの値が取られるので、再帰的じゃなくて、下から計算すればいいんじゃないかと思います。

#define SIZE 10000001
using namespace std;

int memo[SIZE];
int s = 10007;
int func(int n){
    if(n == 3) return 1;
    if(n <= 2) return 0;
    if(memo[n] != 0) return memo[n];

    return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s;
}

// ここから
int position = 4;
int func_invoker(int n){
    for(; position < n; position++)
    {
        func(position);
    }
    return func(n);
}
// ここを追加

int main(){
    int n;
    cin >> n;

    // func_invokerに処理を渡す
    // cout << func(n) << endl;
    cout << func_invoker(n) << endl;

    return 0;
}

この関数は現状のサンプルでは参照透過なので、予め決まったnの値に対応する辞書を生成しておくことによってメモリスペースと計算量をトレードオフにできます。
ファイルに全部書き出しておいてそこから値を引っ張ってきてもいいですし、等間隔に辞書で計算結果をもっておくことによって計算量の最大を固定することもできます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/02 09:15

    このような書き方で解決もできるんですね!勉強になります。
    一応確認なのですが、
    これはposition=4から計算する事でmemo[n]に値が保存されて、それを利用して計算できるから
    スタックオーバーフローが起きずに済むと言う解釈で大丈夫でしょうか?

    キャンセル

  • 2017/03/02 09:28

    そうです。
    このメソッドは再帰呼び出しをしていますが、バッファ(memo[n])に計算結果を記録していて、記録済みの値の呼び出し時はネストがありません。そのため、下から呼び出していくと常に呼び出しの深さは1回にしかならないため、スタックが消費されません。

    こういう書き方ができるかどうかは計算内容にもよりますが、nが整数値の場合は比較的やりやすいです。

    キャンセル

  • 2017/03/02 17:34

    なるほど!わざわざ例まで出していただき、ありがとうございました!
    簡単なプログラムですが、色々と勉強になりました・・・。考えてプログラムを書けるように頑張ります。

    キャンセル

+1

Segmentation Fault が出たならば、たいていは配列の添え字オーバーです。
と考えると、そもそも memo[10000001] が確保しきれてない可能性があります。

単純計算で、int = 4byte の環境だと仮定して、38MB 超ですか。
ヒープ領域に確保されているはずですが、ヒープがそこまで大きくないのかもしれませんね。
malloc で動的に確保するようにして、失敗するかどうか確認してみるのもいいかもしれません。

(追記)
あともう一つ、スタック領域が足りない可能性がありますか。
memo[] は初期状態で 0 クリアされているでしょうから、その場合 func(X)を考えると、再帰の段数はX-3 になるはずです。(最初に func(X-1) を呼び出し、さらにそこから func(X-2) を呼び出し…となる)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/01 13:24

    わかりやすい回答ありがとうございます!
    スタックオーバーフローを起こしているようで、別の書き方で取り組んでみます。
    アドバイスありがとうございます!

    キャンセル

+1

スタックオーバーフローを起こしているのではないでしょうか。スタック領域の上限サイズは処理系にもよりますが、100万階層もの再帰呼び出しは多すぎのように思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/01 13:20

    別の書き方で取り組んでみます。呼び出しが深すぎたようです・・・・。
    アドバイスありがとうございましす!

    キャンセル

+1

memo[n]って初期化していないが何が入っているのだろうか
それと、終わるまでがすごい長そうだけれど、スタックがすごい積まれそう。
そしてスタックオーバーフローにならないだろうか

tacsheavenさんも書いていますが、int memo[SIZE];は予定通り確保できない可能性がありますね
昔、自分もかなり大きな配列用意しようとしてうまくいかなかった記憶があります。
そこにアクセスした瞬間落ちたような(...ちょっと記憶があいまいです)

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/01 13:19

    グローバル変数として定義している場合は0に初期化されたと思います。
    競技プログラミングのためにSIZEで値を定義してこの値で毎回プログラムを書いていましたが、やはり動的確保をした方が良さそうですね・・・。
    スタックオーバーフローを起こしているようなので、別の書き方で取り組んでみます。
    アドバイスありがとうございます!

    キャンセル

  • 2017/03/01 13:21

    昔の SPARC 上の HP-UX で、確保してないはずの領域にアクセスできた、って逆の例もありました。
    ※int buffer[10] なのに buffer[15] とかに正常にアクセスできる

    あとはまったのだと、確保する領域の計算を間違えて malloc(0) を発行したとき……これ、null が返ってこない(正常に確保できたように見える)くせに、アクセスした瞬間に segmentation fault 起こすという嫌な動きをしてくれたことが。

    キャンセル

  • 2017/03/01 13:31

    逆の例、初めて聞きました。笑
    やはり他の人のエラーを聞くと非常に勉強になりますね・・・!
    配列の扱いでしょっちゅうエラーを起こしてしまうので慣れるまで頑張ります。

    キャンセル

  • 2017/03/01 13:36

    あれ、HP-UX だったか Solalis だったか曖昧(汗 メモリ確保がブロック単位に切りあがってたようで、ブロックの末尾までは使える、という豪快なメモリ管理で(w

    キャンセル

  • 2017/03/01 13:37

    そうか。グローバル変数だと0初期化でしたか。

    >tacsheaven さん
    確かにうまくいくこともありますね。
    ただいつも上手くいくとは限らず、別のところでコード書き換えた際にだめになることもあり、
    原因特定に時間がかかることも・・・
    (つまり、たまたま空いていたのでアクセスしてもエラーにならないだけで、
    次のビルド(またはコンパイル)時に埋まってしまってアウト)

    キャンセル

0

大きな数字ってどのくらい? SIZEを超えてたらふっ飛ぶのはアタリマエだけど。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/01 13:00

    10^6位からエラーが出ます。例えば999999でエラーが出ます。

    キャンセル

0

こんにちは。

大きな数字の用いた時にコアダンプが生じます。

SIZE以上の数字を指定するとコアダンプになってもおかしくないです。
nにはSIZE(10000001)未満の値を指定すれば大丈夫なはずです。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/01 13:04

    記入漏れがあり申し訳有りません。
    SIZE以下の入力でセグメンテーション違反が起きてしまいます。
    例えば10^6でエラーが生じます。

    キャンセル

  • 2017/03/01 13:08 編集

    了解です。やってみました。スタックオーバーフローと思います。
    再帰呼び出しが深くなりすぎてスタックが足りなくなっているようです。

    再帰呼び出しは深さがあまり深くならないことを保証できるケースでのみ使用した方がよいです。
    なので、このケースでは頑張ってループに展開した方がよいと思います。

    キャンセル

  • 2017/03/01 13:27

    毎度わかりやすい回答ありがとうございます!
    スタックオーバーフローを起こしているみたいですね・・・。書き方を変えて取り組んでみます。
    最近なんとなくプログラミングの練習をして来たツケが回って来てエラーに苦労しています・・・。地道に穴を埋めていけるように頑張ります。

    キャンセル

  • 2017/03/02 17:45

    ツケと言うよりは、これは誰もが一度は通る道かも。初期の頃に経験できたのであれば幸運ですよ。
    頑張ってください。

    キャンセル

0

配列として定義する変数の長さの最大はOSやコンパイラによってまちまちです。10000001という配列の長さは確保できる保証はないです。一般的に巨大な配列を定義する場合、配列変数で定義するのではなく、動的メモリ確保でその大きさ分の領域を確保します。

int* memo;
int s = 10007;
int func(int n){
    if(n == 3) return 1;
    if(n <= 2) return 0;
    if(memo[n] != 0) return memo[n];

    return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s;
}

int main(){
    int n;
    cin >> n;
    memo = new int[n]();

    cout << func(n) << endl;

    delete[] memo;
    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/03/01 13:21

    競技プログラミングのために毎度この書き方で使用しておりましたが、
    普段プログラムを書くときは動的確保を行なった方が良さそうですね・・・。徐々に直していきたいと思います。
    アドバイスありがとうございます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3443questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • セグメンテーション違反

    4questions

    セグメンテーション違反とは、ソフトウェア実行時に発生するエラーのひとつであり、許可されていないメモリにアクセスしたときに起きます。しばしば、ポインタの不適切な使用、またはバッファオーバーフローによって起こります。