整点问题
整点是指平面直角坐标系中纵、横坐标都是整数的点，又称为格点．整点问题是数论与解析几何相结合的产物，不仅有趣，而且富有技巧性．对于培养学生分析问题、解决问题的能力和训练思维的灵活性等很有好处，是考核数学竞赛参赛者的良好题材.
1．整点多边形问题
如果一个多边形的所有顶点都是整点，则称这个多边形为整点多边形·平面直角坐标系中是否存在整点正n 边形？对于n=4，我们知道存在整点正方形，对于n=3，n ≥5呢？
例1证明：不存在整点正三角形． 证 反证法，，设平面上3个整点A ，B ，C 组成一个正三角形·由于向上、下或左、右平移整数个单位，整点仍然变为整点，因此不妨设A 为原点，|AB| = r , B ，C 的坐标分别为（a ，b ），（x ，y ），其中a ，b ，x ， y ∈R 如图8-5．于是
,2
3
21)sin 23cos 21()3cos(b a r r x -=-=+
=θθπ
θ .2
321)cos 23sin 21()3sin(a b r r y +=+=+
=θθπ
θ
因为a ，b 均为整数，且至少有一个不为零，所以x ，
y 不可能均为整数，矛盾.因此不存在整点正三角形．
例2证明：不存在整点正五边形·
证 设存在一个整点正五边形ABCDE ，边长为a ，如图8-6， 易知边长a 与对角线d 的比
d
a
满足?=
-2
51
d a 由两点间的距离公式知，任意两个整点的距离的
平方是整数，所以a 2
和d 2
均为整数，从而22d
a 是
有理数，但是,25
3)2
15(
222-=-?=d a 上式右端是一个无理数，矛盾。因此，整点正五边形是不存在的．
下面我们给出本题的另一证法．
设存在整点正五边形，在所有的整点正五边形中选出边长最短的一个，记作ABCDE ，连接所有的对角线-得五边形1111E D C B A I 如图8—7．易知五边形 1111E D C B A I 是正五边形．又因为E ABA 1为平行四边形，A ，B ，E 是整点，令A ，
B ，A 1，E 的坐标为),,(11y x ),,(),,(),,(443322y x y x y x 则
,2
24
231x x x x +=+ 所以?-+=1423x x x x 同理,1423y y y y -+= 所以A 1也是整点，同理，1111,,,E D C B
均为整点·这样就得到了一个比ABCDE 边长更短的整点正五边形,11111E D C B A 矛盾·
我们用完全类似的方法可以证明整点正n 边形不存在。
整点多边形的内部及边界生的整点数目与面积之间有如下的关系。 毕克(Pick 定理) 一个整点多边形的内部有n 个整点，边界上有m 个整点，则此
整点多边形的面积.12
-+=m
n S
下面我们仅对一个两条边分别平行于坐标轴的直角三角形来验证毕克定理. 如图8-8所示，将整点直角三角形ABC 扩充成矩形
ABCD.设AB 和BC 边上分别含有a 个和b 个整点（不包括端点），则AB=a+l ，BC=b+l,于是
)1)(1(2121.++==?b a S s D ABC ABC ).1(2
1
+++=b a ab
设边AC 上有c 个整点（不包括端点）．由于矩形ABCD 内的整点数目为ab ，所以△ABC 内的整点数
),(21
c ab n -=
△ABC 边界上的整点数,3+++=c b a m
因此1)3(21)(2112-++++-=-+
c b a c ab m n ABC S b a ab ?=+++=)1(2
1
由毕克定理马上可以知道，任何一个整点三角形的面积不小于1/2．
例3 整点三角形ABC 的边上除顶点外没有其它的整点，而且它的内部只有一令整点P ．证明：P 是△ABC 的重心·
证 由毕克定理知，,2
1
===???CPA BPC APB s s S
由此可知P 是3条中线的交点，即重心· 如图8-9，事实上，由CPA APB S S ??=可推知
,C P D B P D s S ??=于是?=??ACD ABD s S
所以D 是BC 边上的中点，即AD 是BC 边上的中线，同理P 点在中线BE 和CF 上．
例4证明：整点凸五边形的面积不小于2
5
.
证 整点可按它坐标的两个分量的奇偶性分成（偶，偶），（奇，奇），（偶，奇），（奇；偶）四类，于是5个整点中一定有两个点属于同一类型（抽屉原则），它们的中点M 也是整点，由于是凸五边形，因此M 在此五边形的内部或边界上．… (1) 若M 在凸五边形的内部，根据毕克定理
)5,1(≥≥m n ?=-+≥2
5
1251S
(2) 若M 在边界上，不妨设M 在边P 1P 2上，连接P 3S,如图8-10，则整点凸五边形MP 2P 3P 4P 5的内部或边界上至少有一个整点（不包括顶点）．
于是根据毕克定理，51543254321MP P P P P MP P P P P P s s s ?+=?=++-≥2
5
21)21125(
2．平面区域内的整点数
例5求位于直线10,2
1
32=-=x x y 和横坐标
轴形成的三角形内部和边界上的整点数·
解如图8-11，函数2
1
32-=x y 当x 取1，2,…，
10时（注意，
当4
3
=x 时，0=y )，得到y 依次为
,629,625,27,617,613,23,65,61?6
37,211 于是，位于已知三角形（包括边界）中整点个数等于纵坐标的整数部分之和加上位于横坐标轴上的10个点的个数，即 ]625[]27[]617[]613[]23[]65[]61[++++++.3710]637
[]211[]629[=++++ 所以，三角形的内部与边界上共有37个整点，
例6 m 是正整数时，在曲线3242++-=m x x y 和直线mx y 2=所围区域内（包括边界）所含有的整点有多少个？
解 抛物线3242++-=m x x y 和直线mx y 2=交点的横坐标为方程=++-3242m x x mx 2的实根，即.32,121+==m x x
如图8-12所示，对于满足321+≤≤m i 的整数
i x i =,与直线mx y 2=的交点Ai 是整点),2,(mi i 与
抛物线的交点i B 是整点)324,(2++-m i
i i 于是i i B A 上的整点个数为所以区域内（包括边界）的整点总数为
]1)324(2[2
321
+++--∑+=m i i
mi m i )]1(2)2(2[2
3
21
+-++-=
∑+=m i m i
m i
)42()74)(42)(32(61+++++-=m m m m ·)32)(1(22)
42)(32(++-++m m m m
).432)(32(31
2+++=m m m
下面介绍一个圆内整点问题．
例7设a 为正实数，在圆a y x =+22内的整点数记为),(a R 证明：22)2()()2(+<<-a a R a ππ
证: 以圆a y x =+22内每个格点为左下方的顶点作边与坐标轴平行的单位正方形，因单位正方形的对角线长为.2所以这些正方形内任一点到原点(0，0)的距离不大于,2+a 即所作的正方形均在圆222)2(+=+a y x 内，从而这些单位正方形的面积和（等于圆a y x =+22内的整点数）不超过圆=+22y x 2)2(+a 的面积,)2.(2+a π从而右边不等式得证·
对于圆222)2(-=+a y x 内的任一点P ，必有一个整点以，以A 为左下方顶点、边与坐标轴平行的单位正方形含P 点·此正方形内的任一点与原点(0，0)的距离=+-≤22a ,a 因此正方形在圆a y x =+22内．从而以圆a y x =+22内的整点为左下方顶点所作的在圆a y x =+22内的单位正方形全体覆盖了圆
222)2(-=+a y x 及其内部，因此左边不等式得证．
3．其它
例8 在坐标平面上作一个凸集，使得它含有无限多个整点，但它与任何一条直线的交要么只含有限多个整点，要么不含整点．（注：平面上的一个点集称为凸集，若对此点集中的任意两点，连接这两点的线段仍在该点集中．例如；半平面、圆的内部、三角形区域、带形区域等均为凸集．）
解：在直角坐标平面上作一个带形区域},,212|),{(R x x y x y x A ∈≤≤-= 则此带形区域A 为凸集，下面验证它满足题设条件，
因为当x 为整数时，整点,])2[,(A x x ∈因此凸集A 含有无限多个整点． 对于形如b x y +=2的直线，它与A 的交至多只含有一个整点·这是因为此直线上至多只有一个整点的缘故，否则，若整点),(),,(2211y x y x 均在b x y +=2上，则=
+=211,2y b x y ,22b x +
所以).(21212x x y y -=-这与2211,,,y x y x 均为整数，且),(),(2211y x y x =/矛盾， 对于不是形如b x y +=2的直线，它与A 的交是一线段，故至多只有有限多个整点．
说明本例是一个“存在性”问题·在处理这类问题时，往往需要构造，如何构造，是一个难点，多做练习t ，积累经验，构造方面的能力就会有所提高．下面的例子，也需要“构造性证明”．
例9证明：在直角坐标平面上存在．同心圆的集合，使得 (1)每个整点都在此集合的某一个圆周上； (2)此集合的每个圆周上，有且只有一个整点．
证: 取点),31
,2(P
设整点),(b a 和),(d c 到点P 的距离相等，则
,)3
1
()2()31()2(2222-+-=-+-d c b a
即).(3
2
2)(22222d b b d a c a c -+-+-=-
由于2是无理数，所以上式仅当两边同时为零时成立，故
①,a c =
②.0)(3
2
2222=-+-+-a b b d a c
①式代入②式并化简得.0)3
2
)((=-+-b d b d
由于,03
2
,,=/-+∈b d Z d b
因此b=d ．从而点(a,b)与(c,d)重合，故任意两个整点到)3
1
,2(P 的距离都不相等，
现将所有整点到P 点的距离从小到大排成一列,,,321d d d …，显然，以P 为圆心，
,,,321d d d 为半径作的同心圆的集合即为所求．
例10有101个长方形，边长都是不超过100的整数．证明：这些长方形中必有3个，第一个可以放在第二个中，第二个可以放在第三个中，
证: 我们把这个问题转化为整点问题来解决．将每个长方形用直角坐标系中的整点来表示，横、纵坐标x ，y 分别表示长方形的长和宽．由题意知，
.1001≤≤≤k y
于是我们把问题转化为：有101个整点，它们的坐标均满足≤≤≤x y 1.100 证明其中必有3个整点,3,2,1),,(=i y x i i 满足321x x x ≤≤,321y y y ≤≤
我们考虑如图8-13所
示的“┛”型,第一个的3个端点是(1，1)，(100，1)，(100，100)，第二个的3个端点是(2，2)，(99，2)，(99，99)，……，最后一个退化为一点(50，50)，共有50个“┛”型．现有101个整点，根据抽屉原则，必有一个“┛”型中含有3个已知点，这3个点即为所求.
例11. 平面上有限个点构成一个集合，其中每个点的坐标为整数，可不可以把此集合中某些点染成红色，其余点染成白色，使得与纵、横坐标轴平行的任一条直线l 上所含的红、白点的个数至多相差一个？ ‘ 解．答案是肯定的，对已知点n 的个数进行归纳． 当n=l 时结论显然成立，
假设当所有点数小于n 时结论都成立，考虑n 个点．如果每条横线与竖线上都只有一个已知点，任意染色即可．否则设一条横线上有已知点A 、B 、…．
如果过A 的纵线、过B 的纵线、…，上面都只有一个已知点，那么将直线AB 上的已知点交错地染上红色或白色，其余的点按归纳假设染好色即可． 如果过A 的纵线上还有一个已知点C ，考虑以A ，B ，C 为顶点的矩形ABDC.如果D 是已知点，将A ，D 染成红色，B ，C 染成白色，其余的点按归纳假设染色即可，如果D 不是已知点，将A ，B ，C 除去，D 点加入已知点中，由归纳假设将包括D 在内的点染上颜色，不妨设D 为红色，除去D ，将B ，C 染成红色,A 染成白色即可，
例12. 在平面上任画一条所有顶点都是格点的闭折线，并且各节的长相等．能使这闭折线的节数为奇数吗？证明你的结论．
解 令符合题设条件的闭折线为21A A ,1A A n
则所有顶点i A 的坐标),(i i y x 符合).,,2,1(,n i Z y x i i =∈并且C Y X i i =+22
C n i ,,,2,1(???=为一固定的正整数），其中,1+-=i i i x x X 1+-=i i i y y Y ),,,,,2,1(1111y y x x n i n n ==???=++
则由已知，有
①,01=∑=i
n
i X
②,01
=∑=i
n
i Y
③?+==+=+22
22222121n n Y X Y X Y X
不妨设i X ,i Y 中至少有一个为奇数（因为设m t X i m i ,2=是指数最小的，
i t 为奇数，用m 2除所有的数后，其商仍满足①、②、③式），于是它们的平方和C 只能为14+k 或.24+k
当24+=k C 时，由③，知所有数对i X ,i Y 都必须是奇数，因此，根据①、②式，知，n 必为偶数，
当14+=k C 时，由③，知所有数对i X 与i Y 都必一奇一偶，而由①，知i X 中
为奇数的有偶数个(设为2u)，余下的n-2u 个为偶数（与之对应的i Y 必为奇数），再由②，知这种奇数的i Y 也应有偶数个（设为2v =n-2u)，故n=2（u+v ）=偶数． 综上所述，不能作出满足题设条件而有奇数个节的闭折线．
练习题
1．填空题
(1)设C 是半径为r 的圆，圆心在点r ),3,2(是正实数，则圆C 上整点个数最多有 个.
(2)正整数x ，y 满足?
??≤≤>+,8,
8y x y x 则这样的整点(x,y) 有____个．
(3)三角形3条边长均为整数，且最大边长为11的三角形共有 个.
(4)平面上有若干个整点，要使它们之中总存在两点，使其连线的中点也是整点，则 这样的整点个数至少有____个．
(5)对任意自然数n ，连接原点O 与点),3,(+n n A n 用f(n)表示线段OA n 上除端点外的整点个数，则f(l)+f(2)+…+f(1990)=________．
答：(1)1; (2)20; (3)36; (4)5; (5)1326.
2．三角形ABC 是整点三角形，3条边长分别为a ，b ，c ，外接圆半径为R ． 求证：abc≥2R ． 提示：利用
3．已知x ，y 都是两位的正整数，且x>y ，x+y<100．问x ，y 的解有多少组？
4．一正方形的内部不含整点，且己的两边分别平行于两坐标轴．证明:它的面积不超过1．
5．证明：内部不含整点的圆，面积至多为
2
π． 提示：
6. 已知直线l 经过两个整点，证明：该直线经过无穷多个整点．
7．△ABC 是整点三角形·证明：若AB>AC ，则AB - AC>
p
1
，p 是△ABC 的周长．
证明．设△ABC 的顶点的坐标分别为：A(0，0)、B(x ，y)、C(u ，v)，
三顶点A 、B 、C 的对边长分别为a ，b ，c ，则周长a+b+c ．于是，只需证明：
+-22b c .1)(>-a b c
因,b c >又).(222222v u y x b c +-+=-因x,y,u,v ∈Z, 故Z b c ∈-22故
122≥-b c 。而.1)(>-a b c 故结论正确。
8．设p >3是质数，},0,,|),{(p y x Z y x y x M <≤∈=是直角坐标平面上的一个点集，证明：从M 中可以取出p 个不同的点，使其中任3点不共线，任4点不构成平行四边形的顶点．
9．设△ABC 是整点三角形，且在△ABC 的内部只有一个整点（但在边上允许
有整点）．证明：?≤?2
9
ABC S
10． 如图，在坐标平面上给定凸五边形ABCDE ，它的顶点都是整点．证明：在五边形A 1B 1C 1D 1E 1的内部或周界上至少有一个整点．
证明．若11111E D C B A 周界上含有整点，结论显然成立，若11111E D C B A 周界上不含有整点，
本题中只需证明结论对于,11D AC ?111111,,B DA A CE E BD ???和11C EB ?的内部及周界上不含A ，B ，C,D ，E
以外的整点时，结论成立．这是因为若11D AC ?
内部或周界含有另一整点K ，则格点五边形KBCDE 的“内五边形”包含于
11111E D C B A 中，这样继续下去，总能找到一个符合上述要求的格点五边形其“内
五边形”包含于11111E D C B A 中.
从△ABC 、△BCD 、△CDE 、△DEA 和△EAB 中选出面积最小的一个，不
妨设为△ABC,于是，点A 与直线BC 的距离不大于点O 到该直线的距离；点C 与直线AB 的距离不大于点E 到该直线的距离；为使四边形ABCO 为平行四边形，点O 显然为整点，则O 在△AB l C 的内部，而△AC 1O 1和△CE 1 A 1内部或周界的都不含除A 、C 外的整点，所以点O 在五边形11111E D C B A A 的内部或周界上．
11. 已知直线l 经过两个格点，求证：直线l 必经过无穷多个格点．
证．设直线,0:=++c by ax l 经过两格点),(),,(2211y x y x 则121)1[(])1[(y n b nx x n a ++-+0]2=+-c ny 这说明：格点+-+n nx x n (,)1((21))()121N n ny y ∈- 都在直线l 上，故l 上有无穷多个格点．
实战练习题
1. （1999年全国高中数学联赛）平面直角坐标系中，纵、横坐标都是整数的点叫做整点，那么，满足不等式 (| x |-1) 2 +(| y |-1) 2 ＜2的整点( x , y )的个数是( ) ( A )16 ( B )17 ( C )18 ( D )25 答：(A)
解 因(x,y)是整点，所以x ，y ∈Z ．
故1||-x 及,1||Z y ∈-且≥-1||x ,1-,11||-≥-y 又由于|(|)1|(|2y x +-,2)12<-
故有???=-=-;01||,01||)1(y x ???=-=-;11||,01||)2(y x ???=-=-;01||,11||)3(y x ???-=-=-;11||,01||)4(y x ?
??=--=-.01||,
11||)5(y x
从而，不难得到(z ，y)共有：(1，1)、（1，-1）、（-1，1）、（-1，-1）、(1，2)、
（1，-2）、（-1，2）、（-1，-2）、(2，1)、（2，-1）、（-2，1）、（-2，-1）、(1，0)、 （-1，0）、(0，1)、（0，-1），16个整点．故选A.
2.（2000．全国高中联赛）求平面上整点到直线5
4
35+=x y 的距离的最小值，
解 将直线5
4
35+=x y 化成一般式0121525=+-y x
显然这条直线上不存在整点．由于25和5的最大公约数是5，所以，25x-15y(x ，y 都是整数)一定为5的整数倍，而且可以是5的任何整数倍，因此|25x-15y+12 |
(x ，y 为整数)的最小值为2，因此，平面上的整点到直线5
4
35+=x y 的距离的最
小值为?85
34
3．（1996．全国高中联赛）在直角坐标平面上，以(199，0)为圆心，以199为半径的圆同上整点的个数为
解 设A(x ，y)为圆O 上的一整点，如右图，圆O 的方程为
+2y .199)199(22=-x
显然，x=0，y=0；x=199,y=199; x=199，y= -199; x= 398，y=0为方程的4组解．但当y≠0，±199时，y 与199互素（因199为素数），此时，199，y ，|199-x|是一组勾股数，故199可表示成两个正整数的平方和，即.19922n m +=
因199=4×49+3，可设,12,2+==l n k m 则1)1(414441992222+++=+++=l k l l k 这与199为4d+3型素数矛盾．因而，圆O 上只有4个整点(0,0)、(199, 199)、(398,0)、(199,-199)．
4. (1997年爱朋思杯-上海市高中数学竞赛决赛题)
求平面直角坐标系中格点凸五边形（即每个顶点的纵、横坐标都是整数的凸五边形）的周长的最小值．
[解]格点多边形的边长的值最小为1，其次为2．图中
五边形A BCDE周长为2+32.
若格点五边形周长小于2+32，则其中至少有三边长
为1，这三边中有两边相邻，设为图中AB、AE．若有一边
为BF=1，则ABFE成单位正方形，第五点在直线AE、BF外不可能与这四点成凸五边形．所以与B相邻的另一边为图中BC．同理与E相邻的另一边为图中
ED．这时凸五边形周长为2+32,因此所求最小值即2+32
5. （1992年日本数学奥林匹克预选赛题）A，B分别是坐标平面上的格点的集合：
A={（x，y）|x，y为正整数，1≤x≤20，1≤y≤20}
B={（x，y）|x，y为正整数，2≤x≤19，2≤y≤19}
A中的点分别染成红色或蓝色．染成红色的点有219个，其中有180个包含于B中，又四个角上的点（1，1），（1，20），（20，1），（20，20）都染成蓝色．将水平或垂直方向上相邻两点按下列要求用红、蓝、黑色的线段连接起来：两点均为红色时，用红线连接；两点均为蓝色时，用蓝线连结；两点为一红一蓝时，用黑线连结．
问：（长度为1的）黑线有237段时，（长度为1的）蓝线有多少段？
[解] 集合A中有400个点，其中红点有219个，蓝点有181个，在B内有蓝点144个．A的四周有76个点，其中红点39个，蓝点37个（包括四个角上的点）．每个角上的点引出2条线段；每个边界上（除四个角）的点引出3条线段；每个B内的点引出4条线段．因此，对于蓝点共引出线段2×4+3×33+4×144=683段;
其中黑线有237段，所以蓝线有683-237=446段;
这些蓝线在上述计数时，被重复计算了一次，故实际上有蓝线446÷2=223段
6. (1994年日本数学奥林匹克预选赛题)．
某城市是长宽各为10km 的正方形．城内有间隔各为1km 的棋盘街，东西走向和南北走向各11条．东西走向道路所在的直线记为y=m （m=-5，-4，…，4，5），南北走向道路所在的直线记为x=n （n=-5，-4，…，4，5）．某公司在该市开设5个分店A k （k=1，2，…，5），它们分布在棋盘街道路沿线，其坐标（x k ，y k ）分别是（-5，1.3），（2，4.5），（4.4，3），（4，-1），（-2.7，-2）．分店各派出1名店员，沿棋盘街道路行走，到街道沿线的某地会合．要使得店员们行走的路程总和S （x ，y ）最小，求该地的坐标．
[解] 易知，所求的坐标（x ，y ）中至少有一个为整数，且
若（x ，y ）不是格点（x ，y 均为整数的点），例如，设m 、n 为整数，而x=n ，m ＜y ＜m+1．在（x ，y ）不是分店时，5个店员中有a 人自北向南而至，b 人自南向北而至．当会合点向来人较多的方向移动时，S （x ，y ）将变小．直到这个会合点移至格点或某个分店为止．可能存在这样的分店A k ，其坐标x k ≠n ，m ＜y k ＜m+1．由它出发，到（x ，y ）点的路程不论由南向北来还是由北向南来，都是相等的．此时（x ，y ）向南或向北移动，该店店员所走的路程都是减少的，因而只需考虑其他的人．
当y 是整数而x 不是整数时，考虑会合点东西向的移动，可得同样的结论． 综上所述，所求的点必为格点或某分店所在地．
由于题中的坐标x k （k=1，…，5）与y k （k=1，…，5）的中位数分别是x=2，y=1.3．而最接近（2，1.3）的是格点（不是某分店）（2，1）．即在格点（2，1）处会合，S （x ，y ）最小．
7. (1994年中国数学奥林匹克·第九届数学冬令营) 设M 为平面上坐标为（p·1994，7p·1994）的点，其中p 为素数，求满足下列条件的直角三角形的个数：
（1）三角形的三个顶点都是整点，而且M 是直角顶点； （2）三角形的内心是坐标原点．
[解] 关于OM 中点Q 作中心对称，满足条件的直角三角形变为以O 点为直角顶点、M 为内心的直角三角形OAB ，A 、B 仍是整点．
直线OM 斜率为tanβ=7，直线OA 斜率为
4
3
tan 11tan )45tan(tan =+-=
?-=βββα,
直线OB 斜率为3
4-
由此可设A 点坐标为（4t ，3t ），B 点坐标为（-3s ，4s ）．从而知t=4t-3t ，s=-3s+4s 都是整数．
设△OAB 内切圆半径为r ，则
所以OA+OB-AB=2r
即t2+s2=（t+s）2-4p·1994·（t+s）+4p2·1994
整理得（t-3988p）（s-3988p）=2p2·19942=23·9972·p2
由于5t＞2r，5s＞2r，故所求三角形个数等于23·9972·P2正因子个数．
于是，当P≠2、997时，有（3+1）（2+1）（2+1）=36个解；当P=2时，有（5+1）（2+1）=18个解；当p=997时，有（3+1）（4+1）=20个解．
8. (1982年全国高中数学联赛试题)
已知圆x2+y2=r2（r为奇数），交x轴于A(r,0)，B(-r,0); 交y轴于C(0,-r)，D(0,r). P(u,v)是圆周上的点，u=p m,v=q n（p,q都是质数，m,n都是自然数）且u>v，点P在x轴和y轴上的射影分别是M,N.
求证: |AM|,|BM|,|CN|,|DN|分别为1,9,8,2.
9. (1992年全国高中数学联赛试题)在平面直角坐标系中，横坐标和纵坐标都是整数的点称为格点。任取6个格点)6,5,4,3,2,1(=i P i ，满足
(1) ,2||,2||≤≤i i y x )6,5,4,3,2,1(=i (2) 任何三点不在同一直线上
试证：在以)6,5,4,3,2,1(=i P i 为顶点的所有三角形中，必有一个三角形，它的面积不大于2.
高中数学竞赛中数论问题的常用方法 数论是研究数的性质的一门科学,它与中学数学教育有密切的联系.数论问题解法灵活,题型丰富,它是中学数学竞赛试题的源泉之一.下面介绍数论试题的常用方法. 1.基本原理 为了使用方便,我们将数论中的一些概念和结论摘录如下: 我们用),...,,(21n a a a 表示整数1a ,2a ,…,n a 的最大公约数.用[1a ,2a ,…,n a ]表示1a ,2a ,…,n a 的 最小公倍数.对于实数x ,用[x ]表示不超过x 的最大整数,用{x }=x -[x ]表示x 的小数部分.对于整数 b a ,,若)(|b a m -,,1≥m 则称b a ,关于模m 同余,记为)(mod m b a ≡.对于正整数m ,用)(m ?表示 {1,2,…,m }中与m 互质的整数的个数,并称)(m ?为欧拉函数.对于正整数m ,若整数m r r r ,...,,21中任何两个数对模m 均不同余,则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质,且其中任何两个数关于模m 不同余,则称{)(21,...,,m r r r ?}为模m 的简化剩余系. 定理1 设b a ,的最大公约数为d ,则存在整数y x ,,使得yb xa d +=. 定理2(1)若)(mod m b a i i ≡,1=i ,2,…,n ,)(m od 21m x x =,则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； (2)若)(mod m b a ≡,),(b a d =,m d |,则 )(mod d m d b d a ≡； (3)若b a ≡,),(b a d =,且1),(=m d ,则)(mod m d b d a ≡； (4)若b a ≡(i m mod ),n i ,...,2,1=,M=[n m m m ,...,,21],则b a ≡(M mod ). 定理3(1)1][][1+<≤<-x x x x ； (2)][][][y x y x +≥+； (3)设p 为素数,则在!n 质因数分解中,p 的指数为 ∑≥1 k k p n . 定理4 (1)若{m r r r ,...,,21}是模m 的完全剩余系,1),(=m a ,则{b ar b ar b ar m +++,...,,21}也是模 m 的完全剩余系； (2)若{)(21,...,,m r r r ?}是模m 的简化剩余系,1),(=m a ,则{)(21...,,m ar ar ar ?}是模m 的简化剩余系. 定理5(1)若1),(=n m ,则)()()(n m mn ???=. (2)若n 的标准分解式为k k p p p n ααα (2) 121=,其中k ααα,...,21为正整数,k p p p ,...,21为互不相
常用的8种数字滤波算法 摘要：分析了采用数字滤波消除随机干扰的优点，详细论述了微机控制系统中常用的8种数字滤波算法，并讨论了各种数字滤波算法的适用范围。 关键词：数字滤波；控制系统；随机干扰；数字滤波算法 1 引言 在微机控制系统的模拟输入信号中，一般均含有各种噪声和干扰，他们来自被测信号源本身、传感器、外界干扰等。为了进行准确测量和控制，必须消除被测信号中的噪声和干扰。噪声有2大类：一类为周期性的，其典型代表为50 Hz 的工频干扰，对于这类信号，采用积分时间等于20 ms整倍数的双积分A/D转换器，可有效地消除其影响；另一类为非周期的不规则随机信号，对于随机干扰，可以用数字滤波方法予以削弱或滤除。所谓数字滤波，就是通过一定的计算或判断程序减少干扰信号在有用信号中的比重，因此他实际上是一个程序滤波。 数字滤波器克服了模拟滤波器的许多不足，他与模拟滤波器相比有以下优点： (1)数字滤波器是用软件实现的，不需要增加硬设备，因而可靠性高、稳定性好，不存在阻抗匹配问题。 (2)模拟滤波器通常是各通道专用，而数字滤波器则可多通道共享，从而降低了成本。 (3)数字滤波器可以对频率很低(如0.01 Hz)的信号进行滤波，而模拟滤波器由于受电容容量的限制，频率不可能太低。 (4)数字滤波器可以根据信号的不同，采用不同的滤波方法或滤波参数，具有灵活、方便、功能强的特点。 2 常用数字滤波算法 数字滤波器是将一组输入数字序列进行一定的运算而转换成另一组输出数字序列的装置。设数字滤波器的输入为X(n)，输出为Y(n)，则输入序列和输出序列之间的关系可用差分方程式表示为： 其中：输入信号X(n)可以是模拟信号经采样和A/D变换后得到的数字序列，也
穷举用技巧 【例1】 N是一个各位数字互不相等的自然数，它能被它的每个数字整除。N的最大值是。 【例2】 如果连续N个自然数，每个自然数的数字和都不是11的倍数，则称这连续的N个自然数为一条“龙”，n为这条龙的长度。比如1，2，3，…，28就是一条龙，它的长度是28。问：龙的长度最长可以为多少？写出一条最长的龙。 【例3】 黑板上写有1、2、3、……、100这100个自然数，甲、乙二人轮流每次每人划去一个数，直到剩下两个数为止。如剩下的两数互质则判甲胜，否则判乙胜。 ⑴乙先划甲后划，谁有必胜策略？必胜策略是怎样的？ ⑵甲先划乙后划，谁有必胜策略？必胜策略是怎样的？ 【例4】 如果一个自然数的2004倍恰有2004个约数，这个自然数自己最少有多少个约数？
测试题 【例1】求所有能被30整除，且恰有30个不同约数的自然数。 【例2】在1到100中，恰好有6个约数的数有多少个？ 答案： 【例1】【分析】 由于30235=??，从质数的观点看整除，如果自然数N 能被30整除，那么自然数N 至少含有三个质因数2，3，5。设：312235r r r N =???。自然数N 恰有30个不同的因数，根据约数的个数公式：12311130235r r r +?+?+?==??（）（）（）。注意 到235??是三个约数之积，由此可知自然数N 中质因数的个数恰好有3个。因此 123111235r r r +?+?+=??（）（）（），由此可知123r r r （，，）必是 124（， ， ）的一个排列。 综上所述，所求的自然数有：24235??，42235??，24235??，42235??，42235??，24235??。 【例2】【分析】 6只能表示为()51+或()()1121++，所以恰好有6个约数的数要么能表示成某个质数的5次方，要么表示为某个质数的平方再乘以另一个质数，100以内符合前者的只有32，符合后者的数枚举如下： 222222222222222232527211213217219223 8323537311 45253 2721???????????????种种种种 所以符合条件的自然数一共有1842116++++=(种)。
1、限幅滤波法(又称程序判断滤波法) A、方法: 根据经验判断,确定两次采样允许的最大偏差值(设为A) 每次检测到新值时判断: 如果本次值与上次值之差<=A,则本次值有效 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值B、优点: 能有效克服因偶然因素引起的脉冲干扰 C、缺点 无法抑制那种周期性的干扰 平滑度差 2、中位值滤波法 A、方法: 连续采样N次(N取奇数) 把N次采样值按大小排列 取中间值为本次有效值 B、优点: 能有效克服因偶然因素引起的波动干扰 对温度、液位的变化缓慢的被测参数有良好的滤波效果 C、缺点: 对流量、速度等快速变化的参数不宜 3、算术平均滤波法 A、方法: 连续取N个采样值进行算术平均运算 N值较大时:信号平滑度较高,但灵敏度较低 N值较小时:信号平滑度较低,但灵敏度较高 N值的选取:一般流量,N=12;压力:N=4 B、优点: 适用于对一般具有随机干扰的信号进行滤波 这样信号的特点是有一个平均值,信号在某一数值范围附近上下波动 C、缺点: 对于测量速度较慢或要求数据计算速度较快的实时控制不适用 比较浪费RAM 4、递推平均滤波法(又称滑动平均滤波法) A、方法: 把连续取N个采样值看成一个队列 队列的长度固定为N 每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则) 把队列中的N个数据进行算术平均运算,就可获得新的滤波结果 N值的选取:流量,N=12;压力:N=4;液面,N=4~12;温度,N=1~4 B、优点:
对周期性干扰有良好的抑制作用,平滑度高 适用于高频振荡的系统 C、缺点: 灵敏度低 对偶然出现的脉冲性干扰的抑制作用较差 不易消除由于脉冲干扰所引起的采样值偏差 不适用于脉冲干扰比较严重的场合 比较浪费RAM 5、中位值平均滤波法(又称防脉冲干扰平均滤波法) A、方法: 相当于“中位值滤波法”+“算术平均滤波法” 连续采样N个数据,去掉一个最大值和一个最小值 然后计算N-2个数据的算术平均值 N值的选取:3~14 B、优点: 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰,可消除由于脉冲干扰所引起的采样值偏差C、缺点: 测量速度较慢,和算术平均滤波法一样 比较浪费RAM 6、限幅平均滤波法 A、方法: 相当于“限幅滤波法”+“递推平均滤波法” 每次采样到的新数据先进行限幅处理, 再送入队列进行递推平均滤波处理 B、优点: 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰,可消除由于脉冲干扰所引起的采样值偏差C、缺点: 比较浪费RAM 7、一阶滞后滤波法 A、方法: 取a=0~1 本次滤波结果=(1-a)*本次采样值+a*上次滤波结果 B、优点: 对周期性干扰具有良好的抑制作用 适用于波动频率较高的场合 C、缺点: 相位滞后,灵敏度低 滞后程度取决于a值大小
数学竞赛讲座 数论的方法技巧(上) 数论是研究整数性质的一个数学分支,它历史悠久,而且有着强大的生命力。数论问题叙述简明,“很多数论问题可以从经验中归纳出来,并且仅用三言两语就能向一个行外人解释清楚,但要证明它却远非易事”。因而有人说:“用以发现天才,在初等数学中再也没有比数论更好的课程了。任何学生,如能把当今任何一本数论教材中的习题做出,就应当受到鼓励,并劝他将来从事数学方面的工作。”所以在国内外各级各类的数学竞赛中,数论问题总是占有相当大的比重。 小学数学竞赛中的数论问题,常常涉及整数的整除性、带余除法、奇数与偶数、质数与合数、约数与倍数、整数的分解与分拆。主要的结论有: 1.带余除法:若a,b是两个整数,b>0,则存在两个整数q,r,使得abq+r(0≤r 4.约数个数定理:设n的标准分解式为(1),则它的正约数个数为: d(n)(a1+1)(a2+1)…(ak+1)。 5.整数集的离散性:n与n+1之间不再有其他整数。因此,不等式x 单片机利用软件抗干扰的几种滤波方法 1、限幅滤波法（又称程序判断滤波法） A、方法： 根据经验判断，确定两次采样允许的最大偏差值（设为A），每次检测到新值时判断： 如果本次值与上次值之差<=A,则本次值有效； 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值。 B、优点： 能有效克服因偶然因素引起的脉冲干扰。 C、缺点 无法抑制那种周期性的干扰，平滑度差。 2、中位值滤波法 A、方法： 连续采样N次（N取奇数），把N次采样值按大小排列，取中间值为本次有效值。 B、优点： 能有效克服因偶然因素引起的波动干扰，对温度、液位的变化缓慢的被测参数有良好的滤波效果。 C、缺点： 对流量、速度等快速变化的参数不宜。 3、算术平均滤波法 A、方法： 连续取N个采样值进行算术平均运算，N值较大时：信号平滑度较高，但灵敏度较低；N值较小时：信号平滑度较低，但灵敏度较高；N值的选取：一般流量，N=12；压力：N=4。 B、优点： 适用于对一般具有随机干扰的信号进行滤波，这样信号的特点是有一个平均值，信号在某一数值范围附近上下波动。 C、缺点： 对于测量速度较慢或要求数据计算速度较快的实时控制不适用，比较浪费RAM。 4、递推平均滤波法（又称滑动平均滤波法）。 A、方法： 把连续取N个采样值看成一个队列，队列的长度固定为N，每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则)，把队列中的N个数据进行算术平均运算,就可获得新的滤波结果。N值的选取：流量，N=12；压力：N=4；液面，N=4~12；温度，N=1~4。 B、优点： 对周期性干扰有良好的抑制作用，平滑度高，适用于高频振荡的系统 C、缺点： 灵敏度低，对偶然出现的脉冲性干扰的抑制作用较差，不易消除由于脉冲干扰所引起的采样值偏差，不适用于脉冲干扰比较严重的场合，比较浪费RAM。 5、中位值平均滤波法（又称防脉冲干扰平均滤波法） A、方法： 相当于“中位值滤波法”+“算术平均滤波法”，连续采样N个数据，去掉一个最大值和一个最小值，然后计算N-2个数据的算术平均值，N值的选取：3~14， B、优点： 融合了两种滤波法的优点，对于偶然出现的脉冲性干扰，可消除由于脉冲干扰所引起的采样值偏差。 C、缺点： 测量速度较慢，和算术平均滤波法一样，比较浪费RAM。 6、限幅平均滤波法 第十讲：数论之余数问题 余数问题是数论知识板块中另一个内容丰富，题目难度较大的知识体系，也是各大杯赛小升初考试必考的奥数知识点，所以学好本讲对于学生来说非常重要。 许多孩子都接触过余数的有关问题，并有不少孩子说“遇到余数的问题就基本晕菜了！” 余数问题主要包括了带余除法的定义，三大余数定理（加法余数定理，乘法余数定理，和同余定理），及中国剩余定理和有关弃九法原理的应用。 知识点拨： 一、带余除法的定义及性质： 一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r, 0≤r＜b；我们称上面的除法算式为一个带余除法算式。这里： r=时：我们称a可以被b整除，q称为a除以b的商或完全商 (1)当0 r≠时：我们称a不可以被b整除，q称为a除以b的商或不完全商 (2)当0 一个完美的带余除法讲解模型: 如图，这是一堆书，共有a本，这个a就可以理解为被除数，现在 要求按照b本一捆打包，那么b就是除数的角色，经过打包后共打包了 c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。 这个图能够让学生清晰的明白带余除法算式中4个量的关系。并且 可以看出余数一定要比除数小。 二、三大余数定理： 1.余数的加法定理 a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。 例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等 于4，即两个余数的和3+1. 当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。 例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2. 2.余数的乘法定理 a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。 例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。 当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。 例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2. 3.同余定理 初中奥数：数论问题位值原理的解题技巧 1、一个两位数，其十位与个位上的数字交换以后，所得的两位数 比原来小27，则满足条件的两位数共有______个. 【解析】：11+12+13+14+15+16+17=98.若中心圈内的数用a表示，因三条线的总和中每个数字出现一次，只有a多用3两次，所以98+2a 应是3的倍数，a=11，12，…，17代到98+2a中去试，得到a=11，14，17时，98+2a是3的倍数. (1)当a=11时98+2a=120，120÷3=40 (2)当a=14时98+2a=126，126÷3=42 (3)当a=17时98+2a=132，132÷3=44 相对应的解见上图. 2、一个三位数，它等于抹去它的首位数字之后剩下的两位数的4倍于25之差，求这个数。 解答：设它百位数字为a,十位数字为b,个位数字为c 则100a+10b+c=4(10b+c) 化简得5(20a-6b+5)=3c 因为c为正整数,所以20a-6b+5是3的倍数 又因为0≤c≤9 所以0≤3c/5≤5.4 所以0≤20a-6b+5=3c/5≤5.4 所以3c/5=3 即c=5 所以20-6b+5=3 化简得3b-1=10a 按照同样的分析方法,3b-1是10的倍数,解得b=7 最后再算出10a=3*7-1=20 则a=2 所以答案为275。 3、a、b、c是1——9中的三个不同数码，用它们组成的六个没有重复数字的三位数之和是(a+b+c)的多少倍? 解答：组成六个数之和为： 10a+b+10a+c+10b+a+10b+c+10c+a+10c+b =22a+22b+22c =22(a+b+c) 很显然，是22倍 4、有2个3位数，它们的和是999，如果把较大的数放在较小数的左边，所成的数正好等于把较小数放在较大数左边所成数的6倍，那么这2数相差多少呢? 解答：abc+def=999，abcdef=6defabc，根据位值原 理,1000abc+def=6000def+6abc 化简得994abc=5999def，两边同时除以7得142abc=857def，所以abc=857，def=142 所以857-142=715 5、将一个三位数的数字重新排列，在所得到的三位数中，用的减去最小的，正好等于原来的三位数，求原来的三位数。 费马小定理数论的证明方法 2007年12月28日星期五 01:29 P.M. 费马小定理数论的证明方法 Mod的简单介绍 (Congruence) a=b(mod m) a和b除以m以后有相同的余数 不失一般性地另a>b 则a=km+b比如7=1 mod 2 9=4 mod 5 简单的Congruence 计算 如果a=b mod m c=d mod m 则a=km+b c=tm+d 直接可推出 a+b=c+d (mod m) a-b=c-d (mod m) ab=cd (mod m) 并且可得存在正整数c 使得ac=bc (mod mc) 当然ac=bc(mod m) 费马小定理如果a,p互质且q是质数则a^(p-1)=1 (mod p) 考虑数列An= a,2a,3a,4a…… (p-1)a 假设An中有2项ma, na 被p除以后的余数是相同的.那么必然有ma=na (mod p) 即a(m-n)=0(mod p) 由于a和p互质,所以m-n=0(mod p) 但是m,n属于集合{1,2,3..p-1} 且m不等于n,所以m-n不可能是p的倍数.和假设产生矛盾所以An中任意2项被p除 得到的余数都是不同的, 并且对于任一个整数被p除以后的余数最多有p-1个,分别是 1,2,3,….p-1 而数列An中恰好有p-1个数,所以数列中的数被p除以后的余数一定正好包含所有的1,2,3,4,5…. p-1 由此我们可以用Congruence的乘法性质, a*2a*3a*…(p-1)a=1*2*3*4..*(p-1) (mod p) 对两边进行化简,即可以得到a^(p-1)=1 (mod p) Euler’s Totient function 定义o(n)是所有比n小且和n互质的数的总数(包括1) 例如o(5)=4 o(10)=8 我们发现引入这个以后费马小定理可以改写为a^o(p)=1 (mod p) 事实上,这个结论对所有的正整数n都成立即a^o(n)=1 (mod n) 软件滤波在嵌入式的数据采集和处理中有着很重要的作用，这10种方法各有优劣，根据自己的需要选择。同时提供了C语言的参考代码，希望对各位能有帮助。 1、限幅滤波法（又称程序判断滤波法） A、方法： 根据经验判断，确定两次采样允许的最大偏差值（设为A） 每次检测到新值时判断： 如果本次值与上次值之差<=A,则本次值有效 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值 B、优点： 能有效克服因偶然因素引起的脉冲干扰 C、缺点 无法抑制那种周期性的干扰 平滑度差 /* A值可根据实际情况调整 value为有效值，new_value为当前采样值 滤波程序返回有效的实际值 */ #define A 10 char value; char filter() char new_value; new_value = get_ad(); if ( ( new_value - value > A ) || ( value - new_value > A ) return value; return new_value; } 2、中位值滤波法 A、方法： 连续采样N次（N取奇数） 把N次采样值按大小排列 取中间值为本次有效值 B、优点： 能有效克服因偶然因素引起的波动干扰 对温度、液位的变化缓慢的被测参数有良好的滤波效果 C、缺点： 对流量、速度等快速变化的参数不宜 /* N值可根据实际情况调整 排序采用冒泡法*/ #define N 11 char filter() { char value_buf[N]; char count,i,j,temp; for ( count=0;count 小学奥数中的数论问题 在奥数竞赛中有一类题目叫做数论题，这一部分的题目具有抽象，思维难度大，综合运用知识点多的特点，基本上出现数论题目的时候大部分同学做得都不好。 一、小学数论究包括的主要内容 我们小学所学习到的数论内容主要包含以下几类： 整除问题：（1）整除的性质；（2）数的整除特征（小升初常考内容） 余数问题：（1）带余除式的运用被除数=除数×商+余数.（余数总比除数小） （2）同余的性质和运用 奇偶问题：（1）奇偶与加减运算；（2）奇偶与乘除运算质数合数：重点是质因数的分解（也称唯一分解定理）约数倍数：（1）最大公约最小公倍数两大定理 一、两个自然数分别除以它们的最大公约数，所得的商互质。 二、两个数的最大公约和最小公倍的乘积等于这两个数的乘积。 （2）约数个数决定法则（小升初常考内容） 整数及分数的分解与分拆：这一部分在难度较高竞赛中常 出现，属于较难的题型。二、数论部分在考试题型中的地位 在整个数学领域，数论被当之无愧的誉为“数学皇后”。翻开任何一本数学辅导书，数论的题型都占据了显著的位置。在小学各类数学竞赛和小升初考试中，系统研究发现，直接运用数论知识解题的题目分值大概占据整张试卷总分的30%左右，而在竞赛的决赛试题和小升初一类中学的分班测试题中，这一分值比例还将更高。 出题老师喜欢将数论题作为区分尖子生和普通学生的依据，这一部分学习的好坏将直接决定你是否可以在选拔考试中拿到满意的分数。三、孩子在学习数论部分常常会遇到的问题 数学课本上的数论简单，竞赛和小升初考试的数论不简单。 有些孩子错误地认为数论的题目很简单，因为他们习惯了数学课本上的简单数论题，比如：例1：求36有多少个约数？ 这道题就经常在孩子们平时的作业里和单元测试里出现。可是小升初考题里则是：例2：求3600有多少个约数？ 很多孩子就懵了，因为“平时考试里没有出过这么大的数！”（孩子语）于是乎也硬着头皮用课堂上求约数的方法去求，白白浪费了大把的时间，即使最后求出结果也并不划 数论短期班100题手册 知识框架体系 一、奇偶性质 1．奇数和偶数的表示方法： 因为偶数是2的倍数，所以通常用2k这个式子来表示偶数(这里k是整数)； 因为任何奇数除以2其余数总是1，所以通常用式子21 k+来表示奇数(这里k是整数)．特别注意，因为0能被2整除，所以0是偶数．最小的奇数是1，最小的偶数是0． 2．奇数与偶数的运算性质： 性质一：偶数+偶数=偶数(偶数-偶数=偶数) 奇数+奇数=偶数(奇数-奇数=偶数) 偶数+奇数=奇数(偶数-奇数=奇数) 可以看出：一个数加上(或减去)偶数，不改变这个数的奇偶性； 一个数加上(或减去)奇数，它的奇偶性会发生变化． (也可以这样记：奇偶性相同的数加减得偶数，奇偶性不同的数加减得奇数．) 性质二：偶数?奇数=偶数(推广开来还可以得到：偶数个奇数相加得偶数) 偶数?偶数=偶数(推广开就是：偶数个偶数相加得偶数) 奇数?奇数=奇数(推广开就是：奇数个奇数相加得奇数) 可以看出：一个数乘以偶数时，乘积必为偶数；几个数的积为奇数时，每个乘数都是奇数．(也可以这样简记：对于乘法，见偶(数)就得偶(数))． 性质三：任何一个奇数一定不等于任何一个偶数． 二、整除 1．整除的定义 所谓“一个自然数a能被另一个自然数b整除”就是说“商a b 是一个整数”；或者换句话说： 存在着第三个自然数c，使得a b c =?．这是我们就说“b整除a”或者“a被b整除”，其中b 叫a的约数，a是b的倍数，记作：“|b a”． 2．整除性质： ⑴传递性若|c b，|b a，则|c a． ⑵可加性若|c a，|c b，则|c a b ± （）． ⑶可乘性若|c a，|d b，则| cd ab． 3．整除的特征 ⑴4,25,8,125,16,625的整除特征 能否被4和25整除是看末两位；能否被8和125整除是看末三位；能否被16和625整除是看末四位(100425 =?,10008125 =?,1000016625 =?,100000323125 =?) ⑵3,9的整除特征 能否被9整除是看数字之和是否是9的倍数，并且这个数除以9的余数和这个数数字之和除以9的余数相同，因此判断一个数除以九余几就可以先把和是9的倍数的数划掉，剩下的数是几就代表 软件滤波算法（转载） 这几天做一个流量检测的东西，其中用到了对数据的处理部分，试了很多种方法，从网上找到这些个滤波算法，贴出来记下 需要注意的是如果用到求平均值的话，注意总和变量是否有溢出，程序没必要照搬，主要学习这些方法，相信做东西的时候都能用得上 1、限幅滤波法（又称程序判断滤波法） A、方法： 根据经验判断，确定两次采样允许的最大偏差值（设为A） 每次检测到新值时判断： 如果本次值与上次值之差<=A,则本次值有效 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值 B、优点： 能有效克服因偶然因素引起的脉冲干扰 C、缺点 无法抑制那种周期性的干扰 平滑度差 2、中位值滤波法 A、方法： 连续采样N次（N取奇数） 把N次采样值按大小排列 取中间值为本次有效值 B、优点： 能有效克服因偶然因素引起的波动干扰 对温度、液位的变化缓慢的被测参数有良好的滤波效果 C、缺点： 对流量、速度等快速变化的参数不宜 3、算术平均滤波法 A、方法： 连续取N个采样值进行算术平均运算 N值较大时：信号平滑度较高，但灵敏度较低 N值较小时：信号平滑度较低，但灵敏度较高 N值的选取：一般流量，N=12；压力：N=4 B、优点： 适用于对一般具有随机干扰的信号进行滤波 这样信号的特点是有一个平均值，信号在某一数值范围附近上下波动 C、缺点： 对于测量速度较慢或要求数据计算速度较快的实时控制不适用 比较浪费RAM 4、递推平均滤波法（又称滑动平均滤波法） A、方法： 把连续取N个采样值看成一个队列 队列的长度固定为N 每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则) 把队列中的N个数据进行算术平均运算,就可获得新的滤波结果 N值的选取：流量，N=12；压力：N=4；液面，N=4~12；温度，N=1~4 B、优点： 对周期性干扰有良好的抑制作用，平滑度高 适用于高频振荡的系统 C、缺点： 灵敏度低 对偶然出现的脉冲性干扰的抑制作用较差 不易消除由于脉冲干扰所引起的采样值偏差 不适用于脉冲干扰比较严重的场合 比较浪费RAM 5、中位值平均滤波法（又称防脉冲干扰平均滤波法） A、方法： 相当于“中位值滤波法”+“算术平均滤波法” 连续采样N个数据，去掉一个最大值和一个最小值 然后计算N-2个数据的算术平均值 N值的选取：3~14 B、优点： 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰，可消除由于脉冲干扰所引起的采样值偏差 C、缺点： 测量速度较慢，和算术平均滤波法一样 比较浪费RAM 整数的p 进位制及其应用 基础知识 给定一个m 位的正整数A ，其各位上的数字分别记为021,,,a a a m m ，则此数可以简记为：021a a a A m m （其中01 m a ）。 由于我们所研究的整数通常是十进制的，因此A 可以表示成10的1 m 次多项 式 ， 即 12211101010a a a a A m m m m ，其中 1,,2,1},9,,2,1,0{ m i a i 且01 m a ，像这种10的多项式表示的数常常简 记为10021)(a a a A m m 。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作021a a a A m m ，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。为了具备一般性，我们给出正整数A 的p 进制表示： 012211a p a p a p a A m m m m ，其中1,,2,1},1,,2,1,0{ m i p a i 且 01 m a 。而m 仍然为十进制数字，简记为p m m a a a A )(021 。 典例分析 例1．(2007年中国数学奥林匹克协作体竞赛试题)假定正整数N 的8进制表示为 8)43211234567765( N ，那么下面四个判断中，正确的是（ ） A 、N 能被7整除而不能被9整除 B 、N 能被9整除而不能被7整除 C 、N 不能被7整除也不能被9整除 D 、N 既能被7整除也能被9整除 答 D 由于)7(mod 18 ，所以)7(m od 18 i k i k i i i i k k a a a a a a N 0 8011)7(mod 8 即N 能被7整除 N 的8进制表示下各位数字之和能被7整除。 类似的，N 能被9整除 N 的8进制表示下奇数位数字之和与偶数位数字之和的差能被9整除 1、限幅滤波法（又称程序判断滤波法） A、方法： 根据经验判断，确定两次采样允许的最大偏差值（设为A） 每次检测到新值时判断： 如果本次值与上次值之差<=A,则本次值有效 如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值 B、优点： 能有效克服因偶然因素引起的脉冲干扰 C、缺点 无法抑制那种周期性的干扰 平滑度差 2、中位值滤波法 A、方法： 连续采样N次（N取奇数） 把N次采样值按大小排列 取中间值为本次有效值 B、优点： 能有效克服因偶然因素引起的波动干扰 对温度、液位的变化缓慢的被测参数有良好的滤波效果 自动化科协 C、缺点： 对流量、速度等快速变化的参数不宜 3、算术平均滤波法 A、方法： 连续取N个采样值进行算术平均运算 N值较大时：信号平滑度较高，但灵敏度较低 N值较小时：信号平滑度较低，但灵敏度较高 N值的选取：一般流量，N=12；压力：N=4 B、优点： 适用于对一般具有随机干扰的信号进行滤波 这样信号的特点是有一个平均值，信号在某一数值范围附近上下波动 C、缺点： 对于测量速度较慢或要求数据计算速度较快的实时控制不适用 比较浪费RAM 4、递推平均滤波法（又称滑动平均滤波法） A、方法： 把连续取N个采样值看成一个队列 队列的长度固定为N 每次采样到一个新数据放入队尾,并扔掉原来队首的一次数据.(先进先出原则) 把队列中的N个数据进行算术平均运算,就可获得新的滤波结果 N值的选取：流量，N=12；压力：N=4；液面，N=4~12；温度，N=1~4 B、优点： 对周期性干扰有良好的抑制作用，平滑度高 适用于高频振荡的系统 C、缺点： 灵敏度低 对偶然出现的脉冲性干扰的抑制作用较差 不易消除由于脉冲干扰所引起的采样值偏差 不适用于脉冲干扰比较严重的场合 比较浪费RAM 5、中位值平均滤波法（又称防脉冲干扰平均滤波法） A、方法： 相当于“中位值滤波法”+“算术平均滤波法” 连续采样N个数据，去掉一个最大值和一个最小值 然后计算N-2个数据的算术平均值 N值的选取：3~14 B、优点： 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰，可消除由于脉冲干扰所引起的采样值偏差 C、缺点： 自动化科协 测量速度较慢，和算术平均滤波法一样 比较浪费RAM 6、限幅平均滤波法 A、方法： 相当于“限幅滤波法”+“递推平均滤波法” 每次采样到的新数据先进行限幅处理， 再送入队列进行递推平均滤波处理 B、优点： 融合了两种滤波法的优点 对于偶然出现的脉冲性干扰，可消除由于脉冲干扰所引起的采样值偏差 C、缺点： 比较浪费RAM 7、一阶滞后滤波法 A、方法： 取a=0~1 本次滤波结果=（1-a）*本次采样值+a*上次滤波结果 B、优点： 对周期性干扰具有良好的抑制作用 适用于波动频率较高的场合 C、缺点： 初一数学竞赛培训讲座数论的方法技巧（上） 数论是研究整数性质的一个数学分支，它历史悠久，而且有着强大的生命力.数论问题叙述简明，“很多数论问题可以从经验中归纳出来，并且仅用三言两语就能向一个行外人解释清楚，但要证明它却远非易事”.因而有人说：“用以发现天才，在初等数学中再也没有比数论更好的课程了.任何学生，如能把当今任何一本数论教材中的习题做出，就应当受到鼓励，并劝他将来从事数学方面的工作.”所以在国内外各级各类的数学竞赛中，数论问题总是占有相当大的 比重. 小学数学竞赛中的数论问题，常常涉及整数的整除性、带余除法、奇数与偶数、质数与合数、约数与倍数、整数的分解与分拆.主要的结论有： 1．带余除法：若a，b是两个整数，b＞0，则存在两个整数q，r，使得a=bq+r（0≤r＜b），且q，r 是唯一的.特别地，如果r=0，那么a=bq.这时，a被b整除，记作b|a，也称b是a的约数，a是b的倍数. 2．若a|c，b|c，且a，b互质，则ab|c. 3．唯一分解定理：每一个大于1的自然数N都可以写成质数的连乘积， 即 (1，其中p1＜p2＜…＜p k为质数，a1，a2，…，a k为自然数，并且这种表示是唯一的.（1）式称为N的质因数分解或标准分解. 4．约数个数定理：设n的标准分解式为（1），则它的正约数个数为： d（n）=（a1+1）（a2+1）…（a k+1）. 5．整数集的离散性：n与n+1之间不再有其他整数.因此，不等式x＜y与x≤y-1是等价的. 下面，我们将按解数论题的方法技巧来分类讲解. 一、利用整数的各种表示法 对于某些研究整数本身的特性的问题，若能合理地选择整数的表示形式，则常常有助于问题的解决.这些常用的形式有： 1．十进制表示形式：n=a n10n +a n-110 n-1 +…+a0； 数论问题的常用方法 数论是研究数的性质的一门科学，它与中学数学教育有密切的联系。数论问题解法灵活，题型丰富，它是中学数学竞赛试题的源泉之一。下面介绍数论试题的常用方法. 1.基本原理 为了使用方便，我们将数论中的一些概念和结论摘录如下： 我们用),...,,(21n a a a 表示n 个整数1a ,2a ,…,n a 的最大公约数。用[1a ,2a ,…,n a ]表示 1a ,2a ,…,n a 的最小公倍数。对于实数x ，用[x ]表示不超过x 的最大整数，用{x }=x -[x ] 表示x 的小数部分。对于整数b a ,,若)(|b a m -，,1≥m 则称b a ,关于模m 同余，记为 )(mod m b a ≡。对于正整数m ，用)(m ?表示{1，2，…，m }中与m 互质的整数的个数， 并称)(m ?为欧拉函数。对于正整数m ，若整数m r r r ,...,,21中任何两个数对模m 均不同余，则称{m r r r ,...,,21}为模m 的一个完全剩余系；若整数)(21,...,,m r r r ?中每一个数都与m 互质，且其中任何两个数关于模m 不同余，则称{)(21,...,,m r r r ?}为模m 的简化剩余系。 定理1 设b a ,的最大公约数为d ，则存在整数y x ,，使得 yb xa d +=. 定理2 （1）若)(mod m b a i i ≡，1=i ，2，…，n ，)(mod 21m x x =，则 1 1n i i i a x =∑≡2 1 n i i i b x =∑； （2）若)(mod m b a ≡，),(b a d =，m d |，则 )(mod d m d b d a ≡； （3）若)(mod m b a ≡，),(b a d =，且1),(=m d ，则)(mod m d b d a ≡； （4）若b a ≡（i m mod ），n i ,...,2,1=，M=[n m m m ,...,,21]，则b a ≡（M mod ）. 定理3 （1）1][][1+<≤<-x x x x ； （2）][][][y x y x +≥+； （3）设p 为素数，则在!n 质因数分解中，p 的指数为 ∑ ≥1 k k p n . 几个精彩的数论问题 从同事那里借来了一本单墫教授?主编的《初等数论》奥数书，看到很多精彩的问题，在这里做个笔记，与大家一同分享。不少问题和答案都有过重新叙述，个别问题有所改动。 问题：找出所有使得 2n - 1 能被 7 整除的正整数 n 。 答案：由于 2n的二进制表达为1000…00 （n 个 0），因此 2n - 1 的二进制表达为111…11 （n 个 1）。而 7 的二进制表达是 111 ，要想让它整除 n 个1 ，显然 n 必须是也只能是 3 的倍数。 问题：是否存在 100 个数，使得它们的和等于它们的最小公倍数？ 答案：是的。考虑3, 2 × 3, 2 × 32, 2 × 33, …, 2 × 398, 399，它们的和为： 3 + 2 × 3 + 2 × 32+ 2 × 33+ … + 2 × 398 + 399 = 3 × (1 + 2) + 2 × 32+ 2 × 33+ … + 2 × 398 + 399 = 32+ 2 × 32+ 2 × 33+ … + 2 × 398 + 399 = 32× (1 + 2) + 2 × 33+ … + 2 × 398 + 399 = 33+ 2 × 33+ … + 2 × 398 + 399 = ... ... = 399 + 399 = 2 × 399 而这 100 个数的最小公倍数正是 2 × 399。 问题：能否找出 100 个不同的正整数，使得其中任意 2 ≤ k ≤ 100 个数的算术平均数都恰为整数。 答案：能。这个问题非常唬人，它的答案异常简单： 1 · 100!, 2 · 100!, 3 · 100!, …, 100 · 100! 显然满足要求。 问题：求证，存在任意长的连续正整数，使得其中任何一个数都不是质数的幂（当然更不能是质数）。 数据处理中的几种常用数字滤波算法 王庆河王庆山 (济钢集团计量管理处，济南250101) (济钢集团中厚板厂，济南250101) 摘要随着数字化技术的发展，数字滤波技术成为数字化仪表和计算机在数据采集中的关键性技术，本文对常用的几种数字滤波算法的原理进行描述，并给出必要的数学模型。 关键词：数据采样噪声滤波移动滤波 一、引言 在仪表自动化工作中，经常需要对大量的数据进行处理，这些数据往往是一个时间序列或空间序列，这时常会用到数字滤波技术对数据进行预处理。数字滤波是指利用数学的方法对原始数据进行处理，去掉原始数据中掺杂的噪声数据，获得最具有代表性的数据集合。 数据采样是一种通过间接方法取得事物状态的技术如将事物的温度、压力、流量等属性通过一定的转换技术将其转换为电信号，然后再将电信号转换为数字化的数据。在多次转换中由于转换技术客观原因或主观原因造成采样数据中掺杂少量的噪声数据，影响了最终数据的准确性。 为了防止噪声对数据结果的影响，除了采用更加科学的采样技术外，我们还要采用一些必要的技术手段对原始数据进行整理、统计，数字滤波技术是最基本的处理方法，它可以剔除数据中的噪声，提高数据的代表性。 二、几种常用的数据处理方法 在实际应用中我们所用的数据滤波方法很多，在计算机应用高度普及的今天更有许多新的方法出现，如逻辑判断滤波、中值滤波、均值滤波、加权平均 2中值滤波 中值滤波是对采样序列按大小排滤波、众数滤波、一阶滞后滤波、移动滤波、复合滤波 等。 假设我们采用前端仪表采集了一组采样周期为1s的温度数据的时间序列 T0为第0s 采集的温度值，Ti为第is采集的温度值。下面介绍如何应用几种不同滤波算法来计算结果温度T。 1.程序判断滤波 当采样信号由于随机干扰、误检测或变送器不稳定引起严重失真时，可采用程序判断滤波算法，该算法的基本原理是根据生产经验，确定出相邻采样输入信号可能的最大偏差△T,若超过此偏差值，则表明该输入信号是干扰信号，应该去掉，若小于偏差值则作为此次采样值。 (1)限幅滤波 限幅滤波是把两次相邻的采集值进行相减，取其差值的绝对值△T作为比较依据，如果小于或等于△T,则取此次采样值,如果大于△T,则取前次采样值，如式(1)所示：10种简单的数值滤波方法
六年级奥数-第十讲.数论之余数问题.教师版
初中奥数：数论问题位值原理的解题技巧
费马小定理数论的证明方法
常用的软件滤波方法(工程师必备).
(完整版)小学奥数中的数论问题
数论班100题手册
(整理)11种滤波方法+范例代码.
数论的方法和技巧05整数的p进位制及其应用
十种数字滤波方法
初一数学竞赛培训讲座 数论的方法技巧(上)
10数论问题的常用方法(教师版)
几个精彩的数论问题
数据处理中的几种常用数字滤波算法
相关主题
文本预览