UVA11549计算机谜题-白红宇

UVA11549计算机谜题

阅读量：5273 次

发布时间：2019-06-14

本文共 1556 字，大约阅读时间需要 5 分钟。

UVA11549计算机谜题

【题目描述】：

有一个计算器，只能显示n位数字，给定初始数字k和位数n，做无数次的k^2运算，记录每次的k^2的前n位数字，并将这个新的数字做为下次平方的对象。记录在这无数次运算中，出现的最大的n位数字。

【思路分析】：

这道题目在经验之下，应该看出是存在循环节的，反而观之，在大学生数学水平下，不可能直接找到结果的分布。

所以问题就转化成了一道模拟题，因为以前没用过set，所以写了这道比较水的题。

【注意事项】：

循环结不一定又回到初始的k，这点我想错了；

显示前n位不是后n位，所以传统的取模运算失效，应该按位读取每个数，才方便运算；

【重点】：对过程的模拟是难点

【完整代码】：

1 #include
          
            2 #include
           
             3 #include
            
              4 #include
             
               5 #include
              
                6 #include
               
                 7 #include
                
                  8 #include
                 
                   9 #include
                  
                   10 #include
                   11 #define MAXN 100000+512 #define MAXM 20000+513 #define oo 955653114 #define eps 0.00000115 #define PI acos(-1.0)//这个精确度高一些16 #define REP1(i,n) for(int i=0;i<=(n);i++)17 #define REP2(i,n) for(int i=1;i<=(n);i++)18 #define LL long long19 using namespace std;20 21 LL getnext(int n,LL k)//返回k^2的最多前n位22 {23 int digit[55],cnt=0;24 LL k2=k*k;25 while(k2>0){digit[cnt++]=k2%10;k2=k2/10;}//从低位向高位存储26 if (cnt
                    
                     s;35 int cas,n;36 LL k;37 int main()38 {39 cin>>cas;40 for(;cas;cas--)41 {42 cin>>n>>k;43 s.clear();44 LL ans=k;s.insert(k);45 for(;;)46 {47 LL nk=getnext(n,k);48 if (s.count(nk)) break;49 s.insert(nk);50 ans=max(ans,nk);51 k=nk;52 }53 cout<
                     
                      <

【拓展学习】: set的内部函数原理和使用

【little from】：

平衡二叉树实现,所以查找、插入、删除都是O(log2(N))

begin() 　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear() 　 ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

转载于:https://www.cnblogs.com/little-w/p/3517411.html

你可能感兴趣的文章