约瑟夫环C++程序设计

#include
struct Node
{
int data;
struct Node *next;
};
int main()
{
int m,n;
cout<<"请输入m的值";
cin>>m;
cout<<"请输入n的值";
cin>>n;
Node *first,*last;
first=last=new Node;//生成第一个结点
first->data=1;
for(int i=2;i{
Node *p=new Node;
p->data=i;
last->next=p;last=p;//链接结点
}
last->next=first;
int number=n;
Node *pre=last;
while(number>1)
{
for(int j=1;jpre=pre->next;
Node *p=pre->next;
pre->next=p->next;
cout<data<<" ";
delete p;
number--;
}
cout<data<<" ";
delete pre;
}
































约瑟夫问题：
#include
struct Node
{
int data;
Node *pNext;
};

void main()
{
int n,k,m,i;
Node *p,*q,*head;
cout<<"输入n的值:";
cin>>n;
cout<<"输入起始报数人号码k的值:";
cin>>k;
cout<<"输入 数到m出列的m的值:";
cin>>m;
head=(Node*)new Node; //确定头结点
p=head;
for(i=1;i<=n-1;i++) //赋初值
{
p->data=i;
p->pNext=(Node*)new Node; //为下一个新建内存
p=p->pNext;
}
p->data=n; //最后一个单独处理
p->pNext=head; //指向头，形成循环链表
p=head;

while(p->data!=(p->pNext)->data) //p->data==(p->pNext)->data表示只剩下一个结点的
{
while(p->data !=k) //寻找编号为k的结点
p=p->pNext;
if(m==1)
{
for(i=1;i<=n;i++)
{
cout<data<<'\t' ;
p=p->pNext ;
}
cout<<'\n';
return;
}
else
for(i=1;i{p=p->pNext;} //找到报m-1的结点

q=p->pNext; //q为报m的结点
cout<data<<"\t"; //输出报m的结点的值
k=(q->pNext)->data; //k为下一个报数的起点
p->pNext=q->pNext; //删除报m的结点
}
cout<data<<'\n'; //输出最后一个结点的值
}











●一般解法：

#include
#include
#include
#include

/* 结构体和函数声明 */
typedef struct _node_t
{
int n_num;
struct _node_t *next;
} node_t;

node_t *node_t_create(int n);
node_t *node_t_get(node_t **pn, int m);

/* 功能函数实现 */

/*
* name: node_t_create
* params:
* n [in] 输入要构造的链表的个数
* return:
* 返回构造成功的环形单向链表指针
* notes:
* 构造节点数量为 n 的环形单向链表
*
*/
node_t * node_t_create(int n)
{
node_t *p_ret = NULL;

if (0 != n)
{
int n_idx = 1;
node_t *p_node = NULL;

/* 构造 n 个 node_t */
p_node = (node_t *) malloc(n * sizeof(node_t));
if (NULL == p_node)
return NU

LL;
else
memset(p_node, 0, n * sizeof(node_t));

/* 内存空间申请成功 */
p_ret = p_node;
for (; n_idx < n; n_idx++)
{
p_node->n_num = n_idx;
p_node->next = p_node + 1;
p_node = p_node->next;
}
p_node->n_num = n;
p_node->next = p_ret;
}

return p_ret;
}

/*
* name: main
* params:
* none
* return:
* int
* notes:
* main function
*/
int main()
{
int n, m;
node_t *p_list, *p_iter;

n = 20; m = 6;

/* 构造环形单向链表 */
p_list = node_t_create(n);

/* Josephus 循环取数 */
p_iter = p_list;
m %= n;
while (p_iter != p_iter->next)
{
int i = 1;

/* 取到第 m-1 个节点 */
for (; i < m - 1; i++)
{
p_iter = p_iter->next;
}

/* 输出第 m 个节点的值 */
printf("%d\n", p_iter->next->n_num);

/* 从链表中删除第 m 个节点 */
p_iter->next = p_iter->next->next;
p_iter = p_iter->next;
}
printf("%d\n", p_iter->n_num);

/* 释放申请的空间 */
free(p_list);
}●另一种比较巧妙的解法int f(int n, int m)
{
int i, r = 0;
for (i = 2; i <= n; i++)
r = (r + m) % i;
return r+1;
}