【蓝桥杯省赛】冲刺练习题【数学公式】倒计时【06】天(准考证组委会已下发，请查询)

举报
红目香薰 发表于 2022/04/20 20:06:01 2022/04/20
【摘要】 ​   🙏🤗距离【第十三届蓝桥杯4月9日省赛】仅剩【06天】🤗🙏​📋今日题型：【数学公式】📋⭐️🤗循环是一切暴力的基础，暴力基础，转起来。🤗⭐️🤗国一镇楼🤗​📋比赛题目与分数比例📋​确认范围：结果填空题5道，共计45分。程序设计题5道，共计105分。⭐️🤗刷题安排🤗⭐️日期题目类型题目数量3月25日循环63月26日超大数63月27日数组63月28日枚举63月29日...

​

   🙏🤗距离【第十三届蓝桥杯4月9日省赛】仅剩【06天】🤗🙏

​

📋今日题型：【数学公式】📋

⭐️🤗循环是一切暴力的基础，暴力基础，转起来。🤗⭐️

🤗国一镇楼🤗

​

📋比赛题目与分数比例📋

​

确认范围：

结果填空题5道，共计45分。

程序设计题5道，共计105分。

⭐️🤗刷题安排🤗⭐️

日期 题目类型 题目数量
3月25日 循环 6
3月26日 超大数 6
3月27日 数组 6
3月28日 枚举 6
3月29日 递归 6
3月30日 绘图 6
3月31日 深搜广搜 5
4月1日 动态规划 5
4月2日 填空题 5
4月3日

数学公式:查询准考证

点击查询准考证链接

 5
4月4日 第十届省赛题 10
4月5日 第十一届省赛题 10
4月6日 第十二届省赛1套题 10
4月7日 第十二届省赛2套题 10
4月8日 经典题目练习 8
4月9日 9点考试

目录

1、判断质数

2、分解质因数

3、快速幂

3、欧几里得定力

4、海伦公式（求三角形面积）

5、排列数公式

排列数:

排列数公式

符号

推导过程

示例：

附加1：矩阵相乘

附加2：线性同余方程(B组以上)

理论示例：

代码示例：

青蛙的约会

1、判断质数

质数又称为素数，是指大于1的并且除了1和它本身外，没有其他因数的自然数。

判断一个数是否是质数
假设该数为n， 我们只需要判断[2, \sqrt{n} ]​内是否有n的因子。如果有，则n为合数，否则，n为质数。

这种方法被称为试除法， 即试着除一下所有可能的因子。

package action;

public class demo {
	public static void main(String[] args) {
		System.out.println(isf(5));;
	}
	public static Boolean isf(int n){
	    if(n == 1) return false;
	    for(int i = 2; i <= n / i; i++){
	        if(n % i == 0){
	            return false;
	        }
	    }
	    return true;
	}
}

​​

2、分解质因数

根据算术基本定理又称唯一分解定理，对于任何一个合数， 我们都可以用几个质数的幂的乘积来表示。

​​

接下来我们利用这个公式分解质因数。
设一个质数为p.如果n%p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n/p, 这样就从n中剔除了一个p,接着重复上述两步，直到n%p ！= 0

package action;

public class demo {
	public static void main(String[] args) {
		isf(500);
	}
	public static void isf(int n) {
		for (int i = 2; i <= n / i; i++) {
			int a = 0, b = 0;
			while (n % i == 0) {
				a = i;
				n /= i;
				b++;
			}
			if (b > 0) {
				System.out.println(a + " " + b);
			}
		}
		if (n > 1) {
			System.out.println(n + " " + 1);
		}
	}
}

​​

3、快速幂

当我们计算k^{n}​时，常用的做法是对n连乘k次， 但如果k特别大，假如k = 1e6， 如果仍然对n连乘1e6次的话，时间消耗就太大了。那么我们如何在短时间内求出一个数的k次方呢。

求n^{k}​

​​

快速幂

​​

没有处理超大数

package action;

public class demo {
	public static void main(String[] args) {
		System.out.println(ksm(2, 10));
	}

	public static int ksm(int a, int b) { // 求 a^b
		int res = 1; // res保存结果
		while (b != 0) {
			if ((b & 1) == 1) { // 如果k的二进制数的最后一位是 1。 比如1011 & 1 = 1
				res = (res * a);
			}
			a = a * a;// 得到 a^1, a^2, a^4, a^8, .....
			b = b >> 1; // 将b右移一位，去掉最低位。为了开始判断下一位。
		}
		return res;
	}

}

3、欧几里得定力

最大公约数、最小公倍数

package Action;
 
public class demo {
	/*
	 * 求最大公约数 最小公倍数 思路：根据欧几里得定理 gcd(a,b)=gcd(b,a%b);
	 */
	static int gcd(int a, int b) {
		// 出口：b=0;5和0的最大公约数是5
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}
 
	static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
 
	public static void main(String[] args) {
		System.out.println(gcd(45, 35));
		System.out.println(lcm(45, 35));
		System.out.println(gcd(42, 60));
		System.out.println(lcm(42, 60));
	}
}

4、海伦公式（求三角形面积）

​

​

5、排列数公式

排列数公式就是从n个不同元素中，任取m（m≤n）个元素（被取出的元素各不相同），按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。排列与元素的顺序有关，组合与顺序无关。加法原理和乘法原理是排列和组合的基础。

排列数:

从n个不同的元素中任取m(m≤n)个元素的所有排列的个数，叫做从n个不同的元素中取出m(m≤n)个元素的排列数。记作符号A\tfrac{m}{n}​ 。A是英文arrangement（排列）的第一个大写字母。


例如，从7个不同的元素中任取5个元素的排列数为A\frac{5}{7}​ ，从10个不同的元素中任取7个元素的排列数为A\frac{7}{10}​。

排列数公式

​

 公式A是排列公式，从N个元素取M个进行排列（即排序）。

符号

C：组合数

A：排列数（在旧教材为P）

N：元素的总个数

M：参与选择的元素个数

!：阶乘，如5！=5×4×3×2×1=120

C：Combination 组合

P：Permutation排列 (现在教材为A-Arrangement)

推导过程


A\frac{m}{n}​求排列数A\frac{m}{n}​可以按依次填m个空位来考虑：假定有排好顺序的m个空位,从n个不同元素a1,a2,a3,…,an中任意取m个去填空,一个空位填1个元素，每一种填法就对应1个排列，因此，所有不同填法的种数就是排列数。

​

填空可分为m个步骤：

第1步，第1位可以从n个元素中任选一个填上，共有n种填法；

第2步，第2位只能从余下的n-1个元素中任选一个填上，共有n-1种填法；

第3步，第3位只能从余下的n-2个元素中任选一个填上，共有n-2种填法；

……

第m步，当前面的m-1个空位都填上后，第m位只能从余下的n-(m-1)个元素中任选一个填上，共有n-m+1种填法。

根据分步计数原理，全部填满m个空位共有n(n-1)(n-2)…(n-m+1)种填法。所以得到公式：

​

 这里n，m∈N*，并且m≤n这个公式叫做排列数公式其中，公式右边第一个因数是n，后面的每个因数都比它前面一个因数少1，最后个因数为n-m+1，共有m个因数相乘。

排列数公式还可以写成：

​

注意：为了保证公式在n=m时成立，特规定0! =1。

示例：

在10个球中，任意取3个（不放回），求有多少种取法？

package action;

public class demo2 {
	public static void main(String[] args) {
		// 在10个球中，取3个(不放回)
		System.out.println(f(10) / f(10 - 3));
	}

	public static int f(int n) {
		if (n <= 1)
			return 1;
		return f(n - 1) * n;
	}
}

​

附加1：矩阵相乘

资源限制

内存限制：256.0MB   C/C++时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　小明最近在为线性代数而头疼，线性代数确实很抽象（也很无聊），可惜他的老师正在讲这矩阵乘法这一段内容。
　　当然，小明上课打瞌睡也没问题，但线性代数的习题可是很可怕的。
　　小明希望你来帮他完成这个任务。

　　现在给你一个ai行aj列的矩阵和一个bi行bj列的矩阵，
　　要你求出他们相乘的积（当然也是矩阵）。
　　(输入数据保证aj=bi,不需要判断)

输入格式

　　输入文件共有ai+bi+2行，并且输入的所有数为整数（long long范围内）。
　　第1行：ai 和 aj
　　第2~ai+2行：矩阵a的所有元素
　　第ai+3行：bi 和 bj
　　第ai+3~ai+bi+3行：矩阵b的所有元素

输出格式

　　输出矩阵a和矩阵b的积（矩阵c)
　　（ai行bj列）

样例输入

2 2
12 23
45 56
2 2
78 89
45 56

样例输出

1971 2356
6030 7141
package action;

import java.io.IOException;
import java.util.Scanner;

public class demo2 {
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		String[] line1 = sc.nextLine().split(" ");
		int row1 = Integer.parseInt(line1[0]);
		int column1 = Integer.parseInt(line1[1]);

		int[][] m1 = new int[row1][column1];
		for (int i = 0; i < m1.length; i++) {
			String[] data = sc.nextLine().split(" ");
			for (int j = 0; j < m1[i].length; j++) {
				m1[i][j] = Integer.parseInt(data[j]);
			}
		}

		String[] line2 = sc.nextLine().split(" ");
		int row2 = Integer.parseInt(line2[0]);
		int column2 = Integer.parseInt(line2[1]);

		int[][] m2 = new int[row2][column2];
		for (int i = 0; i < m2.length; i++) {
			String[] data = sc.nextLine().split(" ");
			for (int j = 0; j < m2[i].length; j++) {
				m2[i][j] = Integer.parseInt(data[j]);
			}
		}
		sc.close();

		int[][] result = new int[105][105];
		for (int i = 0; i < row1; i++) {
			for (int j = 0; j < column2; j++) {
				for (int k = 0; k < row2; k++) {
					result[i][j] += m1[i][k] * m2[k][j];
				}
			}
		}

		for (int i = 0; i < row1; i++) {
			for (int j = 0; j < column2; j++) {
				if (j == column2 - 1) {
					System.out.println(result[i][j]);
				} else {
					System.out.print(result[i][j] + " ");
				}
			}
		}
	}
}

 ​​​​​

附加2：线性同余方程(B组以上)

数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次.

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：

ax≡b (mod n)的方程。

此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。

这时，如果 x0 是方程的一个解，那么所有的解可以表示为：

{x0+kn/d|(k∈z)}

其中 d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。

理论示例：

在方程3x ≡ 2 (mod 6)中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程无解。


在方程5x ≡ 2 (mod 6)中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。


在方程4x ≡ 2 (mod 6)中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2 and x=5。

代码示例：

青蛙的约会

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入
输入只包括一行5个整数x，y，m，n，L，

其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

输出
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

输入示例

1 2 3 4 5

输出示例

4

题目分析

设跳次数为t，则跳t次后两个青蛙的位置分别为(x+mt) mod L、(y+nt) mod L，相遇即是(x+mt)%L=(y+nt)%L转化为ax+by=c方程： (m-n)t+kL=y-x。设a=m-n，b=L，c=y-x，然后套用拓展欧几里得即可得出答案。

package action;

import java.util.Scanner;

// 求解同余方程的本质就是求线性方程
// 将求余方程转化为线性方程
public class demo2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextInt(); // 坐标
		long y = sc.nextInt(); // 坐标
		long m = sc.nextInt(); // A第一次跳
		long n = sc.nextInt(); // B第一次跳
		long l = sc.nextInt(); // 维度总长
		sc.close();
		long a = m - n;
		long b = l;
		m = y - x;
		long d = 0;
		try {
			d = ExtGcd.linearEquation(a, b, m);
		} catch (Exception e) {
			System.out.println("Impossible");
		} // 求解线性方程
		long x0 = ExtGcd.x;
		b /= d; // 约一下
		b = Math.abs(b); // 有可能小于0
		/* =========这里是AC的关键=========== */
		x0 = (x0 % b + b) % b; // 要求大于0的第一个解
		System.out.println(x0);
	}

	// 私有的静态的内部类
	private static class ExtGcd {
		static long x, y;

		public static long ext_gcd(long a, long b) {
			if (b == 0) {
				x = 1;
				y = 0;
				return a;
			}
			long res = ext_gcd(b, a % b);
			long x1 = x;
			x = y;
			y = x1 - a / b * y;
			return res;
		}

		public static long linearEquation(long a, long b, long m) throws Exception {
			long d = ext_gcd(a, b);
			if (m % d != 0)
				throw new Exception("无解");
			long n = m / d;
			x *= n;
			y *= n;
			return d;
		}
	}
}

​


​

【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
人工智能 汇编语言
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入