有一群猴子摘了一堆桃子,他们每天都吃当前桃子的一半且再多吃一个,到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求: 1)采用数组数据结构实现上述求解 2)采用链数据结构实现上述求解 3)采用递归实现上述求解
时间: 2024-03-01 10:50:23 浏览: 30
1. 采用数组数据结构实现:
```python
peach = [0] * 10 # 定义长度为10的数组,用于保存每天剩余的桃子数
peach[9] = 1 # 第10天剩余1个桃子
for i in range(8, -1, -1): # 从第9天向前推算
peach[i] = (peach[i+1] + 1) * 2 # 前一天的桃子数为后一天的一半加1再乘2
total = sum(peach) # 计算总共摘了多少个桃子
print(total)
```
2. 采用链数据结构实现:
```python
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
tail = Node(1) # 第10天剩余1个桃子
for i in range(9):
head = Node((tail.val + 1) * 2, tail) # 当前天剩余桃子数为后一天的一半加1再乘2
tail = head
total = 0
while head:
total += head.val # 计算总共摘了多少个桃子
head = head.next
print(total)
```
3. 采用递归实现:
```python
def peach(n):
if n == 10:
return 1
else:
return (peach(n+1) + 1) * 2
total = peach(1) * 10 # 计算总共摘了多少个桃子
print(total)
```
以上三种方法都可以求出原来这群猴子共摘了多少个桃子,结果都为1534个桃子。