4.15. 练习¶

4.15. Exercises

中文英文

绘制汉诺塔问题的调用栈。 假设你从一个包含三张盘子的堆栈开始。
使用递归规则绘制谢尔宾斯基三角形。 使用纸和铅笔完成。
使用动态规划算法计算找零问题，找出用最少数量的硬币来找33美分的零钱。 除了通常的硬币，还假设你有一个8美分的硬币。
编写一个递归函数来计算一个数字的阶乘。
编写一个递归函数来反转一个列表。
修改递归树程序，使用以下一个或多个想法：
- 修改分支的粗细，使得随着 branch_len 的减小，线条变得更细。
- 修改分支的颜色，使得 branch_len 非常短时，它被着色为叶子。
- 修改转弯角度，使得在每个分支点，角度在某个范围内随机选择。例如，选择15到45度之间的角度。进行实验，看看效果如何。
- 递归地修改 branch_len，使得每次递减的量在某个范围内随机选择。
如果实现以上所有想法，你将得到一个非常逼真的树形图像。
找到或发明一个绘制分形山脉的算法。 提示：一种方法是再次使用三角形。
编写一个递归函数来计算斐波那契数列。 递归函数的性能与迭代版本相比如何？
使用三个堆栈来解决汉诺塔问题。
使用 turtle 图形模块，编写一个递归程序来显示希尔伯特曲线。
使用 turtle 图形模块，编写一个递归程序来显示科赫雪花。
编写一个程序来解决以下问题： 你有两个水壶：一个4加仑的水壶和一个3加仑的水壶。两个水壶上都没有刻度。可以使用一个泵来填充水壶。如何在4加仑的水壶中准确地获得2加仑的水？
将上述问题进行推广，使得解决方案的参数包括每个水壶的大小和大水壶中剩余的最终水量。
编写一个程序来解决以下问题： 三个传教士和三个食人族来到一条河边，发现一只可以容纳两个人的船。所有人必须过河才能继续旅程。然而，如果食人族在任何一岸上数量超过传教士，传教士就会被吃掉。找到一个过河的系列，使所有人安全到达对岸。
使用 turtle 图形模块修改汉诺塔程序，使得盘子的移动有动画效果。 提示：你可以创建多个 turtle 并将它们设置成矩形形状。
帕斯卡尔三角形是一个数字三角形，数字按错开行的方式排列，满足：

\(a_{nr} = \frac{n!}{r!(n-r)!}\)

这是二项式系数的方程。你可以通过将三角形中对角线上的两个数字相加来构建帕斯卡尔三角形。下面是帕斯卡尔三角形的示例：
```
        1
    1   1
    1   2   1
1   3   3   1
1   4   6   4   1
```
编写一个程序打印出帕斯卡尔三角形。你的程序应接受一个参数，指定要打印多少行三角形。
你是一个计算机科学家/艺术小偷，闯入了一个主要的艺术画廊。 你唯一能用来搬运偷来的艺术品的是一个只能装 \(W\) 磅艺术品的背包，但对于每件艺术品你知道它的价值和重量。编写一个动态规划函数来帮助你最大化利润。以下是一个示例问题：假设你的背包能容纳总重量为20磅的物品。你有5件物品，如下所示：
```
item     weight      value
1        2           3
2        3           4
3        4           8
4        5           8
5        9          10
```
这个问题被称为字符串编辑距离问题，并在许多研究领域中非常有用。 假设你要将单词 algorithm 转换为 alligator。对于每个字母，你可以选择以5的成本将字母从一个单词复制到另一个单词，删除一个字母的成本为20，插入一个字母的成本为20。将一个单词转换为另一个单词的总成本是拼写检查程序用于提供类似单词建议的依据。使用动态规划技术开发一个算法，以获得任何两个单词之间的最小编辑距离。

Draw a call stack for the Tower of Hanoi problem. Assume that you start with a stack of three disks.
Using the recursive rules as described, draw a Sierpinski triangle using paper and pencil.
Using the dynamic programming algorithm for making change, find the smallest number of coins that you can use to make 33 cents in change. In addition to the usual coins assume that you have an 8 cent coin.
Write a recursive function to compute the factorial of a number.
Write a recursive function to reverse a list.
Modify the recursive tree program using one or all of the following ideas:
- Modify the thickness of the branches so that as the branch_len gets smaller, the line gets thinner.
- Modify the color of the branches so that as the branch_len gets very short it is colored like a leaf.
- Modify the angle used in turning the turtle so that at each branch point the angle is selected at random in some range. For example, choose an angle between 15 and 45 degrees. Play around to see what looks good.
- Modify the branch_len recursively so that instead of always subtracting the same amount you subtract a random amount in some range.
If you implement all of the above ideas you will have a very realistic looking tree.
Find or invent an algorithm for drawing a fractal mountain. Hint: one approach to this uses triangles again
Write a recursive function to compute the Fibonacci sequence. How does the performance of the recursive function compare to that of an iterative version?
Implement a solution to the Tower of Hanoi using three stacks to keep track of the disks.
Using the turtle graphics module, write a recursive program to display a Hilbert curve.
Using the turtle graphics module, write a recursive program to display a Koch snowflake.
Write a program to solve the following problem. You have two jugs: a 4-gallon jug and a 3-gallon jug. Neither of the jugs have markings on them. There is a pump that can be used to fill the jugs with water. How can you get exactly two gallons of water in the 4-gallon jug?
Generalize the problem above so that the parameters to your solution include the sizes of each jug and the final amount of water to be left in the larger jug.
Write a program that solves the following problem. Three missionaries and three cannibals come to a river and find a boat that holds two people. Everyone must get across the river to continue on the journey. However, if the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten. Find a series of crossings that will get everyone safely to the other side of the river.
Modify the Tower of Hanoi program using turtle graphics to animate the movement of the disks. Hint: you can make multiple turtles and have them shaped like rectangles.
Pascal’s triangle is a number triangle with numbers arranged in staggered rows such that

\(a_{nr} = {n! \over{r! (n-r)!}}\)

This is the equation for a binomial coefficient. You can build Pascal’s triangle by adding the two numbers that are diagonally above a number in the triangle. An example of Pascal’s triangle is shown below.
```
        1
    1   1
    1   2   1
1   3   3   1
1   4   6   4   1
```
Write a program that prints out Pascal’s triangle. Your program should accept a parameter that tells how many rows of the triangle to print.
Suppose you are a computer scientist/art thief who has broken into a major art gallery. All you have with you to haul out your stolen art is your knapsack which only holds \(W\) pounds of art, but for every piece of art you know its value and its weight. Write a dynamic programming function to help you maximize your profit. Here is a sample problem for you to get started: suppose your knapsack can hold a total weight of 20 pounds. You have 5 items as follows:
```
item     weight      value
1        2           3
2        3           4
3        4           8
4        5           8
5        9          10
```
This problem is called the string edit distance problem, and is quite useful in many areas of research. Suppose that you want to transform the word algorithm into the word alligator. For each letter you can either copy the letter from one word to another at a cost of 5, you can delete a letter at cost of 20, or insert a letter at a cost of 20. The total cost to transform one word into another is used by spell-check programs to provide suggestions for words that are close to one another. Use dynamic programming techniques to develop an algorithm that gives you the smallest edit distance between any two words.

最后更新: 2024年9月12日
创建日期: 2024年9月9日