列表

详情


NC16785. [NOIP1999]Cantor表

描述

现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的:

 我们以Z字形给上表的每一项编号。第一项是1/1,然后是1/2,2/1,3/1,2/2,…


输入描述

整数N(1≤N≤10000000)

输出描述

表中的第N项

示例1

输入:

7

输出:

1/4

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

Pascal(fpc 3.0.2) 解法, 执行用时: 2ms, 内存消耗: 256K, 提交时间: 2019-07-29 08:59:49

var
a,i,n:longint;
begin
read(n);
for i:=1 to 5000 do
 if a+i>=n then break else a:=a+i;
if i mod 2=0 then writeln(n-a,'/',i+1+a-n) else writeln(i+1+a-n,'/',n-a);
end.

C 解法, 执行用时: 2ms, 内存消耗: 316K, 提交时间: 2023-05-05 20:29:42

#include <stdio.h>
int main()
{int n,i=1;
scanf("%d",&n);
for(i=1;n>i;i++)
n-=i;
 if(i%2==0)
printf("%d/%d",n,i+1-n);
 else printf("%d/%d",i+1-n,n);
return 0;}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 360K, 提交时间: 2019-04-03 20:01:09

#include<stdio.h>
int main()
{
	int i,j=0,s=0,n;
	scanf("%d",&n);
	while(s<n){
		j++;
		s=s+j;
	}
	i=n-(s-j);
	printf("%d/%d",(j+1-i),i);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 2ms, 内存消耗: 376K, 提交时间: 2020-10-07 07:57:57

#include<cstdio>
main()
{
	int n,t;scanf("%d",&n);
	for(t=1;n>t;t++)n-=t;
	if(t%2)printf("%d/%d",t-n+1,n);
	else printf("%d/%d",n,t-n+1);
}

Python3 解法, 执行用时: 44ms, 内存消耗: 4556K, 提交时间: 2022-10-26 17:45:59

N = int(input())
t = 1
while N-t > 0:
    N = N-t
    t += 1
if t%2 == 0:
    print("%d/%d"%(N,t-N+1))
else:
    print("%d/%d"%(t-N+1,N))

上一题