约瑟夫环c++.将1到m这m个自然数由小到大围成一圈,并建立一个循环双向链表.以1为起点,先沿顺时针方向每数到第n个数划去一个数（n）,然后沿反时针方向每数到第k个数就划去一个数,这样一直

Question

约瑟夫环c++.
将1到m这m个自然数由小到大围成一圈,并建立一个循环双向链表.以1为起点,先沿顺时针方向每数到第n个数划去一个数（n）,然后沿反时针方向每数到第k个数就划去一个数,这样一直进行下去,直到最后一个数为止,问最后是哪个数?请编制算法,完成上述功能.

Answer 1

这个只有第n个数划去一个数（n）,反时针方向也是相同的道理.你可以参考下.
#include
#include

// 链表节点
typedef struct _RingNode
{
int pos; // 位置
struct _RingNode *next;
}RingNode, *RingNodePtr;

// 创建约瑟夫环,pHead:链表头指针,count:链表元素个数
void CreateRing(RingNodePtr pHead, int count)
{
RingNodePtr pCurr = NULL, pPrev = NULL;
int i = 1;
pPrev = pHead;
while(--count > 0)
{
pCurr = (RingNodePtr)malloc(sizeof(RingNode));
i++;
pCurr->pos = i;
pPrev->next = pCurr;
pPrev = pCurr;
}
pCurr->next = pHead; // 构成环状链表
}

void PrintRing(RingNodePtr pHead)
{
RingNodePtr pCurr;
printf("%d", pHead->pos);
pCurr = pHead->next;
while(pCurr != NULL)
{
if(pCurr->pos == 1)
break;
printf("\n%d", pCurr->pos);
pCurr = pCurr->next;
}
}

void KickFromRing(RingNodePtr pHead, int m)
{
RingNodePtr pCurr, pPrev;
int i = 1; // 计数
pCurr = pPrev = pHead;
while(pCurr != NULL)
{
if (i == m)
{
// 踢出环
printf("\n%d", pCurr->pos); // 显示出圈循序
pPrev->next = pCurr->next;
free(pCurr);
pCurr = pPrev->next;
i = 1;
}
pPrev = pCurr;
pCurr = pCurr->next;
if (pPrev == pCurr)
{
// 最后一个
printf("\n%d", pCurr->pos); // 显示出圈循序
free(pCurr);
break;
}
i++;
}
}

int main()
{
int m = 0, n = 0;
RingNodePtr pHead = NULL;
printf("---------------Josephus Ring---------------\n");
printf("N(person count) = ");
scanf("%d", &n);
printf("M(out number) = ");
scanf("%d", &m);
if(n next = NULL;
CreateRing(pHead, n);
#ifdef _DEBUG
PrintRing(pHead);
#endif

// 开始出圈
printf("\nKick Order: ");
KickFromRing(pHead, m);
printf("\n");
system("pause");
return 0;
}