c语言程序设计大赛资料

《c语言程序设计大赛资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、C语言程序设计大赛资料一：知识点数据结构：1，单，双链表及循环链表2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等）3，文件操作（从文本文件中读入数据并输出到文本文件中）4，图（基本概念，存储结构，图的运算）数学知识1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑）2，数论知识3，线性代数4，组合代数5，计算几何二算法1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序）2，查找（顺序查找，二分发）3，回溯算法4，递归算法5，分治算法6，模拟法7，贪心法8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法9，动态

2、规划的思想及基本算法10，高精度运算三、ACM竞赛的题型分析竞赛的程序设计一般只有16种类型，它们分别是：DynamicProgramming（动态规划）Greedy（贪心算法）CompleteSearch（穷举搜索）FloodFill（不知该如何翻译）ShortestPath（最短路径）RecursiveSearchTechniques（回溯搜索技术）MinimumSpanningTree（最小生成树）Knapsack（背包问题）ComputationalGeometry(计算几何学)NetworkFlow（网络流）EulerianPath（欧拉回路）Two-Dimensio

3、nalConvexHull（不知如何翻译）BigNums（大数问题）HeuristicSearch（启发式搜索）ApproximateSearch（近似搜索）AdHocProblems（杂题）四ACM竞赛参考书《实用算法的分析与程序设计》(吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法和程序设计》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学）《计算机算法设计与分析》（王晓东编著，最好的数据结构教材）《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材）《信息学奥林匹克竞赛指导――1

4、997-1998竞赛试题解析》(吴文虎，王建德著，清华大学出版社）《计算机程序设计技巧》D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大）39《计算几何》周陪德著《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社）《数学建模竞赛培训教材》共三本叶其孝主编《数学模型》第二版姜启源《随机规划》《模糊数学》《数学建模入门》徐全智《计算机算法设计与分析》国防科大五如何备战ACM/ICPC1，个人准备（算法书，习题集，网上做题和讨论）2，1000题=亚洲冠军=世界决赛3，做好资料收集和整理工作实验一：递归与分治实验目的理解递归算法的思想和递归

5、程序的执行过程，并能熟练编写递归程序。掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题：二分搜索、合并排序、快速排序。对本实验中的问题，设计出算法并编程实现。试验内容和步骤1．二分查找在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。程序略2．合并排序程序略3．快速排序程序略实验总结及思考合并排序的递归程序执行的过程实验二：回溯算法实验目的：熟练掌握回溯算法实验内容：回溯算法的几种形式a)用回溯算法搜索子集树的一般模式voidsearch(intm){

6、if(m>n)//递归结束条件output();//相应的处理(输出结果)else{a[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示要该物品search(m+1);//递归搜索：继续确定下一个物品}}b)用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i<=n;i++){39swap(m,i);//交换a[m]和a[i]if()if(canplace(m))//如果m处可放置sea

7、rch(m+1);//搜索下一层swpa(m,i);//交换a[m]和a[i](换回来)}}习题1．0-1背包问题在0/1背包问题中，需对容量为c的背包进行装载。从n个物品中选取装入背包的物品，每件物品i的重量为wi，价值为pi。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。程序如下：#includevoidreaddata();voidsearch(int);voidcheckmax();voidprintresult();i