怎么根据递推公式证明会出现循环 - C语言论坛

楼主

已结贴√ 问题点数：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　

第 2 楼

得分:5

f(n-2) 在 0到6 之间
f(n-1) 在 0到6 之间
那么 f(n-2) f(n-1) 至多也就是只有七七四十九种可能，因此至多49为一个循环周期

第 3 楼

得分: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 编辑 ]

第 4 楼

得分: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];
}

第 5 楼

得分: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]];
}

第 6 楼

得分:5

每项的值只与其前两项有关，每项的值域为0到6，那么最多49项必然出现循环。判断循环出现的方式是看有没有连续两项重复出现。所以一共最多计算前51项就足矣。

第 7 楼

得分:0

回复 3楼 jklqwe111

你的代码依然是超时的，我还没仔细看你的代码，稍后再看，你先自己看看有没有可以继续改进的地方。

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

Black Cat Hello Tomorrow~

第 8 楼

得分:0

最近有点忙，这个题目我还没好好写，暂时先结贴，等我提交自己代码试过之后再来详细回复各位的讨论。

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

Black Cat Hello Tomorrow~

第 9 楼

得分: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~

第 10 楼

得分:0

回复 4楼 rjsp

你的代码可以通过，但是这样的思想不太通用，比如说公式里面的7换成别的数的时候，存储空间的大小就要改变是不是？

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

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

Black Cat Hello Tomorrow~