首页 > 代码库 > Floyd判圈算法

Floyd判圈算法

今天是在不想听英语课了,于是就选择看刘汝佳的神书,结果发现了Floyd判圈算法,直接把空间复杂度降到O(1),自己写一遍就当做复习一下。

UVa11549计算机谜题

  有一个古老的计算机,只能显示n位数字。有一天你无聊了,于是输入一个整数k,然后反复平方,直到溢出。每次溢出是,计算会显示出结果的最高位n位和一个错误标记。然后清除错误标记,继续平方如果一直这样做下去,能得到的最大数是多少?比如,当n=1,k=6时,计算器将依然显示6、3(36的最高位),9、8(81最高位)、6(64的最高位),3……

 

输入格式:

    输入的第一行为一个整数T(1<=T<=200),测试数据数量,每行包括两个整数n和k(1<=n<=9,0<=k<10^n)

输出格式:

    对于每组数据,输出你能得到的最大数。

分析:题目已经暗示有循环出现,我们再看一下数据规模,模拟应该是可以的,所以我们可以选择开数组存下每次出现的数。但是有一个问题k的取值已经能把数据规模撑的大大所以我们可以用stl的集合set。具体用法可以参考我的模板关于篇幅原因我就不打了。不懂得可以直接翻书看了在43页。现在最重要的问题来了。floyd判圈算法。

   嘤嘤嘤~(这不是我) 

   首先我们来看一下刘汝佳大大大大大大大神的解释,想象一下,假设有两个小孩子在一个“可以无限向前跑”的跑道上赛跑,同时出发,但其中一个小孩的速度是另一个的两倍。如果跑道是直的,跑的快的永远在前面;但是如果跑道有环的话,则跑的快的小孩子将追上跑的慢的小孩。

   可能我大脑构造有些特殊。表示不解后来才明白。其实就是以前跑道是直道,而后来跑道是圈,跑的快的把跑得慢的套圈了,当正好追上跑的慢的小孩时,正好比慢的小孩多跑一圈,多循环一次,然后终止好了,在这中间顺便那个变量选一下最大值输出搞定。

代码如下:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int buf[100];
 5 int next(int n,int k)
 6 {
 7     if(!k) return 0;
 8     long long k2=(long long) k * k;
 9     int l=0;
10     while(k2>0){
11         buf[l++]=k2 % 10;
12         k2 /= 10;
13     }
14     if(n>l) n=l;
15     int ans=0;
16     for(int i=0;i<n;i++)
17      ans=ans*10+buf[--l];
18     return ans;
19 }
20 int main()
21 {
22     int t;
23     cin>>t;
24     while(t--)
25     {
26         int n,k;
27         cin>>n>>k;
28         int ans=k;
29         int k1=k,k2=k;
30         do{
31             k1=next(n,k1);
32             k2=next(n,k2); if(k2>ans) ans=k2;
33             k2=next(n,k2); if(k2>ans) ans=k2;
34         }while(k1!=k2);
35         cout<<ans<<endl;
36     }
37     return 0;
38 }

     嘿嘿~

Floyd判圈算法