NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2

  1. 云栖社区>
  2. 博客>
  3. 正文

NOIP-C++大神培养计划 Step1.1.2基础算法——模拟算法2

小笨笨qaq 2018-11-23 22:07:24 浏览489
展开阅读全文

大家好,我是小笨笨,今天我们继续来讲解模拟算法。

我们直接上例题!

栗1.1.2-1 洛谷P1014 Cantor表
https://www.luogu.org/problemnew/show/P1014
题目描述
现代数学的著名证明之一是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

这也是模拟中的一道经典例题,看完了题目,大家对数据范围有什么感觉吗?我想是有的,如果没有,就再看看,10^7,就意味着这里只能用时间复杂度为O(n)的算法。(这里的时间复杂度我们将在下一节课讲到)。

我们对表中元素的访问是“Z”字形的,那么我们不妨来找找每一个点的访问顺序。

首先,我们要找到一个最小的i,使j>n(此处j为 i ! -阶乘-),i 的奇偶决定着斜线上数的顺序,n是第i条斜线上倒数第j-n+1个数,若i是偶数,第i条斜线上倒数第i个元素是(i+1-i)/i。

这个规律大家可以自己找一找,看一看,应该还是可以看出来的。

于是,我们就用代码来实现它:

#include<cstdio>
int main()
{
    int n,i=0,j=0;//前i条斜线一共j个数
    scanf("%d",&n);
    while(n>j)//找到最小的i使得j>=n
    {
        i++;
        j+=i;
    }
    if(i%2==1)
        printf("%d/%d",j-n+1,i+n-j);//i的奇偶决定着斜线上数的顺序,n是第i条斜线上倒数第j-n+1个数
    else
        printf("%d/%d",i+n-j,j-n+1);//若i是偶数,第i条斜线上倒数第i个元素是(i+1-i)/i
    return 0;
}

这也是AC代码啊。

不知大家在做完了这些模拟题后有没有觉得它很简单呢?
可以说简单,也可以说难。
大家可以在
https://www.luogu.org/problemnew/lists?name=&orderitem=pid&tag=1&content=0&type=
做一些模拟的题目,来提升自己的能力。

小笨笨有话说:
NOIP中,模拟是最常考的算法,也是最容易拿分的。NOIP满分600分,一般的弱省的省一分数线在200分左右,强省270左右,如果出到了模拟,最好就要拿下这题。因为这是最好拿的分,所以要尽量拿到。如果模拟拿了100分,其他的在拿100~200左右,省一就稳了。后面的100~200分该怎么拿,我们在后续课程中会教授这些内容。别性急,现在才刚刚开始。

希望大家能把模拟算法学扎实,也为今后的学习做铺垫。

好了,今天的内容就到这里,下次我们将讲到NOIP的重要知识点:时间复杂度,请大家务必好好看看,对其才有一定的认识。

如果大家有问题或者想和我讨论,可以加我的QQ:907916611,我很乐意为您解答!

我们下次见!

网友评论

登录后评论
0/500
评论
小笨笨qaq
+ 关注