算法题——Cantor表
2024-09-07 08:53:03
题目介绍
描述
现代数学的著名证明之一是 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 <=10^7)
输出格式
表中的第N项
样例
输入:
7
输出:
1/4
分析
规律
我们通过题目可知,在Cantor表中走法为Z字形
不妨将Cantor表转化为下图
即
从左往右数
奇数行分母依次递增,分子依次递减
偶数行分母依次递减,分子依次递增
可知奇偶数行分子分母规律正好相反
所以为使奇偶数行变化规律一致并且符合题中所给的项数规律,我们可以规定
在上图中,奇数行从左往右数,偶数行从右往左数
找查
例如我们要找查第7项,前三行一共有6项,前4行一共有10项
很显然 6 < 7 < 10
所以我们可以很方便地确定第7项在第4行中
又
前几行项数 - 所要找的项数 = 所要找的项所在行的最后一项分子 - 所找项分子
同理
前几行项数 - 所要找的项数 = 所找项分母 - 所找项所在行最后一项分母
这两个等式中我们分别知道任意三个量就可以求其中的第四个量
然后,我们继续根据规律确定第7项的具体的值为 1/4
最后,我们可以轻易得出求任意项的算法如下
解法
以下是笔者的解题方法
先上代码
#include <iostream>
using namespace std;
int main()
{
int n = 0, sum = 0, i = 1;
cin >> n;
while(sum < n)
{
++i; //这里一定要让i先自增再求和,否则求出来的和少一项(此处的项指的是等差数列的项)
sum = i*(i - 1)/2; //首项公差均为1的等差数列求和,此处的和为第i行为止的Cantor表的总项数
}
//总项数与所找项的项数的差
int dif = sum - n;
if((i - 1) % 2 != 0)
//如果i-1行为奇数,那么i行为偶数行,偶数行从右开始数(这里在写的时候绕了个弯)
cout << 1 + dif << "/" << i - 1 - dif;
else
//第i行为奇数行,从左边数
cout << i - 1 -dif << "/" << 1 + dif;
}
最新文章
- 【Win 10 应用开发】在App所在的进程中执行后台任务
- node-webkit 桌面开发 初入1
- SQLServer:删除log文件和清空日志的方法
- ios二维码生成
- UML学习笔记1
- Elasticsearch查询
- 洛谷P1736 创意吃鱼法
- 快速开始使用Graph-tool - gt文件格式
- Oracle 过程控制语句整理
- 内存映射mmap
- bootstrap-内联表单 水平(横向)表单 响应式图片 辅助类 [转]
- Unity3D 获得GameObject组件的方法
- Zepto源码笔记(一)
- 全国计算机等级考试二级教程-C语言程序设计_第9章_数组
- smarty模板调数据库并做添加删除修改和分页
- python爬虫从入门到放弃前奏之学习方法
- 洛谷SP22343 NORMA2 - Norma(分治,前缀和)
- 腾讯出品的一个超棒的 Android UI 库
- Python Web Service
- Ajax详细剖析