NYOJ 178 규칙 찾기 (Lagrange 플러그 인 공식)

링크: 여 기 를 클릭 하 십시오
제목:
묘사 하 다.
여러분 은 반드시 이런 문 제 를 본 적 이 있 을 것 입 니 다. 몇 가지 숫자 를 드 리 겠 습 니 다. 이 숫자 들 사이 의 규칙 을 찾 아 다음 에 이 규칙 을 만족 시 키 는 수 를 쓰 세 요.예 를 들 어 25, 10, 17, 26 은 이런 수가 n * n + 1 이라는 통 항 공식 에 부합 되 고 다음 수 는 37 임 을 알 수 있다.이런 통항 공식 은 하나 가 아니 기 때문에 답 은 유일한 것 이 아니다.그러나 N 개 수 를 알 고 있 고 통 항 공식 이 N 보다 적은 다항식 이라는 것 을 알 고 있다 면 답 은 유일 하 게 확정 된다.지금 당신 에 게 수열 을 하나 드 리 겠 습 니 다. 규칙 을 찾 아 다음 숫자 가 얼마 인지 구 해 주 시 겠 습 니까?
입력
첫 번 째 줄 은 정수 T 가 테스트 데 이 터 를 나타 내 는 그룹 수 (T < = 20) 입 니 다.
각 그룹의 테스트 데이터 의 첫 줄 은 하나의 정수 N (1 < = N < = 5) 이다.
다음 줄 에는 N 개의 정수 가 있 는데 이 수열 이 이미 알 고 있 는 N 개의 정수 (이 N 개의 정수 값 은 모두 1000 보다 크 지 않다) 를 나타 낸다.
출력
출력 이 규칙 에 맞 는 다음 수
샘플 입력
2
2
1 2
5
2 5 10 17 26

샘플 출력
3
37

사고방식: Lagrange 삽입 값 공식의 운용. 일종 의 이산 수학 적 방법: Lagrange 삽입 값 법 과 Newton 삽입 값 법 으로 실제 문제 에서 복잡 한 이산 데이터 만 제공 하 는 함수 값 구하 기 문 제 를 해결 하고 고찰 한 함 수 를 단순화 하여 이산 데이터 실제 함수 f (x) 에 대한 근사 함수 P (x) 를 구축한다.따라서 알 수 없 는 점 에서 나 온 함수 값 을 계산 할 수 있 고 삽입 값 법의 기본 적 인 사고방식 이다.
코드:
#include <math.h>
#include <queue>
#include <deque>
#include <vector>
#include <stack>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>

using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
const double eps = 1e-6;
const double Pi = acos(-1.0);
static const int inf= ~0U>>2;
static const int maxn =110;
int in[100],out[100],Map[200];
int T,i,j,n;
double  lagrange(double x,int n)             //    
{
    double xy[5][5];
    for(int i=0; i<n; i++)                  //     
    {
        xy[i][0]=i+1;
        cin>>xy[i][1];
    }
    double lag=0.0;
    for(int i=0; i<n; i++)
    {
        double ji=1.0;
        for(int j=0; j<n; j++)
        {
            if(i!=j)
                ji=ji*((x-xy[j][0])/(xy[i][0]-xy[j][0])); //   
        }
        lag=lag +ji* xy[i][1];                         //   

    }
    return lag;
}
int  main()
{
    //freopen("Intput.txt","r",stdin);
    //freopen("Output(2).txt","w",stdout);
    cin>>T;
    while(T--)
    {
        cin>>n;
        cout<<lagrange(n+1,n)<<endl;
    }
    return 0;
}


When you want to give up, think of why you persist until now!

좋은 웹페이지 즐겨찾기