L1 - 009 N 개수 구 합 (단순 동적 계획 + 최대 공약수 (알고리즘))
이 문제 의 요 구 는 매우 간단 하 다. 바로 N 개의 숫자 와 합 을 구 하 는 것 이다. 번 거 로 운 것 은 이 숫자 들 은 유리수 분자 / 분모 의 형식 으로 제 시 된 것 이 고, 당신 이 수출 한 것 도 유리수 의 형식 이 어야 한 다 는 것 이다.
입력 형식: 첫 줄 을 입력 하면 정수 N (≤ 100) 을 드 립 니 다. 다음 줄 은 형식 a1 / b1 a2 / b2... N 개의 유리 수 를 드 립 니 다. 문 제 는 모든 분자 와 분모 가 긴 정형 범위 내 에 있 음 을 보증 합 니 다. 또한 음수 의 기 호 는 반드시 분자 앞 에 나타 납 니 다.
출력 형식: 상기 숫자 와 가장 간단 한 형식 을 출력 합 니 다. 곧 결 과 를 정수 부분 점수 부분 으로 쓸 것 입 니 다. 그 중에서 점수 부분 은 분자 / 분모 로 쓰 고 분 자 는 분모 보다 작 으 며 공약수 가 없습니다. 결과 의 정수 부분 이 0 이면 점수 부분 만 출력 합 니 다.
입력 샘플 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
문제 풀이 방향:
이 문 제 는 정말 어렵 게 풀 었 다.
점수 계산 과 는 이에 따라 뒤로 누적 계산 을 중첩 하여 동적 계획 과 유사 합 니 다. 약분 알고리즘
//
int A=x,B=y,X;
while(B)
{
X=A%B;
A=B;
B=X;
}
x/=A;
y/=A;
//
/*int in = min(x,y);
for(int i=in;i>=2;i--)
if(x%i==0 && y%i==0)
{
x/=i;
y/=i;
}*/
판단 의 중첩 주의 판단 조건,% / 잘못 썼 습 니 다. 30 분 동안 검 사 했 습 니 다...
if(x<0)
{
x*=-1;
cout<전체 코드
#include
using namespace std;
int main()
{
int n;
int nn[100][100];
cin>>n;
for(int i=0;i>nn[i][0];
getchar();
cin>>nn[i][1];
}
int x=nn[0][0],y=nn[0][1];
for(int i=1;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
프로그램 실행 시간 을 어떻게 출력 합 니까?텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
