蓝桥备赛|常用算法之模拟法

vlambda
2022-03-25

蓝桥备赛|常用算法之模拟法

模拟法

模拟法是打比赛时的一种常用方法，使用各种算法大多都离不开模拟，而对于蓝桥杯只要结果的的填空题是一个非常好的解决方案，而且对于蓝桥杯数论部分需要找规律的题目来说，模拟法是一个非常有用的方法。

今天我们来根据蓝桥杯真题讲解模拟法：

2020年省赛：

题目描述：本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。例如3/4,1/8,7/1都是既约分数请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？运行限制 1. 最大运行时间：1s 2.最大运行内存：128M

题目解析

我们看到这种题，现在一眼就知道只是到纯暴力的题目，即暴力枚举然后依据题目要求模拟即可。

但是这种简单题在比赛中是来送分的，我们要花很少的时间做完，才有时间做其他的题目，这就要求我们对这种题目的熟练度极高，要做到，看到题目，想到思路手里能直接写出来才可以。

这里有一个巧妙的方法是因为分子与分母是对称的我们可以少枚举一半，不过有些同学可能没想明白，没关系，我们用普通的办法，只要能够快速的编程并找到答案，思路正确性能够保证的话，其他的都是可有可无的。

这题目我们首先要两个数是否互质，即最小公约数为 1，我们就定义一个 gcd() 求最小公约数的算法，这里我们采用的是递归的方法。

一般我们按照如下写法。

int gcd(int a,int b){ return a%b?GCD(b,a%b):b;}
//或者int gcd(int a,int b){ int temp;    while(b){     /*利用辗除法，直到b为0为止*/ temp = b; b = a % b; a = temp; } return a;}

有了gcd这个函数，这个题目我们就可以进行枚举了。外层循环为 a，假设是分母，内层循环是 b ，这样就可以进行枚举a 和 b 都是 1 到 2020 。那这个题，思路就非常简单了。

//Java解题方法，仅供参考public class Main {  static int gcd(int a, int b){ int temp;      while(b>0){ /*利用辗除法，直到b为0为止*/ temp = b; b = a % b; a = temp; } return a;  } public static void main(String[] args) { int ans=0;      for(int a=1;a<=2020;a++){          for( int b=1;b<=2020;b++){ if(gcd(a,b)==1) ans++;          }      } System.out.println(ans); }}

//C++解题方法，仅供参考#include <iostream>using namespace std;int gcd(int a,int b){ int temp; while(b) { /*利用辗除法，直到b为0为止*/ temp = b; b = a % b; a = temp; } return a;}int main(){ int ans=0; for(int a=1;a<=2020;a++) { for( int b=1;b<=2020;b++) { if(gcd(a,b)==1) ans++;        } }    cout<<ans<<endl;}

#Python解题方法，仅供参考def gcd(a, b): tem = 0 while (b > 0):        temp = b        b = a % b a = temp    return a
if __name__ == '__main__': ans=0 for a in range(1, 2021): for b in range(1, 2021): if gcd(a,b)==1 :                ans+=1    print(ans)

第二道，2019年国赛

题目描述：本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。学习了约数后，小明对于约数很好奇，他发现，给定一个正整数 t，总是可以找到含有 t 个约数的整数。小明对于含有 t 个约数的最小数非常感兴趣，并把它定义为 St。例如 S1=1,S2=2,S3=4,S4=6，⋅⋅⋅现在小明想知道，当 t=100 时，S100 是多少？运行限制： 1. 最大运行时间：1s 2. 最大运行内存：128M

题目分析

这道题是一道数论题目，但是由于是道填空题，我们不需要过多考虑时间复杂度，所以我们采用模拟法打表做。题目中的描述是找约数，那我们定义个找约束个数的函数，然后枚举即可。这样不考虑时间复杂度，我们采取暴力法，尽快完成题目，让程序去跑答案，节省下时间来去做其他的题目。

我们可以这样暴力写约束计数函数。

这一题，我们给出伪代码，读者请自行完善：

int cnt(int a){ int ans = 0; for (int j = a; j > 0; j--) {        if (a % j == 0){ ans++; } return ans; }}

编辑:冯泽霖

审核:王顺晔

vlambda博客
学习文章列表