題意：
? ? ? ?有一個計(jì)算機(jī)只能保留數(shù)字的前n位，你有一個數(shù)字k（k<=9），反復(fù)平方后在計(jì)算機(jī)上顯示的最大數(shù)字是多少。


思路：
? ? ? 顯然這個題目是有循環(huán)節(jié)的，為什么有循環(huán)節(jié)？首先我們看下k<=9那么也就是說所有的答案都是9位數(shù)之內(nèi)的，也就是說才幾億唄，最慢幾億次之后必然循環(huán)啊，這樣我們就可以不停得枚舉，然后碰到循環(huán)節(jié)的時候就不枚舉了，怎么樣找循環(huán)節(jié)，一開始想的是只記錄第一個，然后等第一個再次出現(xiàn)的時候就直接break結(jié)果果斷錯了，他有可能是類似這樣的循環(huán)節(jié)1 2 3 4 5 4 5 4 5.....循環(huán)節(jié)是4 5，這種的，所以第一種方法失敗了，但是我們可以用最笨的方法去記錄，就是開一個容器，我開的是map，記錄每個數(shù)字是否出現(xiàn)過，提交之后雖然ac了但感覺容器挺耗時的，然后又寫了個書上說的那個Floyd判圈，結(jié)果果然快了很多，一下是兩種方法的代碼。




Floyd判圈


#include<stdio.h>


int mk[15];


void inint()
{
? ? ?mk[0] = 1;
? ? ?for(int i = 1 ;i <= 9 ;i ++)
? ? ?mk[i] = mk[i-1] * 10;
}


long long next(int n ,int a)
{
? ? long long now = (long long)a * (long long)a;
? ? while(now >= mk[n])
? ? now /= 10;
? ? return int(now);
}


int main ()
{
? ?int t ,n ,m ,Ans;
? ?inint();
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? ?scanf("%d %d" ,&n ,&m);
? ? ? ?Ans = m;
? ? ? ?int k1 = m ,k2 = m;
? ? ? ?do
? ? ? ?{
? ? ? ? ? ?k1 = next(n ,k1);if(Ans < k1) Ans = k1;
? ? ? ? ? ?k2 = next(n ,k2);if(Ans < k2) Ans = k2;
? ? ? ? ? ?k2 = next(n ,k2);if(Ans < k2) Ans = k2;
? ? ? ?}while(k1 != k2);
? ? ? ?printf("%d\n" ,Ans);
? ?}
? ?return 0;
}




map判斷是否出現(xiàn)過


#include<stdio.h>
#include<map>


using namespace std;


int mk[15];
map<int ,int>mark;


void inint()
{
? ? ?mk[0] = 1;
? ? ?for(int i = 1 ;i <= 9 ;i ++)
? ? ?mk[i] = mk[i-1] * 10;
}


long long next(int n ,int a)
{
? ? long long now = (long long)a * (long long)a;
? ? while(now >= mk[n])
? ? now /= 10;
? ? return int(now);
}


int main ()
{
? ?int t ,n ,m ,Ans;
? ?inint();
? ?scanf("%d" ,&t);
? ?while(t--)
? ?{
? ? ? ?scanf("%d %d" ,&n ,&m);
? ? ? ?Ans = m;
? ? ? ?mark.clear();
? ? ? ?mark[m] = 1;
? ? ? ?while(1)
? ? ? ?{
? ? ? ? ? m = next(n ,m);
? ? ? ? ? if(Ans < m) Ans = m;
? ? ? ? ? if(mark[m]) break;
? ? ? ? ? mark[m] = 1;
? ? ? ?}
? ? ? ?printf("%d\n" ,Ans);
? ?}
? ?return 0;
}
? ? ? ? ? ??












? ? ? ? ? ??



《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的UVA11549计算器谜题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。