[已解决]递归实现

来自星星的小明

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

最佳答案

月排行榜 / 总排行榜

人造人

2022-5-20 15:48:17

$ cat main.py
#!/usr/bin/env python
#coding=utf-8

import sys

def func(n):
    if n == 1: return 1
    x = 1 if n % 2 == 0 else 0
    return x + func(n - 1)

sys.setrecursionlimit(1002)
print(func(1000))
$ ./main.py
501
$

跳转到最佳答案楼层

人造人

$ cat main.py
#!/usr/bin/env python
#coding=utf-8

import sys

def func(n):
    if n == 1: return 1
    x = 1 if n % 2 == 0 else 0
    return x + func(n - 1)

sys.setrecursionlimit(1002)
print(func(1000))
$ ./main.py
501
$

wp231957

504 对不对啊

t=0
def fun(n):
    global t
    if n<1:
       return t
    t+=n
    return fun(n//2)        

for x in range(500,1000):
    t=0
    s=fun(x)  
    t=0
    s1=fun(x+1)
    if s<1000 and s1>=1000:
      print(x+1)
      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 换的时候都能留下一个瓶盖，可以再换

t=0
def fun(n):
    global t
    if n<=1:
       return t
    t+=n
    if (n+n%2)%2==0 and n%2:
        t-=1
    return fun((n+n%2)//2)        

for x in range(500,520):
    t=0
    s=fun(x)  
    t=0
    s1=fun(x+1)
    if s<1000 and s1>=1000:
      print(x+1)
      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瓶换一瓶   ，他这个 好改嘛

人造人

$ cat main.py
#!/usr/bin/env python
#coding=utf-8

import sys

def func(n):
    x = 1 if n % 2 == 0  or n == 1 else 0
    print(f"第{n}瓶花费{x}元")
    if n == 1: return 1
    x = 1 if n % 2 == 0 else 0
    return x + func(n - 1)

sys.setrecursionlimit(1004)
#print(func(1000))

for i in range(1, 9):
    print(f"i = {i}")
    print(func(i))
    print('')
$ ./main.py
i = 1
第1瓶花费1元
1

i = 2
第2瓶花费1元
第1瓶花费1元
2

i = 3
第3瓶花费0元
第2瓶花费1元
第1瓶花费1元
2

i = 4
第4瓶花费1元
第3瓶花费0元
第2瓶花费1元
第1瓶花费1元
3

i = 5
第5瓶花费0元
第4瓶花费1元
第3瓶花费0元
第2瓶花费1元
第1瓶花费1元
3

i = 6
第6瓶花费1元
第5瓶花费0元
第4瓶花费1元
第3瓶花费0元
第2瓶花费1元
第1瓶花费1元
4

i = 7
第7瓶花费0元
第6瓶花费1元
第5瓶花费0元
第4瓶花费1元
第3瓶花费0元
第2瓶花费1元
第1瓶花费1元
4

i = 8
第8瓶花费1元
第7瓶花费0元
第6瓶花费1元
第5瓶花费0元
第4瓶花费1元
第3瓶花费0元
第2瓶花费1元
第1瓶花费1元
5

$

人造人

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

我研究研究

来自星星的小明

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

def exchange(m):
    num = m
    while m // 2:
        num += m // 2
        m = m % 2 + m // 2
    return num

for money in range(1000):
    if exchange(money) >= 1000:
        print("%d 块钱喝 %d 瓶" %(money,exchange(money)))
        break

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

人造人

#!/usr/bin/env python
#coding=utf-8

import sys

# 3_1
def free(n):
    return True if n != 1 and (n - 1) % 3 == 0 else False

def free_4_1(n):
    return True if n != 1 and (n - 1) % 4 == 0 else False

def free_5_1(n):
    return True if n != 1 and (n - 1) % 5 == 0 else False

def func(n, free_func):
    x = 0 if free_func(n) else 1
    print(f"第{n}瓶花费{x}元")
    if n == 1: return 1
    x = 0 if free_func(n) else 1
    return x + func(n - 1, free_func)

sys.setrecursionlimit(1004)
#print(func(1000))

print("3_1")
for i in range(1, 20):
    print(f"i = {i}")
    print(func(i, free))
    print('')

print("4_1")
for i in range(1, 20):
    print(f"i = {i}")
    print(func(i, free_4_1))
    print('')

print("5_1")
for i in range(1, 20):
    print(f"i = {i}")
    print(func(i, free_5_1))
    print('')

人造人

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

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