ACM课件(lecture_10)特殊的数

格式：ppt
大小：1.45 MB
文档页数：53

下载文档原格式

ACM(lecture_10)特殊的数

空间换时间！！
2021/6/3
26
Catalan number
2021/6/3
27
HDOJ_1134: Game of Connections
8 7 6
5
1 2 3
4
2021/6/3
28
Catalan Number
Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...)
trees with n+1 nodes
3 nodes:
2021/6/3
37
4 nodes: 5 nodes:
2021/6/3
38
4. the number of paths of length 2n through an n-
by-n grid that do not rise above the main diagonal
2021/6/3
6
January
2021/6/3
7
February
2021/6/3
8
March
2021/6/3
9
April
2021/6/3
10
May、June…
???
2021/6/3
11
The number series is—— 1、1、2、3、5… This is fibonacci number！
Some other pictures
2021/6/3
12
2021/6/3
13
2021/6/3
14

竞赛讲座（特殊的正整数）

竞赛讲座(特殊的正整数)一、知识要点1、完全平方数及其性质定义1 如果一个数是一个整数的平方，则称这个数是完全平方数。

如：1、4、9、…等都是完全平方数，完全平方数有下列性质：性质1 任何完全平方数的个位数只能是0，1，4，5，6，9中的一个。

性质2 奇完全平方数的十位数一定是偶数。

性质3 偶完全平方数是4的倍数。

性质4 完全平方数有奇数个不同的正约数。

性质5 完全平方数与完全平方数的积仍是完全平方数，完全平方数与非完全平方数的积是非完全平方数。

2、质数与合数定义2 一个大于1的整数a,如果只有1和a 这两个约数，那么a 叫做质数。

定义3 一个大于1的整数a,如果只有1和a 这两个约数外，还有其他正约数，那么a 叫做合数。

1既不是质数也不是合数。

3、质数与合数的有关性质(1) 质数有无数多个(2) 2是唯一的既是质数，又是偶数的整数，即是唯一的偶质数。

大于2的质数必为奇数。

(3) 若质数p ∣a •b ，则必有p ∣a 或p ∣b 。

(4) 若正整数a 、b 的积是质数p ，则必有a=p 或b=p. (5) 唯一分解定理：任何整数n(n>1)可以唯一地分解为：k a ka a p p p n 2121=, 其中p 1<p 2<…<p k 是质数，a 1，a 2，…，a k 是正整数。

二、例题精讲例1 有一个四位数恰好是个完全平方数，它的千位数字比百位数字多1，比十位数字少1，比个位数字少2，这个四位数是 . 解设所求的四位数为m 2，它的百位数字为a ，则有m 2=1000(a+1)+100a+10(a+2)+(a+3)=1111a+1023=11(101a+93)因为11是质数，所以11∣(101a+93)，而101a+93=11(9a+8)+(2a+5)，所以11∣(2a+5)，由题意 a+3≤9，故a ≤6，从而a=3. 于是所求的四位数为4356.例2 一个四位数有这样的性质：用它的后两位数去除这个四位数得到一个完全平方数(如果它的十位数是0，就只用个位数去除)，且这个平方数正好是前两位数加1的平方。

ACM算法讲座特殊的数

ACM程序设计程序设计
杭州电子科技大学刘春英 acm@
每周一星（）：每周一星（11）：
杭电一名
2011-7-5
2
第十二讲
特殊的数
（Special Number）
2011-7-5
3
Fibonacci Number
The series begins with 0 and 1. After that, use the simple rule: Add the last two numbers to get next. the next. 0 , 1 , 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,...
2011-7-5 44
(3)其他情况： (3)其他情况：其他情况考虑（m+n）个人排队购票的情景， m+n）考虑（m+n）个人排队购票的情景，第（m+n）人站在第（m+n个人的后面，则第（在第（m+n-1）个人的后面，则第（m+n ）个人的排队方式可以由下列两种情况获得：排队方式可以由下列两种情况获得： a.第个人手持￥100的钞票的钞票， a.第（m+n ）个人手持￥100的钞票，则在他之前 (m+（））个人中有个人手持￥50的钞票个人中有m 的钞票，的(m+（n-1））个人中有m个人手持￥50的钞票，个人手持￥100的钞票的钞票，有（n-1）个人手持￥100的钞票，此种情况共有 f(m,nf(m,n-1); b.第个人手持￥50的钞票的钞票， b.第（m+n ）个人手持￥50的钞票，则在他之前的 +n）个人中有m 个人手持￥50的钞票的钞票， (（m-1）+n）个人中有m-1个人手持￥50的钞票，个人手持￥100的钞票此种情况共有f(m 的钞票， f(m有n个人手持￥100的钞票，此种情况共有f(m-1,n);

acm中的数学问题数论部分省公开课一等奖全国示范课微课金奖PPT课件

步骤：
a = 81, b = 63, a mod b = 18 a ← 63, b ← 18, a mod b = 9 a ← 18, b ← 9, a mod b = 0 所以9就是63与81最大条约数
第27页
欧几里德算法
欧几里德算法:
while b>0 do r←a%b a←b b←r
第一部分:同余相关
整除性质
欧几里德算法
扩展欧几里德算法
中国剩下定理
第二部分:素数相关
算术基本定理
欧拉定理
素数测试
Pollard rho方法
第7页
数论主要内容
第一部分:同余相关
整除性质
欧几里德算法
扩展欧几里德算法
中国剩下定理
第二部分:素数相关
算术基本定理
欧拉定理
素数测试
整除基本性质欧几里德算法扩展欧几里德算法中国剩下定理
第43页
中国剩下定理
同模情况下，有这么性质：
乘法标准
8 mod 7 = 1
16 mod 7 = 2 64 mod 7 = 8 mod 7
加法标准 8 mod 7 = 1 10 mod 7 = 3
18 mod 7 = 4
第44页
故d|a。 • 所以d是a,b公因数 • 反之，假如d是a,b公因数，也能证出d
是b,c公因数
第12页
第一部分同余相关
整除基本性质欧几里德算法扩展欧几里德算法中国剩下定理
第13页
请写出12，30共有约数
第14页
请写出12，30共有约数 1,
第15页
请写出12，30共有约数 1, 2,
第37页
扩展欧几里德算法
扩展欧几里德算法(递归实现): int gcd(int a,int b) if b=0 then x←1 y←0 return a d←gcd(b,a%b) x'←y y'←x-[a/b]y x←x' y←y' return d

ACM培训材料PPT课件

}
2020/10/13
7
注意上面程序的M的好处
上面M定义为10000,这样不仅提高了效率而且也节省了空间
如果要你把N阶乘转成2或3进制你会吗? 如:把18!转换成2进制. 如果你不会,那么你还没对那个程序M深刻
理解.
2020/10/13
8
N!末尾有多少个0
很简单,只要N!有多少个5这个因子,就有多少个0.
进位e=0 (e=(a[1]+b[1]+e)/10) c[2]=(a[2]+b[2])%10+e=0, 百位进位e=1,依次下去,
最后把数组输出就是结果(要倒过来输出)
2020/10/13
4
对上面例子的实现
#include<stdio.h>
#include<string.h>
#define N
{
p=a[i]+b[i]+e;
c[i]=p%10;
e=p/10;
}
lc=lb;
while(e>0)
{
lc++;
c[lc]=e%10;
e/=10;
}
for(i=lc;i>=0;i--)
{
printf("%d",c[i]);
}
printf("\n");
return 0;
}
2020/10/13
5
用高精度算N阶乘
汇报人：XXXX 日期：20XX年XX月XX日
11
详细见课堂分析.
2020/10/13
9
fjnu:1743 fjnu:1185 fjnu:1307 fjnu:1191 fjnu:1158

国际大学生程序设计竞赛数论与算法.ppt

分析：显然X1为分子，X2比为分母，其它数可以为分子
也可以为分母。
方法一：将分母X2分解质因数，由于 X2≤1000000000，所以质因数个数不超过29 个。逐一扫描X1，X3，X4…，Xk，看能否将 X2约掉。
方法二：还是逐一扫描X1，X3，X4…，Xk，看能否将X2约掉，但不进行因数分解，而是每次约掉它和X2的最大公约数。
数论基本知识
1。如何求出1～n中的所有素数？ Eraosthenes氏筛法：每次求出一个新的素数，就把n以内的它的所有
倍数都筛去。 2。给出一个数n，如何判断它是不是素数？ 1）朴素的判别法从2开始试除小于n的所有自然数，时间复杂度为
O(n). 2）如果a是n的因子，那么n/a也是n的因子，所以如果n有一个大于1
分析：把数字1，2，3，4从中抽出，然后把其他数字按照原顺序排列组成的自然数w，w×10000整除 7取余有7种可能，即是0，1，2，3，4，5，6。如果能把1，2，3，4排列出7个数，使它们整除7取余的值分别为0，1，2，3，4，5，6，把这4位数接在 w后面即为问题的解。
除法表达式
题目：除法表达式有如下的形式：X1/X2/X3/…/Xk.其中Xi是正整数且X≤1000 000 000（1≤i≤k，k≤10 000）。除法表达式应当按照从左到右的顺序计算。可以在表达式中嵌入顺序。现在给一个除法表达式 E要求告诉是否可以通过增加括号使表达式为E‘，E’ 是整数。
扩展的欧几里德算法
如果（a，b）＝d，那么一定存在x，y满足ax＋by＝d。
Function extended_gcd(a,b:longint; Var x,y:longint):longint;
Begin
if b=0 then begin

(HDUACM2010版_12)特殊的数共52页

(4)Another disguise is the number of ways n votes can come in for each of two candidates A and B in an election, with A never behind B.
08.01.2020
41
HDOJ_1133 Buy the Ticket
trees with n+1 nodes
3 nodes:
08.01.2020
35
4 nodes: 5 nodes:
08.01.2020
36
4. the number of paths of length 2n through an n-by-n grid that do
not rise above the main diagonal
08.01.2020
42
算法分析：
首先假设人无区别
令f(m,n)表示有m个人手持￥50的钞票，n个人手持￥100的钞票时共有的方案总数。则可以分以下情况讨论这个问题：
（1）当n=0时
N=0意味着排队购票的所有人手中拿的都是￥50的钞票，那么这m个人排队方案总数为1。
17
Fibonacci & plants
08.01.2020
18
Fibonacci & plants
08.01.2020
19
Fibonacci & plants
08.01.2020
20
sunflowers （向日葵）
08.01.2020
21
08.01.2020
22
08.01.2020
23பைடு நூலகம்

ACM课件特殊的数.ppt

（2）The self-convolving sequence, c[0]=1, c[n+1] = c[0]c[n] + c[1]c[n-1] + ... + c[n]c[0]
62 2019/12/5
(3) The recurring sequence c[0]=1, (n+2)c[n+1] = (4n+2)c[n], (n>=0).
16 2019/12/5
Some other pictures
17 2019/12/5
18 2019/12/5
19 2019/12/5
20 2019/12/5
21 2019/12/5
Fibonacci number & Golden Section
A special value, closely related to the Fibonacci series, is called the golden section. This value is obtained by taking the ratio of successive terms in the Fibonacci series:
The series begins with 0 and 1. After that, use the simple rule: Add the last two numbers to get the next.
0，1，1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,...
ACM 程序设计
计算机学院刘春英
1 2019/12/5
今天，
你

《ACM递推求解》课件

2 How do recursive algorithms work?
递推算法通常由一个基本情况和一个递推关系组成。当问题达到基本情况时，递归过程结束并返回结果。否则，递归算法将继续调用自身来解决较小的子问题。
3 What are some common examples of recursive algorithms?
Why are ACM递推 problems important?
ACM递推问题是计算机科学和编程中的重要部分。通过解决这些问题，我们可以提高自己的编程能力和算法思维，同时也可以应用递推算法解决实际的问题。
递推算法基础知识
1 What is a recursive algorithm?
递推算法是一种通过不断调用自身来解决问题的算法。它可以将大问题分解成多个较小的子问题，并通过解决子问题的方式来得到最终的解。
3 减少递归深度
通过优化递归算法的终止条件和边界情况，可以减少递归的深度，降低递归算法的时间复杂度。
递推问题的时间复杂度分析
What is time complexity?
时间复杂度是用来衡量算法执行时间与输入规模之间关系的一种指标。它可以帮助我们评估算法的效率和性能。
How to analyze the time complexity of a recursive algorithm?
总结与展望
1 递推算法的重要性
递推算法在算法设计和问题求解中起着重要的作用。通过掌握递推算法的基本知识和常见求解方法，我们可以更好地解决问题并优化算法。
2 未来的发展方向
未来，随着计算机科学和技术的进步，递推算法将继续发展和创新，为解决更复杂的问题提供更高效的求解方法。
《ACM递推求解》PPT课件

Mathematic PPT

2.3.3 随机数函数
随机数函数
名称
Random[ ] Random[Real,xmax] Random[Real,{xmin,xmax}] Random[Complex] Random[Complex,{zmin,zmax}] Random[type,range,n] Random[Integer] Random[Integer,imin,imax] SeedRandom[ ] SeedRandom[s]
复变量的数值函数
名称 x+yI Re[z] Im[z] Conjugate[z] Abs[z] Arg[z] 意义定义复数x+yI 定义复数求复数z的实部求复数的实部求复数z的虚部求复数的虚部求复数z的共轭求复数的共轭求复数z的模求复数的模求复数z的幅角主值求复数的幅角主值
关于机器精度的函数
名称 $MachinePrecision MachineNumberQ[x] 意义获得计算机系统的机器精度判断x是否为机器精度数判断是否为机器精度数是—True；否—False ；
2.2 变量
2.2.1 变量及其定义
在变量名中不能包含空格和标点符号在Mathematica中，对于一次使用后不想保中留的变量，建议使用Clear[]函数立即清除留的变量，建议使用函数立即清除
离散数学中常用，可以组合利用上面介绍的组合函数，离散数学中常用，可以组合利用上面介绍的组合函数，产生各种各样的组合表
2.3.6 初等超越函数
初等超越函数
名称
Exp[x] Log[x] Log[b,x] Sin[z],Cos[z],Tan[z],Csc[z],Sec[z],Cot[z] ArcSin[z], ArcCos[z], ArcTan[z], ArcCsc[z], ArcSec[z], ArcCot[z] Sinh[z],Cosh[z],Tanh[z],Csch[z],Sech[z],Coth[z] ArcSinh[z], ArcCosh[z], ArcTanh[z], ArcCsch[z], ArcSech[z], ArcCoth[z]

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

5
Where this came from?
Key Words:
1225; Pisa; Fibonacci & Frederick II; Math Competition.
2013-8-4 6
January
2013-8-4
7
February
2013-8-4
8
March
2013-8-4
9
April
母牛的故事超级楼梯小兔的棋盘 How Many Trees? Count the Trees Buy the Ticket Game of Connections Train Problem II 下沙的沙子有几粒？
2013-8-4
52
Welcome to HDOJ
Thank You ~
2013-8-4 53
2013-8-4
21
sunflowers （向日葵）
2013-8-4
22
2013-8-4
23
2013-8-4
24
2013-8-4
25
Question:
编程实现这类递归问题时应该注意什么问题？
空间换时间！！
2013-8-4
26
Catalan number
2013-8-4 27
HDOJ_1134: Game of Connections
2. 加括号的方式数目
3 numbers: (1 (2 3)) ((1 2) 3)
4 numbers: (1 (2 (3 4))) (1 ((2 3) 4)) ((1 2) (3 4)) ((1 (2 3)) 4) (((1 2) 3) 4)
2013-8-4
35
(1 (2 (3 (4 5)))) (1 ((2 3) (4 5))) (1 (((2 3) 4) 5)) ((1 2) ((3 4) 5)) ((1 (2 (3 4))) 5) (((1 2) 3) (4 5)) (((1 (2 3)) 4) 5)
2013-8-4 45

(3)其他情况：考虑（m+n）个人排队购票的情景，第（m+n）人站在第（m+n-1）个人的后面，则第（m+n ）个人的排队方式可以由下列两种情况获得： a.第（m+n ）个人手持￥100的钞票，则在他之前的(m+（n-1））个人中有m个人手持￥50的钞票，有（n-1）个人手持￥100的钞票，此种情况共有 f(m,n-1); b.第（m+n ）个人手持￥50的钞票，则在他之前的 (（m-1）+n）个人中有m-1个人手持￥50的钞票，有n个人手持￥100的钞票，此种情况共有f(m-1,n);
(1 (2 ((3 4) 5))) (1 ((2 (3 4)) 5)) ((1 2) (3 (4 5))) ((1 (2 3)) (4 5)) ((1 ((2 3) 4)) 5) (((1 2) (3 4)) 5) ((((1 2) 3) 4) 5)
2013-8-4
36
3.the number of rooted, trivalent
2013-8-4

The series begins with 0 and 1. After that, use the simple rule: Add the last two numbers to get the next. 0 , 1 , 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,...
ACM程序设计
杭州电子科技大学刘春英 acm@
劳动节，
你
了吗？
2013-8-4
2
每周一星（9）：
Lucky-牙牙
2013-8-4
3
第十讲
特殊的数
（Special Number）
2013-8-4
4
Fibonacci Number

Leonardo Fibonacci
1175-1250
2013-8-4
ห้องสมุดไป่ตู้
10
May、June…
???
2013-8-4 11
The number series is—— 1、1、2、3、5…
This is fibonacci number！
Some other pictures
2013-8-4 12
2013-8-4
13
2013-8-4
14
2013-8-4
2013-8-4
43
HDOJ_1133 Buy the Ticket
2013-8-4
44
算法分析：

首先假设人无区别令f(m,n)表示有m个人手持￥50的钞票，n个人手持￥100的钞票时共有的方案总数。则可以分以下情况讨论这个问题：（1）当n=0时 N=0意味着排队购票的所有人手中拿的都是￥50的钞票，那么这m个人排队方案总数为1。（2）当m<n时显然，f(m,n)=0
trees with n+1 nodes
3 nodes:
2013-8-4
37
4 nodes:
5 nodes:
2013-8-4
38
4. the number of paths of length 2n
through an n-by-n grid that do not rise above the main diagonal
15
2013-8-4
16
Fibonacci & Golden Section
2013-8-4
17
Fibonacci & plants
2013-8-4
18
Fibonacci & plants
2013-8-4
19
Fibonacci & plants
2013-8-4
20
Fibonacci & plants
2013-8-4
42
(3) The recurring sequence c[0]=1, (n+2)c[n+1] = (4n+2)c[n], (n>=0). (4)Another disguise is the number of ways n votes can come in for each of two candidates A and B in an election, with A never behind B.
2 x 2 grid:
2013-8-4
39
3 x 3 grid:
4 x 4 grid:
2013-8-4
40
5.
不同形态二叉树的数目
There are 5 binary trees with 3 nodes.
2013-8-4
41
6. 其它应用
（1）The number of ways 2n people, seated round a table, can shake hands in n pairs, without their arms crossing. （2）The self-convolving sequence, c[0]=1, c[n+1] = c[0]c[n] + c[1]c[n-1] + ... + c[n]c[0]
2013-8-4
46
递推公式——

根据加法原理得到: f(m,n)=f(m-1,n)+f(m,n-1) 于是得到f(m,n)的计算公式
2013-8-4
47
计算示意图：
0 0 0 0 0 0 0 0 0 0
2013-8-4
48
计算示意图：
0 1 0 0 0 0 0 0
1
1 1
2013-8-4
0
0
0
49
计算示意图：
0 1 1 0 0 0 0 0 0
1
1 1
2013-8-4
2
3 4
2
5
0
5
0
0
9 14 14
50
对于一般情况（m>=n>0）
可以推出下面直接的公式：
f(m,n)= C(m+n,n)-C(m+n,m+1)
2013-8-4
51
相关练习

2018 2041 2067 1130 1131 1133 1134 1023 1267
2013-8-4 29
Catalan数有哪些应用?
2013-8-4
30
1. 多边形的三角剖分数目
4 sides, 2 ways
2013-8-4 31
5 sides, 5 ways
2013-8-4
32
6 sides, 14 ways
2013-8-4
33
7 sides, 42 ways:
2013-8-4 34
8 1
7
2
6
3
5
4
2013-8-4
28
Catalan Number
Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...)
(1814—1894 Belgium)