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

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

新規登録して質問してみよう
ただいま回答率
85.48%
セグメンテーション違反

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

C++

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

Q&A

解決済

7回答

8002閲覧

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

waya

総合スコア20

セグメンテーション違反

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

C++

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

0グッド

0クリップ

投稿2017/03/01 03:55

編集2017/03/01 04:03

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

c++

1#define ffor(i,a,b) for (int i=(a);i<(b);i++) 2#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--) 3#define rep(i,n) for (int i=0;i<(n);i++) 4#define rrep(i,n) for (int i=(n)-1;i>=0;i--) 5#include<iostream> 6#include<iomanip> 7#include<algorithm> 8#include<cmath> 9#include<string> 10#include<stack> 11#include<queue> 12#define SIZE 10000001 13#define MOD 1000000007 14#define INF 100000000 15using namespace std; 16 17int memo[SIZE]; 18int s = 10007; 19int func(int n){ 20 if(n == 3) return 1; 21 if(n <= 2) return 0; 22 if(memo[n] != 0) return memo[n]; 23 24 return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s; 25} 26 27int main(){ 28 int n; 29 cin >> n; 30 31 cout << func(n) << endl; 32 33 return 0; 34} 35

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答7

0

ベストアンサー

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

幸い、今回の設計の場合は隙間なく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/01 06:09

編集2017/03/01 07:02
haru666

総合スコア1591

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/02 00:15

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

2017/03/02 00:28

そうです。 このメソッドは再帰呼び出しをしていますが、バッファ(memo[n])に計算結果を記録していて、記録済みの値の呼び出し時はネストがありません。そのため、下から呼び出していくと常に呼び出しの深さは1回にしかならないため、スタックが消費されません。 こういう書き方ができるかどうかは計算内容にもよりますが、nが整数値の場合は比較的やりやすいです。
waya

2017/03/02 08:34

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

0

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

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

投稿2017/03/01 04:16

編集2017/03/01 04:17
ardin

総合スコア544

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/01 04:19

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

2017/03/01 04:21

昔の SPARC 上の HP-UX で、確保してないはずの領域にアクセスできた、って逆の例もありました。 ※int buffer[10] なのに buffer[15] とかに正常にアクセスできる あとはまったのだと、確保する領域の計算を間違えて malloc(0) を発行したとき……これ、null が返ってこない(正常に確保できたように見える)くせに、アクセスした瞬間に segmentation fault 起こすという嫌な動きをしてくれたことが。
waya

2017/03/01 04:31

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

2017/03/01 04:36

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

2017/03/01 04:37

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

0

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

投稿2017/03/01 04:12

catsforepaw

総合スコア5938

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/01 04:20

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

0

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

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

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

投稿2017/03/01 04:04

編集2017/03/01 04:11
tacsheaven

総合スコア13703

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/01 04:24

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

0

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

C++

1 2int* memo; 3int s = 10007; 4int func(int n){ 5 if(n == 3) return 1; 6 if(n <= 2) return 0; 7 if(memo[n] != 0) return memo[n]; 8 9 return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s; 10} 11 12int main(){ 13 int n; 14 cin >> n; 15 memo = new int[n](); 16 17 cout << func(n) << endl; 18 19 delete[] memo; 20 return 0; 21}

投稿2017/03/01 04:08

masaya_ohashi

総合スコア9206

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/01 04:21

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

0

こんにちは。

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

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

投稿2017/03/01 04:00

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/01 04:04

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

2017/03/01 04:08 編集

了解です。やってみました。スタックオーバーフローと思います。 再帰呼び出しが深くなりすぎてスタックが足りなくなっているようです。 再帰呼び出しは深さがあまり深くならないことを保証できるケースでのみ使用した方がよいです。 なので、このケースでは頑張ってループに展開した方がよいと思います。
waya

2017/03/01 04:27

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

2017/03/02 08:45

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

0

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

投稿2017/03/01 03:58

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

waya

2017/03/01 04:00

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.48%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問