来自星星的小明 发表于 2022-5-20 15:48:16

递归实现

一元可以买一瓶汽水，两个瓶盖可以换一瓶汽水，问:喝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
$

wp231957 发表于 2022-5-20 16:13:59

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

来自星星的小明 发表于 2022-5-20 16:20:37

我用循环实现的是 501

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

本帖最后由 wp231957 于 2022-5-20 16:26 编辑

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

501对的我的算法有问题

来自星星的小明 发表于 2022-5-20 16:30:04

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

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

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

来自星星的小明 发表于 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 发表于 2022-5-20 16:54:44

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


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

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

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


大佬{:5_108:}

人造人 发表于 2022-5-20 17:19:53

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

^_^

人造人 发表于 2022-5-20 17:24:32

来自星星的小明 发表于 2022-5-20 17:40:04

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


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

人造人 发表于 2022-5-20 17:44:12

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

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

来自星星的小明 发表于 2022-5-20 17:50:33

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

{:9_228:}收下我的膝盖

来自星星的小明 发表于 2022-5-20 17:52:07

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

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

人造人 发表于 2022-5-20 17:54:08

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

import sys

def func(n):
    x = 1 if n % 2 == 0or 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:57:14

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

我研究研究

来自星星的小明 发表于 2022-5-20 18:01:43

人造人 发表于 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

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

人造人 发表于 2022-5-20 18:21:59

#!/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:30:00

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

不能，递归和迭代的思路是不一样的
页: [1]
查看完整版本: 递归实现