<kbd id="afajh"><form id="afajh"></form></kbd>
<strong id="afajh"><dl id="afajh"></dl></strong>
    <del id="afajh"><form id="afajh"></form></del>
        1. <th id="afajh"><progress id="afajh"></progress></th>
          <b id="afajh"><abbr id="afajh"></abbr></b>
          <th id="afajh"><progress id="afajh"></progress></th>

          【騰訊面試題】猴子分桃

          共 958字,需瀏覽 2分鐘

           ·

          2021-11-09 14:36


          01
          故事起源
          有這么一天,森林里有一袋桃子??,來了5只猴子。


          第一只猴子把這堆桃子平分為五份,多了一個。這只猴子把多的一個扔掉了,拿走了一份。

          第二只猴子把剩下的桃子又平分成五份,又多了一個,它同樣把多的一個扔掉了,拿走了一份。

          第三、第四、第五只猴子也都是一樣的情況,問袋子里原來最少有多少個桃子?


          每只猴子的分桃情形

          02
          數(shù)學(xué)方法
          看到這個題目的第一反應(yīng)應(yīng)該是——這是一個數(shù)學(xué)問題。

          那么數(shù)學(xué)問題我們就用數(shù)學(xué)方法來解。下面牛牛就跟大家一起推演一下。


          假設(shè)原有桃子x個,最后剩下y個。

          第一只猴子扔了1個,又拿走了剩下的(x-1)個的1/5,相當(dāng)于拿走的桃子數(shù)量一共為:1/5(x-1)+1;

          剩下的桃子數(shù)量y = 4/5(x-1)

          第二只猴子來了,進行了同樣的操作,相當(dāng)于一共拿走的桃子數(shù)量為:1/5(4/5(x-1)-1)+1;

          剩下的桃子數(shù)量為:y = 4/5(4/5(x-1)-1)

          ......

          找到規(guī)律了嗎?

          每來一個猴子,剩下的桃子數(shù)量就從原數(shù)中減1,再乘4/5。這里有5只猴子,所以最后剩下的桃子個數(shù)為:


          整理一下,得到式子:


          因為x,y均為正整數(shù),所以(x+4)必須是5×5×5×5×5的倍數(shù)。

          題目中要求出最小的x,所以x+4=5^5,x=3125-4=3121。即開始最少有3121個桃子,最后剩余的桃子個數(shù)為1020個。



          03
          程序解法
          我們接下來看看在程序世界里又如何解決這個問題呢!

          根據(jù)題目我們只知道一個數(shù)字,那就是5個猴子

          所以桃子總共被分割了5次,每次分桃時候的桃子數(shù)量有5份多1個,至于每份是多少,不確定。

          這也是本題最難的地方,每份的桃子個數(shù)不確定,而且每次分完桃子后,桃子的數(shù)量也不確定。

          但是通過讀題,我們發(fā)現(xiàn),每個猴子都是進行同樣的操作,即將桃子數(shù)先-1,然后再拿走1/5數(shù)量的桃子,只剩下4/5的桃子,并且下一個猴子又將重復(fù)這一操作。

          這個操作總共重復(fù)5次,想到了什么?

          這不就是程序里的循環(huán)嘛!一共循環(huán)了5次。

          那我們先弄一個循環(huán)出來:


          i?=?1//?循環(huán)的條件變量,表示是第幾只猴子在操作while i <= 5//分桃操作......i++


          分桃具體怎么表示呢,通過上面的分析,就是將一個數(shù)-1,然后再乘以4/5,并且這個數(shù)要是正整數(shù)。

          既然是桃子個數(shù),那我們定義這個數(shù)為peach,分桃操作就表示為peach = (peach 整除 5) * 4,但有個條件,那就是每次分完會多出1個,所以得加上一個if條件:peach % 5 == 1。

          整體代碼如下:


          i = 1while i <= 5: #-1后才能分平均五份,不就代表著模5要等于1嘛     if peach % 5 == 1:#每次分完后,就剩下原數(shù)量的 - 1后的五分之四了,所以每次要將這個數(shù)更新一下         peach = peach // 5 * 4    i += 1


          現(xiàn)在的難點就只剩下peach該初始化為多少了。

          內(nèi)心os:要定義為啥數(shù)我也不知道,要是我知道的話那就不用求這個數(shù)了。。。

          不要急,既然不知道,那我們就按照程序的思想,一個一個往上試嘛,大不了從1開始,找到那個能滿足這個循環(huán)條件5次的數(shù)peach。

          所以peach又將是一個循環(huán)的過程。于是得到以下代碼:

          i = 1peach = 1while i <= 5: #-1后才能分平均五份,不就代表著模5要等于1嘛     if peach % 5 == 1:#每次分完后,就剩下原數(shù)量的 - 1后的五分之四了,所以每次要將這個數(shù)更新一下         peach = peach // 5 * 4        i += 1        continue    i += 1    peach += 1


          但仔細推敲,這個代碼是有問題的。

          因為這5次循環(huán)必須作為一個整體,連續(xù)滿足,即i從1變化到5的過程中,要一直滿足peach % 5 == 1,然后更新peach = peach // 5 * 4。

          當(dāng)5次中出現(xiàn)一次不滿足時,i又要從1開始變化到5,而這個代碼當(dāng)出現(xiàn)不滿足peach % 5 == 1時,peach會繼續(xù)+1向上嘗試,但是i卻沒有重置為1,這樣就不滿足題意了。

          所以關(guān)于i的變化,在一次循環(huán)中要么+1,要么重置為1,但是peach卻要從第一個數(shù)開始不斷向上嘗試,不重復(fù)。

          所以要有一個數(shù)來記錄已經(jīng)嘗試到的桃子個數(shù),我們定義為count,于是最終代碼如下:

          def sum_peach():      i = 1      peach = 1      count = 1      while i <= 5:             #-1后才能分平均五份,不就代表著模5要等于1嘛             if peach % 5 == 1:            #每次分完后,就剩下原數(shù)量的 - 1后的五分之四了,所以每次要將這個數(shù)更新一下                   peach = peach // 5 * 4                  i += 1            else:                  i = 1                  count += 1                  peach = count      return count


          最終求得count為3121,所以原來海灘上最少有3121個桃子。

          這個解題思路其實是用到了程序的暴力求解,根據(jù)題目的限定條件,一個數(shù)一個數(shù)的去嘗試判斷,哪個數(shù)能符合題意就代表數(shù)值找到了。

          04
          桃桃復(fù)盤
          之前我們就提到了,算法大多都是通過暴力法、貪心算法以及動態(tài)規(guī)劃能夠解決的,很多小伙伴花了大把時間研究后兩者,但其實暴力法也是非常重要的,有些算法還只能通過這樣簡單粗暴的方式解決。

          所謂大道至簡,只要我們做足了準備,要真在面試時遇到了這樣只能用暴力法解決的問題,不要懷疑,相信自己的判斷!
          ---------------- END---------------
          最后,歡迎加入帥地的知識星球,帥地會在星球知無不言,無論是 學(xué)習(xí)規(guī)劃,offer 選擇,簡歷修改,還是學(xué)習(xí)路線,帥地都會在 48 小時以內(nèi)答復(fù)你的問題,并且根據(jù)你自身的情況,為你量身定制學(xué)習(xí)路線。
          同時超全學(xué)習(xí)攻略也已經(jīng)更新好了,小白跟著帥地的學(xué)習(xí)攻略學(xué)就行了
          各類學(xué)習(xí)資料,項目資料都會提供給大家。
          而且你有任何的疑惑,帥地都會答復(fù)你,并且星球里也有一群和你相同年齡的小伙伴在奮斗,都是未來的卷王
          帥地會在星球會提供如下服務(wù)
          1、【一對一咨詢服務(wù)】48 小時以內(nèi)超詳細回答你的任何問題,包括寫作等等,這是知識星球最重要的功能。最近一周就回答了十幾個 offer 選擇,校招等學(xué)習(xí)路線問題。
          2、【學(xué)習(xí)攻略】校招這方面比較有經(jīng)驗,帥地會提供完整的學(xué)習(xí)攻略,并且隨著時間的積累,這份攻略會越來越完善哦。
          3、簡歷修改,項目等學(xué)習(xí)資源,offer 收割機嘉賓分享等等。
          目前星球是專注于校招,在校生學(xué)習(xí)指導(dǎo)這塊,一定可以讓你少走彎路,已經(jīng)有 670+ 位小伙伴加入,這里還有一些 20 元的優(yōu)惠卷,如果你信的過帥地,那么歡迎你的加入。

          點擊閱讀原文可以了解詳情
          瀏覽 72
          點贊
          評論
          收藏
          分享

          手機掃一掃分享

          分享
          舉報
          評論
          圖片
          表情
          推薦
          點贊
          評論
          收藏
          分享

          手機掃一掃分享

          分享
          舉報
          <kbd id="afajh"><form id="afajh"></form></kbd>
          <strong id="afajh"><dl id="afajh"></dl></strong>
            <del id="afajh"><form id="afajh"></form></del>
                1. <th id="afajh"><progress id="afajh"></progress></th>
                  <b id="afajh"><abbr id="afajh"></abbr></b>
                  <th id="afajh"><progress id="afajh"></progress></th>
                  青青草原夫妇在线观看视频网站 | 69精品无码成人久久久久久 | 亚洲一区三区 | 成人午夜福利日韩高清亚洲 | 久久久精品视频三级 |