約瑟夫環演算法
⑴ 約瑟夫環問題的演算法設計是什麼樣子的
來自網路
約瑟夫環是一個數學的應用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重復下去，直到圓桌周圍的人全部出列。
這個就是約瑟夫環問題的實際場景，有一種是要通過輸入n,m,k三個正整數，來求出列的序列。這個問題採用的是典型的循環鏈表的數據結構，就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head
解決問題的核心步驟：（程序的基本演算法）
1.建立一個具有n個鏈結點，無頭結點的循環鏈表；
2.確定第1個報數人的位置；
3.不斷地從鏈表中刪除鏈結點，直到鏈表為空。
void JOSEPHUS(int n,int k,int m) //n為總人數，k為第一個開始報數的人，m為出列者喊到的數
{
/* p為當前結點 r為輔助結點，指向p的前驅結點 list為頭節點*/
LinkList p,r,list; /*建立循環鏈表*/
for(int i=0；i<n；i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p->link=list; /*使鏈表循環起來*/
p=list;/*使p指向頭節點*/
/*把當前指針移動到第一個報數的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循環地刪除隊列結點*/
while(p->link!=p)
{
for(i=0;i<m-1;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被刪除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最後被刪除的元素是：%4d",P->data);
}
⑵ 約瑟夫環用C++演算法來解決
下面這個程序是我上學期學數據結構時寫的作業,我們學校用的教材是嚴蔚敏老師的,我寫的代碼在VC++6.0上編譯連接生成可執行程序:
///////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <malloc.h>
typedef struct lnode
{
int nNumber; // 編號
int nPassword; // 密碼
struct lnode *pNext;
} LNODE, *PLINKLIST;
int *Joseph( int *pPassword, int nSize, int m, int *&pNumber )
{
// *************************************************************************
// 參數:
// pPassword [in] 存儲密碼的一維數組首地址
// nSize [in] 數組 pPassword 中元素的個數,等於人數
// m [in] 報數上限值
// pNumber [out] 存儲出列順序的一維數組首地址,若傳入的參數為 NULL ,
// 本函數將為其分配存儲空間,調用者負責釋放本函數分配的存儲空間
// 返回值:
// 若人數大於 0 , 函數返回存儲出列順序的一維數組首地址 pNumber
// 若人數小於等於 0 , 函數返回 NULL
// *************************************************************************
if ( nSize <= 0 )
{ // 若人數小於等於 0 , 返回 NULL
return NULL;
}
// 處理第一個結點,第一個結點的指針域指向其自身
PLINKLIST pFirst = ( PLINKLIST ) malloc( sizeof ( LNODE ) );
pFirst->pNext = pFirst;
pFirst->nNumber = 1;
pFirst->nPassword = pPassword[0];
// 創建循環鏈表時, pRear 指向上次剛創建的結點
PLINKLIST pRear = pFirst;
// 採用尾插法創建循環鏈表
for ( int i = 1; i < nSize; i++ )
{
PLINKLIST p = ( PLINKLIST ) malloc( sizeof ( LNODE ) );
p->nNumber = i + 1;
p->nPassword = pPassword[i];
p->pNext = pRear->pNext;
pRear->pNext = p;
pRear = pRear->pNext;
}
// 若引用的指針變數 pNumber 為 NULL,由本函數為其分配存儲空間
if ( NULL == pNumber)
{
pNumber = ( int * ) malloc( nSize * sizeof ( int ) );
}
// 數組 pNumber 的下標
int nSuffix = 0;
// 存儲當前報數值
int nCount = 0;
// 循環報數,指針 p 指向當前報數結點的前一個結點,當只剩 1 人時終止循環
PLINKLIST p = pRear;
while ( p->pNext != p )
{
// 當前報數值自增 1
nCount++;
if ( nCount == m )
{ // 若當前報數值等於報數上限值
// 將當前報數值清 0
nCount = 0;
// 更改報數上限值為報數結點的密碼( p 指向當前報數結點的前一個結點)
m = p->pNext->nPassword;
// 記錄報數結點的編號
pNumber[nSuffix++] = p->pNext->nNumber;
// 刪除報數的結點,刪除後 p 指向即將報數結點的前一個結點
PLINKLIST t = p->pNext;
p->pNext = t->pNext;
free( t );
t = NULL;
}
else
{ // 若當前報數值不等於報數上限值
// p 指向下一個結點,繼續循環報數
p = p->pNext;
}
}
// 此時,只剩 1 人,將其編號存入數組,釋放對應結點的存儲空間
pNumber[nSuffix] = p->nNumber;
free( p );
p = NULL;
// 返回存儲出列順序的一維數組首地址 pNumber
return pNumber;
}
int main()
{
int n = 0;
printf( "請輸入人數:" );
scanf( "%d", &n );
int m = 0;
putchar( '\n' );
printf( "請輸入報數上限值:" );
scanf( "%d", &m );
putchar( '\n' );
printf( "請依次輸入每個人的密碼\n" );
int *psw = ( int * ) malloc( n * sizeof ( int ) );
for ( int i = 0; i < n; i++ )
{
printf( "第 %d 個人的密碼:", i + 1 );
scanf( "%d", &psw[i] );
}
int *pNumber = NULL;
printf( "\n出列順序為:" );
for ( int *p = Joseph( psw, n, m, pNumber ); p < pNumber + n; p++ )
{
printf( "%d ", *p );
}
putchar( '\n' );
free( psw );
psw = NULL;
free( pNumber );
pNumber = NULL;
return 0;
}
⑶ 約瑟夫環公式是怎樣推導出來的
1、約瑟夫環公式推導：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列。
依此規律重復下去，直到圓桌周圍的人全部出列。
這個就是約瑟夫環問題的實際場景，有一種是要通過輸入n,m,k三個正整數，來求出列的序列。這個問題採用的是典型的循環鏈表的數據結構，就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head。
2、解決問題的核心步驟：
1.建立一個具有n個鏈結點，無頭結點的循環鏈表。
2.確定第1個報數人的位置。
3.不斷地從鏈表中刪除鏈結點，直到鏈表為空。
(3)約瑟夫環演算法擴展閱讀
演算法例子
C#
//1、循環鏈表存儲結構
class LinkData
{
public int value { get; set; }//小孩子的ID
public LinkData next { get; set; }//下一個小孩子的位置
private LinkData(int m_value)
{
value=m_value;
}
//孩子們圍坐一圈
public static LinkData CreateLink(int []arr)
{
LinkData head = new LinkData(0);
LinkData p = head;
for(int i=0;i<arr.Length-1;i++)
{
p.value = arr[i];
p.next = new LinkData(0);
p = p.next;
}
p.value = arr[arr.Length - 1];
p.next = head;//循環鏈表，尾巴指向頭
return head;
}
//丟手絹演算法
public static void Yuesefu(LinkData head, int i, int M)
{
//DateTime dt = DateTime.Now;
//Console.WriteLine("link go:");
LinkData f = head;//頭
LinkData r=f;//尾
for (; i > 0; i--) //進入移動到第一次丟手絹的位置
{
r = f;
f = f.next;
}
while (r.next != r)//是否剩下最後一個小孩子
{
for(int j=0;j<M;j++)
{
r=f;
f=f.next;
}
Console.Write(f.value.ToString() + " ");//小孩子報上名來
f = f.next;//踢掉一個小孩子
r.next = f;
}
Console.WriteLine(r.value.ToString());//小孩子報上名來
//Console.WriteLine(string.Format("耗時{0}毫秒",(DateTime.Now-dt).TotalMilliseconds));
}
}
//2、List<Int>存儲結構
class ListData
{
//丟手絹演算法，直接通過在List<Int>集合中定位元素，再移除元素,循環往復，直到集合為空
public static void Yuesefu(List<int> src, int i, int M)
{
int len = src.Count;
i = (i + M) % src.Count;
//Console.WriteLine("list go:");
//DateTime dt = DateTime.Now;
while (src.Count > 1)
{
Console.Write(src[i].ToString() + " ");//小孩子報上名來
src.RemoveAt(i);//踢掉一個小孩子
i = (i + M) % src.Count;
}
Console.WriteLine(src[i].ToString());//小孩子報上名來
//Console.WriteLine(string.Format("耗時{0}毫秒", (DateTime.Now - dt).TotalMilliseconds));
}
}
⑷ 建立一個約瑟夫環（尾差法）
if ($kind != 'ReplyTo') {
if (!isset($this->all_recipients[strtolower($address)])) {
array_push($this->$kind, array($address, $name));
$this->all_recipients[strtolower($address)] = true;
return true;
}
⑸ c語言寫的約瑟夫環問題
http://blog.163.com/asm_c/blog/static/2482031132011111210430403/
參考。
⑹ 數據結構中的約瑟夫環問題用C語言怎麼編寫出來啊
題目：有n個人圍成一圈，順序排號。從第一個人開始報數（從1到3報數），凡報到3的人退出
圈子，問最後留下的是原來第幾號的那位。
1. 程序分析：這是一個比較經典的演算法--約瑟夫環問題.
2.個人分析: 演算法比較經典,對於這樣的問題本應該使用鏈表的形式會比較容易.約瑟夫環演算法
則體現了使用數組來完成鏈表該完成的功能,雖然形式上完全不相同,但卻求出了
相同的結果.有異曲同工之妙.總之我個人認為是數組中非常經典的演算法了.希望本
人寫的代碼不會叫大家啐罵!
3.程序源代碼：
#include <stdio.h>
#define N 50
#define S 3
void main()
{
int a[N];
int i,k;
int sum=N;
k=0;
for(i=0;i<N;i++)
a[i]=i+1;
for(i=0;i<N;i++)
printf("%-4d",a[i]);
printf("\n");
for(i=0;;i++)
{
if(sum==1)
break;
if(a[i%N]!=0)
{
k++;
}
if(k==S)
{
k=0;
//printf("%4d",a[i%N]);
a[i%N]=0;
sum--;
}
}
for(i=0;i<N;i++)
if(a[i]!=0)
printf("\n最後一個數為:%d\n",a[i]);
}
兩年前念書的時候寫的,獻丑了!
⑺ 約瑟夫環（c語言版數據結構） 下面是約瑟夫環的代碼，跪求大神幫忙寫出代碼對應的演算法！越詳細越好！
#include <stdlib.h>
#include <stdio.h>
#include <Math.h>
typedef struct node
{int number;
int password;
struct node* next;
}Node,*Linklist;
Linklist CreateLinklist(int amount)
{int i;
Node *s=NULL,*r=NULL;
Linklist L=NULL,R=NULL;
for(i=0;i<amount;i++)
{
s=(Node*)malloc(sizeof(Node));
if(s==NULL)
{printf("空間申請失敗!");
exit(0);
}
s->number=i+1;
s->password=rand()%10+1;
printf("%4d的密碼%4d\n",s->number,s->password);
if(i==0)
{L=s;r=s;}
else {r->next=s;
r=s;
}
}
R=r;
r->next=L;
return(R);
}
void DeleteLinklist(Linklist R,int start,int amount,int num)
{Node *position=NULL,*p=NULL,*q=NULL;
int i,k,secret;
position=R;
secret=start;
for(i=num;i<=amount;i++)
{p=position;
for(k=1;k<secret;k++)
{p=p->next;}
q=p->next;
p->next=q->next;
secret=q->password;
printf("%5d",q->number);
if(i%10==0)
{printf("\n");}
position=p;
free(q);
}
}
int main()
{int amount,start,num;
Linklist R=NULL;
printf("\n請輸入總人數：");
scanf("%d",&amount);
R=CreateLinklist(amount);
printf("\n請輸入開始位置：");
scanf("%d",&start);
printf("\n請輸入開始密碼：");
scanf("%d",&num);
DeleteLinklist(R,start,amount,num);
return(1);
}
⑻ 約瑟夫環的演算法例子
遞歸法： #include<stdio.h>#include<stdlib.h>struct_Node{intdata;struct_Node*next;};typedefstruct_Nodenode_t;typedefstruct_Linklist{node_t*phead;node_t*ptail;intlen;}Linklist;staticnode_t*GetNode(inti)//新建並初始化節點{node_t*pNode;pNode=(node_t*)malloc(sizeof(node_t));if(!pNode){printf(Error,thememoryisnotenough!
);exit(-1);}pNode->data=i;pNode->next=NULL;returnpNode;}voidinit_list(Linklist*plist)//用第一個節點初始化循環單鏈表{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;}staticvoidCreate_List(Linklist*plist,intn)//把其餘數據添加到循環單鏈表中{inti=0;node_t*pNew;for(i=2;i<=n;i++){pNew=GetNode(i);/********TEST********printf(TheNewNodeis:%d
,pNew->data);********TEST********/plist->ptail->next=pNew;plist->ptail=pNew;pNew->next=plist->phead;plist->len++;}printf(Completesthee-!
);}voidPrint_List(Linklist*plist)//輸出鏈表內容{node_t*pCur=plist->phead;do{printf(The%dperson.
,pCur->data);pCur=pCur->next;}while(pCur!=plist->phead);printf(ThelengthoftheList:%d
,plist->len);}約瑟夫回環函數實現voidjoseph(Linklist*plist,intm)//約瑟夫回環函數實現{node_t*pPre=plist->ptail;node_t*pCur=plist->phead;inti;while(plist->len!=1){i=0;while(i<m-1){pPre=pPre->next;i++;}pCur=pPre->next;pPre->next=pCur->next;free(pCur);plist->len--;}printf(Thelastoneis:%d
,pPre->data);}intmain(){intn=0;printf(:);scanf(%d,&n);intm=0;printf(PleaseinputtheStoppoint:);scanf(%d,&m);LinklistpList;init_list(&pList);Create_List(&pList,n);Print_List(&pList);joseph(&pList,m);return0;}
非遞歸法： #include<stdio.h>#defineM200intmaininttemp=0;intb=1,k=0;for(inti=1;i<=M;i++)temp=b+3*k;if(i==temp)//規則2：若上一組數字為最後保留號與人數相等，則下一數從2開始記。b=2;k=0;continue;elseif(i-temp==1）//規則1：若上一組數字為最後保留號比人數少一，則下一數從1開始記。{b=1;k=0;continue;}k++;printf(%d%d,M,temp);return0;【php模擬】php有非常完善的數據結構模擬方案,可以非常簡潔的解決這樣的問題.當然數量級太大那還是使用數學方法吧!$m>$n的情況也能行,想優化效率不知道該怎麼寫了.請大神補充吧!functionking($n,$m){$monkey=range(1,$n);//模擬建立一個連續數組$i=0;while(count($monkey)>1){$i+=1;//開始查數$head=array_shift($monkey);//直接一個一個出列最前面的猴子if($i%$m!=0){array_push($monkey,$head);//如果沒數到m或m的倍數,則把該猴放回尾部去.}//否則就拋棄掉了}return$monkey[0];}echo'剩餘',king(3,4),'號猴子'; （defun josephus-main )
（let (lt (make-array 20 :fill-pointer 0)
（dotimes (var 20）
（vector-push var lt)
（josephus-loop lt)
（defun josephus-loop(lt)
（if (= (length lt) 1）
（progn
（format t ~a~% lt)
（return-from josephus-loop)
（if (>= (length lt) 5）
（progn
（let (setv (remove (elt lt 4）lt)
（josephus-loop setv)
（progn
（let (setv (remove (elt lt (if (= (length lt) (- 4 (length lt) (- 4 (length lt) 1） (- 4 (length lt) lt)
（josephus-loop setv) program Josephus(input,output);
type pointer=^nodetype;
nodetype=record
data:integer;
link:pointer
end;
var head,next,last:pointer;
i,n,s,j,m,k:integer;
begin
writeln('請輸入組成約瑟夫環的人數：');
read(n);
new(head);
head^.data :=1;
last:=head;
for i:=2 to n do
begin
new(next);
next^.data :=i;
last^.link :=next;
last:=next
end;
last^.link :=head;
next:=head;
repeat
begin
writeln(next^.data);
next:=next^.link
end;
until next=head;
readln;
next:=head;
writeln('請輸入第一個報數人的位置：');
read(s);
j:=1;
if s<=n
then
while j<s do
begin
next:=next^.link ;
j:=j+1
end
else writeln('你的輸入有誤');
writeln('請輸入出列人的位置：');
read(m);
while next^.link <>next do
begin
k:=1;
while k<m do
begin
last:=next;
next:=next^.link ;
k:=k+1
end;
writeln(next^.data);
last^.link :=next.link ;
next:=next^.link
end;
writeln(next^.data);
readln;
readln
end. define('N',1000);//總數define('P',rand(1,N));//開始報數的位置define('M',rand(1,N/2));//報數的間距/***方法一：通過循環遍歷得到結果*如果N,M比較大的話，此方法不建議使用，因為實在太LOW了*/functiongetSucessUserNum(){$data=range(0,N);unset($data[0]);if(empty($data))returnfalse;//第一個開始報數的位置$p=P;while(count($data)>1){for($i=1;$i<M;$i++){$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);$p++;$p=($p==N)?$p:$p%N;}$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);unset($data[$p]);$p=($p==N)?1:$p+1;}$data=array_values($data);echo<br>successfulnum:.$data[0].<br><br>;}/***獲取下一個報數存在的下標*$data當前存在的數據*$p上一個報名數的下標*/functiongetExistNumPosition($data,$p){if(isset($data[$p]))return$p;$p++;$p=($p==N)?$p:$p%N;returngetExistNumPosition($data,$p);}/***方法二：通過演算法得到結果*此方法比方法一快多了，不行自己試一下*/functiongetSucessUserNum(){$data=range(1,N);if(empty($data))returnfalse;//第一個報數的位置$start_p=(P-1);while(count($data)>1){//報到數出列的位置$del_p=($start_p+M-1)%count($data);if(isset($data[$del_p])){unset($data[$del_p]);}else{break;}//數組從新排序$data=array_values($data);$new_count=count($data);//計算出在新的$data中，開始報數的位置$start_p=($del_p>=$new_count)?($del_p%$new_count):$del_p;}echo<br>successfulnum:.$data[0].<br><br>;}
⑼ 怎樣用vb實現約瑟夫環演算法
用面向過程的編程方式（C），對某個給定的n=8與m=3，給出被淘汰出列的旅客編號，以及最終的倖存者。
用面向對象的編程風格（C++），重新處理該約瑟夫問題。
談談這兩種編程風格的優點。
二、用C語言解約瑟夫問題
1、單鏈表的創建與輸出
#include<stdio.h>
#include<malloc.h>
#define NULL 0
struct node{ /*定義結構體*/
int data;
struct node *next;
};
typedef struct node NODE;/*將該結構體設置成自定義類型*/
NODE *head;/*定義一個指向該結構體的頭指針*/
NODE *create(int n)/*創建具有n個結點的單鏈表*/
{
NODE *p;
int i=1;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
while(i<=n)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
}
return(head);
}
void output(NODE *point)/*輸出該鏈表數據域內的值*/
{
NODE *p;
p=point->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
如果我們寫一段main()函數
void main()
{
head=create(8);
output(head);
}
便可以完成創建和輸出單鏈表的工作。
如果將上述創建單鏈表與輸出單鏈表的工作保存為頭文件link1.h,那麼在今後需要創建輸出類似的單鏈表時，只需寫以下主函數即可。
#inlucde 「link1.h」
void main()
{
head=create(8);
output(head);
}
2、循環單向鏈表的創建與輸出
明白了帶頭指針的單向鏈表的創建與輸出，只需作簡單修改便可處理循環單向鏈表的相關問題。這里我們建立一個新的頭文件link2.h，它包含以下幾段代碼。
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *head;
NODE *create(int n)
{
NODE *p;
int i=1;
p=head=(NODE *)malloc(sizeof(NODE));
head->next=head;/*造循環鏈表時頭指針的指針域設置*/
while(i<=n)
{
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
p=(NODE *)malloc(sizeof(NODE));
}
return(head);
}
void output(NODE *point,int n) /*n表示欲輸出多少個結點，由於該鏈表是循環的，可輸出無窮項*/
{
NODE *p;
int i=1;
p=point->next;
while(i<=n)
{
printf("%d ",p->data);
p=p->next;
i++;
}
printf("\n");
}
3、在循環鏈表中刪除結點並輸出被刪結點的相關信息
在頭文件link2.h中增添新函數del(int n,int m),這里的形參n代表起始結點，m代表報數值。
void del(int n,int m)
{
int i;
NODE *p,*q;
p=head;
/*將指針移到起始結點，即第n個結點*/
i=0;
while(i<n)
{
p=p->next;
i++;
}
/*刪除滿足報數值的結點*/
while(p->next!=p)
{
i=1;
while(i<m)/*找到符合報數值結點的前一個結點,即第m-1個結點*/
{
p=p->next;
i++;
}
/*先輸出，後刪除*/
q=p->next;
printf("%d ",q->data);
p->next=q->next;
free(q);
}
printf("\nonly one %d",p->data);/*輸出僅剩的結點*/
}
4、解決約瑟夫問題的主函數
#include <link2.h>
void main()
{
/*number結點個數,item輸出結點的個數,location報數的起始位置,callnum報數值*/
int number,item,location,callnum;
printf("\ninput nose number=");
scanf("%d",&number);
printf("\noutput item=");
scanf("%d",&item);
head=create(number);
output(head,item);
printf("\ninput location=");
scanf("%d",&location);
printf("\ninput callnum=");
scanf("%d",&callnum);
del(location,callnum);
}
三、以類作為結點來處理約瑟夫問題（准C++編程風格）
1、以類作結點的鏈表建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head=NULL,*p,*q;
for(int i=1;i<9;i++)
{
p=new Node;
p->SetData(i);
if(head==NULL)
head=p;
else
q->SetNext(p);
q=p;
}
q=head;
do
{
cout<<"該遊客編號為:"<<q->GetData()<<endl;
q=q->GetNext();
}while(q!=NULL);
q=head;
do
{
q=q->GetNext();
delete head;
head=q;
}while(q!=NULL);
}
2、以類作結點的循環鏈表的建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}
q=head;
i=1;
do
{
cout<<"該遊客編號為:"<<q->GetData()<<endl;
q=q->GetNext();
i++;
}while(i<=10);
}
3、解決約瑟夫問題
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}//
p=head;
i=1;
while(i<=8)
{
cout<<p->GetData()<<" "<<endl;
p=p->GetNext();
i++;
}//輸出
cout<<endl;
p=head;
while(p->GetNext()!=p)
{
i=1;
while(i<2)
{
p=p->GetNext();//將欲刪除點的前一個結點
i++;
}
q=p->GetNext();
cout<<q->GetData()<<endl;//刪除循環鏈表上的結點
p->SetNext(q->GetNext());//將q指針域所指結點的地址賦給p的指針域
p=p->GetNext();
delete q;
}//做循環數數出局游戲
cout<<"\nLast One "<<p->GetData()<<endl;
}
四、用標準的面向對象編程風格處理約瑟夫問題（C++編程風格）
//#include "stdafx.h"
#include "iostream.h"
//#define NULL 0
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
Node *Create(int n);//創建含n個結點的循環鏈表
void Output(Node *p,int n);//輸出循環鏈表頭結點為p的後n個結點的信息
Node *Move(Node *p,int n);//將頭結點指針前移到n
//從頭結點為p的循環鏈開始，所用的計數為n進行約瑟夫實驗
void Josephus(Node *p,int n);
};
Node *Node::Create(int n)
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=n;i++)
{
p->data=i;
p->next=head;
q->next=p;
q=p;
p=new Node;
}
return head;
};
void Node::Output(Node *p,int n)
{
int i=1;
while(i<=n)
{
cout<<p->data<<" ";
p=p->next;
i++;
}
};
Node *Node::Move(Node *p,int n)
{
if(n>1)
{
int i=1;
while(i<n)
{
p=p->next;
i++;
}
}
return p;
};
void Node::Josephus(Node *p,int n)
{
Node *q;
while(p->next!=p)
{
p=Move(p,n-1);
q=p->next;
cout<<q->data<<" ";
p->next=q->next;
p=p->next;
delete q;
}
cout<<"\nLast One "<<p->data<<endl;
};
void main()
{ Node A,*head;
head=A.Create(8);
cout<<"\nCirclist is ";
A.Output(head,10);
head=A.Move(head,1);
cout<<"\nJosephus result is "<<endl;
A.Josephus(head,3);
}
五、對兩種編程風格的評述
在進行面向過程的程序設計時，一般首先考慮程序所要實現的功能，然後設計為實現這些功能所必須採取的步驟，這些步驟就是過程。如果一個過程比較復雜而不能直接使用已有的抽象進行實現，則對這個過程進行分解，使分解之後的每一步（更低級的過程）能夠直接對應著一條語句。通過將分解之後的一系列過程封裝在一個函數抽象中，程序員在特定的時刻只關心有限的細節，這個新的函數抽象比其較低級的抽象更接近問題求解的過程，因而，能夠很好地映射問題求解中的過程。如果這個過程出現在許多問題求解中，那麼，這個函數抽象就可能被重復利用。
函數是面向過程程序設計的基礎，按照結構化程序設計的思想，又可將完成某一復雜工作的函數放在一個頭文件，便於我們多次復用。
面向過程的程序設計方法與面向對象的程序設計方法的根本區別在於對待數據和函數的關繫上。
在面向過程的程序設計中，數據只被看作是一種靜態的結構，它只有等待調用函數來對它進行處理。
在面向對象的程序設計中，將數據和對該數據進行合法操作的函數封裝在一起作為一個類的定義。另外，封裝還提供了一種對數據訪問嚴格控制的機制。因此，數據將被隱藏在封裝體中，該封裝體通過操作介面與外界交換信息。
面向對象的思想需要在實踐中不斷摸索和體會，在以後的程序設計中，可主動運用這種思想去實踐。
⑽ 用數據結構編寫約瑟夫環演算法思想
vb 寫的
Sub test()
'約瑟夫環程序代碼
Dim e() As String
Dim f() As String
Dim a, b, c As String
a = "1 2 3 4 5 6 7 8 9 0 11 12" '基數(可增減)
b = 7 '刪除序號(可變)
e = Split(a)
Do Until UBound(Split(a)) = 0
Do Until UBound(e) >= b
e = Split(Trim(Replace(Join(e) & " " & a, " ", " ")))
Loop
For i = UBound(e) To LBound(e) Step -1
If i = b - 1 Then
a = Trim(Replace(" " & a & " ", " " & e(i) & " ", " "))
f = Split(Trim(Join(f) & " " & e(i)))
c = Trim(Replace(" " & c & " ", " " & e(i) & " ", " "))
Exit For
End If
c = e(i) & " " & c
Next
e = Split(Trim(c)): c = ""
Loop
Debug.Print "刪除順序為" & Join(f) & " " & a
End Sub