首页 > itarticle > 数字游戏

数字游戏

admin 11月 14, 2020 0

递归过不了数据卷子交完才想起来可以用动态规划难过。。。

数字游戏

给定一个数字若可以开方则去开方否则减一循环次操作多少次后数字变为1？

递归

let res = 0
function numberGame(num){
	if(num==1){
		return res
	}
	let nextparam
	let n = Math.sqrt(num)
	if(Math.floor(n)==n){
		nextparam = n
	}else{
		nextparam = n-1
	}
	res++
	numberGame(nextparam)
}

动态规划

function numberGameDP(num){
	let dp = []
	dp[0] = 0
	dp[1] = 0
	for(let i=2;i<=number;i++){
		let c = Math.sqrt(num)
		if(c == Math.floor(c)){
			dp[i] = dp[c]+1
		}else{
			dp[i] = dp[i-1]+1
		}
	}
	console.log(dp[num])
	return dp[num]
}