1
florije 2016-02-26 15:31:29 +08:00 1
def fib(n):
a,b = 1,1 for i in range(n-1): a,b = b,a+b return a print fib(5) 先来个最简单的吧~ |
2
MyLeoWind 2016-02-26 15:31:48 +08:00 via Android
a, b = b, a+b
这个确实是最简洁的。 |
3
kevinyoung 2016-02-26 15:34:01 +08:00
送分题不做
|
4
songkaiape 2016-02-26 15:39:40 +08:00
@kevinyoung 有一百个人,分别从 1 一直到 100 。现在有人拿枪从第一个开始枪毙,每枪毙一个跳过一个, 一直到一轮完成。接着在活着的人里面再次枪毙第一个,间隔一个再枪毙一个,请问最后活着的是这一百个人里的第几个人?给你个有难度的=。=
|
5
1373569162 2016-02-26 15:47:43 +08:00 1
俺贴个别人总结版的, 有兴趣的看下
http://www.cnblogs.com/figure9/archive/2010/08/30/1812927.html 还有一个求质数的有兴趣的可以实现一下 https://program-think.blogspot.com/2011/12/prime-algorithm-1.html |
6
glchaos 2016-02-26 15:51:39 +08:00
@kevinyoung 不送分的题不会做,就是这么任性
|
7
random2case 2016-02-26 15:55:48 +08:00
俺喜欢斐波那契数列,先来一个 rust 写的
fn fibonacci (n:i32) ->i32{ if n<=2 {1} else {fibonacci(n-1)+fibonacci(n-2)} } 再来一个 scala 写的 object test{ def fibonacci(n:Int):Int={ if (n<2) 1 else fibonacci(n-1)+fibonacci(n-2) } } |
8
eote 2016-02-26 15:58:04 +08:00 1
```
import json import urllib2 import lxml.etree html = urllib2.urlopen('https://oeis.org/A000045/list').read() pre = lxml.etree.HTML(html).xpath('//pre') rst = json.loads(pre[0].text) for i in rst: print(str(i) + '\n') ``` 输出前 38 个 Fib |
9
jixiangqd 2016-02-26 16:01:44 +08:00
@songkaiape 这个貌似也没难度啊,直接按字面意思翻译成程序就能跑出结果?
a=[i+1 for i in range(100)] while len(a)>1: b=a[:] for i in range(0,len(a),2): a.remove(b[i]) print a |
10
jixiangqd 2016-02-26 16:03:37 +08:00
重新贴一下程序
```python a=[i+1 for i in range(100)] while len(a)>1: b=a[:] for i in range(0,len(a),2): a.remove(b[i]) print a ``` |
11
qiuhanyuan 2016-02-26 16:08:52 +08:00
def fibs(num):
result = [1, 1] for i in range(num-2): result.append(result[-1]+result[-2]) return result |
12
Lihz 2016-02-26 16:19:15 +08:00 1
楼上的都不喜欢用 yield 构建生成器么?如果拿这做面试题,侧重的不在于能否给出答案,而是被面试者能否脑补出不同条件并构建对应方案以及在不同方案下暴露出的编程习惯吧
|
13
Lihz 2016-02-26 16:20:55 +08:00
类似的还有素数筛选这种看似简单,但深入而言可挖掘的点是非常多的
|
14
fulvaz 2016-02-26 16:25:59 +08:00
斐波那契数列很多结果都可以重复利用, 只需要加个缓存, 就能有非常棒的速度
: ) |
15
songkaiape 2016-02-26 16:29:03 +08:00
@jixiangqd 嗯,是不难啊,不过你为什么这样写 a=[i+1 for i in range(100)] ,直接 a=list(range(1,101))不就好了么
|
16
songkaiape 2016-02-26 16:30:38 +08:00
|
17
livc 2016-02-26 16:30:38 +08:00
@songkaiape 约瑟夫环
|
18
jixiangqd 2016-02-26 16:32:08 +08:00
@songkaiape 这倒是,- -,随手写的,留了些坏习惯在代码里
|
19
mcfog 2016-02-26 16:36:25 +08:00 2
在 V2EX 要大家贴派森代码简直残忍(つД`)ノ
|
20
jixiangqd 2016-02-26 16:40:40 +08:00
@songkaiape 18 楼真是 Pythonic.... 突然发现我还是新手。。。水平惨不忍睹
|
22
mouer 2016-02-26 17:21:53 +08:00
fib = lambda n : 1 if n <= 2 else fib(n - 1) + fib(n - 2)
|
24
tempuseraccount 2016-02-26 17:25:19 +08:00
由此工作中还真有用了 fibonacci 数列的地方。
真使用的话还是最好把值存在数组里直接取。能少算尽量少算 |
25
wentian 2016-02-26 17:48:18 +08:00
def fib():
fib1,fib2 = 1, 1 while True: yield fib1 fib1, fib2 = fib2, fib1+fib2 |
27
dofy 2016-02-26 17:52:24 +08:00
可以贴 gist
|
28
ipconfiger 2016-02-26 17:55:19 +08:00
print [x[0] for x in [ (a[i][0], a.append((a[i][1], a[i][0]+a[i][1]))) for a in ([[1,1]], ) for i in xrange(100) ]]
一行 |
29
RqPS6rhmP3Nyn3Tm 2016-02-26 18:18:18 +08:00 via Android
Python 官网就有,一行搞定
|
30
RqPS6rhmP3Nyn3Tm 2016-02-26 18:24:34 +08:00 via Android
来个神经病版的
print '1,1,2,5,7,12,19,31,50' |
31
wellsc 2016-02-26 18:32:53 +08:00
```
def fib(n): f1 = f2 = 1 for k in range(1, n) f1, f2 = f2, f2 + f1 return f2 ``` |
32
bdbai 2016-02-26 19:44:29 +08:00 via iPhone
@random2case 俺不懂 fp ,不过用递归的效率真的好吗?
|
33
mailto1587 2016-02-26 20:43:25 +08:00
递归不 memoize 一下?
``` memo = {1: 1, 2: 1} fib = lambda n: memo.get(n) or memo.setdefault(n, fib(n - 1) + fib(n - 2)) ``` 这方案的缺陷是,需要慢慢调教它,一下子 fib(5000)肯定会撒娇,需要 fib(1000)、 fib(2000)、 fib(3000)、 fib(4000)、 fib(5000), Done ! |
34
random2case 2016-02-26 20:46:14 +08:00
@bdbai 尾递归好的多,如 @fulvaz 所说的,加上了缓存,效率也高多了,据说相当于循环。尾递归不会每一次都分配新栈了。但是看着难理解了,幸好 scala 有一个 @tailrec 检查是否是尾递归呢。
def fib_out(n:Int):Int={ @tailrec def _loop(n:Int,acc1:Int,acc2:Int):Int={ if(n < 2) acc2 else _loop(n-1,acc2,acc1+acc2) } _loop(n,1,1) } 函数式编程是程序员的一个福利吧,如果你喜欢,并且可以因此发挥你的才智,创造,获得快乐。那么你完全可以享用它,同时,函数式编程作为一个福利,你也可以选择拒绝它。 |
35
random2case 2016-02-26 20:52:22 +08:00
@mailto1587 把俺写的这个 Int 换成 BigInt,试了下, fib(5000)瞬间出来了, 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626 ,俺没办法把 fib(100000)贴上来,这装不下。但是也是不到一秒。
|
36
happywowwow 2016-02-26 21:12:21 +08:00
|
37
kevinyoung 2016-02-26 21:13:11 +08:00
@songkaiape 第一次会把奇数编号的去掉,剩下偶数编号的全部编号除以二,再进行这个过程,所以最后剩下的那个肯定是 100 以内最“偶”的那个, 64
|
38
shyling 2016-02-26 21:18:46 +08:00
@random2case 要有尾递归优化的尾递归才有用吧=。=, py 嘛~~~~~
|
39
kevinyoung 2016-02-26 21:24:44 +08:00
@bdbai 我觉得递归最大的好处是有些问题用递归的语言描述非常简洁,比如快排比如对树进行操作,但这并不总是成立的
回到 python , python 虽然能递归,但并不会自动做尾递归优化,所以递归算这种东西可能会爆栈,另外函数调用也会造成额外的时间开销,直观的看同样作用的 python 代码,循环的就是比递归的快。所以写 python 的话其实不推荐写递归,而是想办法写成循环好一些 其他的语言另说,比如 Haskell 根本没有循环只能写递归,或者有些语言递归优化的好也可以。 |
40
random2case 2016-02-26 21:40:09 +08:00
@shyling python 尾递归是否优化,俺不太清楚,俺只是拿 python 做一些简单的事,对语言本身不了解。但是 scala 确实是对尾递归做过优化的。 https://www.google.com/#q=+scala+tail+recursion ,自行 google 一下吧。
如 @kevinyoung 所说, Haskell 根本没有循环只能写递归。 scala 借鉴了 Haskell 。但是 scala 也可以写循环的。 |
41
luobuda 2016-02-26 21:51:47 +08:00
|
42
RqPS6rhmP3Nyn3Tm 2016-02-26 22:08:50 +08:00 via Android
@happywowwow 才发现…口算跳步骤习惯了…
|
43
bdbai 2016-02-26 22:10:35 +08:00 via iPhone
|
45
zangxixi OP @qiuhanyuan O(∩_∩)O 哈哈~这个也是我第一种写法
|
46
random2case 2016-02-26 22:16:24 +08:00
@bdbai 啊,争论哪个语言好永无止境。。。呵呵
|
47
zangxixi OP |
48
wentian 2016-02-26 22:54:12 +08:00
|
49
zoudm 2016-02-26 23:14:23 +08:00
@songkaiape
@kevinyoung 100 个人结果并不是 64 ,再考虑一下吧。 假如 10 个人,第一轮死了 1 3 5 7 9 ,那么 10 不会死, 10 的下一个人是 2 ,于是死的依次是 2 6 10 ,剩 4 8 ; 10 的下一个是 4 , 10 死了, 4 不会死,于是 8 死了。答案是 4 。 100 个人答案是 73 (编号从 0 开始是 72 ) https://en.wikipedia.org/wiki/Josephus_problem |
50
edsgerlin 2016-02-26 23:22:05 +08:00
Y Combinator 写的比较好玩!
https://rosettacode.org/wiki/Y_combinator#Python >>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) >>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1)) >>> [ Y(fac)(i) for i in range(10) ] [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] >>> fib = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2)) >>> [ Y(fib)(i) for i in range(10) ] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] |
51
mailto1587 2016-02-26 23:42:47 +08:00
@random2case Python 不支持尾递归优化,除非做 CPS 变换,还得靠 trampoline 方法才能 work around
``` def trampoline(obj): while hasattr(obj, '__call__'): obj = obj() return obj def memoize(func): memo = {} def wrapper(n, ret=lambda x: x): if n in memo: return lambda: ret(memo[n]) def with_value(value): memo[n] = value return lambda: ret(value) return lambda: func(n, with_value) return wrapper @memoize def fib_cps(n, ret): if n < 2: return lambda: ret(n) def with_a(a): def with_b(b): return lambda: ret(a + b) return lambda: fib_cps(n - 1, with_b) return lambda: fib_cps(n - 2, with_a) print(trampoline(fib_cps(100000))) ``` 恩,递归版本差不多被玩坏了 |
52
mailto1587 2016-02-26 23:45:34 +08:00
v2ex 文本功能太渣,放 gist 吧( https://gist.github.com/mailto1587/827c0140e5775a986ddb )
|
53
ShiHou 2016-02-27 04:50:01 +08:00
<script src="https://gist.github.com/Lyken17/5bffba48807fea6efd77.js"></script>
|
54
kevinyoung 2016-02-27 09:58:06 +08:00
@zoudm 这就是个问题怎么描述的事情,按照 @songkaiape 的说法就是每次从头开始枪毙,是 64 ,按照你的说的最后一个不直接跳过去那就是 73
|
55
qiuhanyuan 2016-02-27 10:11:42 +08:00
@zangxixi 哈哈,握爪
|
56
shuson 2016-02-27 12:32:40 +08:00 via iPhone
import fib
fib.get(10) |
58
ZRS 2016-02-27 22:40:36 +08:00 1
还可以考虑用斐波拉契的通项公式嘛
import math sqrtfive = math.sqrt(5) def Fibonacci(n): return sqrtfive/5*(math.pow(((1+sqrtfive)/2),n)-math.pow(((1-sqrtfive)/2),n)) n = 4 while n>=1: print Fibonacci(n) n -= 1 |
59
ZRS 2016-02-27 22:41:08 +08:00
咦缩进没了....
|