約瑟夫環(約瑟夫問題)是一個數學的應用問題:已知n個人(以編號1,2,3...n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數,數到m的那個人出列;他的下一個人又從1開始報數,數到m的那個人又出列;依此規律重復下去,直到圓桌周圍的人全部出列。
?
約瑟夫環運作如下:
1、一群人圍在一起坐成環狀(如:N)
2、從某個編號開始報數(如:S)
3、數到某個數(如:M)的時候,此人出列,下一個人重新報數
4、一直循環,直到所有人出列??,約瑟夫環結束
模擬過程,求出最后的人。
把數組看成一個環,從第s個元素開始按m-1間隔刪除元素,重復過程,直到元素全部去掉。
?
void Josephus(int a[],int n,int m,int s)
{int i,j;int k=n;for(i=0;i<n;i++)a[i]=i+1;//編號i=(s+n-1)%n;while(k){for(j=1;j<m;j++)i=(i+1)%k;//依次報數,頭尾相連printf("%d\n",a[i]);//出局for(j=i+1;j<k;j++)a[j-1]=a[j];//刪除本節點k--;}//模擬結束,最后輸出的就是留下的人
}
?
可以用帶頭單循環鏈表來求解:
也是一樣的,只是實現不同,給出核心代碼:
while(k){for(j=1;j<m;j++){pr=p;p=p->link;if(p==head)//頭結點跳過{pr=p;p=p->link;}}k--;//打印pr->link=p->link;//刪結點free(p);p=pr->link;//從下一個繼續}
雙向循環鏈表也可以解,和單鏈表類似,只是不需要保持前趨指針。
?
數學可解:
效率最高
int check_last_del(int n,int m)
{int i = 1;int ret = 0;for (i = 2; i<=n;i++)ret = (ret + m) %i;return ret+1;//因為ret是從0到n-1,最后別忘了加1。
}
?