Algorithm One Day One -- 約瑟夫環(丟手絹問題)
來源：程序員人生 發布時間：2015-02-02 08:20:39 閱讀次數：2878次
算法是編程的靈魂，是編程思想的精華――――Algorithm One Day One
/********************************************************************
created:2015年1月20日 23:06:46
author: Jackery
purpose: Joseph problem
*********************************************************************/
#include"stdafx.h"
#include<iostream>
using namespace std;
typedef struct _Node
{
int data;
struct _Node*next;
} node_t;
typedef struct _Linklist
{
node_t*phead;
node_t*ptail;
int len;
}Linklist;
static node_t*GetNode(int i )//新建并初始化節點
{
node_t*pNode;
pNode=new node_t;
if(!pNode)
{
cout <<"內存分配失敗" <<endl;
exit(⑴);
}
pNode->data=i;
pNode->next=NULL;
return pNode;
delete pNode;
}
void init_list(Linklist*plist)//用第1個節點初始化循環單鏈表
{
node_t*p;
p=GetNode(1);
//printf("TheNewNodeis:%d
",p->data);//****TEST****
plist->phead=p;
plist->ptail=p;
p->next=plist->phead;
plist->len=1;
}
//把其余數據添加到循環單鏈表中
static void Create_List(Linklist*plist,int n)
{
int i=0;
node_t*pNew;
for(i=2;i<=n;i++)
{
pNew=GetNode(i);
/********TEST********
cout <<"The New Node is:" <<pNew->data << endl;
********TEST********/
plist->ptail->next=pNew;
plist->ptail=pNew;
pNew->next=plist->phead;
plist->len++;
}
}
//輸出鏈表內容
// void Print_List(Linklist*plist)
// {
// node_t*pCur=plist->phead;
// do
// {
// cout << "The "<< pCur->data <<"person." <<endl;
// pCur=pCur->next;
// }while(pCur!=plist->phead);
// cout << "The length of the List "<< plist->len<< endl;;
// }
//Joseph function implement
void joseph(Linklist* plist,int m,int k)
{
node_t *pPre=plist->ptail;
node_t *pCur=plist->phead;
int i,j;
cout << "出隊列的順序順次為： "<< endl;
while(plist->len != 1)
{
i=0;
j=0;
while(j<k⑴)
{
pPre=pPre->next;
j++;
}
while(i< m ⑴)
{
pPre=pPre->next;
i++;
}
pCur=pPre->next;
int temp=pCur->data;
cout <<"第 " << temp << " 個人 "<< endl ;
pPre->next=pCur->next;
free(pCur);
plist->len--;
}
cout <<"第 " << pPre->data << " 個人" << endl; ;
cout << "The last one is:" << pPre->data<< endl;
}
int main(int argc, char * argv[])
{
int n=0;
cout <<"約瑟夫環長度為 : "<<endl;;
cin >> n;
int m=0;
cout << "每此數到m個時，這人出列"<<endl;
int k;
cin >> k;
cout << "從第k 個開始數" << endl;
cin >>m;
Linklist pList;
init_list(&pList);
Create_List(&pList,n);
// Print_List(&pList);
joseph(&pList,m,k);
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
