C++博客-Dain

tate

Dain — Thu, 18 Sep 2008 11:58:00 GMT

Dain 2008-09-18 19:58 发表评论

Getting the Minimum and Maximum Values for a Numeric Type

Dain — Tue, 29 May 2007 02:38:00 GMT

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

Dain 2007-05-29 10:38 发表评论

3017

Dain — Fri, 25 May 2007 02:06:00 GMT

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

Dain 2007-05-25 10:06 发表评论

3017

Dain — Fri, 25 May 2007 02:06:00 GMT

Dain 2007-05-25 10:06 发表评论

不要再犯低级的错误

Dain — Thu, 24 May 2007 05:56:00 GMT

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

真是气人啊

不要再犯了

Dain 2007-05-24 13:56 发表评论

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

Dain — Mon, 16 Apr 2007 09:29:00 GMT

最简单的是穷举，不过那可要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;
}

Dain 2007-04-16 17:29 发表评论

最大的子序列和问题

Dain — Wed, 07 Feb 2007 02:52:00 GMT

求解该问题的四种算法：
时间O(N³)，算法一

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

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

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

Dain 2007-02-07 10:52 发表评论

编写递归四条基本法则

Dain — Wed, 31 Jan 2007 13:03:00 GMT

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

Dain 2007-01-31 21:03 发表评论

读书计划

Dain — Wed, 31 Jan 2007 12:07:00 GMT

遇到了好多不能解决的问题后，觉得应该重新读读书了
最近买了几本书

《More Effective CPP》
《Effective STL》
《并行程序设计》
《数据结构与算法分析——C语言描述》

Dain 2007-01-31 20:07 发表评论

引用和指针参数的关系

Dain — Fri, 19 Jan 2007 01:56:00 GMT

两种参数都允许函数修改实参指向的对象，都允许有效地向函数传递大类型对象。所以怎么样决定把函数参数声明成引用还是指针呢？
引用必须被初始化为指向一个对象，一旦初始化了，它就不能再指向其他对象。指针可以指向一系列不同的对象也可以什么都不指向。
因为指针可能指向一个对象或没有任何对象，所以函数在确定指针实际指向一个有效的对象之前不能安全解引用一个指针。如：

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页的第二个程序例子是错的

Dain 2007-01-19 09:56 发表评论