런타임 오류가 나옵니다 roots문제

  • kksuhj
    kksuhj 
    RTE (SIGSEGV: segmentation fault, probably incorrect memory access)

    라는 오류가 나옵니다.

    roots문제를 푸는 중에 나왔는데요

    visual studio에서 돌릴때는 아무 이상이 없던 것이

    채점시에 문제가 되네요

    코드는 아래와 같습니다.. 

    #include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

int testcase,n;
vector<double> poly;
const double limit=10;

void input()
{
    vector<double> empty;
    double temp;

    poly=empty;

    cin>>n;
    for(int i=0;i<n+1;i++)
    {
        cin>>temp;
        poly.push_back(temp);
    }   
}

vector<double> differentiate(const vector<double>& p)
{
    vector<double> dif;
    for(int i=0;i<n;i++)
        dif.push_back( (n-i)*p[i] );
    return dif;
}

vector<double> solveNaive(const vector<double>& p)
{
    vector<double> ret;

    //1차식
    if(p.size()==2)
    {
        ret.push_back(-p[1]/p[0]);
    }else if(p.size()==3)//2차식
    {
        double a=p[0],b=p[1],c=p[2];
        ret.push_back( (-b+sqrt(pow(b,2)-4*a*c))/(2*a) );
        ret.push_back( (-b-sqrt(pow(b,2)-4*a*c))/(2*a) );
    }
    sort(ret.begin(),ret.end());
    return ret;
}

double eval(const vector<double>& p, double x)
{
    double ret=0;
    for(int i=0; i<=n ;i++)
        ret+=pow(x,n-i)*p[i];
    return ret;
}

vector<double> solve(const vector<double>& p)
{
    int degree=p.size()-1;

    if(degree<=2) return solveNaive(p);
    vector<double> ret;
    vector<double> derivative = differentiate(p);
    vector<double> sols = solve(derivative);

    sols.insert(sols.begin(),-limit-1);
    sols.insert(sols.end(),limit+1);

    for(int i=0;i<sols.size()-1;i++)
    {
        double x1=sols[i],x2=sols[i+1];
        double y1=eval(p,x1),y2=eval(p,x2);

        if(y1*y2>0) continue;
        if(y1>y2) {swap(y1,y2); swap(x1,x2);}

        for(int i=0;i<100;i++)
        {
            double mx=(x1+x2)/2;
            double my=eval(p,mx);

            if(y1*my<=0)
            {
                x2=mx;
                y2=my;
            }else
            {
                x1=mx;
                y1=my;
            }
        }
        ret.push_back( (x1+x2)/2 );
    }
    sort(ret.begin(),ret.end());
    return ret;
}

int main()
{
    cin>>testcase;
    while(testcase--)
    {
        input();
        vector<double> ret(solve(poly));// 이 부분에서 문제인듯 합니다. 
        for(int i=0;i<ret.size();i++)
            printf("%.8f",ret[i]);
    }
    return 0;
}

    마지막에 메인에서 vector ret(solve(poly));에 문제가 있는 듯 한데 어떤식으로 고쳐야 할 지를 잘 모르겠습니다... 도움을 주세요 ㅠㅠ


    11년 전
2개의 댓글이 있습니다.
  • Signin
    Signin

    함수 differentiate()과 eval()에서,
    반복문 도는 횟수가 항상 n으로 고정되어 문제가 생기는 것 같습니다.

    처음 인풋이 5차식으로 들어와도, 극대/극소 위치를 구하기 위해서
    식을 미분하다 보면, 차수가 점점 줄어들게 됩니다.

    이 경우에 주어진 식은 3차식(원소 4개인 vector)인데
    반복문은 5번 돌게 되고, 따라서 존재하지 않는 p[4]를 참조하게 됩니다.

    각 함수의 n을 p.size()-1로 바꿔주시면 에러가 나지 않을 것 같습니다.


    11년 전 link
  • kksuhj
    kksuhj

    감사합니다. ㅜㅜ 혼자서 터득해야 하는데 이렇게 힘을 빌리네요 ㅠㅠ


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.