PTA (7) N 개수 구 합

데이터 구조 (21)
데이터 구조 와 알고리즘 과정 에서 얻 은 소감 과 지식 점 의 정 리 를 배 워 서 제 가 직접 찾 을 수 있 고 여러분 과 함께 교류 할 수 있 기 를 바 랍 니 다.
- N 개 수 를 합 쳐 -
1. 제목 설명
이 문제 의 요 구 는 매우 간단 하 다. 바로 N 개의 숫자 를 구 하 는 것 이다.번 거 로 운 것 은 이 숫자 들 은 유리수 분자 / 분모 의 형식 으로 제 시 된 것 이 며, 당신 이 수출 한 것 과 유리수 의 형식 이 어야 한 다 는 것 이다.
1.1 입력 형식:
첫 줄 을 입력 하여 정수 N (≤ 100) 을 드 립 니 다.이 어 한 줄 은 격식 a1/b1 a2/b2... 에 따라 N 개의 유리 수 를 제시 했다.제목 은 모든 분자 와 분모 가 장정 형 범위 내 에 있 음 을 보증한다.또 음수 의 기 호 는 반드시 분자 앞 에 나타난다.
1.2 출력 형식:
상기 숫자 와 가장 간단 한 형식 을 출력 합 니 다. 곧 결 과 를 정수 부분 점수 부분 으로 쓸 것 입 니 다. 그 중에서 점수 부분 은 분자 / 분모 로 쓰 고 분 자 는 분모 보다 작 으 며 공약수 가 없습니다.결과 의 정수 부분 이 0 이면 점수 부분 만 출력 한다.
1.3 샘플 입 출력
입력 샘플 1: 5 2 / 5 4 / 15 1 / 30 - 2 / 60 8 / 3 출력 샘플 1: 3 1 / 3 입력 샘플 2: 2 4 / 3 2 / 3 출력 샘플 2: 2 입력 샘플 3: 3 1 / 3 - 1 / 6 1 / 8 출력 샘플 3: 7 / 24
2. 코드 구현
c
#include
#include
long sum_int,sum_son,sum_mom;

long gongyinshu(long mom1,long mom2)
{
    long m1=mom1,m2=mom2,ys;
    while(m2!=0)
    {
        ys=m1%m2;
        m1=m2;
        m2=ys;
    }
    return m1;
}

int main()
{
	int a;
	long c,d;
	scanf("%d",&a);
	long num[a][2];
	for(int i=0;i<a;i++)
    {
        scanf("%ld/%ld",&c,&d);
        if(d==0)
        {
            i--;
            break;
        }
        num[i][0]=c;
        num[i][1]=d;
    }

    long gbs,gys;//   、   
    sum_int=0;
    sum_son=num[0][0];
    sum_mom=num[0][1];

    for(int i=1;i<a;i++)
    {
        if(num[i][1]==sum_mom)
            sum_son=sum_son+num[i][0];
        else
        {
            gys=gongyinshu(num[i][1],sum_mom);
            gbs=num[i][1]*sum_mom/gys;
            num[i][0]=num[i][0]*(gbs/num[i][1]);
            sum_son=sum_son*(gbs/sum_mom)+num[i][0];
            sum_mom=gbs;
        }
    }
    if(sum_son>sum_mom)
    {
        sum_int=sum_son/sum_mom;
        sum_son=sum_son%sum_mom;
    }
    if(sum_int==0 && sum_son==0)
        printf("0");
    if(sum_int!=0)
        printf("%ld",sum_int);
    if(sum_son!=0)
    {
        gys=gongyinshu(sum_mom,sum_son);
        sum_son=sum_son/gys;
        sum_mom=sum_mom/gys;
        if(sum_int!=0)
            printf(" %ld/%ld",sum_son,sum_mom);
        else
            printf("%ld/%ld",sum_son,sum_mom);
    }

	return 0;
}

3. 코드 설명
이 단락 코드 는 기본적으로 테스트 점 을 통과 할 수 있 습 니 다. 만약 에 테스트 점 이 '답 오류' 나 '부동 소수점 오류' 를 잘못 보고 하면 이 테스트 점 의 테스트 데이터 에서 점수 의 분자 분모 자릿수 가 너무 커서 공 배수 에 직접 곱 한 전체 연산 이 log 의 크기 를 초과 한 것 일 것 입 니 다. 해결 방법 은 뒤의 간단 한 부분 (순환) 을 해결 하 는 것 입 니 다.입력 의 순환 에 직접 병합 합 니 다.이렇게 하면 한 쪽 의 공배수 와 연산 을 입력 하면 서 간단하게 가산 한 후의 점 수 를 입력 할 수 있 으 며, 이렇게 하면 전체 계산 과정 이 롱 의 크기 를 초과 하지 않도록 확보 할 수 있다.

좋은 웹페이지 즐겨찾기