| ||||||||||
Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
借此帖请教 约瑟夫问题的数学公式, concrete mathematics 上面看懂了 n==2 的, 但是 n 为任意正整数的推广公式那些不明白,请大牛指点一下In Reply To:由于其他方法吗? Posted by:90303121 at 2004-05-25 20:15:57 > 我也只能想到枚举法,但是提交时,总是,memory limit exceted. > 可能是算法有问题。 > 哪位大虾帮忙看看,指点指点。感激涕零!!!!! > > > 以下是我用环链表作的 > > #include<iostream> > #include<iomanip> > > using namespace std; > > struct joseph > { > int num; > joseph * left; > joseph * right; > }; > > typedef joseph * ring; > > void creat(ring & head,int k) > { > > ring pr,p; > int i=1; > p=new joseph; > p->num=1; > pr=p; > while(i<k*2) > { > > if(head==NULL) > head=p; > else > { > i++; > > p=new joseph; > p->num=i; > p->left=pr; > pr->right=p; > > pr=p; > } > } > p->right=head; > head->left=p; > > > > } > > > void del(ring & pr) > { > ring temp=pr; > pr=pr->right; > temp->left->right=temp->right; > temp->right->left=temp->left; > delete(temp); > > > } > > void print(const ring & head) > { > ring p=head->right; > cout<<head->num; > while(p->num!=head->num) > { > cout<<p->num; > p=p->right; > } > } > > > void main() > { > int k; > cin>>k; > > while(k!=0) > { > for(long m=k+1;;m++) > { > ring head=NULL; > creat(head,k); > ring p=head; > for(int l=1;l<=k;l++) > { > for(int i=1;i<m;i++) > p=p->right; > if(p->num >k) > del(p); > else > break; > > if(l==k) > { > cout<<m<<endl; > goto end; > } > > > } > for(ring h=head->right;h->num!=head->num;) > { > ring i=h;h=h->right; > delete(i); > } > > } > end: > > cin>>k; > } > > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator