CodeVS Problem 01 – Cantor表

Cantor表
现代数学的著名证明之一是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,…

输入描述 Input Description
整数N(1≤N≤10000000)

输出描述 Output Description
表中的第N项

样例输入 Sample Input
7

样例输出 Sample Output
1/4

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
// 制定移动规律
enum Direct {
	RIGHT = 1,
	LEFTDOWN = 2,
	DOWN = 3,
	RIGHTUP = 4
};

std::vector Locus(int step) {
	std::vector directs;
	int currentTime = 1;
	int l = 1;
	for (int i = 1; i <= step;) {
		if (l % 4 == 1) {
			// 右
			directs.push_back(RIGHT);
			i = i + 1;
		} else if (l % 4 == 3) {
			// 下
			directs.push_back(DOWN);
			i = i + 1;
		} else if (l % 4 == 2) {
			// 左下
			for (int j = 0; j < currentTime; j++) {
				directs.push_back(LEFTDOWN);
				i = i + 1;
				if (i == step + 1) {
					break;
				}
			}
			currentTime = currentTime + 1;
		} else if (l % 4 == 0) {
			// 右上
			for (int j = 0; j < currentTime; j++) { directs.push_back(RIGHTUP); i = i + 1; if (i == step + 1) { break; } } currentTime = currentTime + 1; } l = l + 1; } return directs; } int main() { // 定义默认 X = 1, Y = 1 int X = 1, Y = 1; int step = 0; cin >> step;
	std::vector directs = Locus(step - 1);
	for (int i = 0; i < directs.size(); i++) {
		Direct direct = directs[i];
		if (direct == RIGHT) {
			X = X + 1;
		} else if (direct == LEFTDOWN) {
			X = X - 1;
			Y = Y + 1;
		} else if (direct == DOWN) {
			Y = Y + 1;
		} else if (direct == RIGHTUP) {
			X = X + 1;
			Y = Y - 1;
		}
	}
	cout << Y << "/" << X;
}




欢迎留言

avatar
  Subscribe  
Notify of