论坛 › Python交流 › Python：每日一问 74 (答题领鱼币)

MSK 发表于 2017-8-8 22:20:54

Python：每日一问 74 (答题领鱼币)

本帖最后由 新手·ing 于 2017-8-17 12:28 编辑





台阶问题~{:10_248:}




题目:

一只青蛙一次可以跳一级台阶,也可以跳两级台阶,
定义一个函数,求有n级台阶时有几种跳法?{:10_256:}




答案：
**** Hidden Message *****

冬雪雪冬 发表于 2017-8-9 09:35:26

本帖最后由 冬雪雪冬 于 2017-8-9 09:47 编辑

先写了一个特别笨的方法，效率很低。
import itertools
def jump(n):
    count = 0
    for i in range(1, n + 1):
      p = itertools.product('12', repeat = i)
      for j in p:
            sum1 = sum()
            if sum1 == n:
                count += 1
    return count
验算了一下结果就是斐波那契数列。
那就简单了。
def fab(n):
    n1 = 1
    n2 = 2
    for i in range(1, n):
      n1, n2 = n2, n1 + n2
    return n1

新手·ing 发表于 2017-8-9 08:55:44

竟然还有这种操作！

新手·ing 发表于 2017-8-9 08:56:06

老铁等一两天，提升一下

jerryxjr1220 发表于 2017-8-9 09:33:19

本帖最后由 jerryxjr1220 于 2017-8-9 09:44 编辑

这是动态规划的经典例题啊！

同类型的题目还有：在m*n的“田”字形的方格中，从左下角出发，每次只能往右或者往上行走，问走到左上角一共有多少种走法？{:5_97:}

左手十字 发表于 2017-8-9 12:03:46

我怎么就不会解呢

九九八十一 发表于 2017-8-9 12:25:47

耶{:10_297:}
def jump(n):
   if n== 1:
          return 1
   elif n == 2:
          return 2
   else:
          return jump(n-1)+jump(n-2)

n = int(input('请输入台阶数：'))
print('%d 级台阶有 %d 种跳法。' % (n, jump(n)))

woigh 发表于 2017-8-9 12:29:11

本帖最后由 woigh 于 2017-8-9 12:30 编辑

想到递回的方式

def steps(n):
    if n==0 or n==1 or n==2:
      return n

    return steps(n-1) + steps(n-2)

曹子孝 发表于 2017-8-10 11:56:39

斐波那契数列

michaelol 发表于 2017-8-10 13:09:38

刚入坑编程 写的代码简直要多长有多长 先贴代码：
#青蛙跳级问题 青蛙一次可以跳一级 也可以跳两级 求n级阶梯有多少种跳法 结果是菲波那切数列

a=[]
b=[]
def allcombine(n,k1,k2):
    '求二元一次方程k1*x+k2*y=n的解'
    x=k1
    y=k2
    global a
    global b
    a=[]
    b=[]
    for i in range(n+1):
      if (n-x*i)%y==0:
            a.append(i)
            b.append(int((n-x*i)/y))
    #print(a)
    #print(b)

def factorial(n):
    '求n的阶乘'
    if n==0:
      return 1
    else :
      return n*factorial(n-1)

def red_white_ball(m,n):
    '求m个红球n个白球排成一排的总的排法数'
    return int(factorial(m+n)/factorial(m)/factorial(n))

def frog_ladder(n):
    result=0
    #n=input('请输入正整数n\n')
    #flag=n.isnumeric()
    if 1:
      n=int(n)
      allcombine(n,1,2)
      print('阶梯级数',n)
      print('跳一级的次数',a)
      print('跳两级的次数',b)
   #   print(factorial(n))
    else:
      print('输入错误！')
    for i in range(len(a)):
      result+=red_white_ball(a,b)
    #print('跳法的总数',result)
    return result
for i in range(12):
    print('总的跳法',frog_ladder(i))

说解题思路 先求解x+2y=n 的一次方程，得到所有跳法的组合，存到列表a[]b[]中，再把跳一级看做是一类，跳2级是另一类，即转换为m个红球n个白球排成一排有多少种排法的问题， 最后将所有组合类型的可能加起来，确实是斐波那契数列，结果如下：
阶梯级数 0
跳一级的次数
跳两级的次数
总的跳法 1
阶梯级数 1
跳一级的次数
跳两级的次数
总的跳法 1
阶梯级数 2
跳一级的次数
跳两级的次数
总的跳法 2
阶梯级数 3
跳一级的次数
跳两级的次数
总的跳法 3
阶梯级数 4
跳一级的次数
跳两级的次数
总的跳法 5
阶梯级数 5
跳一级的次数
跳两级的次数
总的跳法 8
阶梯级数 6
跳一级的次数
跳两级的次数
总的跳法 13
阶梯级数 7
跳一级的次数
跳两级的次数
总的跳法 21
阶梯级数 8
跳一级的次数
跳两级的次数
总的跳法 34
阶梯级数 9
跳一级的次数
跳两级的次数
总的跳法 55
阶梯级数 10
跳一级的次数
跳两级的次数
总的跳法 89
阶梯级数 11
跳一级的次数
跳两级的次数
总的跳法 144

小明1201 发表于 2017-8-10 14:55:37

都是大牛

sw546190767 发表于 2017-8-10 15:08:19

查看答案

bozhen 发表于 2017-8-14 15:05:06

查看答案，学习了

s1986q 发表于 2017-8-15 21:22:18

看看吧？

solomonxian 发表于 2017-8-18 20:28:25

如果用枚举法，那实在是很慢，n=10 就要等了
import itertools as it
cal = lambda n: sum() if n>0 else 0
要跳上第n阶首先要站在第n-1阶或者第n-2阶上，
那么要站到第n-1阶或第n-2阶有几种方法呢？
不就是去掉第一项的斐波那契数列嘛
# 结果就是斐波那契数列
def fibs(n):
    a,b = 1,1
    for i in range(n):
      a,b = b,a+b
    return a if n>0 else 0

shigure_takimi 发表于 2017-12-6 09:35:34

本帖最后由 shigure_takimi 于 2017-12-6 09:39 编辑

def method(n):
    if n < 0:
      return -1
    elif n in :
      return n
    else:
      return method(n-1)+method(n-2)

# 也是首先想到了递归，但是到n=35就已经很慢了。
# 所以还是要用循环，上面已经有人写了。

yjsx86 发表于 2018-1-27 02:43:46

def setup(n):
    shortest = (n//2 if n % 2 == 0 else n//2+1)
    longest = n
    count = 1
    for i in range(shortest,longest):
      it = itertools.product(,repeat=i)
      for item in it:
            if sum(item) == n:
                count += 1
    print('There are %d combinations' % count)

setup(20)

kwty 发表于 2018-2-12 22:18:46

def f(n):
        if n == 0:
                return 1
        else:
                return n * f(n - 1)
               
def numbers(n):
        c = 0
        for i in range(n // 2 +1):
                c += f(n - i) // f(i) // f(n - 2 * i)
        return c

n = int(input('请输入台阶数: '))
print('一共有%d种跳法'%(numbers(n)))

Geoffreylee 发表于 2020-3-11 16:30:21

def f_74(n):
    # 斐波那契数列
    a, b = 0, 1
    while True:
      a, b, n = b, a + b, n - 1
      if n == 0:
            return b

print(f_74(4))

aironeng 发表于 2020-11-24 13:38:10

学习一下

查看完整版本: Python：每日一问 74 (答题领鱼币)