放牧代码和思想
专注自然语言处理、机器学习算法

UVa 100 The 3n + 1 problem

翻完了两本算法书,准备水一下UVa,这是UVa的Hello World,不要笑。

题目

首先吐个槽,为毛各大OJ都不支持C++11?看我的两次提交:

①不认识auto

code.cpp: In function ‘int pickLength(int)’:
code.cpp:29:7: error: ‘it’ does not name a type
  auto it = coll.find(i);
       ^
code.cpp:30:6: error: ‘it’ was not declared in this scope
  if (it == coll.end())
      ^

②不认识EXIT_SUCCESS

code.cpp: In function ‘int main(int, char**)’:
code.cpp:68:9: error: ‘EXIT_SUCCESS’ was not declared in this scope
  return EXIT_SUCCESS;
         ^

题目简单,值得注意的有两点:

1、溢出,必须用long long

2、i和j的大小要检验

#include <iostream>
#include <map>
using namespace std;

map<long long, long long> coll;

long long getLength(long long n)
{
	long long length = 1;
	while (n != 1)
	{
		++length;
		if (n % 2 == 0)
		{
			n = n / 2;
		}
		else
		{
			n = 3 * n + 1;
		}
	}

	return length;
}

long long pickLength(long long i)
{
	long long iLength = 0;
	map<long long, long long>::iterator it = coll.find(i);
	if (it == coll.end())
	{
		iLength = getLength(i);
		coll[i] = iLength;
	}
	else
	{
		iLength = it->second;
	}

	return iLength;
}

long long solve(long long i, long long j)
{
	if (i > j)
	{
		long long temp = i;
		i = j;
		j = temp;
	}
	long long result = pickLength(i);
	for (long long n = i + 1; n <= j; ++n)
	{
		long long nLength = pickLength(n);
		if (nLength > result)
		{
			result = nLength;
		}
	}

	return result;
}

///////////////////////////SubMain//////////////////////////////////
int main(long long argc, char *argv[])
{
	long long i = 0;
	long long j = 0;
	while (cin >> i >> j)
	{
		cout << i << ' ' << j << ' ' << solve(i, j) << endl;
	}
	/*system("pause");*/
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » UVa 100 The 3n + 1 problem

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机