设为首页 加入收藏

TOP

ACM程序设计节课总结(三)
2017-06-20 10:22:47 】 浏览:500
Tags:ACM 程序设计 总结
可。以下是该题二分算法的关键实现代码:

bool fun(int mid)

{

int cnt=1;

int m=x[1];

for(int i=2; i<=N; i++)

{

if(x[i]-m>=mid)

{

cnt++;

m=x[i];

}

if(cnt>=C)

return true;

}

return false;

}

而三分查找法则是二分查找法的进阶,随实际问题而使用,三分查找法就是将一组单调的先用一次二分查找找到一个mid,然后在mid和极值点再找一个mid2,不停的缩小范围,直到得出结果。

2.5 贪心算法

贪心算法就是在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解,这种求解方法就是贪心算法。

从贪心算法的定义可以看出,贪心算法不是从整体上考虑问题,它所做出的选择只是在某种意义上的局部最优解,而由问题自身的特性决定了该题运用贪心算法可以得到最优解。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。老师说,贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法,通过一系列的选择得到一个问题的解,而它所做的每一次选择都是当前状态下某种意义的最好选择。即希望通过问题的局部最优解求出整个问题的最优解。这种策略是一种很简洁的方法,对许多问题它能产生整体最优解,但不能保证总是有效,因为它不是对所有问题都能得到整体最优解。以下便是贪心算法的一般流程:

//A是问题的输入集合即候选集合

Greedy(A)

{

S={ };//初始解集合为空集

while (not solution(S))//集合S没有构成问题的一个解

{

x = select(A);//在候选集合A中做贪心选择

if feasible(S, x)//判断集合S中加入x后的解是否可行

S = S+{x};

A = A-{x};

}

return S;

2.6 背包问题

背包问题就是给定一个载重量为M的背包,考虑n个物品,其中第i个物品的重量 ,价值wi (1≤i≤n),要求把物品装满背包,且使背包内的物品价值最大。背包问题分为两类(根据物品是否可以分割),如果物品不可以分割,称为0—1背包问题(使用动态规划);如果物品可以分割,则称为背包问题(使用贪心算法)。

解决背包问题的时候基本都要创建一个数据结构体bag:

struct bag

{

int w; //物品的重量

int v; //物品的价值

double c; //性价比

}a[1001]; //存放物品的数组

//形参n是物品的数量,c是背包的容量M,数组a是按物品的性价比降序排序

double knapsack(int n, bag a[], double c)

{

double cleft = c;        //背包的剩余容量

int i = 0;

double b = 0;          //获得的价值

//当背包还能完全装入物品i

while(i

{

cleft -= a[i].w;

b += a[i].v;

i++;

}

//装满背包的剩余空间

if (i

return b;

}

2.7 搜索专题

搜索分广度优先搜索和深度优先搜索,这两者的区别可以用一张图来分别,

广度优先搜索就是先将本行的所有情况遍历,再去遍历下一行,直到搜索到结果。而深度优先搜索是将一列所有的子状态遍历之后才会队同一层的下一个子状态进行遍历。这种算法可以在很多地方用到,是一种思想,不过在运用这种思想的时候要注意时间的问题,很容易超时。

2.8 图论

图论这一章是这学期最后所学的内容,将图与定义相结合,图论的内容就不会变得那么抽象,graph=(V,E)。V是一个非空有限集合,代表顶点(结点),E代表边的集合。

图也有遍历,并且可用广度优先搜索和深度优先搜索,从图中某一顶点出发系统地访问图中所有顶点,使每个顶点恰好被访问一次,这种运算操作被称为图的遍历。为了避免重复访问某个顶点,可以设一个标志数组visited[i],未访问时值为false,访问一次后就改为true。

图论中有最短路径算法:

初始化:点u、v如果有边相连,则dis[u][v]=w[u][v]。

  如果不相连则dis[u][v]=0x7fffffff

For (k = 1; k <= n; k++)

For (i = 1; i <= n; i++)

For (j = 1; j <= n; j++)

If (dis[i][j] >dis[i][k] + dis[k][j])

dis[i][j] = dis[i][k] + dis[k][j];

算法结束:dis[i][j]得出的就是从i到j的最短路径。

3、总结

经过一学期的ACM程序设计课程,我从费老师那里知道了山农现在ACM队的现状也不是太好。这学期有一次ACM程序设计省赛,但是我没去,经过半个学期的学习,我越发觉得自己的不足,所以觉得还是再学习一段时间,参加下一次的比赛吧,我相信学习ACM的同学都有一颗想要参加ACM程序设计大赛的心,ACM程序设计大赛是大学级别最高的脑力竞赛,素来被冠以"程序设计的奥林匹克"的尊称。大赛至今已有近40年的历史,是世界范围内历史最悠久、规模最大的程序设计竞赛。比赛形式是:从各大洲区域预赛出线的参赛队伍,于指定的时间、地点参加世界级的决赛,当然这需要极大的努力。在virtual judge上做题的时候感觉到题目的难度,有时候熬夜赶工只为了出那么一个题,老师所说的学这门课要牺牲大部分的业余时间大概就是这样吧,不过我感觉我还远远没有到达这种境界,还有些懒惰,做不来的题目,看别人做的要看很久才能明白。因此深深感到自己的不足,希望能参加暑假的集训来提高自己,只要这份热情还未泯灭,坚持,始终会在ACM的路上前行。

 

首页 上一页 1 2 3 下一页 尾页 3/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C++ 20道基础知识题 下一篇容器与算法

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目