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 閱讀(822) | 評論 (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 閱讀(270) | 評論 (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 閱讀(226) | 評論 (0) | 編輯 收藏

不要再犯低級的錯誤

posted @ 2007-05-24 13:56 Dain 閱讀(255) | 評論 (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 閱讀(1117) | 評論 (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 閱讀(1065) | 評論 (7) | 編輯 收藏

編寫遞歸四條基本法則

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

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

讀書計劃

遇到了好多不能解決的問題后，覺得應該重新讀讀書了
最近買了幾本書

《More?Effective?CPP》
《Effective?STL》
《并行程序設計》
《數據結構與算法分析——C語言描述》?

posted @ 2007-01-31 20:07 Dain 閱讀(459) | 評論 (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;
}

如果一個參數可能在函數中指向不同的對象，或者這個參數可能不指向任何對象，則必須使用指針參數。
引用參數的一個重要用法，它允許有效地實現重載操作符的同時，還能保證用法的直觀性?？梢詤⒖肌禖++ Primer》

ps 發現書287頁的第二個程序例子是錯的

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