qinzuoyan

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 16 Comments :: 0 Trackbacks

常用链接

留言簿(3)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2010年12月13日 #

#include <iostream>
#include 
<cmath>
using namespace std;

/*
long long max(long long n)
{
    long long i=2;
    while(n != 1)
    {
        while (n % i == 0)
            n /= i;
        i++;
    }
    return i-1;
}
*/

// return the max prime factor of n
long long max(long long n)
{
    
long long i=2;
    
long long m = (long long)sqrt(n);
    
while(i <= m)
    {
        
if (n % i == 0)
        {
            n 
/= i;
            m 
= (long long)sqrt(n);
        }
        
else {
            i
++;
        }
    }
    
return n;
}

int main()
{
    cout 
<< max(13195<< endl;
    cout 
<< max(600851475143LL) << endl;
    
return 0;
}
posted @ 2010-12-13 00:19 左言 阅读(553) | 评论 (0)编辑 收藏

2010年10月22日 #

#include <iostream>
#include 
<stack>
#include 
<map>
using namespace std;

struct Node {
    
int v;
    Node 
*lchild;
    Node 
*rchild;
};

struct StackNode {
    Node 
*ptr;
    
int flag; // 1 means the right sub-tree has been travelled
};

void visit(Node *p)
{
    cout 
<< p-><< ' ';
}

void preorder_travel(Node *root)
{
    
if(root == NULL)
        
return;
    stack
<Node*> s;
    Node 
*= root;
    
while (p || !s.empty())
    {
        
while (p)
        {
            s.push(p);
            visit(p);
            p 
= p->lchild;
        }
        
if (!s.empty())
        {

            p 
= s.top();
            s.pop();
            p 
= p->rchild;
        }
    }
}

void inorder_travel(Node *root)
{
    
if(root == NULL)
        
return;
    stack
<Node*> s;
    Node 
*= root;
    
while (p || !s.empty())
    {
        
while (p)
        {
            s.push(p);
            p 
= p->lchild;
        }
        
if (!s.empty())
        {
            p 
= s.top();
            s.pop();
            visit(p);
            p 
= p->rchild;
        }
    }
}

void postorder_travel(Node *root)
{
    
if(root == NULL)
        
return;
    stack
<StackNode> s;
    StackNode x;

    Node 
*= root;
    
while (p || !s.empty())
    {
        
while (p)
        {
            x.ptr 
= p;
            x.flag 
= 0;
            s.push(x);
            p 
= p->lchild;
        }
        
while (!s.empty() && s.top().flag)
        {
            visit(s.top().ptr);
            s.pop();
        }
        
if (!s.empty())
        {
            s.top().flag 
= 1;
            p 
= s.top().ptr->rchild;
        }
    }
}

int main()
{
    
int i, j;
    map
<int, Node*> m;

    
int a[][3= {
        {
1,2,3},
        {
2,4,5},
        {
3,6,7},
        {
4,-1,-1},
        {
5,-1,-1},
        {
6,8,-1},
        {
7,-1,9},
        {
8,-1,-1},
        {
9,-1,-1},
        
-1
    };

    
for (i=0; a[i][0]!=-1; i++) {
        Node 
*= new Node;
        n
->= a[i][0];
        m[n
->v] = n;
    }
    
for (i=0; a[i][0]!=-1; i++) {
        
int s = a[i][0];
        
int l = a[i][1];
        
int r = a[i][2];
        Node 
*= m[s];
        n
->lchild = (l==-1 ? NULL : m[l]);
        n
->rchild = (r==-1 ? NULL : m[r]);
    }

    Node 
*root = m[a[0][0]];

    preorder_travel(root);
    cout 
<< endl;
    inorder_travel(root);
    cout 
<< endl;
    postorder_travel(root);
    cout 
<< endl;

    
return 0;
}
posted @ 2010-10-22 14:23 左言 阅读(317) | 评论 (0)编辑 收藏

使用非递归后续遍历:
#include<iostream>
#include
<stack>
#include
<map>
using namespace std;

struct Node
{
    
int v;
    Node 
*lchild;
    Node 
*rchild;
};

struct StackNode
{
    Node 
*ptr;
    
int flag;
};

int maxDepth(Node *root)
{
    stack
<StackNode> s;
    StackNode x;
    Node 
*= root;
    
int max = 0;
    
while (p || !s.empty())
    {
        
while (p)
        {
            x.ptr 
= p;
            x.flag 
= 0;
            s.push(x);
            
if (s.size() > max)
                max 
= s.size();
            p 
= p->lchild;
        }
        
while (!s.empty() && s.top().flag)
        {
            s.pop();

        }
        
if (!s.empty())
        {
            s.top().flag 
= 1;
            p 
= s.top().ptr->rchild;
        }
    }
    
return max;
}


int main()
{
    
int i, j;
    map
<int, Node*> m;

    
int a[][3= {
        {
1,2,3},
        {
2,4,5},
        {
3,6,7},
        {
4,-1,-1},
        {
5,-1,-1},
        {
6,8,-1},
        {
7,-1,9},
        {
8,-1,-1},
        {
9,-1,10},
        {
10,-1,-1},
        
-1
    };

    
for (i=0; a[i][0]!=-1; i++) {
        Node 
*= new Node;
        n
->= a[i][0];
        m[n
->v] = n;
    }
    
for (i=0; a[i][0]!=-1; i++) {
        
int s = a[i][0];
        
int l = a[i][1];

        
int r = a[i][2];
        Node 
*= m[s];
        n
->lchild = (l==-1 ? NULL : m[l]);
        n
->rchild = (r==-1 ? NULL : m[r]);
    }

    Node 
*root = m[a[0][0]];

    cout 
<< maxDepth(root) << endl;

    
return 0;
}

posted @ 2010-10-22 14:16 左言 阅读(528) | 评论 (0)编辑 收藏

2010年6月10日 #

     摘要: 实现这个函数:
char* strrep(const char* src, const char* from, const char* to);

将src中出现的所有from替换成to  阅读全文
posted @ 2010-06-10 12:16 左言 阅读(2338) | 评论 (1)编辑 收藏

2009年8月27日 #

     摘要: 美国《时代》周刊评出了2009年“50个最佳网站”,都是哪些网站上榜?它们具有哪些特点?  阅读全文
posted @ 2009-08-27 11:27 左言 阅读(296) | 评论 (0)编辑 收藏

2009年8月14日 #

     摘要: 最近一个朋友在用计算机模拟人来玩文曲星上的“猜数字”游戏,也邀我一起讨论。我以前没有玩过,不过发现这个还是蛮有趣的,于是也想写一个能猜数据的小程序。通过几日思考,终于实现了一个稍微有点聪明的,可以保证在7次之内猜对数字。  阅读全文
posted @ 2009-08-14 14:11 左言 阅读(3036) | 评论 (15)编辑 收藏

2009年8月11日 #

     摘要: 最近因为使用Ruby写一个多线程爬虫,所以积累了一点小心得。  阅读全文
posted @ 2009-08-11 00:09 左言 阅读(346) | 评论 (0)编辑 收藏

2009年8月8日 #

     摘要: 今天分析数据的时候需要检查一个图是否有向无环图,于是用脚本写了个小的检查工具。基本原理:如果能够完全拓扑排序,则是无环图。
  阅读全文
posted @ 2009-08-08 10:47 左言 阅读(551) | 评论 (0)编辑 收藏