cantor 의 수치 표
아래 수열, 앞의 5 항 은 각각 1 / 1, 1 / 2, 2 / 1, 3 / 1, 2 / 2...n 을 입력 하고 n 번 째 항목 을 출력 합 니 다.
1/1 1/2 1/3 1/4 1/5
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1
샘플 입력
3
14
7
12345
샘플 출력
2/1
2/4
1/4
59/99
【 알고리즘 】
먼저 문제 가 어떤 규칙 에 따라 배열 되 는 지 알 아야 한다. 먼저 사선 을 누 른 다음 에 하나의 사선 이 위 에서 아래로, 다른 사선 이 아래 에서 위로 교차 하 는 것 이다.
그 다음 에 i 조 사선 을 분석 하면 i 개의 수가 있 고 앞의 i 조 사선 은 모두 S (k) = 1 + 2 + 3 + · · + k = k (k + 1) / 2 개의 수가 있다.
n 은 어느 사선 에 있 습 니까?n < = S (k) 를 최소 정수 k 로 찾 으 면 n 은 k 조 사선 의 두 번 째 또는 마지막 S (k) - n + 1 개의 요소 입 니 다.
k 조 사선 의 i 번 째 요 소 는 i / (k + 1 - i) 이 고 마지막 i 번 째 요 소 는 (k + 1 - i) / i 이다.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int k=(int)floor((sqrt(8.0*n+1)-1)/2-1e-9)+1;
// k (1+k)*k/2>n
// k
//k>=-1+sqrt(1+8n)/2
//
int sum=(1+k)*k/2;
printf("%d/%d",sum-n+1,k+1-(sum-n+1));
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.