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 閱讀(841) | 評(píng)論 (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 閱讀(237) | 評(píng)論 (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 閱讀(279) | 評(píng)論 (0) | 編輯 收藏

不要再犯低級(jí)的錯(cuò)誤

posted @ 2007-05-24 13:56 Dain 閱讀(266) | 評(píng)論 (0) | 編輯 收藏

列出所有9位數(shù)，它的前n位能被n整除

最簡(jiǎn)單的是窮舉，不過(guò)那可要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 閱讀(1135) | 評(píng)論 (5) | 編輯 收藏

最大的子序列和問(wè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;
}

時(shí)間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 );????
}

時(shí)間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;
}

參考《數(shù)據(jù)結(jié)構(gòu)與算法分析》

posted @ 2007-02-07 10:52 Dain 閱讀(1081) | 評(píng)論 (7) | 編輯 收藏

編寫遞歸四條基本法則

1. 基準(zhǔn)情形。必須要有某些基準(zhǔn)情形，它無(wú)須遞歸就能解出，也就是要有退出遞歸的條件。
2. 不斷推進(jìn)。對(duì)于那些需要遞歸求解的情形，每一次遞歸調(diào)用都必須要使求解狀況朝接近基準(zhǔn)情形的方向推進(jìn)。
3. 設(shè)計(jì)法則。假設(shè)所有的遞歸調(diào)用都能運(yùn)行。
4. 合成效益。求解一個(gè)問(wèn)題的同一個(gè)實(shí)例時(shí)，切勿在不同的遞歸調(diào)用中做重復(fù)性的工作。

posted @ 2007-01-31 21:03 Dain 閱讀(457) | 評(píng)論 (0) | 編輯 收藏

讀書計(jì)劃

遇到了好多不能解決的問(wèn)題后，覺(jué)得應(yīng)該重新讀讀書了
最近買了幾本書

《More?Effective?CPP》
《Effective?STL》
《并行程序設(shè)計(jì)》
《數(shù)據(jù)結(jié)構(gòu)與算法分析——C語(yǔ)言描述》?

posted @ 2007-01-31 20:07 Dain 閱讀(476) | 評(píng)論 (1) | 編輯 收藏

引用和指針參數(shù)的關(guān)系

class ?X;
void ?fun(X? * x)
{
?? // ?在解引用指針之前確信它非0
?? if (x? != ? 0 )
???? // ?解引用指針
} ??

而，對(duì)于引用參數(shù)，函數(shù)不需要保證它指向一個(gè)對(duì)象。引用必須指向一個(gè)對(duì)象，不希望向指針那樣進(jìn)行解引用。如：

class?Type;
void?op(const?Type?&t1,const?Type?&t2);

int?main()
{
??Type?obj1;
??//?設(shè)置obj1為某個(gè)值

??//?錯(cuò)誤：引用參數(shù)的實(shí)參不能為0
??op(obj1,0);

??//?
??return?0;
}

如果一個(gè)參數(shù)可能在函數(shù)中指向不同的對(duì)象，或者這個(gè)參數(shù)可能不指向任何對(duì)象，則必須使用指針參數(shù)。
引用參數(shù)的一個(gè)重要用法，它允許有效地實(shí)現(xiàn)重載操作符的同時(shí)，還能保證用法的直觀性。可以參考《C++ Primer》

ps 發(fā)現(xiàn)書287頁(yè)的第二個(gè)程序例子是錯(cuò)的

posted @ 2007-01-19 09:56 Dain 閱讀(3238) | 評(píng)論 (1) | 編輯 收藏