UVa 371 Ackermann function

解題策略

爛題目，首先光題目就誤導人了，這題不是Ackermann function ，是 3n+1 ，我還特別跑去確認 Ackermann function 的樣子。

然後兩個很爛的陷阱 (題目敘述沒明說)
1. 有可能 L>H。而最後輸出時必須交換成L<=H ，這跟UVa 100 3n+1不一樣。
2. 題目說範圍不會超過long的真正的意思是unsigned long，所以一般 int 會吃WA。

被細節弄得很火。

提供測資

==input==
2000 3000
3000 2000
0 0

==Output==
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.
Between 2000 and 3000, 2919 generates the longest sequence of 216 values.

	/**
	* UVa 371 Ackermann function
	* Author: chchwy
	* Last Modified: 2010.03.18
	* Tag: Brute Force
	*/
	#include<cstdio>
	#include<algorithm>
	int getLength(long long n)
	{
	int length = 0;
	do
	{
	length++;
	if (n % 2 == 0)
	n = n >> 1; // div 2
	else
	n = n * 3 + 1;
	}
	while (n != 1);
	return length;
	}
	int main()
	{
	int L, H;
	while (scanf("%d %d", &L, &H))
	{
	if (L == 0 && H == 0)
	break;
	if (L > H) std::swap(L, H); //L may be greater than H
	int maxLen = 1, max = L;
	for (int i = L; i <= H; ++i)
	{
	int curLen = getLength(i);
	if (curLen > maxLen)
	{
	max = i;
	maxLen = curLen;
	}
	}
	printf("Between %d and %d, ", L, H);
	printf("%d generates the longest sequence of %d values.\n", max, maxLen);
	}
	return 0;
	}

view raw 371.cpp hosted with ❤ by GitHub