第3.2讲-算法类问题求解框架练习题1

【算法的特性】 算法是计算机科学的基础，它是一组有序的、有限的规则，用于解决特定问题。算法必须具备以下关键特性： 1. **有穷性**：算法必须有明确的结束条件，确保它在有限步骤后能够终止。这避免了无限循环的发生，保证了算法的可行性。 2. **确定性**：算法的每一步骤都应该有清晰无歧义的定义，使得任何人在执行算法时都能得到相同的结果。 3. **输入输出性**：算法可以接受零个或多个输入，并产生零个或多个输出。输入可以是问题的初始条件，输出则是问题的解答。 4. **能行性**：算法中的运算和操作应该是基础的，可由计算机执行，并且能在有限时间内完成，确保算法的实用性。 5. **有效性**：算法的每一步都应该是有效的，意味着执行这些步骤后，算法的进程应该朝着解决方案前进。 【算法与程序、计算机语言的关系】 算法是思想，它描述了解决问题的步骤，而程序是算法的具体实现，通常用一种或多种计算机语言编写。算法不能直接被计算机执行，需要转换为程序，这可以是用高级语言、低级语言或汇编语言实现。不同的算法可以解决同一问题，但结果可能不同。 【背包问题】 背包问题是一种经典的优化问题，目标是在给定的重量限制下，选择物品以最大化价值。在这个例子中，物品的组合数量可以用二进制表示，因此可能的解的数量是 \(2^n\)，其中 \(n\) 是物品的数目。根据题目，物品数目未知，但选项给出的解的数量是 64，暗示物品数为6。对于贪心策略，选择单位重量价值最高的物品，可能会得到总价值15的解。遍历所有可能的组合，可以找到最优解，但具体总价值需要根据具体物品的重量和价值来计算。 【数据结构】 数据结构是组织和管理数据的关键，它包括逻辑结构、存储结构和对数据的操作。数据结构不仅涉及数据元素本身，还涉及它们之间的关系。例如，向量使用顺序存储结构，树结构则使用指针表示元素间的层次关系。在树中，每个元素通常指向其子节点，而不是父节点，除非是反向链接树。 【树型数据的存储】 树型数据可以用多种方式存储，包括数组或链表。图 I 表示的树可以用三个数组存储，分别存储元素、左指针和右指针。树的逻辑关系可以通过这些数组来表示，如图 II 的(a)、(b)、(c)和(d)所示。改变树的逻辑关系可能涉及到数组元素的修改和重新排列。 总结来说，本讲主要讨论了算法的基本特性、算法与程序的关系，以及数据结构特别是背包问题和树型数据结构的相关概念，这些都是计算机科学和算法设计的核心内容。理解并掌握这些知识对于解决复杂问题至关重要。