CSP-j初赛及其试题_附件:数学专题
2025-08-06 11:25:53
发布于:河北
本文将分为四个部分:
进制转换
哈夫曼树
排列组合
表达式
进制转换
首先我们要明白进制是什么
进制:数字的位数规则
比如说我们用的正常的数字就是十进制的,他的每一位上最高只能是9,经典的二进制一样,每一位上最高只能是1,所以k进制每位最高是k-1
那么进制怎么转换能,咱们需要一个借位,也就是十进制,如果x进制要转y进制,则要先转十进制,再转y进制
先来讲x进制转十进制:
我们先来看一个数
107415
随机取一位7
7是7个1000,也就是7*,他是第4位,刚好是位数-1,那么其他是不是这样呢?
我们再来看5,他是5*,是第1为,也对上了
那么k进制就是x*,是第y+1位
我们可以推出这样一个式子:
至于十进制转x进制吗
我直接说吧:短除法
自行理解
哈夫曼树
这个可以说是最简单的东西了
就是利用规则构造一个树
规则:将序列里最小的两个数据到一起放回队列并重复
构成的树左边是0,右边是1,某节点的编号就是路径上的数字
注意:合成的元素不一定是最小的,否则就要从新找小的元素
比如序列
{1 4 2 5 9 12 6}
排列组合
排列
假如有这样一个问题:有6个不同的人排队,共有多少种解法?
相信你不会一个一个列,那么我们来看一个思路:
一号有6种方式
二号有5种方式,因为总有一个是被1占了的
以此类推,到6号时只剩一个位置
然后遍历一遍,就能得到一个式子:
6 * 5 * 4 * 3 * 2 * 1=720
假如说有7个位置,但有六个人呢?
第一个人有7个
第二个人有6个
直到最后1个有两个位置
则能推出式子:7 * 6 * 5 * 4 * 3 * 2=5040
这样,我们就得到了排列公式:A
即=m * (m-1) * (m-2) * …… * (m-n+1)
组合
有10个苹果,我要取三个吃,有多少种方式取?
还是现将这三个排列,得到10 * 9 * 8=720
但是这是排列,讲究顺序,可组合不讲究顺序,所以我们还需要除以个
即
另外有一种经常考的题型,就是某某某要挨在一起,这种就是把挨在一起的当一个人来算,在乘一下挨着的人排列总数
表达式
表达式是我们用的一种式子,由+-*/、数字、括号组成的
表达式的数字永远比符号多1
位缀表达式
表达式氛围前缀种植和后缀
前缀被称为波兰式,而后缀则是逆波兰式,中缀是我们现在用的式子
中缀转前缀:
先转最高运算律的,把符号搁到式子前面,再把式子当成一个数,从新放回表达式
比如(变化步骤):
中缀:A*B+C-D/E
*AB+C-D/E
*AB+C-/DE
+*ABC-/DE
前缀:-+*ABC/DE
中缀转后缀转后缀也是如此,只是把符号放到式子后面
前/后缀转中缀:
(如果是转入中缀,就不分前后缀,唯一的区别就是扫描方向相反)
咱们需要一个栈
然后重复以下操作:
遇到数字放到栈里
遇到符号去除栈里头两个数并转回中缀表达式(把符号放两数中间),再把这个中缀表达式当成数字放回栈
直到栈里只剩一个数字(式子),那个数字就是中缀表达式
这里空空如也
有帮助,赞一个