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

我们直接上例题！

栗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，我很乐意为您解答！

我们下次见！