程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 11549計算器謎題（floyd判圈算法）

uva 11549計算器謎題（floyd判圈算法）

編輯：C++入門知識

uva 11549計算器謎題（floyd判圈算法）

題意：有個老式計算器，每次只能記住一個數字的前n位。現在輸入一個整數k，然後反復平方，一直做下去，能得到的最大數是多少。例如，n=1，k=6，那麼一次顯示：6,3,9,1...

思路：這個題一定會出現循環，所以一個個模擬，遇到相同的就再之前所有數中找最大的輸出即可。

最容易想到的就是set判重，一開始k直接生算每次除十......超時

然後看了書，用string，ac，很方便但是時間達到了4s，果然string和stringstream好慢啊.........

又改成了記錄k*k的每一位，時間為1s

最後用了floyd判圈算法，0.5s，空間復雜度為o（1）........果然神奇

先上set代碼：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#include
using namespace std;  
#define LL long long  
//const int maxn = ;
const int INF = 1000000000;
//freopen("input.txt", "r", stdin);
int buf[100];

LL next(LL n, LL k) {
	stringstream ss;
	ss << k * k;
	string s = ss.str();
	if(s.length() > n) s = s.substr(0, n);
	LL ans;
	stringstream ss2(s);
	ss2 >> ans;
	return ans; 
}

int main() {
	int t; scanf("%d", &t);
	while(t--) {
		set a;
		LL n, k; scanf("%lld%lld", &n, &k);
		LL ans = 0;
		while(!a.count(k)) {
			a.insert(k);
			ans = max(ans, k);
			k = next(n, k);
		}
		
		printf("%lld\n", ans);
	}
	return 0;
}

然後是floyd判圈代碼

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
#include
using namespace std;  
#define LL long long  
//const int maxn = ;
const int INF = 1000000000;
//freopen("input.txt", "r", stdin);
int buf[100];

LL next(LL n, LL k) {
	if(!k) return 0;
	LL k2 = (LL)k * k;
	int L = 0;
	while(k2 > 0) {buf[L++] = k2 % 10; k2 /= 10;}
	if(n > L) n = L;
	int ans = 0;
	for(int i = 1; i < n; i++) ans = ans * 10 +buf[--L];
	return ans;
}

int main() {
	int t; scanf("%d", &t);
	while(t--) {
		int n, k;
		cin >> n >> k;
		int ans = k;
		int k1 = k, k2 = k;
		do {
			k1 = next(n, k1);
			k2 = next(n, k2); if(k2 > ans) ans = k2;
			k2 = next(n, k2); if(k2 > ans) ans = k2;
		} while(k1 != k2);
		cout << ans << endl;
	}
	return 0;
}