USTCOJ1381 老式電腦 uva11549 （Set判重、Floyd判圈）

題目連結：http://acm.ustc.edu.cn/ustcoj/problem.php?id=1381

題目來源：uva11549

題目：對于給定的n和k，求k平方，取其高n位數指派給k，如是不斷平方，給出這一運算過程中k可能取到的最大值。

題目分析：顯然，對于一個n位整數而言，其可能的取值是有限的，是以上述過程必然出現循環。我們隻要在平方過程中得到此前出現過的k值，就表示已經周遊了所有可能的k值。

程式頭代碼如下

#include<iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
           

以下兩中解法均使用int next(int n, int k)函數來求解k平方的高n位組成的整數。該函數有多中實作方式，見第三節。

解題思路一

将所有出現的k值存起來，并定義一個變量ans存儲目前已知的k已取得的最大值。當新産生的k值已出現過，則退出循環，輸出ans值。

代碼實作，使用stl set存儲所有可能的k值。如下:

/*STL Set判重
*by: lance*/
int main()
{
    int t;
    set<int> result;
    scanf("%d", &t);
    while (t--)
    {
        result.clear();
        int n, k;
        scanf("%d%d", &n, &k);
        int ans = k;
        while (result.find(k) == result.end())
        {
            if (ans < k)
                ans = k;
            result.insert(k);
            k = next(n, k);
        }
        printf("%d\n", ans);
    }

    return 0;
}
           

解題思路二

由于必然出現循環，可使用Floyd判圈算法求解。相關分析可參考： 連結清單環的檢測（Floyd判圈算法）

/*Floyd判圈算法*/
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, k;
        cin >> n >> k;
        int ans = k;
        int k1 = k, k2 = k;
        do
        {
            k1 = next(n, k1); // 小孩1
            k2 = next(n, k2); // 小孩2，第一步
            if(k2 > ans) ans = k2;
            k2 = next(n, k2); // 小孩2，第二步
            if(k2 > ans) ans = k2;
        }
        while(k1 != k2);   // 追上以後才停止
        cout << ans << endl;
    }
    return 0;
}
           

next函數實作

在具體的代碼代碼實作中，求解一個數k的平方的高n位數有多種解法。我們定義該函數為int next(int n, int k)。如下是該函數的幾種可能的實作。

/*方案一：
*by: Rujia Liu*/
int buf[100];
int next(int n, int k)
{
    if(!k) return 0;
    long long k2 = (long long)k * k;
    int L = 0;
    while(k2 > 0)
    {
        buf[L++] = k2 % 10;    // 分離并儲存k2的各個數字
        k2 /= 10;
    }
    if(n > L) n = L;
    k = 0;
    for(int i = 0; i < n; i++) // 把前min{n,L}位重新組合
        k = k * 10 + buf[--L];
    return k;
}
           

/*方案二：
* by：ustczz*/
int next(int n, int k)
{
    char str[100] = {0};    //初值為零
    long long k2 = (long long)k * k;
    sprintf(str,"%lld",k2);  //整數轉化為字元串
    str[n]='\0';//截取n位
    k=atoi(str);//字元串轉化為整數
    return k;
}
           

/*方案三：
*by: 54whao
*by: lance*/
long long pow10(int e)
{
    long long p = 1;
    while (e--)
        p *= 10;
    return p;
}
int next(int n, int k)
{
    /*通過将變量聲明為“靜态存儲類型”，
    使其可以記錄函數上一次調用時的值
    進而避免pow10的重複調用
    */
    static int nflag = -1;
    static long long p;
    if (nflag != n)
    {
        nflag = n;
        p = pow10(n);
    }

    long long k2 = (long long)k * k;
    while (k2 >= p)
        k2 /= 10;
    k = k2;
    return k;
}