約瑟夫(josephus)環(huán)是這樣的：假設(shè)有n個(gè)小孩坐成一個(gè)環(huán)，假如從第一個(gè)小孩開(kāi)始數(shù)，如果數(shù)到m個(gè)小孩，則該小該離開(kāi)，問(wèn)最后留下的小孩是第幾個(gè)小孩？例如：總共有6個(gè)小孩，圍成一圈，從第一個(gè)小孩開(kāi)始，每次數(shù)2個(gè)小孩，則游戲情況如下：
????小孩序號(hào)：1，2，3，4，5，6
????離開(kāi)小孩序號(hào)：2，4，6，3，1
最后獲勝小孩序號(hào)：5
????這樣的問(wèn)題，我可以先考慮輸入的內(nèi)容有哪些？輸出內(nèi)容有哪些？
????????要求用戶(hù)輸入的內(nèi)容有：
?????????1、是小孩的個(gè)數(shù)，也就是n的值；
?????????2、是離開(kāi)小孩的間隔是多少？也就是m的值。
?????????3、所有小孩的序號(hào)要求存在數(shù)組或者鏈表中，所以需要定義一個(gè)指針，這里我們用數(shù)組來(lái)存放小孩的序號(hào)。
????????而要求輸出的內(nèi)容是：
?????????1、離開(kāi)小孩的序號(hào)；
?????????2、最后留下小孩的序號(hào)；
所以，根據(jù)上面分析輸入輸出參數(shù)，我們考慮離開(kāi)小孩的序號(hào)可以直接輸出，這樣可以使函數(shù)的復(fù)雜性。那么函數(shù)定義如下：
//輸入?yún)?shù)：
//Childs為指向一個(gè)整形指針，指向保存小孩數(shù)組的首地址；
//n為小孩的個(gè)數(shù)；
//m為數(shù)小孩的個(gè)數(shù)；
int?Josephus(int?*Child,int?n,int?m)
{
int?i=-1,j=0,k=1;
//開(kāi)始數(shù)小孩，只到留下一個(gè)小孩
while(1)
{
//數(shù)m個(gè)小孩
??for(j=0;j<m;)
??{
???i=(i+1)%n;????//取下標(biāo)加1的模，當(dāng)i的值在0到n-1之間循環(huán)
???if(Child[i]!=-1)?//小孩在環(huán)中則數(shù)數(shù)有效；
????j++;
???
??}
???if(k==n)????????????????????????//如果k==n則表示，此時(shí)數(shù)組中只留下一個(gè)小孩，
????break;??????????????????????????//序號(hào)為Child[i]中的值，跳出循環(huán);
???cout<<Child[i]<<",";??//輸出離開(kāi)小孩的序號(hào);
???Child[i]=-1;???????????????//離開(kāi)的小孩用-1作標(biāo)記
???k=k+1;
}
cout<<endl;
return(Child[i]);????//返回最獲勝小孩的序號(hào)
}
完整的程序，在VC6中調(diào)試通過(guò)。
//-----------------------------------------------------------
#include<iostream.h>
int?Josephus(int?*Child,int?n,int?m);
void?main()
{
int?*allChild,j,k,l;
cin>>j>>k;
??if((allChild=?new?int[j])!=NULL)
??{
????for(l=0;l<j;l++)
????{??
?????cout<<l+1<<",";
?????allChild[l]=l+1;
????}
????cout<<endl;
????cout<<Josephus(allChild,j,k);
??}
}
int?Josephus(int?*Child,int?n,int?m)
{
int?i=-1,j=0,k=1;
while(1)
{
??for(j=0;j<m;)
??{
???i=(i+1)%n;????
???if(Child[i]!=-1)?
????j++;
???
??}
???if(k==n)????????????????????????
????break;????????????????????????
???cout<<Child[i]<<",";??
???Child[i]=-1;?????????
???k=k+1;
}
cout<<endl;
return(Child[i]);????
}
posted on 2006-04-29 09:30
炙熱的太陽(yáng) 閱讀(563)
評(píng)論(0) 編輯 收藏 引用