QQ登录

只需一步,快速开始

搜索
查看: 344|回复: 14

[技术交流] Python:每日一问 74 (答题领鱼币)

[复制链接]
最佳答案
26 
累计签到:128 天
连续签到:1 天
发表于 2017-8-8 22:20:54 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

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





台阶问题~






题目:

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





答案:
游客,如果您要查看本帖隐藏内容请回复

本帖被以下淘专辑推荐:

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
465 
累计签到:682 天
连续签到:1 天
发表于 2017-8-9 09:35:26 | 显示全部楼层
本帖最后由 冬雪雪冬 于 2017-8-9 09:47 编辑

先写了一个特别笨的方法,效率很低。
  1. import itertools
  2. def jump(n):
  3.     count = 0
  4.     for i in range(1, n + 1):
  5.         p = itertools.product('12', repeat = i)
  6.         for j in p:
  7.             sum1 = sum([int(x) for x in j])
  8.             if sum1 == n:
  9.                 count += 1
  10.     return count
复制代码

验算了一下结果就是斐波那契数列。
那就简单了。
  1. def fab(n):
  2.     n1 = 1
  3.     n2 = 2
  4.     for i in range(1, n):
  5.         n1, n2 = n2, n1 + n2
  6.     return n1
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
MSK + 5 + 5 厉害~

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
243 
累计签到:230 天
连续签到:67 天
发表于 2017-8-9 08:55:44 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
243 
累计签到:230 天
连续签到:67 天
发表于 2017-8-9 08:56:06 | 显示全部楼层
老铁等一两天,提升一下
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
50 
累计签到:326 天
连续签到:4 天
发表于 2017-8-9 09:33:19 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-8-9 09:44 编辑

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

同类型的题目还有:在m*n的“田”字形的方格中,从左下角出发,每次只能往右或者往上行走,问走到左上角一共有多少种走法?
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
24 
累计签到:132 天
连续签到:1 天
发表于 2017-8-9 12:03:46 From FishC Mobile | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:41 天
连续签到:2 天
发表于 2017-8-9 12:25:47 | 显示全部楼层

  1. def jump(n):
  2.      if n== 1:
  3.           return 1
  4.      elif n == 2:
  5.           return 2
  6.      else:
  7.           return jump(n-1)+jump(n-2)

  8. n = int(input('请输入台阶数:'))
  9. print('%d 级台阶有 %d 种跳法。' % (n, jump(n)))
复制代码

评分

参与人数 1荣誉 +4 鱼币 +4 收起 理由
新手·ing + 4 + 4 为你鼓掌

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:24 天
连续签到:1 天
发表于 2017-8-9 12:29:11 | 显示全部楼层
本帖最后由 woigh 于 2017-8-9 12:30 编辑

想到递回的方式

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

  4.     return steps(n-1) + steps(n-2)
复制代码

评分

参与人数 1荣誉 +4 鱼币 +4 收起 理由
新手·ing + 4 + 4 可以的~

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-8-10 11:56:39 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:1 天
连续签到:1 天
发表于 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[i],b[i])
    #print('跳法的总数',result)
    return result
for i in range(12):
    print('总的跳法',frog_ladder(i))

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

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
MSK + 5 + 5 大牛

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:9 天
连续签到:2 天
发表于 2017-8-10 14:55:37 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-8-10 15:08:19 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:63 天
连续签到:3 天
发表于 2017-8-14 15:05:06 | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:222 天
连续签到:1 天
发表于 2017-8-15 21:22:18 From FishC Mobile | 显示全部楼层
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
1 
累计签到:261 天
连续签到:3 天
发表于 2017-8-18 20:28:25 | 显示全部楼层
如果用枚举法,那实在是很慢,n=10 就要等了
  1. import itertools as it
  2. cal = lambda n: sum([len(set(it.permutations('1'*(n-2*i)+'2'*i))) for i in range(n//2+1)]) if n>0 else 0
复制代码

要跳上第n阶首先要站在第n-1阶或者第n-2阶上,
那么要站到第n-1阶或第n-2阶有几种方法呢?
不就是去掉第一项的斐波那契数列嘛
  1. # 结果就是斐波那契数列
  2. def fibs(n):
  3.     a,b = 1,1
  4.     for i in range(n):
  5.         a,b = b,a+b
  6.     return a if n>0 else 0
复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-10-20 17:06 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表