閑話系列：每日一題，禿頭有我，Hello！！！！！,我是IF‘Maxue，歡迎大佬們來參觀我寫的藍(lán)橋杯系列，我好久沒有更新博客了，因?yàn)閡p豬我寒假用自己的勞動(dòng)換了臺(tái)新電腦，沒用父母的錢哦！！！，雖然進(jìn)度慢了，但是值得，藍(lán)橋杯快開始了，所以我也開始努力起來了。同時(shí)，我也歡迎各位大佬互三，看到我會(huì)及時(shí)回復(fù)的！！！

放一張阿刃在這，除大家的霉運(yùn)

題目解析

1. 搞懂定義

• 對(duì)于一個(gè)正整數(shù)，每一次替換為它每個(gè)位置上的平方和。

• 舉例：

• 

  • 19這個(gè)數(shù)字經(jīng)過處理可以變成1，2這個(gè)數(shù)字變成了無限循環(huán)，
  • 所以19是快樂數(shù)字，2就不是
  • 判斷最后的那一個(gè)環(huán)是否都是一

算法原理解析

我們仔細(xì)觀察，在最后的結(jié)尾，

• 為快樂數(shù)的數(shù)字最后的結(jié)尾都是1，我們可以理解成一個(gè)園環(huán)。

• 非快樂數(shù)的數(shù)字最后結(jié)尾我們知道，肯定不是1，但是因?yàn)轼澇苍砦覀儠?huì)得出結(jié)論肯定成環(huán)。（不知道也沒關(guān)系，下面有詳細(xì)解析）

• 原理如圖所示，上面的是快樂數(shù)，下面的數(shù)是非快樂數(shù)：
  

• 判斷最后的環(huán)的數(shù)字是否都是1.

具體解法

• 解法 快慢雙指針。
  • 定義快慢指針 > - 慢指針每次后移一步，快指針每次后移兩步 讓慢指針一次進(jìn)行一次操作，讓快指針進(jìn)行2次快樂數(shù)操作
    - 判斷相遇的值
    - 直接判斷相遇的值

• 鴿巢原理詳解：
  • 我們可是讓慢指針執(zhí)行一次，然后對(duì)于快指針每一次后移進(jìn)行執(zhí)行快樂數(shù)的兩次操作

    • 為什么這些數(shù)字不會(huì)一直鋪開，為什么一定要成環(huán)？
      證明原理：鴿巢原理

    • 如果有n個(gè)巢，n+1個(gè)鴿子可以推論

    • 

      證明這道題：

    • 一個(gè)數(shù)字2.1 * 10^9
      

      • 我們已經(jīng)知道n個(gè)巢穴，n+1個(gè)鴿子，如果鴿子全部歸位，至少有一個(gè)巢穴里面的鴿子大于1.

      • 我們拿出9999999999這個(gè)數(shù)字，進(jìn)行快樂數(shù)操作，

      • 范圍將會(huì)鎖定在【1，810（9^2 * 10）】（這個(gè)就是巢穴），我們進(jìn)行811次快樂數(shù)字操作（這個(gè)就是鴿子）

代碼實(shí)現(xiàn)

int HappyC(int n)//快樂數(shù)的操作{   int x=0;int sum=0;while(n){x=n%10;sum=x*x+sum;n=n/10;}return sum;}bool isHappy(int n) {//定義兩個(gè)快慢指針，用數(shù)字代替int fast=0;int slow=0;slow=n,fast=n;while(1){fast=HappyC(fast);fast=HappyC(fast);slow=HappyC(slow);if(fast==slow){if(fast==1){return true;}else{return false;}}}}

運(yùn)行結(jié)果展示：