|
約瑟夫環(huán)問題可以簡單的使用數(shù)組的方式實現(xiàn)，但是現(xiàn)在我使用循環(huán)鏈表的方法來實現(xiàn)，因為上午看到一道面試題規(guī)定使用循環(huán)鏈表解決約瑟夫環(huán)問題。
什么是約瑟夫環(huán)？
“約瑟夫環(huán)是一個數(shù)學(xué)的應(yīng)用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列?！保?a >百度百科中的解決辦法列出了很多，可以看到循環(huán)鏈表并不是最簡單的方法）
這道面試題考察了循環(huán)鏈表的“創(chuàng)建”，“遍歷”和“刪除”。
創(chuàng)建的循環(huán)鏈表的結(jié)構(gòu)圖：
解決約瑟夫環(huán)問題的過程
#include<iostream>
using namespace std;
struct ele {
int no;
struct ele *link;
} main() {
struct ele *h, *u, *p;
int n, m, i;
printf("Please input n&m:\n");
scanf("%d%d", &n, &m);/*輸入n和m*/
h = u = (struct ele *) malloc(sizeof(struct ele));/*形成首表元*/
h->no = 1;
for (i = 2; i <= n; i++)/*形成其余的n-1個表元*/
{
u->link = (struct ele *) malloc(sizeof(struct ele));
u = u->link;
u->no = i;/*第i個表元置編號i*/
}
u->link = h;/*末表元后繼首表元，形成環(huán)*/
puts("\nThe numbers of who will quit the cycle in turn are:");
while (n) {
for (i = 1; i < m; i++)
/*掠過m－1個表元*/
u = u->link;
p = u->link;/*p指向第m個表元*/
u->link = p->link;/*第m個表元從環(huán)中脫鉤*/
printf("%4d", p->no);
free(p);/*釋放第m個表元占用的空間*/
n--;
}
printf("\n\n Press any key to quit...\n");
getchar();
}
|
