資訊專欄INFORMATION COLUMN
摘要：題目描述每年六一兒童節(jié)?？投紩蕚湟恍┬《Y物去看望孤兒院的小朋友今年亦是如此。作為?？偷馁Y深元老自然也準備了一些小游戲。其中有個游戲是這樣的首先讓小朋友們圍成一個大圈。然后他隨機指定一個數(shù)讓編號為的小朋友開始報數(shù)。
題目描述
每年六一兒童節(jié),?？投紩蕚湟恍┬《Y物去看望孤兒院的小朋友,今年亦是如此。HF作為?？偷馁Y深元老,自然也準備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0...m-1報數(shù)....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到?？兔F的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)
分析這是個約瑟夫環(huán)的問題，可以上網(wǎng)查查，很經(jīng)典的題目
簡單的實現(xiàn)就是使用環(huán)形單鏈表，一圈一圈的繞，到了號為m的節(jié)點就刪掉繼續(xù)繞，最后只剩一個節(jié)點時，就可以返回了。
通過遞推出下一次的叫號和編號的關(guān)系，來遞歸操作，詳細可以看約瑟夫環(huán)
代碼實現(xiàn) 解法一function node(x){
this.val = x;
this.next = null;
}
function LastRemaining_Solution(n, m)
{
if(n < 1 || m < 1)
return -1;
// 構(gòu)造環(huán)形單鏈表
var head;
var last;
for(var i = 0;i < n;i++) {
if(i === 0){
head = new node(i);
last = head;
}else{
var temp = new node(i);
last.next = temp;
last = temp;
}
}
last.next = head;
var count = 0;
while(last !== head) {
if(++count === m){
last.next = head.next;
count = 0;
}else{
last = last.next;
}
head = head.next;
}
return head.val;
}
解法二
function LastRemaining_Solution(n, m)
{
if(n==0)
return -1;
if(n==1)
return 0;
else
return (LastRemaining_Solution(n-1,m)+m)%n;
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/96352.html
摘要：歲的余宙華是少兒編程培訓(xùn)機構(gòu)阿兒法營的創(chuàng)辦者，也是這個培訓(xùn)機構(gòu)課程體系的主要研發(fā)者。如今少兒編程培訓(xùn)行業(yè)正越來越熱，最近幾年國內(nèi)的少兒編程培訓(xùn)機構(gòu)雨后春筍般一個個地冒出來。這時，余宙華意識到是他作為父親出手的時候了。 什么是計算機的靈魂？余宙華用孩子式的語氣問長桌旁坐著的小女孩。 小女孩認真地想了半天，有些靦腆地猶豫著給出了余宙華期待的答案：程序。 2018年7月，我在阿兒法營海淀人大...
摘要：然而和他的朋友并不想遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第個與第個位置，于是逃過了這場死亡游戲。問最后一個人的最開始的編號是幾先是筆者的樸素想法。這種想法雖然素樸，比較容易實現(xiàn)，但是時間復(fù)雜度為接著是數(shù)學方法。 ??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰(zhàn)爭——馬薩達戰(zhàn)爭，深為震撼，有興趣的同學可以移步：http://finance.ifeng.com/a/20...
摘要：然而和他的朋友并不想遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第個與第個位置，于是逃過了這場死亡游戲。問最后一個人的最開始的編號是幾先是筆者的樸素想法。這種想法雖然素樸，比較容易實現(xiàn)，但是時間復(fù)雜度為接著是數(shù)學方法。 ??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰(zhàn)爭——馬薩達戰(zhàn)爭，深為震撼，有興趣的同學可以移步：http://finance.ifeng.com/a/20...
閱讀 1152·2021-11-23 10:04
閱讀 2412·2021-11-22 15:29
閱讀 2806·2021-11-19 09:40
閱讀 729·2021-09-22 15:26
閱讀 2129·2019-08-29 16:27
閱讀 2498·2019-08-29 16:10
閱讀 1932·2019-08-29 15:43
閱讀 3285·2019-08-29 12:43
