本文主要是介绍【算法小题 go程序版】递归练习 -- 猴子吃桃问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
注:
本系列所有题解都用go实现,主要go方便,想要其他版本的实现关注并私信博主。
题目
有一堆桃子,猴子第一天吃了其中一半,并再多吃了一个,以后每天猴子都吃其中一半,并多吃一个,到了第十天猴子发现只剩一个桃子了,问猴子最开始有多少个桃子?
题解与程序实现
我们假设初始总有m个桃,假设天数为n最后一天桃为f(n == 10) == 1个,第n天的桃个数等于其前一天的个数减去其一半再减1,f(n -1) - (f(n-1)/2 + 1) = f(n),也即 f(n-1) / 2 - 1那么我们可以写出:f(n) = f(n-1)/2 - 1
package main
import ("fmt"
)func calc_tao(n int) int {if n == 10 {return 1}if n > 0 {// calc_tao(n) = calc_tao(n - 1)/2 - 1 ret = (calc_tao(n + 1) + 1) * 2fmt.Printf("ret:%d, n:%d", ret, n)}
}func main() {// 求哪天的就传哪天,第一天传1,求第三天的穿第三天ret := calc_tao(1)fmt.Printf("get 1st day tao num:%d", ret)
}
有人估计想要非递归的实现,我这里也将伪代码写出来,补充就当你自己的小练习了。非递归可以有多种写法,用栈、队列、list甚至一个额外的变量都可以实现
// 用一个变量实现
func calc_tao(n) int {m := 10tao_num := 1for m > n {m--tao_num = (tao_num + 1) * 2}return tao_num
}
// 用一个栈实现,实际上这里没必要
func calc_tao(n) int {m := 10tao_num := 1stack_t tao_stacktao_stack.push_back(tao_num)for m > n && !tao_stack.empty() {m--local_tao_num := tao_stack.pop_front()tao_stack.push_back((local_tao_num + 1) * 2)}
}
这篇关于【算法小题 go程序版】递归练习 -- 猴子吃桃问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!