cantor 의 수치 표

2583 단어
제목 설명
아래 수열, 앞의 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;

}

좋은 웹페이지 즐겨찾기