C語言版約瑟夫問題算法實現

Posted on by

1、問題描述：

       有n個人圍坐一圈,現從第s個人開始報數,數到m的人出列,接著從出列的下一個人開始重新報數,數到m的人又出列.如此下去,直到所有人都出列為止.試設計確定他們出列次序序列的程序

2、算法步驟：

        1、確定存儲結構：n個人圍成一圈，故使用循環單鏈表來存儲序號

        2、算法實現：

該問題共n、m、s三個未知量，所以可以通過三個循環來實現，第一個循環用來確定最開始第一個報數的人的指針位置（單鏈表的頭節點指針指向第s個人），第二個循環用來控制輸出序號的次數（共n次），第三個循環用來數數（每一次循環使指針移動m次）

3、實現源代碼：

# include <stdio.h>
# include <malloc.h>
 
typedef struct Node
{
	int number;
	struct Node * pNext;
}NODE, *PNODE;
 
PNODE creat_list(int n);
 
int main (void)
{
	int n,m,s;
	printf("約瑟夫環問題：\n");
	printf("設有n（編號為“0 1 2 3 .....n-1 n”）個人圍坐一圈,現從第s個人開始報數，數到m的人出列,\n求最後的出列順序。\n");
	printf("請設置n, s, m ：\n");
	printf("n = ");
	scanf("%d", &n);
	printf("s = ");
	scanf("%d", &s);
	printf("m = ");
	scanf("%d", &m);                    //問題引導提示代碼段
 
 
	PNODE pHead = NULL;
	pHead = creat_list(n); 
    pHead->number = 1;                   //創建單鏈表
 
	PNODE p = pHead;                       //定義頭指針
	int i,j,k;                            //定義循環參數
	for(j = 1; j < s; j++)
		{
			p = p->pNext;
		}                                //第一個循環確定第一個報數的人在循環單鏈表中的位置  
 
	for(i = 1; i <= n; i++)              //外部循環代表遍歷到最後一個所需要的循環次數
	{
		for(k = 1; k < m; )              //內部循環代表遍歷出列的人
		{
			if(p -> pNext -> number != 0)
			{
				p = p -> pNext;
				k++;
			}
			else
			{
				p = p -> pNext;
			}
		}
		printf("%d  ",p -> number);
		p -> number = 0;
	    do
		{
		    p = p -> pNext;
		}while(p -> number == 0); 
	}
	printf("\n");
	
	return 0;
}
PNODE creat_list(int n)                        //單鏈表的創建
{
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
    PNODE pTail = pHead;
	int i;
    for(i = 2; i <= n; i++)
	{
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		pNew->number = i;
		pTail->pNext = pNew;
		pNew->pNext = pHead;
		pTail = pNew;
	}
	return pHead;
}

到此這篇關於C語言版約瑟夫問題算法實現的文章就介紹到這瞭,更多相關C語言約瑟夫問題內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：