Dain

写出一个可以工作的程序并不够

统计

留言簿(3)

积分与排名

良师益友

阅读排行榜

评论排行榜

置顶随笔 #

[置顶]励志

师兄太强了，拿到了baidu、M$、Google的offer，可是实验室第一人啊，实在是admire
现在都说工作难找，不过只要努力，总会找到自己满意的，向师兄学习
我一定要努力啊

posted @ 2006-12-08 10:42 Dain 阅读(861) | 评论 (14) | 编辑 收藏

2008年9月18日 #

tate

posted @ 2008-09-18 19:58 Dain 阅读(177) | 评论 (0) | 编辑 收藏

2007年5月29日 #

Getting the Minimum and Maximum Values for a Numeric Type

Getting numeric limits

#include <iostream>
#include <limits>

using namespace std;

template<typename T>
void showMinMax() {
   cout << "min: " << numeric_limits<T>::min() << endl;
   cout << "max: " << numeric_limits<T>::max() << endl;
   cout << endl;
}

int main() {
   cout << "short:" << endl;
   showMinMax<short>();
   cout << "int:" << endl;
   showMinMax<int>();
   cout << "long:" << endl;
   showMinMax<long>();
   cout << "long long:" << endl;
   showMinMax<long long>();
   cout << "float:" << endl;
   showMinMax<float>();
   cout << "double:" << endl;
   showMinMax<double>();
   cout << "long double:" << endl;
   showMinMax<long double>();
   cout << "unsigned short:" << endl;
   showMinMax<unsigned short>();
   cout << "unsigned int:" << endl;
   showMinMax<unsigned int>();
   cout << "unsigned long:" << endl;
   showMinMax<unsigned long>();
   cout << "unsigned long long:" << endl;
   showMinMax<unsigned long long>();
}

posted @ 2007-05-29 10:38 Dain 阅读(804) | 评论 (2) | 编辑 收藏

2007年5月25日 #

3017

#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

struct Node {
    int i,j;
    int value;
};

long num[100000];
vector<Node> matrix;

int main() {
    long n;
    long long m;
    scanf("%ld %lld",&n,&m);

    long i,j;
    for(i = 0;i < n;++i) {
        scanf("%ld",&num[i]);
    }

    for(i = 0;i < n;++i) {
        if(num[i] > m) {
            break;
        }
    }

    if(i < n) {
        printf("-1\n");

        return 0;
    }

    long long res = -1;
    long long sum;
    long max,min = 0;
    for(i = 0;i < n;++i) {
        if(i > 0) {
            min = 1000000;
            for(j = 0;j < matrix.size();++j) {
                if(matrix[j].j == i - 1 && matrix[j].value < min) {
                    min = matrix[j].value;
                }
            }
        }
        else {
            min = 0;
        }

        sum = 0;
        Node node;
        max = -1;
        for(j = i;j < n;++j) {
            sum += num[j];
            if(sum <= m) {
                if(max < num[j]) {                    
                    max = num[j];
                }
                node.i = i;
                node.j = j;
                node.value = max + min;
                matrix.push_back(node);
                if(j == n - 1) {
                    if(res != -1) {
                        if(node.value < res) {
                            res = node.value;
                        }
                    }
                    else {
                        res = node.value;
                    }
                }
            }
            else {
                break;
            }
        }
    }
    
    printf("%lld\n",res);

    return 0;
}

posted @ 2007-05-25 10:06 Dain 阅读(263) | 评论 (0) | 编辑 收藏

3017

#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

struct Node {
    int i,j;
    int value;
};

long num[100000];
vector<Node> matrix;

int main() {
    long n;
    long long m;
    scanf("%ld %lld",&n,&m);

    long i,j;
    for(i = 0;i < n;++i) {
        scanf("%ld",&num[i]);
    }

    for(i = 0;i < n;++i) {
        if(num[i] > m) {
            break;
        }
    }

    if(i < n) {
        printf("-1\n");

        return 0;
    }

    long long res = -1;
    long long sum;
    long max,min = 0;
    for(i = 0;i < n;++i) {
        if(i > 0) {
            min = 1000000;
            for(j = 0;j < matrix.size();++j) {
                if(matrix[j].j == i - 1 && matrix[j].value < min) {
                    min = matrix[j].value;
                }
            }
        }
        else {
            min = 0;
        }

        sum = 0;
        Node node;
        max = -1;
        for(j = i;j < n;++j) {
            sum += num[j];
            if(sum <= m) {
                if(max < num[j]) {                    
                    max = num[j];
                }
                node.i = i;
                node.j = j;
                node.value = max + min;
                matrix.push_back(node);
                if(j == n - 1) {
                    if(res != -1) {
                        if(node.value < res) {
                            res = node.value;
                        }
                    }
                    else {
                        res = node.value;
                    }
                }
            }
            else {
                break;
            }
        }
    }
    
    printf("%lld\n",res);

    return 0;
}

posted @ 2007-05-25 10:06 Dain 阅读(220) | 评论 (0) | 编辑 收藏

2007年5月24日 #

不要再犯低级的错误

最近，总是犯非常低级的错误
看题不仔细
将j误写成k，而且怪的是，测试的例子都通过了，后来通过debug才找到了这个很低级的错误

真是气人啊

不要再犯了

posted @ 2007-05-24 13:56 Dain 阅读(246) | 评论 (0) | 编辑 收藏

2007年4月16日 #

列出所有9位数，它的前n位能被n整除

最简单的是穷举，不过那可要O(9*109)，不可取 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> fun(int n)
{
    vector<int> last,all;
    int i,j,k;
    for(i = 1;i < 10;++i)
        all.push_back(i);

    if(n == 1)
        return all;

    int size;
    int num;
    for(i = 2;i <= n;++i)
    {
        last = all;
        all.clear();
        size = (int)last.size();
        for(j = 0;j < size;++j)
        {
            for(k = 0;k < 10;++k)
            {
                num = last[j] * 10 + k;
                if(num % i == 0)
                    all.push_back(num);
            }
        }
        last.clear();
    }

    return all;
}

posted @ 2007-04-16 17:29 Dain 阅读(1106) | 评论 (5) | 编辑 收藏

2007年2月7日 #

最大的子序列和问题

求解该问题的四种算法：
 时间O(N3)，算法一
int  MaxSubsequenceSum( const   int  A[], int  N)
 {
     int  ThisSum,MaxSum,i,j,k;
    
    MaxSum  =   0 ;
     for (i  =   0 ;i  <  N;i ++ )
         for (j  =  i;j  <  N;j ++ )
         {
            ThisSum  =   0 ;
             for (k  =  i;k  <=  j;k ++ )    ThisSum  +=  A[k];                
             if (ThisSum  >  MaxSum)    MaxSum  =  ThisSum;
        }
        
     return  MaxSum;
}
时间O(N2)，算法二
int  MaxSubsequenceSum( const   int  A[], int  N)
 {
     int  ThisSum,MaxSum,i,j;
    
    MaxSum  =   0 ;
     for (i  =   0 ;i  <  N;i ++ )
     {
        ThisSum  =   0 ;
         for (j  =  i;j  <  N;j ++ )
         {
            ThisSum  +=  A[k];                
             if (ThisSum  >  MaxSum)    MaxSum  =  ThisSum;
        }
    }
        
     return  MaxSum;
}
时间O(NlogN)，算法三
static   int  MaxSubSum( const   int  A[], int  Left, int  Right)
 {
     int  MaxLeftSum,MaxRightSum;
     int  MaxLeftBorderSum,MaxRightBorderSum;
     int  LeftBorderSum,RightBorderSum;
     int  Center,i;
    
     if (Left  ==  Right)
         if (A[left]  >   0 )     return  A[left];
         else      return   0 ;
            
    Center  =  (Left  +  Right)  /   2 ;
    MaxLeftSum  =  MaxSubSum(A,Left,Center);
    MaxRightSum  =  MaxSubSum(A,Center  +   1 ,Right);
    
    MaxLeftBorderSum  =   0 ;
    LeftBorderSum  =   0 ;
     for (i  =  Center;i  >=  Left;i -- )
     {
        LeftBorderSum  +=  A[i];
         if (LeftBorderSum  >  MaxLeftBorderSum)    MaxLeftBorderSum  =  LeftBorderSum;
    }
    
    MaxRightBorderSum  =   0 ;
    RightBorderSum  =   0 ;
     for (i  =  Center  +   1 ;i  <=  Right;i ++ )
     {
        RightBorderSum  +=  A[i];
         if (RightBorderSum  >  MaxRightBorderSum)    MaxRightBorderSum  =  RightBorderSum;
    }
    
     return  Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum  +  MaxRightBorderSum);
}

int  MaxSubsequenceSum( const int  A[],int  N)
 {
     return  MaxSubSum(A, 0 ,N  -   1 );    
}
时间O(N)，算法四
intMaxSubsequenceSum( const int  A[], int  N)
 {
     int  ThisSum,MaxSum,i;
    
    ThisSum  =  MaxSum  =   0 ;
     for (i  =   0 ;i  <  N;i ++ )
     {
        ThisSum  +=  A[i];
         if (ThisSum  >  MaxSum)
            MaxSum  =  ThisSum;
         else
            ThisSum  =   0 ;
    }
    
     return  MaxSum;
}


参考《数据结构与算法分析》

posted @ 2007-02-07 10:52 Dain 阅读(1048) | 评论 (7) | 编辑 收藏

2007年1月31日 #

编写递归四条基本法则

  1. 基准情形。必须要有某些基准情形，它无须递归就能解出，也就是要有退出递归的条件。
  2. 不断推进。对于那些需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。
  3. 设计法则。假设所有的递归调用都能运行。
  4. 合成效益。求解一个问题的同一个实例时，切勿在不同的递归调用中做重复性的工作。

posted @ 2007-01-31 21:03 Dain 阅读(434) | 评论 (0) | 编辑 收藏

读书计划

遇到了好多不能解决的问题后，觉得应该重新读读书了
最近买了几本书
《More Effective CPP》
《Effective STL》
《并行程序设计》
《数据结构与算法分析——C语言描述》 

posted @ 2007-01-31 20:07 Dain 阅读(447) | 评论 (1) | 编辑 收藏

2007年1月19日 #

引用和指针参数的关系

两种参数都允许函数修改实参指向的对象，都允许有效地向函数传递大类型对象。所以怎么样决定把函数参数声明成引用还是指针呢？
引用必须被初始化为指向一个对象，一旦初始化了，它就不能再指向其他对象。指针可以指向一系列不同的对象也可以什么都不指向。
因为指针可能指向一个对象或没有任何对象，所以函数在确定指针实际指向一个有效的对象之前不能安全解引用一个指针。如：
class  X;
 void  fun(X  * x)
 {
   //  在解引用指针之前确信它非0
   if (x  !=   0 )
     //  解引用指针
}   
而，对于引用参数，函数不需要保证它指向一个对象。引用必须指向一个对象，不希望向指针那样进行解引用。如：
class Type;
void op(const Type &t1,const Type &t2);

int main()
{
  Type obj1;
  // 设置obj1为某个值

  // 错误：引用参数的实参不能为0
  op(obj1,0);

  // 
  return 0;
}
如果一个参数可能在函数中指向不同的对象，或者这个参数可能不指向任何对象，则必须使用指针参数。
引用参数的一个重要用法，它允许有效地实现重载操作符的同时，还能保证用法的直观性。可以参考《C++ Primer》

ps 发现书287页的第二个程序例子是错的

posted @ 2007-01-19 09:56 Dain 阅读(3217) | 评论 (1) | 编辑 收藏

仅列出标题  下一页