Dain

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 阅读(801) | 评论 (2) | 编辑 收藏

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) | 编辑 收藏

不要再犯低级的错误

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

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

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

#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) | 编辑 收藏

最大的子序列和问题

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(N²)，算法二

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;
}

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 阅读(1044) | 评论 (7) | 编辑 收藏

编写递归四条基本法则

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) | 编辑 收藏

引用和指针参数的关系

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) | 编辑 收藏