uva 11549计算器谜题(floyd判圈算法)463.com

uva 11549计算器谜题(floyd判圈算法)


题意:有个老式计算器,每次只能记住一个数字的前n位。现在输入一个整数k,然后反复平方,一直做下去,能得到的最大数是多少。例如,n=1,k=6,那么一次显示:6,3,9,1…

思路:这个题一定会出现循环,所以一个个模拟,遇到相同的就再之前所有数中找最大的输出即可。

 

463.com,最容易想到的就是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;
} 

 

http://www.bkjia.com/cjjc/1003428.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1003428.htmlTechArticleuva 11549计算器谜题(floyd判圈算法)
题意:有个老式计算器,每次只能记住一个数字的前n位。现在输入一个整数k,然后反复平方,一直做…

题意:有一个老式计算器,只能显示n为数字。有一天,你无聊了,于是输入一个整数k,然后反复平方,直到溢出。每次溢出时,计算器会显示出结果最高的

n位和一个错误标记。然后清除错误标记,继续平方。如果一直这样做下去,能得到的最大数是多少。

题解:简单的推一下,发现其前几位是一个环状结构,及计算器显示出的数将出现循环,应为不管怎么样,数总会出现重复。

这样方法一可以不断模拟,吧结果存入数组中不断找,map去做应该是可以的。

 

相关文章