Project Euler 14 Longest Collatz sequence

题意：对于任意一个数 N ，寻找在 100,0000 之内按照规则（ N 为奇数 N = N * 3 + 1 ，N 为偶数 N = N / 2 ，直到 N = 1 时的步数）步数的最大值

思路：记忆化搜索即可，利用之前搜索的值加速搜索，如果当前搜索值在之前已经处理过，那么直接利用当前搜索值 + 到当前数的步数即为该数的步数

/*************************************************************************

    > File Name: euler014.c

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年06月24日 星期六 19时36分58秒

 ************************************************************************/

#include <stdio.h>

#include <inttypes.h>

#include <stdlib.h>

#define MAX_N 1000000

#define MAX_KEEP_RANGE 50000000

int64_t skeep[MAX_KEEP_RANGE+5] = {0};

int64_t DFS(int64_t x){

	if( x == 1 )	return 1;

	if( x <= MAX_KEEP_RANGE && skeep[x] != 0 )	return skeep[x];

	int64_t ans;

	if( x & 1 )		ans = DFS( x*3 + 1 ) + 1;

	else			ans = DFS( x >> 1 ) + 1;

	if( x <= MAX_KEEP_RANGE )	skeep[x] = ans;

	return ans;

}

int32_t main(){

	int64_t maxN = 0;

	for(int64_t i = 1 ; i <= MAX_N ; i++){

		skeep[i] = DFS(i);

		maxN = maxN > skeep[i] ? maxN : skeep[i];

	}

	printf("%"PRId64"\n",maxN);

	return 0;

}

巴特西

Project Euler 14 Longest Collatz sequence

最新文章

热门文章