没有合适的资源?快使用搜索试试~ 我知道了~
首页算法概论习题详解与数学归纳法应用
算法概论习题详解与数学归纳法应用
需积分: 50 1 下载量 169 浏览量
更新于2024-07-24
收藏 689KB PDF 举报
《算法概论》习题集解答由吴彧文提供,该文档包含了多个练习题及其详细解答。首先,我们来看一些基础题目: 1. Ex.0.1部分涉及了时间复杂度的表示: - a) 提供了一个函数的运行时间分析,使用了大O符号(O)来表示其最坏情况下的增长速率。大O表示法用来描述算法效率的上限。 - b) 通过等比数列求和公式,讨论了函数的时间复杂度与项数的关系,展示了当条件满足时,时间复杂度如何计算。 - c-e) 类似的问题,通过不同函数和复杂度符号表示运行时间。 2. Ex.0.2中,等比数列求和的运用进一步说明了在递归或动态规划问题中如何计算总和,并指出当数列的性质满足特定条件时,总和的计算方式。 3. 数学归纳法在Ex.0.3被应用: - a) 用数学归纳法证明一个关于序列的不等式,通过递推关系展示如何一步步推导出最终结果。 - b) 再次使用数学归纳法,证明一个关于某个函数值的不等式,需要确保递推过程中的基本情况和归纳步骤。 这些题目涵盖了算法分析的基本概念,如时间复杂度分析、数列求和和数学归纳法,这些都是理解算法效率和设计高效算法的重要工具。解答部分深入浅出,有助于学习者理解和掌握算法设计与分析的基础理论。对于学习算法的学生来说,这些习题解答提供了宝贵的实践参考和理论支撑,可以帮助他们巩固对算法概论的理解,并提高解决实际问题的能力。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/6709123/bg10.jpg)
()
()
gcd 1 !,NN−
必大于 1,于是出现矛盾。从而得证。
d) 设
N 的二进制位数为 n ,在用费马小定理测试素性时只需计算
1N
a
−
,因此只
需要
()
On次乘法。而用本定理则需要
(
)
2
n
O 次,显然是太慢了。
Ex.1.36
a) 3 mod 4 1 0 mod 4 1 4
p
ppk≡⇒+≡⇒+=。
b) 首先,化简一下有:
()
(
)
() ()
2
1/4 1/2 1/2
pp p
aaaa
++ −
==×。由费马小定理知
()
()
2
1/2
1mod
p
ap
−
≡ ,再由 Ex.1.35.a 的结论可得:
(
)
1/2
1mod
p
ap
−
≡ 或
(
)
1/2
1mod
p
ap p
−
≡− 。对于这两种情况,如果
(
)
1/2
1
p
a
−
≡
成立的话,当然有
()
()
()
2
1/4 1/2
amod
pp
aaa p
+−
≡× ≡ ,但是如果
(
)
1/2
1mod
p
ap p
−
≡− 呢?
假设
(
)
1/2
1mod
p
ap p
−
≡− 时,存在
2
mod
x
ap≡ ,将后式代入前式得:
()
(
)
()
()
1/2
1
2
1mod
p
p
x
xp p
−
−
≡≡−
,这与费马小定理冲突,所以可知,当
(
)
1/2
1mod
p
ap p
−
≡− , a 的模
p
平方根是不存在的。终上所述,如果
(
)
1/2
1
p
a
−
≡ ,那么 a 的模
p
平方根为
()
(
)
2
1/4p
a
+
,否则 a 的模
p
平方根不存在。
Ex.1.37
a) 列表如下,似乎题目要求是要竖表,不过也没关系了☺。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
规律是:在上图中,以颜色标识的二元组各不相同,且遍历了
{
}
{
}
0,1, 2 , 0,1, 2,3, 4⎡⎤
⎣⎦
所有可能的排列。
b) 对于二元组
{, }
j
k ,如果同时存在
12
,ii使得 mod , mod
nn
ij pik q
≡
≡ ,则有:
![](https://csdnimg.cn/release/download_crawler_static/6709123/bg11.jpg)
11
22
12 12
12
mod , mod
mod , mod
0mod , 0mod
0mod
ij pik q
ij pik q
ii pii q
ii pq
≡≡
≡≡
−≡ −≡
⇒−≡
因
12
,ii均小于
p
q ,所以必有
12
0ii−=,唯一性得证。如果把
Φ
看到是
{
}
i
到
()
{
}
,
j
k
的一个映射,因为元素个数相等,每个 i 均对应到一个
(
)
,
j
k
,且由上
面可知不存在多对一的情况,所以
Φ
必是一一映射。
c) 公式好长:
(
)
(
)
{
}
11
mod mod modijqq pkpp q pq
−−
=+ ,当然有
0 ipq≤< ,另外注意到
(
)
(
)
mod mod , mod modnpqnpnpqnq≡≡
,得:
mod , modij pik q≡≡
d) 对于素数
123
,,,
n
p
pp p ,有
123
0
n
ippp p≤< ,与 n 元组
(
)
123
,,,,
n
j
jj j
形成一一对应,其中 mod , [1, ]
mm
j
ipmn
=
∈ 。另有:
()
1
1
11,
mod mod ,
nn
n
mm m m mm l
m
mllm
ijwwp pw p
−
=
==≠
⎧⎫
=•• =
⎨⎬
⎩⎭
∑
∏
∏
Ex.1.38
a) 直觉告诉我,这里的 r 只需满足两个条件:
1)
10 1
r
p
−> ,即是保证存在 r 位的十制数比
p
大。
2)
10 1mod
r
p
≡ ,即是保证对任意
(
)
,0 9ii
<
< ,有 10 mod
r
ii p≡× 。
以上只是直觉性的猜测,所以这里就不详细证明或证伪了。于是可以算得,当
13p = 时,
6r
=
,因为
6
10 1mod13≡ 。当 17p
=
时,
16r =
,因为
16
10 1mod17≡
。
b) 由费马小定理知
1
10 1mod
p
p
−
≡ ,所以 r 最大只能是 1
p
−
,此外 r 也可能在
![](https://csdnimg.cn/release/download_crawler_static/6709123/bg12.jpg)
1
p
n
−
处,也只可能在
1
p
n
−
处取得。为嘛?设 t 是最小的使得10 1mod
t
p
≡ 的
整数,且
1
p
t
n
−
≠
,由费马小定理
1
10 1mod
p
p
−
≡ 知,必然有
(
)
1mod
10 1mod
pt
p
−
≡ 。于是
()
1mod
p
t− 也满足条件,这与 t 是最小的矛盾。
从而得知,
r 只可能在
1
p
n
−
处取得。
Ex.1.39
利用费马小定理
1
1mod
p
ap
−
≡ ,有:
(
)
mod 1
mod
c
c
bp
b
aa p
−
≡ ,两次 Modular
Exponentiation 操作,如果 ,,,abc p是 n 位数,则时间复杂度为
(
)
3
On 。
Ex.1.40
反证法:如果存在
2
1mod , 1mod
x
px p≡≠±,且
p
为素数,则有:
()
(
)
(
)
2
mod 1 0 mod mod 1 mod 1 0 mod
x
p pxpxp p−≡ ⇔ + − ≡
因为
1mod
x
p≠± ,所以可知1mod1mod1
x
pxpp≤−<+<,又
p
为素数,
知
mod 1
x
p ± 与
p
互素,于是由
()
(
)
mod 1 mod 1 0 mod
x
pxp p+−≡
,根据除
法定理得:
mod 1 0 mod
x
pp
±
≡ ,显然矛盾。于是
p
只能是合数。
Ex.1.41
a) 如果
a
是一个非零的 quadratic residue 模 N ,即存在
2
modax N≡
,显然同时
也应该有
()()
22
modaNx x N≡−≡−
, N 是奇数所以
x
Nx
≠
− 。此外,除
了
,
x
Nx− 之外还有没有可能存在别的数
y
,使得
2
moday N≡ 呢,设存在:
(
)
(
)
22
mod mod mod 0 mod
x
yNxyNxyN N≡⇔+ − ≡
⎡⎤⎡⎤
⎣⎦⎣⎦
![](https://csdnimg.cn/release/download_crawler_static/6709123/bg13.jpg)
其中 ,
x
yNxy+≠ ≠。类似于 Ex.1.40,根据除法定理可推出矛盾。所以可得,
满足
2
modax N≡
的
x
有且恰好只有两个。
b) 首先
0 是一个,除去 0 之外每一对
x
与 Nx
−
可得一个 quadratic residue 模 N ,
所以总共有
11
1
22
NN
−
+
+=
个。
c) 在这一问中
N 可以不必是素数了,取 9, 16aN
=
= ,注意
(
)( )
16 5 3 5 3
=
+−
,
有
22 2 2
9 3 5 13 11 mod16≡≡≡ ≡
。
Ex.1.42
对 e 的要求是与
(
)
1p −
互素,先求出
(
)
1
mod 1de p
−
=
−
,则有
()
()
mod 1
mod
d
ed p
e
mm mp
−
≡≡,时间复杂度为
(
)
3
On 。
Ex.1.43
设 Npq= ,
(
)
(
)
11Cp q
=
−−
,则有 1moded C
≡
,代入 3e = ,即
31
31
d
dkC k
C
−
=+⇒=
。因为 0 dC<<,于是 1, 2k
=
。利用 k 值试探计算得
C ,由 ,NC可容易解得 ,
p
q 。
Ex.1.44
设
mod
i
e
ii
E
MN=
,其中 3
i
e = ,
iii
Npq
=
。则
3
mod
ii
M
Ep≡
,
3
mod
ii
M
Eq≡ 。由中国剩余定理知,在
33
11
ii i
ii
p
qN
==
=
∏
∏
范围内,这样的
3
M
是
存在且唯一的。若:
![](https://csdnimg.cn/release/download_crawler_static/6709123/bg14.jpg)
()
{
}
()
{}
()
{}
1
123 23 1
1
213 13 2
1
312 12 3
mod
mod
mod
SENN NN N
ENNNN N
ENN NN N
−
−
−
=×
+×
+×
则
3
3
1
mod
i
i
M
SN
=
⎛⎞
=
⎜⎟
⎝⎠
∏
满足条件
3
mod
ii
M
Eq≡ ,且唯一。开立方即得到
M
。
Ex.1.45
a) 略,如果不清楚请自行 Google.
b) 利用
()
mod
e
d
M
MN≡ 来进行验证过程。正确性证明和安全性分析同 RSA。
c) 再略。
d) 391 17 23N ==×,所以
(
)
{
}
1
17 mod 16 22 145d
−
=×=。
Ex.1.46
a) 将密文 mod
e
M
N 交给
B
ob
进行数字签名后为
(
)
mod
d
e
M
N ,即得原文
M
。
b) 为了打乱密文,可以选择一个与
N 互素的随机数 r ,计算出
mod
e
rN
,再将
ee
M
r 发给
B
ob
进行数字签名,得到
(
)
mod
d
ee
M
rMrN≡ ,于是可解得原文
1
mod
M
Mr r N
−
≡×
。
剩余102页未读,继续阅读
![application/pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
wjflcy
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- AirKiss技术详解:无线传递信息与智能家居连接
- Hibernate主键生成策略详解
- 操作系统实验:位示图法管理磁盘空闲空间
- JSON详解:数据交换的主流格式
- Win7安装Ubuntu双系统详细指南
- FPGA内部结构与工作原理探索
- 信用评分模型解析:WOE、IV与ROC
- 使用LVS+Keepalived构建高可用负载均衡集群
- 微信小程序驱动餐饮与服装业创新转型:便捷管理与低成本优势
- 机器学习入门指南:从基础到进阶
- 解决Win7 IIS配置错误500.22与0x80070032
- SQL-DFS:优化HDFS小文件存储的解决方案
- Hadoop、Hbase、Spark环境部署与主机配置详解
- Kisso:加密会话Cookie实现的单点登录SSO
- OpenCV读取与拼接多幅图像教程
- QT实战:轻松生成与解析JSON数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)