P1014 [NOIP1999 普及组] Cantor 表

题目链接https://www.luogu.com.cn/problem/P1014

目录

 题目描述

输入输出样例

题解： 

下来我们展示代码：

（java代码）

（c语言代码）

---

 题目描述

---

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。

他是用下面这一张表来证明这一命题的：

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, …

…

我们以 Z 字形给上表的每一项编号。

第一项是 1/1，然后是 1/2，2/1，3/1，2/2，…

 

输入格式 

---

整数N（1≤N≤10000000）

---

输出格式：

---

表中的第N项

输入输出样例

---

输入样例#1：

7

---

输出样例#1：

1/4

题解： 

---

表的初始样子 
1/1     1/2      1/3      1/4     1/5
2/1     2/2      2/3      2/4     2/5
3/1     3/2      3/3      3/4     3/5
4/1     4/2      4/3      4/4     4/5
5/1     4/2      3/3      2/4     1/5

此时我们并不好发现规律。

。

于是我们按着题目提示重新排序

排序过后 
1/1     
1/2   2/1    
3/1   2/2     1/3    
1/4   2/3     3/2    4/1    
5/1   4/2     3/3    2/4    1/5

经过排序后可知，奇数行时分子由行数开始递减，分母由行数开始递增，偶数行反之

下来我们展示代码： （java代码）

public class Main {

    public static void main(String[] args) {

        Scanner scanf = new Scanner(System.in);
        int n = scanf.nextInt();
        //表示行
        int i = 0;
        //表示共有多少个
        int j = 0;
        //先确定在第几行
        //当j大于或等于n时就可以确定n在第几行
        while (n > j) {

            i++;
            j += i;
        }
        //1.确定在倒数的第几个(画图并找规律)  (j-n+1)
        //2.确定正数第几个，注意行数加一就是这一行分子分母的和
        //3.奇数行与偶数行规律相反
        if (i % 2 == 0) {

            System.out.printf("%d/%d\n", i - j + n, j - n + 1);
            //（i+1）-（j-n+1）=i-j+n
        }
        if (i % 2 != 0) {

            System.out.printf("%d/%d\n", j - n + 1, i - j + n);
        }
    }
}

（c语言代码）

#define _CRT_SECURE_NO_WARNINGS
#include 
int main()
{
	int n;
	int i=0, j=0;
	scanf("%d", &n);
	while (n > j)
	{
		i++;
		j = j + i;
	}
	if (i % 2 == 0)
		printf("%d/%d", i-(j-n), j - n+1);
	if (i % 2 != 0)
		printf("%d/%d", j - n + 1, i - (j - n));
	return 0;
}