3N加1算法迭代次数分布 2011-09-07

任取一个自然数,如果是偶数则除以2,如果是奇数则乘3加1,将计算得到的数重复以上过程,那么它总会回到1(该定理目前尚未得到证明)。但我们想看下所需迭代次数与所选数有什么关系,如下图所示。

###############3N+1算法试验##################
###执行算法的主函数f(n),展示过程并返回迭代次数i
f <- function(n)
{
	i=0
	while(n>1)
	{
	if(n%%2==0)
	n <- n/2
	else
	n <- 3*n+1
	cat(i,'\t',n,'\n')
	i = i+1
	}
	return(i)
}

#保存1到n所有整数的迭代次数到vec
n <- 1e5
vec <- rep(0,n)
for(i in 1:n)
{vec[i] <- f(i)}
save(vec, file="vec.dat")
vec <- read.table(file="vec.dat")


#寻找1到n中所需迭代次数最多的整数n_max
n_max<-which(vec==max(vec))
#结果是97@0.1k,871@1k,6171@10k,26623@100k

#3N+1算法迭代次数分布图
op <- par(bg = "light blue")
plot(vec[1:25000], type="p", pch=21, bg=par("bg"), col = "blue", cex=.6,
 main='3N+1算法迭代次数分布图')
par(op)

3N+1算法迭代次数分布图



Powered by Jekyll on GitHub | ©2016 Meroa | Last modified: 2018-03-22