• 找到分类:

  • 最大子段和

    05-19-19

    最大子段和问题

    一、问题描述:

    给定由n个整数组成的序列a_{1},a_{2},\cdots,a_{n},求该序列子段和的最大值。当所有整数均为负值时,定义其最大子段和为0.

    由此定义,可以得出所求的最优值为:

    \max \{0, \max\limits_{1 \leq i \leq j \leq n} \sum\limits_{k=i}^{j} a_{k} \}

    例如,当( a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6})=(-2,11,-4,13,5,-2)时,最大子段和为a_{2}+a_{3}+a_{4}=11-4+13=20

    二、一个简单算法

    int MaxSum(int n, int a[], int& besti, int& bestj)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                int thissum = 0;
                for (int k = i; k <= j; k++)
                    thissum += a[k];
                if (thissum > sum)
                {
                    sum = thissum;
                    besti = i + 1;
                    bestj = j + 1;
                }
            }
        return sum;
    }//时间复杂度O(n3)
    //main函数
    int main()
    {
        int a[] = { -2,11,-4,13,-5,-2 };
        int sum = 0, besti = 0, bestj = 0;
        sum = MaxSum(sizeof(a) / sizeof(int), a, besti, bestj);
        cout << "Sum from " << besti << " to " << bestj << endl;
        cout << "The sum is " << sum << endl;
        return 0;
    }

    运行结果:

    1558232847886814.png




    三、简单算法的改进

    int MaxSum(int n, int a[], int& besti, int& bestj) //简单算法的改进
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            int thissum = 0;
            for (int j = i; j < n; j++)
            {
                thissum += a[j];
                if (thissum > sum)
                {
                    sum = thissum;
                    besti = i + 1;
                    bestj = j + 1;
                }
            }
        }
        return sum;
    }//时间复杂度O(n2)

    运行结果:

    1558232894395881.png




    四、分治算法

    将最大子段和a[1:n]分为a[1:n/2]a[n/2 + 1:n]两段,则可能有以下三种情况:

    1) a[1:n]的最大子段和 = a[1:n/2]的最大子段和

    2) a[1:n]的最大子段和 = a[n/2 + 1:n]的最大子段和

    3) a[1:n]的最大子段和\sum\limits_{k=i}^{j}a_{k},1 \leq i \leq n/2, n/2+1 \leq j \leq n

    此时,可分别计算a[1:n/2]a[n/2 + 1:n]的最大子段和s1=\max\limits_{1 \leq i \leq n/2} \sum\limits_{k=i}^{n/2}a[k]s2=\max\limits_{n/2+1 \leq i \leq n} \sum\limits_{k=n/2+1}^{i}a[k]

    int MaxSubSum(int a[], int left, int right, int &besti, int &bestj)
    {
        int sum = 0;
        if (left == right) sum = a[left] > 0 ? a[left] : a[0]; //递归出口
        else
        {
            int center = (left + right) / 2;
            int leftsum = MaxSubSum(a, left, center,besti,bestj);
            int rightsum = MaxSubSum(a, center + 1, right,besti, bestj);
            int s1 = 0, lefts = 0;
            for (int i = center; i >= left; i--)
            {
                lefts += a[i];
                if (lefts > s1)
                {
                    s1 = lefts;
                    besti = i + 1;
                }
            }
            int s2 = 0, rights = 0;
            for (int i = center + 1; i <= right; i++)
            {
                rights += a[i];
                if (rights > s2)
                {
                    s2 = rights;
                    bestj = i + 1;
                }
            }
            sum = s1 + s2;
            if (sum < lefts) sum = leftsum;
            if (sum < rightsum) sum = rightsum;
        }
        return sum;
    }
    int main()
    {
        int a[] = { -2,11,-4,13,-5,-2 };
        int sum = 0, besti = 0, bestj = 0;
        
        sum = MaxSubSum(a, 0, 5, besti, bestj);
        cout << "Sum from " << besti << " to " << bestj << endl;
        cout << "The sum is " << sum << endl;
        return 0;
    }

    运行结果:

    1558232984320001.png




    复杂性分析:

    T(n)=\begin{cases}O(1), & \text{if} \quad n \leq c;\\2T(n/2)+O(n), & \text{if} \quad n > c\end{cases}

    即每个问题可以分为两个n/2的子问题,其中的O(n)为从center处遍历每个节点,求解最优解的过程。

    由主定理,可得出T(n) = O(nlogn)

    五、动态规划算法

    b_{j}=\max\limits_{1 \leq i \leq j}\sum\limits_{k=i}^{j}a_{k},(1 \leq j \leq n),表示a[1…j]的前j个元素中最大子段和,则b_{j-1}表示a[1…j-1]的前j-1个元素中的最大子段和,如下所示

    \underbrace{\overbrace{a_{1} \quad a_{2} \quad \cdots \quad a_{j-1}}^{b_{j-1}} \quad a_{j}}_{b_{j}} \quad \cdots \quad a_{n}

    显然,当b_{j-1}>0时,b_{j}=b_{j-1}+a_{j};b_{j-1} \leq 0时,放弃前面选取的元素,从a_{j}开始重新选取,b_{j}=a_{j}。用一维动态规划数组dp存放b,对应的状态方程如下

    \begin{cases}dp[0]=0 &\\dp[j]=\max\{dp[j-1]+a_{j},a_{j}\}, & 1 \leq j \leq n\end{cases}

    则序列a的最大子段和等于\max\limits_{1 \leq j \leq n}dp[j]

    从中看到,若序列a的最大子段和等于dp[maxj],在dp中从该位置向前找,找到第一个值小于或等于0的元素dp[k],则a序列中从k+1开始到maxj位置的所有元素恰好构成最大子段和序列。

    例如,若a序列为(-2,11,-4,13,-5,-2)dp[0]=0,求其他元素如下:

    1dp[1]=max{dp[0]+(-2),-2}=max{-2,-2}=-2

    2dp[2]=max{dp[1]+11,11}=max{9,11}=11

    3dp[3]=max{dp[2]+(-4),-4}=max{7,-4}=7

    4dp[4]=max{dp[3]+13,13}=max{20,13}=20

    5dp[5]=max{dp[4]+(-5),-5}=max{15,-5}=15

    6dp[6]=max{dp[5]+(-2),-2}=max{13,-2}=13

    其中,dp[4]=20为最大值,向前找到dp[1]小于等于0,所以由a_{2}~a_{4}的元素即(11,-4,13)构成最大子段和,其和为20

    #include<iostream>
    using namespace std;
    #define max(x,y) ((x)>(y) ? (x):(y))
    #define MAXN 20
    //问题表示
    int n = 6;
    int a[] = { 0,-2,11,-4,13,-5,-2 }; //a[0]不使用
    int dp[MAXN];
    //求dp数组
    void maxSubSum()
    {
        dp[0] = 0;
        for (int i = 1; i <= n; i++)
            dp[i] = max(dp[i - 1] + a[i], a[i]);
    }
    //输出结果
    void dispmaxSum()
    {
        int maxj = 1;
        int k = 0; //k用于存放dp中从maxj向前遍历,第一个值小于等于0的下标
        for (int j = 2; j <= n; j++)
            if (dp[j] > dp[maxj])
                maxj = j;
        for (k = maxj; k >= 1; k--)
            if (dp[k] <= 0)  break;
        cout << "最大子段和:" << dp[maxj] << endl;
        cout << "所选子段:";
        for (int i = k + 1; i <= maxj; i++)
            cout << a[i] << " ";
        cout << endl;
    }
    int main()
    {
        maxSubSum();
        cout << "求解结果如下" << endl;
        dispmaxSum();
        return 0;
    }

    运行结果:

    1558233095570238.png

  • C++ 笔记2

    05-03-19

    C++ 笔记2 文件读写

    可以将顺序文件看作一个有限字符构成的顺序字符流,然后像对cin,cout一样的读写。回顾下输入输出流的层次结构。

    1556815037308328.png






    (一)、创建文件

    #include<fstream> //包含头文件

    l  方式1:定义ofstream,在构造函数中给出参数

    ofstream outFile(“clients.dat”,ios::out|ios::binary);

    -clients..dat         要创建的文件的名字

    -ios::out               文件打开方式

           ios::out         输出到文件,删除原有内容

           ios::app        输出到文件,保留原有内容,总是在尾部添加(app - append

    -ios::binary          以二进制方式打开文件

    l  方式2:创建ofstream对象,再用open函数打开

    ofstream fout; //创建ofstream对象

    fout.open(“test.out”,ios::out|ios::binary);

    判断打开是否成功

    if(!fout){
           cout<<”File open error!”<<endl;
    }

    文件名可以给出绝对路径,也可以给出相对路径。没有交代路径信息,就是在当前文件夹下寻找。

    l  绝对路径

    e.g. “c:\\tmp\\mydir\\some.txt”

    l  相对路径

    Ø  “\\tmp\\mydir\\some.txt”        

    当前盘符的根目录下的tmp\dir\some.txt

    Ø  “tmp\\mydir\\some.txt”           

    当前文件夹的tmp子文件夹里面的

    Ø  “..\\ tmp\\mydir\\some.txt”     

    当前文件夹的父文件夹下面的tmp子文件夹里面的

    Ø  “..\\..\\ tmp\\mydir\\some.txt” 

    当前文件夹的父文件夹的父文件夹下面的tmp子文件夹里面的

     

    (二)、文件的读写指针

    对于输入文件,有一个读指针;对于输出文件,有一个写指针;对于输入输出文件,有一个读写指针;指针的作用即为,标识文件操作的当前位置,该指针在哪里,读写操作就在哪里进行。

    l  写操作

    tellp()取得写指针位置 seekp(location)向指定位置写入

    ofstream fout(“a1.out”,ios::app); //以添加方式打开

    long location = fout.tellp(); //取得写指针的位置

    location p = 10;

    fout.seekp(location); //将写指针移动到底10个字节处

    fout.seekp(location, ios::beg); //从头部数location个字节 (beg-begin)

    fout.seekp(location, ios::cur); //从当前位置数location个字节 (cur-current)

    fout.seekp(location, ios::end); //从尾部数location个字节 (这种情况下location0)

    l  读操作

    tellg()取得读指针位置 seekg(location)从指定位置读

    ifstream fin(“a1.in”,ios::ate); //打开文件,定位文件指针到文件尾(ate-at end)

    long location = fin.tellg(); //获取读指针的位置,从而可以获取文件长度

    location = 10;

    fin.seekg(location); //将头指针移动到低10个字节处

    fin.seekg(location, ios::beg); //从头部数location个字节

    fin.seekg(location, ios::cur); //从当前位置数location个字节

    fin.seekg(location, ios::end); //从尾部数location个字节

    l  显示关闭文件

    ifstream fin(“test.dat”, ios::in);

    fin.close();

     

    ofstream fout(“test.dat”, ios::out);

    fout.close();


    (三)、文件读写

    1.字符文件读写

    因为文件也是流,所以流的成员函数和流操作算子也同样适用于文件流。

    e.g. 1.写一个程序,将文件in.txt里面的整数排顺后,输出到out.txt

    #include<iostream>
    #include<fstream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int main()
    {
        vector<int> v;
        ifstream srcFile("in.txt",ios::in);
        ofstream destFile("out.txt",ios::out);
        int x;
        while (srcFile >> x)
            v.push_back(x);
        sort(v.begin(),v.end());
        for(int i = 0; i < v.size(); i++)
            destFile<<v[i]<<" ";
        destFile.close();
        srcFile.close();
        return 0;
    }

    运行结果:

    1556815273454791.png






    1556815226116977.png





    2.二进制文件读写

    a.从文件读入内存

    ifstreamfstream的成员函数:

    istream& read (char* s, long n);

    将文件读指针指向的地方的n个字节的内容,读入到内存地址s,然后将文件读指针向后移动n字节。

    b.从内存写入文件

    ofstreamfstream的成员函数:

    istream& write(const char* s, long n);

    将内存地址s处的n个字节内容,写入到文件中写指针指向的位置,然后将文件写指针向后移动n字节。

     

    e.g. 1.从键盘输入几个学生的姓名的成绩,并以二进制文件形式保存

    #include<iostream>
    #include<fstream>
    using namespace std;
    struct Student{
        char name[20];
        int score;
    };
    int main()
    {
        Student s;
        ofstream OutFile("students.dat",ios::out|ios::binary);
        while(cin>>s.name>>s.score)
            OutFile.write((char *) & s, sizeof(s) );
    //(char *) & s表示取s的地址,并转为char*类型
        OutFile.close();
        return 0;
    }

    输入:

    Tom 60

    Jack 80

    Peter 100

    ^Z + 回车

    运行结果:

    1556815368897534.png





    当前文件夹下生产student.dat文件,且为72字节(20B+4B*3 = 72B

    1556815412538921.png





    使用记事本打开,呈现:

    1556815432125292.png




    使用sublime text3打开,呈现:

    1556815452575721.png









    会发现其以二进制形式存储,3C(16)对应分数60(10)50(16)对应分数80(10) 64(16)对应分数100(10).

    还可以发现,这里是以大端模式进行存储的。(即数据的高字节,在内存的低地址;数据的低字节,在内存的高地址)


    e.g. 2.student.dat文件的内容读出并显示出来

    #include<iostream>
    #include<fstream>
    using namespace std;
    struct Student{
        char name[20];
        int score;
    };
    int main()
    {
        Student s;
        ifstream inFile("students.dat",ios::in|ios::binary);
        if(!inFile){
            cout<<"Error."<<endl;
            return 0;
        }
        while(inFile.read((char* ) &s, sizeof(s) )){
            cout<<s.name<<" "<<s.score<<endl;
        }
        inFile.close();
        return 0;
    }

    运行结果:
    1556815574228819.png

  • C++ 笔记1

    05-02-19

    C++ 笔记1 输入输出相关的类及流操纵算子

    学C++有一年多的时间了,当时有些东西理解不够深入,也忘记了好多细节的部分,于是出了C++笔记这个专辑吧,哈哈哈!

    一、输入输出

    (一)、与输入输出有关的类

    1556727022247958.png
















    istream是用于输入的流类,cin(读作see-in)就是该类的对象

    ostream是用于输出的流类,cout(读作see-out)就是该类的对象

    ifstream是用于从文件读取数据的类

    ofstream是用于向文件写入数据的类

    iostream是既能用于输入,又能用于输出的类

    (二)、标准流对象

    输入流对象:cin与标准输入设备相连

    输出流对象:cout与标准输出设备相连

    cerr与标准错误输出设备相连

    clog与标准错误输出设备相连

    缺省情况下:
               cerr<<”Hello, world”<<endl;

               clog<<”Hello, world”<<endl;

               cout<<”Hello, world”<<endl;

               三者一样

    1.cin对应与标准输入流,用于从键盘读取数据,也可以被重定向为从文件中读取数据。

    2.cout对应于标准输出流,用于向屏幕输出数据,也可以被重定向为向文件中写入数据。

    3.cerr对应于标准错误输出流,用于向屏幕输出出错误信息。

    4.clog对应于标准错误输出流,用于向屏幕输出出错误信息。

    Notice:cerr和clog的区别在于cerr不使用缓冲区,直接向屏幕输出信息;而clog中的信息会先被存放在缓冲区,缓冲区满或者刷新时才输出到屏幕。

    (三)、判断输入流结束

    可以用如下方法判断输入流结束

    int x;
    while(cin>>x){
        …
    }

    如果是从文件输入,则读到文件尾部,输入流就算结束

    如果是从键盘输入,Windows系统中,在单独的一行输入Ctrl+Z代表输入流结束;在Unix(包括Mac OS X) 系统中,在单独的一行输入Ctrl+D代表输入流结束。

    (四)、输出重定向

    #include<iostream>
    using namespace std;
    int main()
    {
        double x, y;
        freopen("text.txt","w",stdout); //将标准输出重定向到text.txt文件
        if(y == 0) //除数为0则在屏幕上输出错误信息
            cerr<<"error."<<endl;
        else
            cout<<x/y<<endl; //输出结果到text.txt
        return 0;
    }

    运行结果:

    1556727174744279.png





    1556727192794316.png






    Question:怎样将stdout重定向到屏幕?

    Answer:C标准库的回复是:不支持。没有任何方法可以恢复原来的输出流。

    那是否存在依赖具体平台的实现呢?存在。在操作系统中,命令行控制台(即键盘或者显示器)被视为一个文件,既然是文件,那么就有“文件名”。由于历史原因,命令行控制台文件在DOS操作系统和Windows操作系统中的文件名为"CON",在其它的操作系统(例如Unix、Linux、Mac OS X、Android等等)中的文件名为"/dev/tty"。因此,在Windows中可以使用freopen( "CON", "w", stdout );其它操作系统中使用:freopen( "/dev/tty", "w", stdout );

    (五)、输入重定向

    #include<iostream>
    using namespace std;
    int main()
    {
        double f;
        int n;
        freopen("t.txt","r",stdin); //cin被改为从t.txt中读取数据
        cin>>f>>n;
        cout<<f<<" "<<n<<endl;
        return 0;
    }

    运行结果:

    1556727229429865.png


    1556727773122328.png




    二、流操纵算子

    l  整数流的基数:流操纵算子dec(十进制),oct(八进制),hex(十六进制),setbase(指定进制)

    l  浮点数的精度(precision, setprecision)

    l  设置域宽(setw, width)

    l  用户自定义的流操纵算子

    Notice:使用流操纵算子需要#include<iomanip>

    (一)、整数流的基数

    #include<iostream>
    using namespace std;
    int main()
    {
        int n = 10;
        cout<<n<<endl;
        cout<<hex<<n<<endl;
        cout<<dec<<n<<endl;
        cout<<oct<<n<<endl;
        return 0;
    }

    运行结果:

    1556727304832367.png






    (二)、控制浮点数精度的流操纵算子

    precision, setprecision

    l  precision是成员函数,其调用方式为:

    cout.precision(5);

    l  setprecision是流操纵算子,其调用方式为:

    cout<<setprecision(5);//可以连续输出

    它们的功能相同:

    1.指定输出浮点数的有效位数(非定点方式输出时)

    2.指定输出浮点数的小数点的后的有效位数(定点方式输出时)

    定点方式:小数点必须出现在个位数后面

    e.g.以浮点数输出最多6位有效数字

    #include<iostream>
    #include<iomanip>
    using namespace std;
    int main()
    {
        double x = 1234567.89, y = 12.34567;
        int n = 1234567;
        int m = 12;
        cout<<setprecision(6)<<x<<endl;
        cout<<y<<endl;
        cout<<n<<endl;
        cout<<m<<endl;
        return 0;
    }

    运行结果:

    1556727332374762.png





    e.g.以小数点位置固定的方式输出 setiosflags(ios::fixed)

    #include<iostream>
    #include<iomanip>
    using namespace std;
    int main()
    {
        double x = 1234567.89, y = 12.34567;
        int n = 1234567;
        int m = 12;
        cout<<setiosflags(ios::fixed)<<setprecision(6)<<x<<endl;
        cout<<y<<endl;
        cout<<n<<endl;
        cout<<m<<endl;
        return 0;
    }

    运行结果:

    1556727390900712.png





    e.g.取消以小数点位置固定的方式输出 resetiosflags(ios::fixed)

    #include<iostream>
    #include<iomanip>
    using namespace std;
    int main()
    {
        double x = 1234567.89;
        cout<<setiosflags(ios::fixed)<<setprecision(6)<<x<<endl;
        cout<<resetiosflags(ios::fixed)<<x<<endl;
        return 0;
    }

    运行结果:

    1556727416382954.png




    (三)、设置宽域的流操纵算子

    setw,width

    两者功能相同,一个是成员函数,另一个是流操纵算子,调用方式不同

    cin>>setw(4);或者cin.width(5);

    cout<<setw(4);或者cout.width(5);

    e.g.

    #include<iostream>
    #include<iomanip>
    using namespace std;
    int main()
    {
        int w = 4;
        char string[10];
        cin.width(5);
        while (cin>>string)
        {
            cout.width(w++);
            cout<<string<<endl;
            cin.width(5);
        }
        return 0;
    }

    Notice:宽度设置有效性是一次性的,在每次读入和输出之前都要设置宽度。

    1556727477274358.png





    分析:

    首先执行while时1234会被读入string(因为还有’\0’),此时w=4并显示,之后w++,w=5,接着从输入流读取数据到string,因为刚才输入流为1234567890,其中1234已被读入,所以5678被读入string并显示,后面同理。

    (四)、用户自定义流操纵算子

    #include<iostream>
    #include<ostream>
    using namespace std;
    ostream &tab(ostream &output)
    {
        return output<<'\t';
    }
    int main()
    {
        cout<<"aa"<<tab<<"bb"<<endl;
        return 0;
    }

    运行结果:

    1556727513526663.png