| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1109 人关注过本帖
标题:怎么根据递推公式证明会出现循环
只看楼主 加入收藏
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
结帖率:96.08%
收藏
已结贴  问题点数:20 回复次数:10 
怎么根据递推公式证明会出现循环
问题:http://acm.hdu.

我的代码:
程序代码:
#include<iostream>
using namespace std;

int numArry[3]={0};
int main()
{
    int *pFn_2=&numArry[0];
    int *pFn_1=&numArry[1];
    int *pFn=&numArry[2];

    int a,b,n;
    cin>>a>>b>>n;
    a=a%7;
    b=b%7;
    while (a||b||n)
    {
        *pFn_2=1;
        *pFn_1=1;
        for(int i=2;i<n;i++)
        {
            *pFn=(a * (*pFn_1) + b * (*pFn_2))%7;

            int *tmp=pFn;
            pFn=pFn_2;
            pFn_2=pFn_1;
            pFn_1=tmp;
        }

        cout<<*pFn_1<<endl;

        cin>>a>>b>>n;
        a=a%7;
        b=b%7;
    }

    return 0;
}


提交问题:运行超时
自我分析:题目要求n可以是非常大的数据,不能单纯从1到n进行循环,要想缩短时间,只能证明F(n)序列是循环出现的,我想用链表的方式存储F(n),一边算一边寻找何时会出现循环。可是我现在在想,能否从数学上证明,这种递推公式产生的序列一定是循环的序列?

问题:证明可循环,或者使用其他算法。
搜索更多相关主题的帖子: color 
2015-09-28 11:18
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9026
专家分:54030
注 册:2011-1-18
收藏
得分:5 
f(n-2) 在 0到6 之间
f(n-1) 在 0到6 之间
那么 f(n-2) f(n-1) 至多也就是只有七七四十九种可能,因此至多49为一个循环周期

2015-09-28 12:12
jklqwe111
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:35
帖 子:336
专家分:1135
注 册:2014-4-13
收藏
得分:5 
由于有a,b两个系数,没有找到可能的循环,只能做一些优化,尽可能把循环之内的计算挪到外面,对于不同数据找出一些规律,能使后面的计算利用前面的结果。

程序代码:
#include<iostream>
#include<time.h>
#include<memory.h>
#include<string.h>
using namespace std;


int ArrA[7][7]={{0,0,0,0,0,0,0},{0,1,2,3,4,5,6},{0,2,4,6,1,3,5},{0,3,6,2,5,1,4},{0,4,1,5,2,6,3},{0,5,3,1,6,4,2},{0,6,5,4,3,2,1}};
int ArrMod[13]={0,1,2,3,4,5,6,0,1,2,3,4,5};
struct strdata
{
  int a;
  int b;
  int n;
};

int main()
{
    int numArr[2]={0};
      long t;
    int a,b,n;
    struct strdata * pd;
    int m=0,size=0;
    int* id;
    int i;
    struct strdata type[54];//记录a,b不同比值的计算结果,保存f(n-1),f(n-2)

     int getvol(int*data,const int ns,const int ne ,const int a,const int b);
     //录入数据
    size=128;
    pd=(struct strdata *)malloc(sizeof(struct strdata)*size);
    
    cin>>a>>b>>n;
    while (a||b||n)
    {
      if(m+1>size) 
      {
          size+=128;
          pd=(struct strdata *)realloc(pd,sizeof(struct strdata)*size);
      }
          
          pd[m].a =a;
          pd[m].b =b;
          pd[m].n =n;
          m++;
         cin>>a>>b>>n; 
    }
//为数据建立n的升序的索引


 t=clock();
  id=(int*)malloc(sizeof(int)*m);//索引空间
  id[0]=0;
  // 查找pd[i]在id[]中的位序
  for (i=1 ;i<m; i++)
  {
     int s=0,e,c,k;
     e=i-1;
     if (pd[id[s]].n>pd[i].n) s=e;
     if (pd[id[e]].n<=pd[i].n) k=i;
     else
     { 
         while(e-s>1)
         {
           c=s+(e-s)/2;
           if (pd[id[c]].n>pd[i].n)  e=c;
           else s=c;
         }
         k=e;

     }

    
        memmove(id+k+1,id+k,(i-k)*sizeof(int));//后移索引
       id[k]=i;//写入索引

  }

  memset(type,0,sizeof(struct strdata)*54);

  for (i=0;i<m;++i)
  {
    int a,b,n,k=1,j,ns;
    a=pd[id[i]].a%7 ;
    b=pd[id[i]].b%7 ;
    n=pd[id[i]].n ;
    if(n==1 || n==2) {pd[id[i]].n=1;continue;}
    if(a==0 && b==0) {pd[id[i]].n=0;continue;}
    if (a==2 && b==4) {k=2;a=1;b=2;}
    else if (a==2 && b==6) {k=2;a=1;b=3;}
    else if (a==3 && b==6) {k=3;a=1;b=2;}
    else if (a==4 && b==6) {k=2;a=2;b=3;}
    else if (a==6 && b==4) {k=2;a=3;b=2;}
    else if (a==6 && b==3) {k=3;a=2;b=1;}
    else if (a==6 && b==2) {k=2;a=3;b=1;}
    else if (a==4 && b==2) {k=2;a=2;b=1;}
    else if (a==b){k=a;a=1;b=1;}
    
    
    j=(a<<3)+b;//type[]下标4,5,6位对应a,1,2,3位对应b
    if(type[j].n==0) //初始计算//原来的判断if(type[j].a==0)不准确
    {
      numArr[0]=1;
      numArr[1]=1;
      ns=getvol(numArr,3,n,a,b);
      // 保存计算结果以备后用
      type[j].a=numArr[(ns-1)&1];
      type[j].b=numArr[(ns-2)&1];
      type[j].n=ns;
      pd[id[i]].n=(numArr[(ns-1)&1]*k)%7;

    }
    else//在以前的计算结果上继续
    {
      ns=type[j].n ;
      numArr[(ns-1)&1]=type[j].a;
      numArr[(ns-2)&1]=type[j].b;
      ns=getvol(numArr,ns,n,a,b);
      type[j].a=numArr[(ns-1)&1];
      type[j].b=numArr[(ns-2)&1];
      type[j].n=ns;
      pd[id[i]].n=(numArr[(ns-1)&1]*k)%7;
    }

  }
   

 for(i=0;i<m;++i)

 {

    cout<<pd[i].n<<endl;
        

 }

 free(pd);

 free(id);

 

 cout<<(float)(clock()-t)/1000<<endl;


 return 0;
}

int getvol(int*data,const int ns,const int ne ,const int a,const int b)
{
  int i;

  for(i=ns;i<=ne;i++)
  {
      
      if (i&1) data[i&1]= ArrMod[ArrA[a][data[0]]+ArrA[b][data[1]]];
      else data[i&1]= ArrMod[ArrA[a][data[1]]+ArrA[b][data[0]]];

  }
  return i;
}


[ 本帖最后由 jklqwe111 于 2015-9-29 08:26 编辑 ]
2015-09-29 00:14
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9026
专家分:54030
注 册:2011-1-18
收藏
得分:5 
简单点儿,可以利用循环,这么写:
unsigned foo( unsigned a, unsigned b, unsigned n )
{
    a%=7, b%=7;

    if( n <= 2 )
        return 1;
    if( a==0 && b==0 )
        return 0;

    unsigned buf[49]={1,(b+a)%7}, cnt=1;
    for( cnt; buf[cnt]!=1 || (buf[cnt-1]!=1 && b!=0); ++cnt )
        buf[cnt+1] = (b*buf[cnt-1] + a*buf[cnt])%7;
    return buf[(n-2)%cnt];
}

2015-09-29 08:56
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9026
专家分:54030
注 册:2011-1-18
收藏
得分:0 
若还想更快的话,那就直接查表(这个表是利用楼上的代码生成的)

程序代码:
unsigned foo( unsigned a, unsigned b, unsigned n )
{
    static const unsigned maps[7][7][50] =

    {
        {
            /*[0][0] =*/ { 1, 0 },
            /*[0][1] =*/ {  1, 1 },
            /*[0][2] =*/ {  6, 1, 2, 2, 4, 4, 1 },
            /*[0][3] =*/ { 12, 1, 3, 3, 2, 2, 6, 6, 4, 4, 5, 5, 1 },
            /*[0][4] =*/ {  6, 1, 4, 4, 2, 2, 1 },
            /*[0][5] =*/ { 12, 1, 5, 5, 4, 4, 6, 6, 2, 2, 3, 3, 1 },
            /*[0][6] =*/ {  4, 1, 6, 6, 1 }
        },
        {
            /*[1][0] =*/ {  1, 1 },
            /*[1][1] =*/ { 16, 1, 2, 3, 5, 1, 6, 0, 6, 6, 5, 4, 2, 6, 1, 0, 1 },
            /*[1][2] =*/ {  6, 1, 3, 5, 4, 0, 1 },
            /*[1][3] =*/ { 24, 1, 4, 0, 5, 5, 6, 0, 4, 4, 2, 0, 6, 6, 3, 0, 2, 2, 1, 0, 3, 3, 5, 0, 1 },
            /*[1][4] =*/ { 48, 1, 5, 2, 1, 2, 6, 0, 3, 3, 1, 6, 3, 6, 4, 0, 2, 2, 3, 4, 2, 4, 5, 0, 6, 6, 2, 5, 6, 5, 1, 0, 4, 4, 6, 1, 4, 1, 3, 0, 5, 5, 4, 3, 5, 3, 2, 0, 1 },
            /*[1][5] =*/ { 21, 1, 6, 4, 6, 5, 0, 4, 4, 3, 2, 3, 6, 0, 2, 2, 5, 1, 5, 3, 0, 1 },
            /*[1][6] =*/ {  6, 1, 0, 6, 6, 0, 1 }
        },
        {
            /*[2][0] =*/ {  3, 1, 2, 4 },
            /*[2][1] =*/ {  6, 1, 3, 0, 3, 6, 1 },
            /*[2][2] =*/ { 48, 1, 4, 3, 0, 6, 5, 1, 5, 5, 6, 1, 0, 2, 4, 5, 4, 4, 2, 5, 0, 3, 6, 4, 6, 6, 3, 4, 0, 1, 2, 6, 2, 2, 1, 6, 0, 5, 3, 2, 3, 3, 5, 2, 0, 4, 1, 3, 1 },
            /*[2][3] =*/ {  6, 1, 5, 6, 6, 2, 1 },
            /*[2][4] =*/ { 48, 1, 6, 2, 0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6, 1, 5, 0, 6, 5, 6, 4, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1 },
            /*[2][5] =*/ { 24, 1, 0, 5, 3, 3, 0, 1, 2, 2, 0, 3, 6, 6, 0, 2, 4, 4, 0, 6, 5, 5, 0, 4, 1 },
            /*[2][6] =*/ {  1, 1 }
        },
        {
            /*[3][0] =*/ {  6, 1, 3, 2, 6, 4, 5 },
            /*[3][1] =*/ { 16, 1, 4, 6, 1, 2, 0, 2, 6, 6, 3, 1, 6, 5, 0, 5, 1 },
            /*[3][2] =*/ { 48, 1, 5, 3, 5, 0, 3, 2, 5, 5, 4, 1, 4, 0, 1, 3, 4, 4, 6, 5, 6, 0, 5, 1, 6, 6, 2, 4, 2, 0, 4, 5, 2, 2, 3, 6, 3, 0, 6, 4, 3, 3, 1, 2, 1, 0, 2, 6, 1 },
            /*[3][3] =*/ { 42, 1, 6, 0, 4, 5, 6, 5, 5, 2, 0, 6, 4, 2, 4, 4, 3, 0, 2, 6, 3, 6, 6, 1, 0, 3, 2, 1, 2, 2, 5, 0, 1, 3, 5, 3, 3, 4, 0, 5, 1, 4, 1 },
            /*[3][4] =*/ {  6, 1, 0, 4, 5, 3, 1 },
            /*[3][5] =*/ {  1, 1 },
            /*[3][6] =*/ {  8, 1, 2, 5, 6, 6, 5, 2, 1 }
        },
        {
            /*[4][0] =*/ {  3, 1, 4, 2 },
            /*[4][1] =*/ { 16, 1, 5, 0, 5, 6, 1, 3, 6, 6, 2, 0, 2, 1, 6, 4, 1 },
            /*[4][2] =*/ { 48, 1, 6, 5, 4, 5, 0, 3, 5, 5, 2, 4, 6, 4, 0, 1, 4, 4, 3, 6, 2, 6, 0, 5, 6, 6, 1, 2, 3, 2, 0, 4, 2, 2, 5, 3, 1, 3, 0, 6, 3, 3, 4, 1, 5, 1, 0, 2, 1 },
            /*[4][3] =*/ { 21, 1, 0, 3, 5, 1, 5, 2, 2, 0, 6, 3, 2, 3, 4, 4, 0, 5, 6, 4, 6, 1 },
            /*[4][4] =*/ {  1, 1 },
            /*[4][5] =*/ {  6, 1, 2, 6, 6, 5, 1 },
            /*[4][6] =*/ {  8, 1, 3, 4, 6, 6, 4, 3, 1 }
        },
        {
            /*[5][0] =*/ {  6, 1, 5, 4, 6, 2, 3 },
            /*[5][1] =*/ {  6, 1, 6, 3, 0, 3, 1 },
            /*[5][2] =*/ { 48, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6, 0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5, 1 },
            /*[5][3] =*/ {  1, 1 },
            /*[5][4] =*/ { 48, 1, 2, 0, 1, 5, 1, 4, 3, 3, 6, 0, 3, 1, 3, 5, 2, 2, 4, 0, 2, 3, 2, 1, 6, 6, 5, 0, 6, 2, 6, 3, 4, 4, 1, 0, 4, 6, 4, 2, 5, 5, 3, 0, 5, 4, 5, 6, 1 },
            /*[5][5] =*/ { 24, 1, 3, 6, 3, 3, 2, 4, 2, 2, 6, 5, 6, 6, 4, 1, 4, 4, 5, 3, 5, 5, 1, 2, 1 },
            /*[5][6] =*/ { 14, 1, 4, 5, 0, 2, 3, 6, 6, 3, 2, 0, 5, 4, 1 }
        },
        {
            /*[6][0] =*/ {  2, 1, 6 },
            /*[6][1] =*/ { 16, 1, 0, 1, 6, 2, 4, 5, 6, 6, 0, 6, 1, 5, 3, 2, 1 },
            /*[6][2] =*/ {  1, 1 },
            /*[6][3] =*/ { 24, 1, 2, 1, 5, 5, 3, 5, 4, 4, 1, 4, 6, 6, 5, 6, 2, 2, 4, 2, 3, 3, 6, 3, 1 },
            /*[6][4] =*/ { 48, 1, 3, 1, 4, 0, 2, 5, 3, 3, 2, 3, 5, 0, 6, 1, 2, 2, 6, 2, 1, 0, 4, 3, 6, 6, 4, 6, 3, 0, 5, 2, 4, 4, 5, 4, 2, 0, 1, 6, 5, 5, 1, 5, 6, 0, 3, 4, 1 },
            /*[6][5] =*/ { 42, 1, 4, 1, 5, 0, 4, 3, 3, 5, 3, 1, 0, 5, 2, 2, 1, 2, 3, 0, 1, 6, 6, 3, 6, 2, 0, 3, 4, 4, 2, 4, 6, 0, 2, 5, 5, 6, 5, 4, 0, 6, 1 },
            /*[6][6] =*/ {  3, 1, 5, 1 }
        }
    };

    if( n <= 2 )
        return 1;
    if( a%7==0 && b%7==0 )
        return 0;

    const unsigned* buf = maps[a%7][b%7];
    return buf[1+(n-2)%buf[0]];
}

2015-09-29 08:57
黑崎一心
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:53
专家分:158
注 册:2012-4-17
收藏
得分:5 
每项的值只与其前两项有关,每项的值域为0到6,那么最多49项必然出现循环。判断循环出现的方式是看有没有连续两项重复出现。所以一共最多计算前51项就足矣。
2015-09-29 09:17
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
回复 3楼 jklqwe111
你的代码依然是超时的,我还没仔细看你的代码,稍后再看,你先自己看看有没有可以继续改进的地方。


学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2015-10-01 19:13
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
最近有点忙,这个题目我还没好好写,暂时先结贴,等我提交自己代码试过之后再来详细回复各位的讨论。


学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2015-10-01 19:14
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
先帖代码,这是我自己用链表写的,已经测试通过了:

程序代码:
#include<iostream>


class Node
{
public:
    Node();
    Node(int numValue,Node *nextNodeValue);
    ~Node();
    void setNum(int numValue){num=numValue;}
    void setNextNode(Node *nextNodeValue){nextNode=nextNodeValue;}
    int getNum(){return num;}
    Node* getNextNode(){return nextNode;}
private:
    int num;
    Node *nextNode;
};

Node::Node()
{
    nextNode=NULL;
    //num=0;
}

Node::Node(int numValue,Node *nextNodeValue)
{
    num=numValue;
    nextNode=nextNodeValue;
}

Node::~Node()
{
}




Node *checkCircle(Node *head,int tmp,Node *pFn_1);
using namespace std;
int main()
{
    int a,b,n;
    cin>>a>>b>>n;

    Node *pFn=new Node();
    Node *pFn_1=new Node(1,pFn);
    Node *pFn_2=new Node(1,pFn_1);
    Node *head=pFn_2;


    
    while (a||b||n)
    {
        pFn_2=head;
        pFn_1=pFn_2->getNextNode();
        pFn=pFn_1->getNextNode();
        pFn_2->setNum(1);
        pFn_1->setNum(1);

        int flag=0;
        for(int i=2;i<n;i++)
        {
            int tmp=(a * (pFn_1->getNum()) + b * (pFn_2->getNum()))%7;

            Node *tmpPNode=checkCircle(head,tmp,pFn_1);

            if(tmpPNode)
            {
                pFn->setNum(tmp);
                pFn->setNextNode(tmpPNode->getNextNode());

                tmpPNode=tmpPNode->getNextNode();
                int count=1;
                while(tmpPNode!=pFn)
                {
                    count++;
                    tmpPNode=tmpPNode->getNextNode();
                }

                //test code这段if根本不可能成立
                if(count==0)
                {
                    cout<<"test message."<<endl;

                    cout<<tmp<<endl;
                    flag=1;
                    break;
                }

                int j=(n-1-i)%count;
                while(j--)
                {
                    pFn=pFn->getNextNode();
                }
                cout<<pFn->getNum()<<endl;
                flag=1;
                break;
            }

            pFn->setNum(tmp);
            pFn->setNextNode(NULL);
            pFn_2=pFn_1;
            pFn_1=pFn;
            pFn=new Node();
            pFn_1->setNextNode(pFn);
        }

        if(flag==0)
        cout<<pFn_1->getNum()<<endl;

        cin>>a>>b>>n;
    }

    return 0;
}

Node *checkCircle(Node *head,int tmp,Node *pFn_1)
{
    Node *tmpHead=head;
    while(tmpHead!=pFn_1)
    {
        if((tmpHead->getNum())==(pFn_1->getNum()))
        {
            Node *tmpP=tmpHead->getNextNode();

            if((tmpP->getNum())==tmp)
            {
                return tmpP;
            }
        }
        tmpHead=tmpHead->getNextNode();
    }

    return NULL;
}

学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2015-10-01 21:05
蚕头燕尾
Rank: 10Rank: 10Rank: 10
来 自:Gryffindo
等 级:贵宾
威 望:12
帖 子:734
专家分:1546
注 册:2013-3-24
收藏
得分:0 
回复 4楼 rjsp
你的代码可以通过,但是这样的思想不太通用,比如说公式里面的7换成别的数的时候,存储空间的大小就要改变是不是?

无论如何,为你代码的精简实用点个赞!


学习编程,为的是表达自己的思想,而不是被别人的思想所禁锢。要先明白自己想干嘛,而不要先问别人让你干嘛。               

                                                                                                                    Black Cat      Hello Tomorrow~
2015-10-01 21:16
快速回复:怎么根据递推公式证明会出现循环
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.031040 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved