递归的非递归写法

#include<iostream>
#include<deque>
#include <ctime>
using namespace std;
template<class _Ty, class _C = deque<_Ty> >
class zlfStack {
public:
 typedef unsigned _Ty;
 typedef _C::allocator_type allocator_type;
 typedef _C::value_type value_type;
 typedef _C::size_type size_type;
 typedef _C::iterator zlfIterator;
protected:
 _C c;
public:
inline
 const value_type& zlfTop2(){
  return *(c.end()-2);
 }
inline
 const value_type& zlfTop3(){
  return *(c.end()-3);
 }
inline
 void top_3(value_type& x,value_type& y,value_type& b)
 {
  b=*(c.end()-1);
  y=*(c.end()-2);
  x=*(c.end()-3);
 }
inline
void top_2(value_type& x,value_type& y)
{
 y=*(c.end()-2);
 x=*(c.end()-3);
}

 //zlfStack(){ }
 explicit zlfStack(const allocator_type& _Al = allocator_type())
  :c(_Al){}
 allocator_type get_allocator() const
 {return (c.get_allocator()); }
 bool empty() const
 {return (c.empty()); }
 size_type size() const
 {return (c.size()); }
 value_type& top()
 {return (c.back()); }
 const value_type& top() const
 {return (c.back()); }
 void push(const value_type& _X)
 {c.push_back(_X); }
inline
 void push_3(const value_type& x,const value_type& y,const value_type& b)
 {
  c.push_back(x);
  c.push_back(y);
  c.push_back(b);
 }
inline
 void pop()
 {c.pop_back(); }
 };///
enum{B0=0,B1=1,B2=2,B3=3};
int A(unsigned x,unsigned y)
{
 static count=0; 
 if (!x&&!y) {return ++count;return count;}
 if (x==0xffff) {count=0;return 0;}
 if (x) A(--x,y);
AB1: if(y) A(x,--y);
AB2:
  return count;
  
}
inline
void clear(){A(0xffff,0);}
zlfStack<unsigned> s;
inline
void push(unsigned x,unsigned y,unsigned b)
{
 s.push(x);
 s.push(y);
 s.push(b);
}
inline
void pop(unsigned& x,unsigned& y,unsigned& b)
{
 b=s.top();
 s.pop();
// y=s.top();
 s.pop();
// x=s.top();
 s.pop();
}


int main()
{
 unsigned x=1,y=1,b=1,c=0,z=0;
 unsigned temp=0;
 clock_t t1,t2;
 unsigned k=1;
 unsigned long sum1=0,sum2=0,time1=0,time2=0;

 cout<<"AAAA"<<endl;
 t1=clock();
 for (x=1;x<10;x++) {
  for (y=1;y<10;y++) { 
   clear();
   k=A(x,y);
   sum1+=k;
   cout<<k<<" ";
   cout<<"x="<<x<<" "<<"y="<<y<<endl;
  }
 }
 t2=clock();
 time1=t2-t1;
 cout<<endl;


 if (!x&&!y) return 0;//exit
 sum2 = 0;
 t1=clock();
 for (x=1;x<10;x++) { 
  for (y=1;y<10;y++) {// push(x,y,B3);
  s.push_3(x,y,B3);
  c=0;
  b=B0;
  while (!s.empty()) {
   switch(b) {
   case B0:if(x) {//push(--x,y,B1);
    s.push_3(--x,y,B1);
    b=B0;continue;}
   case B1:if(y) {//push(x,--y,B2);
    s.push_3(x,--y,B2);
    b=B0;continue;}
   case B2:if (!x&&!y) c++;
   default:;
   }//switch
  // pop(x,y,b);
   b=s.top();
   s.pop();
   s.pop(); 
   s.pop();
   if(b==B3) break;//return to main
  // pop(x,y,temp);
  // push(x,y,temp);
  // y=s.zlfTop2();
  // x=s.zlfTop3();
   s.top_2(x,y);
  }//while
  sum2+=c;
 // cout<<"c="<<c<<" "<<"x="<<x<<" "<<"y="<<y<<endl;
  }//y
 }//x
 t2=clock();
 time2=t2-t1;
 cout<<"time used :"<<time2<<"ms"<<endl;
 cout<<"routines :"<<sum2<<endl;
 cout<<endl<<endl;
 double t;
 cout<<"routines: "<<sum1<<"  time1: "<<time1<<endl;
 t=sum1/time1;
 cout<<t<<" rps"<<endl;
 cout<<"routines: "<<sum2<<"  time2: "<<time2<<endl;
 t=sum2/time2;
 cout<<t<<" rps"<<endl;
 return 0;
}

posted on 2008-01-11 17:15 zlf 阅读(612) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2008年1月>
303112345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

常用链接

留言簿(1)

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜