面試題六 C/C++面試秘笈 之約瑟夫問題的解答--程式員面試題

//結構體和函數聲明

typedef struct yuesefu

{

int data;

yuesefu *next;

}yuesefu;

//構造節點為N的單向循環連結清單

yuesefu * yuesefu_create(int n)

{

yuesefu * pRet = NULL;

if (0 != n) {

int n_index = 1;

yuesefu *pNode = NULL;

pNode = new yuesefu[n];

if (NULL == pNode) {//申請記憶體失敗，傳回NULL

return NULL;

}else{

memset(pNode, 0, n*sizeof(yuesefu));//初始化記憶體

}

pRet = pNode;

while (n_index < n) {//建構循環連結清單

pNode->data = n_index;//初始化連結清單的每個節點，從1到N

pNode->next = pNode + 1;

pNode = pNode->next;

n_index++;

}

pNode->data = n;

pNode->next = pRet;

}

return pRet;

}

int main(int argc, const char * argv[]) {

//約瑟夫問題的解答

yuesefu * pList =NULL;

yuesefu * pIter =NULL;

int n =12;

int m =3;

pList = yuesefu_create(n);

pIter = pList;

m %= n;

cout<<m<<endl;

while (pIter != pIter->next) {

int i=1;

for (;i < m-1; i++) {

pIter = pIter->next;

}

printf("p->next = %d\n",pIter->next->data);

pIter->next = pIter->next->next;

pIter = pIter->next;

}

printf("最後一個節點：%d\n",pIter->data);

delete [] pList;

return 0;

}

C++程式實作：

int n,m,s=0;

cout<<"N：";cin>>n;

cout<<"M：";cin>>m;

for(int i=2;i<=n;i++)

{

s=(s+m)%i;

}

cout<<"最後一個是："<<s+1;

如果有任何問題，歡迎下方留言談論，或者加入QQ群83459374交流