[已解决]递归实现

来自星星的小明

一元可以买一瓶汽水，两个瓶盖可以换一瓶汽水，问:喝1000瓶汽水最少需要花多少钱?
（差一个瓶盖的时候，不能先赊一瓶汽水，喝完再给老板）需要以递实现

最佳答案

月排行榜 / 总排行榜

人造人

2022-5-20 15:48:17

1. $ cat main.py
   
2. #!/usr/bin/env python
   
3. #coding=utf-8
   
4. 
   
5. import sys
   
6. 
   
7. def func(n):
   
8.     if n == 1: return 1
   
9.     x = 1 if n % 2 == 0 else 0
   
10.     return x + func(n - 1)
    
11. 
    
12. sys.setrecursionlimit(1002)
    
13. print(func(1000))
    
14. $ ./main.py
    
15. 501
    
16. $

复制代码

跳转到最佳答案楼层

人造人

1. $ cat main.py
   
2. #!/usr/bin/env python
   
3. #coding=utf-8
   
4. 
   
5. import sys
   
6. 
   
7. def func(n):
   
8.     if n == 1: return 1
   
9.     x = 1 if n % 2 == 0 else 0
   
10.     return x + func(n - 1)
    
11. 
    
12. sys.setrecursionlimit(1002)
    
13. print(func(1000))
    
14. $ ./main.py
    
15. 501
    
16. $

复制代码

wp231957

504 对不对啊

1. t=0
   
2. def fun(n):
   
3.     global t
   
4.     if n<1:
   
5.        return t
   
6.     t+=n
   
7.     return fun(n//2)        
   
8. 
   
9. for x in range(500,1000):
   
10.     t=0
    
11.     s=fun(x)  
    
12.     t=0
    
13.     s1=fun(x+1)
    
14.     if s<1000 and s1>=1000:
    
15.       print(x+1)
    
16.       break
    

复制代码

来自星星的小明

我用循环实现的是 501

wp231957

来自星星的小明 发表于 2022-5-20 16:20
我用循环实现的是 501

501对的  我的算法有问题  

来自星星的小明

wp231957 发表于 2022-5-20 16:23
501对的  我的算法有问题

501，125，31，15，7，3 换的时候都能留下一个瓶盖，可以再换

wp231957

来自星星的小明 发表于 2022-5-20 16:30
501，125，31，15，7，3 换的时候都能留下一个瓶盖，可以再换

1. t=0
   
2. def fun(n):
   
3.     global t
   
4.     if n<=1:
   
5.        return t
   
6.     t+=n
   
7.     if (n+n%2)%2==0 and n%2:
   
8.         t-=1
   
9.     return fun((n+n%2)//2)        
   
10. 
    
11. for x in range(500,520):
    
12.     t=0
    
13.     s=fun(x)  
    
14.     t=0
    
15.     s1=fun(x+1)
    
16.     if s<1000 and s1>=1000:
    
17.       print(x+1)
    
18.       break
    

复制代码

wp231957

wp231957 发表于 2022-5-20 16:47

还是不对，算519时  和手工计算不一样

月下孤井

人造人 发表于 2022-5-20 17:09

大佬

人造人

月下孤井 发表于 2022-5-20 17:19
大佬

^_^

人造人

来自星星的小明

人造人 发表于 2022-5-20 17:09

有点看不明白啊，能帮我解释一下吗

人造人

来自星星的小明 发表于 2022-5-20 17:40
有点看不明白啊，能帮我解释一下吗

第1瓶和第2瓶花钱，第3瓶免费，用的第1瓶和第2瓶的瓶盖
第4瓶花钱，第5瓶免费，用的第3瓶和第4瓶的瓶盖
6花钱，7免费，8花钱，9免费，。。。
单数免费，双数花钱

来自星星的小明

人造人 发表于 2022-5-20 17:44
第1瓶和第2瓶花钱，第3瓶免费，用的第1瓶和第2瓶的瓶盖
第4瓶花钱，第5瓶免费，用的第3瓶和第4瓶的瓶盖
...

收下我的膝盖

来自星星的小明

人造人 发表于 2022-5-20 17:44
第1瓶和第2瓶花钱，第3瓶免费，用的第1瓶和第2瓶的瓶盖
第4瓶花钱，第5瓶免费，用的第3瓶和第4瓶的瓶盖
...

我想问一下，但是我感觉要是说  3瓶换一瓶    4瓶换一瓶  5瓶换一瓶   ，他这个 好改嘛

人造人

1. $ cat main.py
   
2. #!/usr/bin/env python
   
3. #coding=utf-8
   
4. 
   
5. import sys
   
6. 
   
7. def func(n):
   
8.     x = 1 if n % 2 == 0  or n == 1 else 0
   
9.     print(f"第{n}瓶花费{x}元")
   
10.     if n == 1: return 1
    
11.     x = 1 if n % 2 == 0 else 0
    
12.     return x + func(n - 1)
    
13. 
    
14. sys.setrecursionlimit(1004)
    
15. #print(func(1000))
    
16. 
    
17. for i in range(1, 9):
    
18.     print(f"i = {i}")
    
19.     print(func(i))
    
20.     print('')
    
21. $ ./main.py
    
22. i = 1
    
23. 第1瓶花费1元
    
24. 1
    
25. 
    
26. i = 2
    
27. 第2瓶花费1元
    
28. 第1瓶花费1元
    
29. 2
    
30. 
    
31. i = 3
    
32. 第3瓶花费0元
    
33. 第2瓶花费1元
    
34. 第1瓶花费1元
    
35. 2
    
36. 
    
37. i = 4
    
38. 第4瓶花费1元
    
39. 第3瓶花费0元
    
40. 第2瓶花费1元
    
41. 第1瓶花费1元
    
42. 3
    
43. 
    
44. i = 5
    
45. 第5瓶花费0元
    
46. 第4瓶花费1元
    
47. 第3瓶花费0元
    
48. 第2瓶花费1元
    
49. 第1瓶花费1元
    
50. 3
    
51. 
    
52. i = 6
    
53. 第6瓶花费1元
    
54. 第5瓶花费0元
    
55. 第4瓶花费1元
    
56. 第3瓶花费0元
    
57. 第2瓶花费1元
    
58. 第1瓶花费1元
    
59. 4
    
60. 
    
61. i = 7
    
62. 第7瓶花费0元
    
63. 第6瓶花费1元
    
64. 第5瓶花费0元
    
65. 第4瓶花费1元
    
66. 第3瓶花费0元
    
67. 第2瓶花费1元
    
68. 第1瓶花费1元
    
69. 4
    
70. 
    
71. i = 8
    
72. 第8瓶花费1元
    
73. 第7瓶花费0元
    
74. 第6瓶花费1元
    
75. 第5瓶花费0元
    
76. 第4瓶花费1元
    
77. 第3瓶花费0元
    
78. 第2瓶花费1元
    
79. 第1瓶花费1元
    
80. 5
    
81. 
    
82. $

复制代码

人造人

来自星星的小明 发表于 2022-5-20 17:52
我想问一下，但是我感觉要是说  3瓶换一瓶    4瓶换一瓶  5瓶换一瓶   ，他这个 好改嘛

我研究研究

来自星星的小明

人造人 发表于 2022-5-20 17:57
我研究研究

1. def exchange(m):
   
2.     num = m
   
3.     while m // 2:
   
4.         num += m // 2
   
5.         m = m % 2 + m // 2
   
6.     return num
   
7. 
   
8. for money in range(1000):
   
9.     if exchange(money) >= 1000:
   
10.         print("%d 块钱喝 %d 瓶" %(money,exchange(money)))
    
11.         break

复制代码

这个是我写的循环，能不能以这个思路写递归呢，我研究了半天都写不出来

人造人

1. #!/usr/bin/env python
   
2. #coding=utf-8
   
3. 
   
4. import sys
   
5. 
   
6. # 3_1
   
7. def free(n):
   
8.     return True if n != 1 and (n - 1) % 3 == 0 else False
   
9. 
   
10. def free_4_1(n):
    
11.     return True if n != 1 and (n - 1) % 4 == 0 else False
    
12. 
    
13. def free_5_1(n):
    
14.     return True if n != 1 and (n - 1) % 5 == 0 else False
    
15. 
    
16. def func(n, free_func):
    
17.     x = 0 if free_func(n) else 1
    
18.     print(f"第{n}瓶花费{x}元")
    
19.     if n == 1: return 1
    
20.     x = 0 if free_func(n) else 1
    
21.     return x + func(n - 1, free_func)
    
22. 
    
23. sys.setrecursionlimit(1004)
    
24. #print(func(1000))
    
25. 
    
26. print("3_1")
    
27. for i in range(1, 20):
    
28.     print(f"i = {i}")
    
29.     print(func(i, free))
    
30.     print('')
    
31. 
    
32. print("4_1")
    
33. for i in range(1, 20):
    
34.     print(f"i = {i}")
    
35.     print(func(i, free_4_1))
    
36.     print('')
    
37. 
    
38. print("5_1")
    
39. for i in range(1, 20):
    
40.     print(f"i = {i}")
    
41.     print(func(i, free_5_1))
    
42.     print('')
    

复制代码

人造人

来自星星的小明 发表于 2022-5-20 18:01
这个是我写的循环，能不能以这个思路写递归呢，我研究了半天都写不出来

不能，递归和迭代的思路是不一样的