算法第三章上机实践报告

1.1 问题描述

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

输入格式:

输入有两行：

第一行是n值（1<=n<=10000)；

第二行是n个整数。

输出格式:

输出最大子段和。

输入样例:

在这里给出一组输入。例如：

6
-2 11 -4 13 -5 -2

输出样例:

在这里给出相应的输出。例如：

20

1.2 算法描述

设置一个b[j]数组为前j项的最大子段和,a[j]数组存放元素。若b[j-1]大于等于0时，则b[j]=b[j-1]+a[j]；否则b[j]=a[j]。

1.3 问题求解：

#include<iostream>
using namespace std;
int main()
{
int N;
cin>>N;
int list[N];
for(int i=0;i<N;i++)
{
cin>>list[i];
}
int sum1 = 0;
// int endi=0,endj=0;
for(int i=0;i<N;i++)
{
int sum2 = 0;
for(int j=i;j<N;j++){
sum2 += list[j];
if(sum2>sum1)
{
sum1=sum2;
// endi=i;
// endj=j;
}
}
}
cout<<sum1<<endl;
}

1.1.1 根据最优子结构性质，列出递归方程式，

b[j]=max{b[j-1]+a[j],a[j]}  1<=j<=n

1.1.2 给出填表法中表的维度、填表范围和填表顺序。

表为一维表格，填表范围为n-1，填表顺序是从b[1]填到b[n].

1.1.3 分析该算法的时间和空间复杂度

时间复杂度：O(n);

空间复杂度：O(n);

1.3 心得体会（对本次实践收获及疑惑进行总结）

动态规划关键是弄清楚递归规律，然后总结递归方程式，填表的顺序以及边界条件都可以从递归方程式写起。动态规划解题步骤：分析结构，建立递归方程式，计算最优值，构造最优解，重叠子问题保存在表格中（涉及填表和边界条件）

2. 你对动态规划算法的理解和体会

我觉得动态规划是算法中的一个重难点，最好的学习办法就是先把书上的例子想清楚，再根据我们的编程题一步一步解决问题，遇到不懂得说明这一块没有弄清楚。动态规划算法的难点在于找到初始题的子问题是什么，以及知道递归方程是什么和对边界条件的判断。

算法第二章上机实践报告

实践题目名称

二分搜索（分治法）

 问题描述

输入格式:

第一行为n值(n<=1000)和x值；第二行为n个整数。

输出格式:

如果找到x，输出x的下标；否则，输出-1

输入样例:

5 2
5 4 3 2 1

输出样例:

3

算法时间及空间复杂度分析

 时间复杂度：采取的是二分算法。分解子问题的时间复杂度为O（1），解决各个子问题的时间复杂度为O（n/2）所以总时间复杂度为O（logn）

空间复杂度：采取了递归算法。空间复杂度为O（logn）

问题求解

#include<iostream>
using namespace std;

int bsearch(int x,int a[],int left,int right)
{
　　if(left>right)
　　　　return -1;
　　int mid=(left+right)/2;
　　if(x==a[mid])
　　　　return mid;
　　if(x<a[mid])
　　　　return bsearch(x,a,mid+1,right);
　　else
　　　　return bsearch(x,a,left,mid-1);
}
int main()
{
　　int n,x;
　　int a[10];
　　cin >> n >> x;
　　for(int i=0;i<n;i++)
　　{
　　　　cin >> a[i];
　　}
　　cout << bsearch(x,a,0,n-1);
}

 心得体会

分治思想非常常用，主要的解题思想就是，将一个问题分解成多个子问题，子问题最好要比原问题解决方法简单。最后记得将所有已解决的子问题合并。这才是最终解。可以通过编程题总结什么情况下可以采用分治法，解题步骤以及注意点也可多总结。

分治法的个人思考

这道题目不用分治思想也可以做出，但是分治思想很好的将问题逻辑化，解决步骤虽然比普通的方法看起来繁琐，但是在数量非常多的情况下，分治法可以很大程度上降低时间复杂度