数据结构与算法实验（2）-第11周（猜题版）

思路：虽然上课老师讲了四种方法（暴力、优化暴力、分治和一个不知道什么东西）

从全局来看，遍历整个数组，第i个元素的最大子序列只取决于自己和前面的最大子序列。取个最大值就行。这C语言真垃圾，max函数都没有
ps：题目中如果序列中所有整数皆为负数，则输出0这句话并没有用，也建议大家删去这句话

代码如下：

#include 
#include 
#include 

typedef long long int LL;

#define MAXN 250;

int get_max(int x,int y)
{
    return x>=y?x:y;
}
int main()
{
    int n;
    int a[100100];
    int res = -1e6, sum = 0;
    scanf("%d",&n);
    for(int i=0;i 
2-2 输出全排列 
本题考查DFS/递归 
思路：开两个数组深搜就完了，但是要注意输出空格和x是否等于n的判定 
ps：忽视我的注释
 
代码如下：
 
#include 
#include 
#include 
typedef long long int LL;
#define MAXN 250;
int n,v[15],a[15];
void DFS(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!v[i])
        {
            v[i] = 1;
            a[x] = i;
            if(x == n)
            {
                for(int j=1;j<=n;j++)
                {
                    printf("%d",a[j]);
                    if(j == n)printf("n");
                }
            }
            else
                DFS(x+1);
            v[i] = 0;

        }
    }
}
//int get_max(int x,int y)
//{
//    return x>=y?x:y;
//}
int main()
{
    scanf("%d",&n);
    DFS(1);
    return 0;
}


 
2-3 二分查找 (20 分) 
本题考查二分查找 
思路：直接二分就完了，我为了怕错（其实是自己菜）写了三个条件语句，实际上两个就够用了
 
代码如下：
 
Position BinarySearch(List L, ElementType X)
{
    if(L == NULL)return NotFound;
    int start = 1,end = L->Last;
    int mid;
    while(start<=end)
    {
        mid=(start + end)/2;
            if(X>L->Data[mid])start = mid + 1;
            else if (XData[mid]) end = mid - 1;
            else return mid;
    }
    return NotFound;
}
 
2-4 
本题考查 
思路：
 
代码如下：
 

 
2-5 
本题考查 
思路：
 代码如下：