C++实用算法实现教程：Dmytro Kedyk著
需积分: 22 128 浏览量
更新于2024-06-27
收藏 485.74MB PDF 举报
《在C++中实现实用算法》(Dmytro Kedyk)是一本深入讲解如何在C++编程语言中实际应用各种算法的书籍。作者Dmytro Kedyk在这本教材中详细介绍了如何通过C++来设计和实现一系列实用的算法，包括但不限于搜索、排序、图论算法以及随机数生成等内容。
书中章节涵盖了基础概念如数据结构（如无符号整数类型用于随机数生成函数）以及如何利用C++实现关键算法。例如，作者提供了一个自定义的随机数生成函数`randomNumber()`，它使用了时间戳作为种子，通过位操作实现了一种简单的伪随机数生成方法。这个函数展示了在实际编程中如何结合数学原理与编程技巧。
书中的算法覆盖了广泛的主题，如：
1. **最小生成树**（Minimum Spanning Tree, MST）算法：该部分可能涉及Prim或Kruskal算法的实现，它们用于找到一个加权无向图中连接所有顶点的边集合，使得边的总权重最小。书中提供了具体的成本计算和示例，如"MST Cost"列，展示了解决这类问题的步骤和结果。
2. **搜索算法**：这部分可能包括广度优先搜索（BFS）和深度优先搜索（DFS），用于遍历图或解决路径问题。书中的"Connect edge"和"Connect edge cost"部分可能展示了这些算法在连接节点和计算代价方面的应用。
3. **优化算法**：书中提到的"Cumulative Cost"和"Cumulative Cost"可能是动态规划或贪心算法的应用，用来解决具有累积性质的问题，比如寻找最优化路径或解决问题的序列策略。
4. **图的简化**："Pruning"（剪枝）的概念在这本书中可能用于讨论如何在求解问题过程中减少不必要的计算，如Prim算法中的边删除操作，以提高效率。
5. **决策过程**："Choose"选项可能代表算法执行时的选择决策，比如在多叉树搜索中选择下一个节点或最优解。
6. **复杂度分析**："Lowest"和"Maximum"可能涉及到算法的时间和空间复杂度讨论，帮助读者理解算法性能。
整体而言，《在C++中实现实用算法》是一本实用的编程指南，适合希望提升C++技能并深入了解算法应用的开发者阅读，不仅提供了代码示例，还涵盖了理论和实践的结合，帮助读者将算法理论转化为实际可运行的程序。
1
Background
"I
wish
my
wish
would
not
be
granted"
-
Douglas
Hofstadter
"If
you
don't
know
how
to
do
something,
you
don't
know
how
to
do
it
on
a
computer"
-
Anonymous
1.1
Introduction
Nontrivial
algorithms
are
rarely
implemented
due
to
the
availability
from
various
APIs.
Most
programming
work
is
spent
on
logical
modeling
of
systems
with
domain
experts.
But
occasionally
need
to
understand
what
an
API
does
in
principle,
and
be
able
to
modily
or
extend
the
implementation.
Also
someone
needs
to
develop
and
maintain
the
APIs,
and
for
various
embedded
devices
this
is
commonly
done
from
scratch
or
by
adapting
similar
APIs.
This
book
covers
only
algorithms
that
are
expected
to
be
implemented
and
used,
with
some
exceptions.
Theoretical
algorithms,
which
seem
to
exists
only
because
of
intellectual
curiosity,
are
summarized
well
in
Kao
(2016).
This
chapter
reviews
some
recurring
themes.
1.2
Algorithm
Desiderata
An
algorithm
is
a
well-defined
input-to-output
transformation.
A
data
structure
allows
efficient
access
and
updates
to
the
stored
data.
To
support
software
development
effectively,
both
must
be:
•
Correct
by
giving
a
satisfactory
solution
to
the
exact
problem.
A
formal
proof,
extensive
testing,
or
intuition
can
deem
an
algorithm
and
its
implementation
correct.
Can
get
only
correctness
with
high
certainty
because
formal
proofs
can
be
unobtainable,
intuition
wrong,
and
rarely
invoked
logic
untested.
Correctness
can
be
randomized,
so
that
an
algorithm
that's
wrong
less
often
than
the
com
puter
is
hit
by
lightning
is
effectively
correct.
An
algorithm
should
report
failures
such
as
the
inabil
ity
to
allocate
memory.
Extendable
by
being
applicable
to
general
problems
with
only
minor
changes.
Real-world
problems
sometimes
have
extra
constraints
that
require
augmenting
existing
algorithms.
An
algorithm
that
applies
to
a
variety
of
problems
is
more
valuable
than
a
collection
of
top-performing
custom
algo
rithms
for
every
problem.
An
implementation
is
extendable
if
the
code
applies
to
many
problems
unchanged.
Usually
prefer
reusable
code,
even
at
the
cost
of
reasonable
losses
in
simplicity
and
effi
ciency.
But
exploiting
specific
problem
structure
often
allows
a
better
solution,
so
customized
algo
rithms
have
their
place.
•
Relatively
simple
to
understand,
implement
in
different
environments,
and
use
as
an
abstract
building
block.
Simplicity
of
understanding
is
measured
by
how
long
it
takes
to
understand
and
debug
what
the
algorithm
does
in
all
cases,
of
implementation
by
the
number
of
lines
of
properly
structured
code,
and
of
use
by
how
clean
the
API
is
in
terms
of
the
number
of
functions,
their
parameters,
and
the
availability
of
good
defaults.
An
important
part
of
simplicity
of
understanding
is
that
everything
useful
about
the
algorithm
is
known,
including
theorems
describing
its
behavior
and
details
needed
for
a
robust,
efficient
implementation.
•
Sufficiently
efficient
with
valuable
resources,
at
least
on
practical
problems.
CPU
time
and
memory
are
often
the
most
important.
Can't
use
more
memory
than
time
if
accessing
every
used
bit,
but
memory
is
more
important
because
can
wait
for
another
hour
but
not
another
RAM
chip,
and,
unlike
time,
it
accumulates.
Other
resources
such
as
concurrency
locks,
file
handles,
network
ports,
requests
to
another
process,
and
electricity
also
matter.
Paid
development
time
and
time
waiting
for
the
system
to
respond
are
often
the
most
costly.
Humans
don't
differentiate
between
GUI
response
times
<
150
milliseconds,
so
don't
need
to
optimize
below
that.
Legal
to
use.
Many
aspects
of
algorithms
are
intellectual
property.
Patents
and
trade
secrets
protect
ideas,
trademarks
names,
and
copyrights
code.
Using
protected
software,
including
open
source,
requires
a
special
contract
called
a
license
(see
the
"Introduction
to
Computer
Law"
chapter).
A
correct,
efficient,
and
legal
algorithm
is
useful.
Simplicity
and
extendability
reduce
development
and
maintenance
time.
An
algorithm
is
ideally
useful,
simple,
and
extendable,
though
it's
unclear
how
to
name
this
concept.
Names
such
as
"commodity"
(used
in
the
draft
editions)
or
"toolbox-worthy"
seem
to
confuse
more
than
enlighten.
A
system
composed
of
such
algorithms
handles
users'
requests
correctly
and
effi
ciently
and
allows
quick
feature
addition
and
debugging.
剩余709页未读，继续阅读
2013-02-02 上传
2024-06-28 上传
点击了解资源详情
2015-12-23 上传
2017-02-22 上传
2008-04-16 上传
2009-07-15 上传
2021-09-29 上传
承让@
- 粉丝: 8
- 资源: 380
我的内容管理
展开
最新资源
- 黑板风格计算机毕业答辩PPT模板下载
- CodeSandbox实现ListView快速创建指南
- Node.js脚本实现WXR文件到Postgres数据库帖子导入
- 清新简约创意三角毕业论文答辩PPT模板
- DISCORD-JS-CRUD：提升 Discord 机器人开发体验
- Node.js v4.3.2版本Linux ARM64平台运行时环境发布
- SQLight：C++11编写的轻量级MySQL客户端
- 计算机专业毕业论文答辩PPT模板
- Wireshark网络抓包工具的使用与数据包解析
- Wild Match Map: JavaScript中实现通配符映射与事件绑定
- 毕业答辩利器：蝶恋花毕业设计PPT模板
- Node.js深度解析：高性能Web服务器与实时应用构建
- 掌握深度图技术：游戏开发中的绚丽应用案例
- Dart语言的HTTP扩展包功能详解
- MoonMaker: 投资组合加固神器，助力$GME投资者登月
- 计算机毕业设计答辩PPT模板下载
