d < 1000について、1/dの順環節が最長となるdを求めよ。
以下解答
ncycle <- function(num, den){ rems <- numeric(0) idx <- 1L rem <- num repeat{ quo <- rem %/% den rem <- rem %% den if(rem %in% rems) break rems <- c(rems, rem) rem <- rem * 10L idx <- idx + 1L } if(rem == 0L) return(0L) if(idx == limit) return(NA_integer_) length(rems) - which(rem==rems) + 1L } slimit <- 999L cyclelen <- sapply(1L:slimit, ncycle, num=1L)
余りを調べていけばいい。0.5秒(明示的に整数型にしないと1秒弱かかる)。
ところで、この方法だと順環節の長さの分だけのベクトルが必要になる。また、途中でベクトルを伸ばすので速度的にも不利である。
順環を検出するためのアルゴリズムとして、フロイドの循環検出法というものがある(cf. フロイドの循環検出法 - Wikipedia)。このアルゴリズムでは最新の余りだけを保持しておけばよく、単に順環節の長さを求めるだけであれば、順環節の長さにかかわらず必要なベクトルのサイズが増大しない。
ncycle <- function(num, den){ rabbit <- (((num * 10L) %% den) * 10L) %% den turtle <- ((num * 10L) %% den) while(rabbit != turtle){ rabbit <- (((rabbit * 10L) %% den) * 10L) %% den turtle <- (turtle * 10L) %% den } rabbit <- num while(rabbit != turtle){ rabbit <- (rabbit * 10L) %% den turtle <- (turtle * 10L) %% den } cnt <- 1L rabbit <- (((rabbit * 10L) %% den) * 10L) %% den turtle <- (turtle * 10L) %% den while(rabbit != turtle){ rabbit <- (((rabbit * 10L) %% den) * 10L) %% den turtle <- (turtle * 10L) %% den cnt <- cnt + 1L } return(cnt) } slimit <- 999L cyclelen <- sapply(1L:slimit, ncycle, num=1L) which(max(cyclelen) == cyclelen)
フロイドの循環検出法を使えば0.14秒で終わる。また、探索範囲をd<10000まで増やした場合、最初の方法では2分30秒かかるが、フロイドの循環検出法を使えば8.6秒で終わる。