算法题一道,欢迎讨论

xiaozhu2007

简述：
实现一个函数，对一个正整数n，算得到1需要的最少操作次数：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。
例子：
ret=func(7);
ret=4，可以证明最少需要4次运算
n=7
n--6
n/2 3
n/2 2
n++1
要求：
实现函数（实现尽可能高效）int func(unsign int n)；n为输入，返回最小的运算次数。
给出思路（文字描述），完成代码，并分析你算法的时间复杂度。
请列举测试方法和思路。

xiaozhu2007

n=7
n--6
n/2 3
n/2 2
n++1没看明白是怎么算出来是4次

5毛党党员

n--6
n/2 3

n-- 2  

n/2 1

应该是这么4步吧？

insmile

原帖由 xiaozhu2007 于 2008-9-1 16:42 发表
n=7
n--6
n/2 3
n/2 2
n++1没看明白是怎么算出来是4次

n=7


n--            1
n/2            2(此时n为3)
n--             3（此时n为2）
n/2            4


就是这样来的

insmile

呵呵，重复了

cugb_cat

n++   8
n/2    4
n/2    2
n/2    1

xiaozhu2007

题目中给的这个:
n=7
n--6
n/2 3
n/2 2
n++1莫名其妙

cjaizss

直觉上，这个题目与数的位数，是以10打头还是11打头，1的个数有关。
下班了，喝酒去了，不想了。

snick

直接取模可以么?  只要一次或两次

奇数 X % 2               1 次
偶数  (X + 1) % 2      2 次

5毛党党员

原帖由 snick 于 2008-9-1 17:02 发表
直接取模可以么?  只要一次或两次

奇数 X % 2               1 次
偶数  (X + 1) % 2      2 次

。。。这个和lz的题目有什么关系？