| ||||||||||
| 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