西工大算法复习资料总结(最终修订版)

西北工业大学VC程序设计总复习VC++程序设计总复习主要内容小结第一章程序设计与VC语言简介1、程序设计方法的演变：结构化、面向对象2、VC语言概述：C语言、C++及VC的关系、VC控制台程序的概念、标准设备的输入与输出语句cin和cout的使用。

第二章VC程序设计基础——变量与函数1、变量的作用域：变量的6种作用域(块、函数、类、命名空间、文件、程序)的含义和用法。

2、变量的生存期：分为静态生存期和动态生存期，什么样的变量具有哪一种生存期？3、数组指针与指针数组的区别4、new和delete运算5、引用的含义6、函数参数的传递方式：值传递、地址传递、引用传递第三章类与对象1、面向对象程序设计的特点：抽象、封装、继承、多态。

2、类定义的格式：成员变量和成员函数3、静态成员变量和函数：关键字tatic、静态成员变量和函数的特点。

4、类成员的访问控制权限：public、protected、priviate(默认)5、构造函数和析构函数6、类的继承：继承成员的访问控制规则P60页表3.1、会编写简单的含义继承的代码。

7、类的多态：类型(编译时多态和运行时多态)8、编译时多态的两种方式：函数重载和运算符重载。

9、虚函数和纯虚函数的概念。

第四章Window程序设计的基本概念1、win32编程的特点：消息驱动、应用程序与操作系统紧密相连、图形界面。

2、常见文件扩展名所代表的含义：.h头文件.cpp源程序文件.dw工作区文件.rc资源文件第七章MFC编程的基础知识1、MFC的含义：MicrooftFoundationCla微软基础类库2、MFC类库中的根类是什么？CObject3、MFC应用程序类型有三个：单文档、多文档、基于对话框4、单文档的应用程序框架会自动生成哪些类？View、Doc、MainFrame、App类。

第八章利用CDC类实现绘图程序1、利用MFC编写绘图程序的基本步骤：1)建立MFC单文档工程2)在view类的OnDraw函数中编写绘图代码。

算法的知识点总结算法的知识点非常广泛，涉及到数学、计算机科学、逻辑学等多个领域。

本文将从算法的基本概念、常用算法思想、数据结构和算法的关系以及一些常用的算法进行总结介绍。

一、算法的基本概念1. 算法的定义算法是一种解决问题的方法或技巧，它是一个有序的、确定性的操作序列，用来解决特定的问题或完成特定的任务。

算法可以描述为一系列的步骤，每个步骤都能够被清晰地描述，并且能够按照一定的顺序执行。

2. 算法的特性（1）输入：算法需要接受一些输入数据来解决问题。

（2）输出：算法需要产生一个输出来解决问题。

（3）确定性：算法的每一步骤都必须是明确的，没有二义性。

（4）有限性：算法必须在有限步骤内结束。

3. 算法的评价标准（1）时间复杂度：衡量算法执行所需的时间的指标，通常使用大O表示法来描述。

（2）空间复杂度：衡量算法所需的空间资源的指标，通常使用占用空间的增长率来描述。

二、常用算法思想1. 贪心算法贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望通过局部最优解最终达到全局最优解。

贪心算法通常适用于解决最优化问题，但不能保证一定能得到全局最优解。

例如，找零钱时，可以采用贪心算法，选择面值最大的硬币，直到找零完成。

2. 动态规划动态规划是一种具有重叠子问题和最优子结构性质的解决问题的方法。

动态规划通常适用于不同阶段的决策问题，它将问题分解为若干个相互重叠的子问题，然后按照一定的顺序求解子问题从而得到原问题的最优解。

例如，最长递增子序列、背包问题等都可以使用动态规划来解决。

3. 分治算法分治算法是一种将问题分解成一些小的子问题，然后递归地解决这些子问题，最后将这些子问题的解合并起来得到原问题的解。

分治算法通常包括三个步骤：分解，解决子问题，合并子问题的解。

例如，归并排序、快速排序等都是基于分治思想的算法。

4. 回溯算法回溯算法是一种在解决约束满足问题时的穷举搜索技术，它通过递归地搜索所有可能的解来找到满足约束的解。

大学计算机科学算法知识点归纳总结计算机科学的一个重要分支就是算法，它是解决问题的具体步骤和方法的集合。

通过学习和掌握算法知识，我们可以更加高效地解决各种问题。

本文将对大学计算机科学中常见的算法知识点进行归纳总结。

一、排序算法排序算法是计算机科学中最基本也是最常用的算法之一。

它将一组元素按照特定的规则进行重新排列。

以下是几种常见的排序算法：1. 冒泡排序（Bubble Sort）冒泡排序通过相邻元素的比较和交换来实现排序，每一轮将最大的元素冒泡到末尾。

2. 插入排序（Insertion Sort）插入排序通过将元素逐个插入已经有序的部分来实现排序。

3. 快速排序（Quick Sort）快速排序是一种基于分治法的排序算法，通过选择一个基准元素和其它元素进行比较和交换来实现排序。

4. 归并排序（Merge Sort）归并排序是一种基于分治法的排序算法，将待排序序列分为若干个子序列，分别进行排序后再合并。

二、查找算法查找算法是在给定的数据集合中找到指定元素的算法。

以下是几种常见的查找算法：1. 顺序查找（Sequential Search）顺序查找是一种逐个比较的查找算法，从列表的开头依次比较每个元素，直到找到目标元素或遍历完整个列表。

2. 二分查找（Binary Search）二分查找是一种基于分治法的查找算法，通过将待查找的区间不断缩小，最终找到目标元素。

三、图算法图是由节点和边组成的一种数据结构，图算法是解决图相关问题的一种算法。

以下是几种常见的图算法：1. 深度优先搜索（Depth First Search）深度优先搜索是一种遍历和搜索图的算法，它以深度优先的方式访问节点。

2. 广度优先搜索（Breadth First Search）广度优先搜索是一种遍历和搜索图的算法，它以广度优先的方式访问节点。

3. 最小生成树（Minimum Spanning Tree）最小生成树是一个无环连通子图，它是图中边的一种子集，使得树上所有边的权值之和最小。

算法主要知识点总结算法的主要知识点包括算法的概念、算法的特性、算法的分类、算法的实现、算法的分析和算法的应用。

下面我们逐一介绍这些知识点。

一、算法的概念算法是指针对特定问题而设计出来的一系列解决方案，它描述了如何通过有限的步骤来实现特定的目标。

算法包括输入、输出、确定性、有限性和有效性五个基本要素。

输入是算法的参数，输出是算法解决问题的结果，确定性是指算法每一步都清晰明确，无歧义，在相同的输入下产生相同的输出，有限性是指算法必须在有限的步骤内结束，有效性是指算法必须解决实际问题。

二、算法的特性算法的特性包括正确性、可读性、健壮性、高效性和可维护性。

正确性是指算法的输出与预期结果一致，可读性是指算法具有清晰明了的结构，易于理解和维护，健壮性是指算法能够处理各种异常情况，高效性是指算法在合理的时间和空间内完成任务，可维护性是指算法易于修改和更新。

三、算法的分类算法按照问题解决的方式可以分为递归算法和迭代算法，按照解决问题的途径可以分为贪心算法、分治算法、动态规划算法和回溯算法，按照解决问题的性质可以分为排序算法、查找算法、图算法、字符串算法等。

四、算法的实现算法可以用自然语言描述，也可以用流程图、伪代码、程序设计语言的形式来表示。

在实际应用中，我们通常使用编程语言来实现算法，如C、C++、Java、Python等。

五、算法的分析算法的分析是指在算法的设计和实现阶段对算法进行评估和比较。

主要包括时间复杂度和空间复杂度两个方面。

时间复杂度是指算法执行所需的时间与输入规模之间的关系，空间复杂度是指算法所需的存储空间与输入规模之间的关系。

通常用大O表示法来表示时间复杂度和空间复杂度。

六、算法的应用算法广泛应用于计算机科学、信息技术、人工智能、金融、生物信息学、物理学、化学、医学等领域。

例如，在计算机科学中，算法用于解决图论、网络流、最短路径等问题，在金融领域，算法用于股票交易、风险管理等问题，在生物信息学中，算法用于基因序列分析、蛋白质结构预测等问题。

算法知识点总结第二章1.算法定义2.算法五个特性及五个步骤3.大O、Ω、 证明第四章分治法1.分治法的步骤及其抽象化控制2.知道检索算法和分类排序算法最坏时间复杂度，并知道原因3.SELECT算法最坏和平均复杂度和SELECTS的平均时间复杂度4.二次取中值规则5.特斯拉矩阵乘法算法复杂度6.递推关系式的推导第五章贪心法本章重点是四个定理的证明，以及背包问题求解过程和两个作业排序问题。

1.定理5.1，5.2，5.3，5.4的证明注：定理5.2证明要点：I.贪心解J和最优解I是不包含关系II. a是属于J但不属于I的最大效益作业，b是属于I但不属于J的作业，则Pa>PbIII.J和I相同作业可以安排在同一时间处理IV.考虑I-{b}U{a}效益增加。

连续替换，同一法。

2.背包问题的算例，注意先排序再求解。

3.一台处理机的作业排序问题算例和算法实现。

注意先排序再求解。

4.两台处理机的作业排序问题。

了解其原理：在两台设备上处理的任务若不按相同作业排列次序处理，则所需时间不比按相同次序处理少。

会算F(S)和MTF(S)。

第六章动态规划本章重点是六个算例1.最优性原理以及不能用此原理的一些问题举例2.多段图问题3.0/1背包问题4.任意两点的最短路，会算A，P矩阵5.最优二分检索，同时知道其算法复杂度，以及高德纳采用何种方式降低算法复杂度的6.货郎担问题7.可靠性设计第八章回溯法本章重点掌握黑体字概念，皇后问题，以及状态空间树生成过程，注意不同方法结点编号不一样----深度优先，D-检索，宽度优先。

注意：六、七、八皇后的状态空间树结点总数分别是1957、13700、109601个（书本给的8皇后结果不对）以及教程P203页图8.8第四个样例(8,6,4,2,1,1,1) = 1 + 8 + 48 + 192 + 384 * 4 = 1785第九章分支-界限法1.黑体字的概念2.结点成本函数定义3.15-谜问题可达判断以及搜索过程图4.分枝法失效（不能找到最小成本的结点）的原因及其改进方法5.带罚款的作业排序问题注：重点是概念、15-谜问题和带罚款的作业排序问题第十章NP问题本章掌握定义，能判断某个特定问题是哪类问题1.不确定性算法定义2.P问题和NP问题的定义3.可满足问题(SAT问题)的定义4.COOK定理：SAT在P内当且仅当P=NP5.约化定义6.NP-Hard问题和NP-完全问题定义，会画P、NP、NP-C和NP-Hard问题的维恩图结语：复习时，书本上的算例一定要仔细看！算例占了一半左右的分数。

一、基础知识部分1. 算法的复杂性有时间复杂性和空间复杂性之分。

2. 算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。

3. 快速排序算法是基于分治策略的一种排序算法。

4. 矩阵连乘问题的算法可由动态规划设计实现。

5、算法是指解决问题的一种方法或一个过程。

6、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。

7、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

8、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

9. 贪心算法的基本要素是贪心选择质和最优子结构性质。

10. 动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。

11、合并排序算法是利用（A ）实现的算法A、分治策略B、动态规划法C、贪心法D、回溯法12、下列不是动态规划算法基本步骤的是（ A ）。

A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解13．下列算法中通常以自底向上的方式求解最优解的是（ B ）。

A、备忘录法B动态规划法C、贪心法D回溯法14. 备忘录方法是那种算法的变形。

（B ）A、分治法B动态规划法C、贪心法D回溯法15．最长公共子序列算法利用的算法是（ B ）。

A、分支界限法B动态规划法C贪心法D回溯法16．贪心算法与动态规划算法的主要区别是（ B ）。

A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解17. （D ）是贪心算法与动态规划算法的共同点。

A、重叠子问题B、构造最优解C、贪心选择性质D最优子结构性质18. 矩阵连乘问题的算法可由（B ）设计实现。

A、分支界限算法 B 、动态规划算法C、贪心算法D、回溯算法19、使用分治法求解不需要满足的条件是（ A ）。

A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解20．下列是动态规划算法基本要素的是（ D ）。

算法期末知识点总结算法是计算机科学的核心，它是解决问题的一种方法，其目的是找到一种有效的方式来解决特定的计算问题。

为了更好地理解算法，我们需要熟悉一些基本的概念和知识点。

在这篇文章中，我将总结一些算法的期末考试知识点，并对这些知识点进行详细的解释和举例。

数据结构数据结构是算法的基础，它是一种将数据组织和存储在计算机内存中的方式。

常见的数据结构有数组、链表、堆栈、队列、树、图等。

数据结构有着不同的特点和适用场景，我们需要根据具体的问题选择合适的数据结构。

举例：数组是一种连续存储数据的数据结构，可以通过索引快速访问元素，但插入和删除操作效率较低。

链表是一种非连续存储数据的数据结构，插入和删除操作效率较高，但访问元素的效率较低。

算法分析算法分析是评估算法效率的过程，它包括时间复杂度和空间复杂度的分析。

时间复杂度是一种衡量算法执行时间的方式，通常用大O符号表示。

空间复杂度是一种衡量算法所需存储空间的方式。

举例：假设有一个数组a，长度为n。

如果我们遍历数组a，求和并打印，那么该算法的时间复杂度为O(n)，空间复杂度为O(1)。

排序算法排序算法是一种将数据按照特定顺序排列的算法，常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等。

举例：快速排序是一种高效的排序算法，其原理是选择一个基准元素，将小于基准的元素放到基准的左边，大于基准的元素放到基准的右边，然后递归地对左右子数组进行排序。

搜索算法搜索算法是一种找到特定数据的算法，常见的搜索算法有线性搜索、二分搜索、哈希表等。

举例：二分搜索是一种高效的搜索算法，其原理是选择数组中间的元素与目标值进行比较，如果相等则返回元素的索引，如果小于目标值则在右半部分继续搜索，如果大于目标值则在左半部分继续搜索。

图算法图是一种由顶点和边组成的数据结构，图算法是一种解决图问题的算法，常见的图算法有深度优先搜索、广度优先搜索、最短路径算法、最小生成树算法等。

举例：广度优先搜索是一种搜索算法，其原理是从图的某个顶点开始，依次访问其相邻的顶点，直到访问到所需的顶点为止。

西北工业大学POJ答案绝对是史上最全版（不止100题哦……按首字母排序）1.“1“的传奇2.A+B3.A+BⅡ4.AB5.ACKERMAN6.Arithmetic Progressions7.Bee8.Checksum algorithm9.Coin Test10.Dexter need help11.Double12.Easy problem13.Favorite number14.Graveyard15.Hailstone16.Hanoi Ⅱ17.Houseboat18.Music Composer19.Redistribute wealth20.Road trip21.Scoring22.Specialized Numbers23.Sticks24.Sum of Consecutive25.Symmetric Sort26.The Clock27.The Ratio of gainers to losers28.VOL大学乒乓球比赛29.毕业设计论文打印30.边沿与内芯的差31.不会吧，又是A+B32.不屈的小蜗33.操场训练34.插入链表节点35.插入排序36.插入字符37.成绩表计算38.成绩转换39.出租车费40.除法41.创建与遍历职工链表42.大数乘法43.大数除法44.大数加法45.单词频次46.迭代求根47.多项式的猜想48.二分查找49.二分求根50.发工资的日子51.方差52.分离单词53.分数拆分54.分数化小数55.分数加减法56.复数57.高低交换58.公园喷水器59.韩信点兵60.行程编码压缩算法61.合并字符串62.猴子分桃63.火车站64.获取指定二进制位65.积分计算66.级数和67.计算A+B68.计算PI69.计算π70.计算成绩71.计算完全数72.检测位图长宽73.检查图像文件格式74.奖金发放75.阶乘合计76.解不等式77.精确幂乘78.恐怖水母79.快速排序80.粒子裂变81.链表动态增长或缩短82.链表节点删除83.两个整数之间所有的素数84.路痴85.冒泡排序86.你会存钱吗87.逆序整数88.排列89.排列分析90.平均值函数91.奇特的分数数列92.求建筑高度93.区间内素数94.三点顺序95.山迪的麻烦96.删除字符97.是该年的第几天98.是该年的第几天？99.数据加密100.搜索字符101.所有素数102.探索合数世纪103.特殊要求的字符串104.特殊整数105.完全数106.王的对抗107.危险的组合108.文件比较109.文章统计110.五猴分桃111.小型数据库112.幸运儿113.幸运数字”7“114.选择排序115.寻找规律116.循环移位117.延伸的卡片118.羊羊聚会119.一维数组”赋值“120.一维数组”加法“121.勇闯天涯122.右上角123.右下角124.圆及圆球等的相关计算125.圆及圆球等相关计算126.程序员添加行号127.找出数字128.找幸运数129.找最大数130.整数位数131.重组字符串132.子序列的和133.子字符串替换134.自然数立方的乐趣135.字符串比较136.字符串复制137.字符串加密编码138.字符串逆序139.字符串排序140.字符串替换141.字符串左中右142.组合数143.最次方数144.最大乘积145.最大整数146.最小整数147.最长回文子串148.左上角149.左下角1．“1“的传奇#include <stdio.h>#include <stdlib.h>#include <math.h>int main(){int n,i,j,k=0,x=1,y,z,m,p,q,a,s=0;scanf("%d",&n);m=n;for(i=1;i<12;i++){m=m/10;k++;if(m==0)break;}q=n;k=k-1;for(a=1;a<=k;a++){x=x*10;}y=q%x;z=q/x;p=q-y;if(z>=2)s=s+x+z*k*(x/10); elses=s+z*k*(x/10);for(j=p;j<=n;j++) {m=j;for(i=1;i<12;i++){x=m%10;if(x==1)s++;m=m/10;if(m==0)break;}}printf("%d",s);return 0;}2．A+B#include <stdio.h>int doubi(int n,int m){n=n+m;n=n%100;return n;}int main(){int t,i,a[100],n,m;scanf("%d",&t);for (i=0;i<=(t-1);i++){scanf("%d%d",&n,&m);a[i]=doubi(n,m);}for (i=0;i<=(t-1);i++)printf("%d\n",a[i]);return 0;}3．A+BⅡ#include <stdio.h>int main(){int A,B,sum;scanf("%d%d",&A,&B);sum=A+B;printf("%d\n",sum);return 0;}4．AB#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){char s[100],q[100];double a,b,c;int n=0,i;scanf("%lf%lf",&a,&b);c=a*b;sprintf(s,"%.0lf",c);for(i=0;i<strlen(s);i++){n=n+s[i]-48;}while(n>=10){sprintf(q,"%d",n);n=0;for(i=0;i<strlen(q);i++)n=n+q[i]-48;}printf("%d",n);return 0;}5．ACKERMAN#include <stdio.h>#include <stdlib.h>int ack(int x,int y){int n;if (x==0) {n=y+1;return n;}else if (y==0) n=ack(x-1,1);else n=ack(x-1,ack(x,y-1));return n;}int main(){int m,b;scanf("%d%d",&m,&b);m=ack(m,b);printf("%d",m);return 0;}6．Arithmetic Progressions#include <stdio.h>#include <math.h>int g(int n){int i;if(n==1) return 0;if(n==2) return 1;if(n==3) return 1;for(i=2;i<=sqrt(n);i++) if(n%i==0) return 0;return 1;}int f(int a,int b,int c){int i=0,s=a-b;if(c==1&&g(a)==1) return a;if(b==0&&g(a)!=1) return -1;while(1){s=s+b;if(g(s)) i++;if(i>=c) break;}return s;int main(){int a,b,c,d[100],i=0,n;while(1){scanf("%d%d%d",&a,&b,&c);if(a==0&&b==0&&c==0) break;d[i]=f(a,b,c);i++;}n=i;for(i=0;i<n;i++)printf("%d\n",d[i]);return 0;}7．Bee#include <stdio.h>#include <stdlib.h>int main()int A[100],i=0,j,k,female=0,male=1,x;for(;;i++){scanf("%d",&A[i]);if(A[i]==-1)break;}for(j=0;j<i;j++){female=0,male=1;for(k=1;k<A[j];k++){x=female;female=male;male=x+male+1;}printf("%d %d\n",male,female+male+1);}return 0;}8．Checksum algorithm #include <stdio.h>#include <stdlib.h>#include <string.h>int main(){int i,n,t,j;char s[100][100];for(i=0;;i++){gets(s[i]);if(s[i][0]=='#') break;}n=i;for(i=0;i<n;i++){t=0;for(j=0;j<strlen(s[i]);j++)if(s[i][j]==32) t=t;else t=t+(j+1)*(s[i][j]-64);printf("%d\n",t);}return 0;}9．Coin Test#include <stdio.h>#include <stdlib.h>int main(){char A[100000];int n,i=0,a=0,b=0,j;double x;while(1){scanf("%c",&A[i]);if(A[i]=='\n')break;i++;}for(j=0;j<i;j++){if(A[j]=='S'){printf("WA");goto OH;}if(A[j]=='U')a++;if(A[j]=='D')b++;}x=a*1.0/(a+b)*1.0;if(x-0.5>0.003||x-0.5<-0.003) printf("Fail");elseprintf("%d/%d",a,a+b);OH:return 0;}10．Dexter need help#include <stdio.h>int fun(int a){if(a==1) return 1;elsereturn fun(a/2)+1;}int main(){int a,b[100],i=0,j; while(1){scanf("%d",&a);if(a==0)break;b[i]=fun(a);i++;}for(j=0;j<i;j++){printf("%d\n",b[j]); }return 0;}11．Double#include <stdio.h>#include <stdlib.h>int main(){int a[100],b[100],i,j,n,t=0;for(i=0;;i++){scanf("%d",&a[i]);if(a[i]==0) break;}n=i;for(i=0;i<n;i++)b[i]=2*a[i];for(i=0;i<n;i++)for(j=0;j<n;j++)if(a[i]==b[j]) t++;printf("%d",t);return 0;}12．Easy problem#include <stdio.h>#include <math.h>int main(){int N,i,n,j=0;scanf("%d",&N);for(i=2;i<N+1;i++){if((N+1)%i==0)j++;}printf("%d",j/2);return 0;}13．Favorite number #include <stdio.h>#include <string.h>#define MAXNUM 100000int prime_number = 0;int prime_list[MAXNUM]; bool is_prime[MAXNUM]; int ans[MAXNUM + 2];int dp[MAXNUM + 2];void set_prime() {int i, j;memset(is_prime, 0, sizeof(is_prime));for (i = 2; i < MAXNUM; i++) {if (is_prime[i] == 0) {prime_list[prime_number++] = i;if (i >= MAXNUM / i) continue;for (j = i * i; j < MAXNUM; j+=i) {is_prime[j] = 1;}}}}int main() {int i, j, k,o=0,d[100];memset(dp, -1, sizeof(dp));set_prime();ans[0] = 0;dp[1] = 0;for (i = 1; i <= MAXNUM; i++) {ans[i] = ans[i - 1] + dp[i];if (dp[i + 1] == -1 || dp[i + 1] > dp[i] + 1) { dp[i + 1] = dp[i] + 1;}for (j = 0; j < prime_number; j++) {if (i > MAXNUM / prime_list[j]) break;k = i * prime_list[j];if (dp[k] == -1 || dp[k] > dp[i] + 1) {dp[k] = dp[i] + 1;}}}while (scanf("%d%d", &i, &j) == 2 && (i || j)) { d[o]=ans[j] - ans[i - 1];o++;}for(i=0;i<o;i++)printf("%d\n",d[i]);}14．Graveyard#include <stdio.h>#include <stdlib.h>#include <math.h>int main(){int a[100],b[100],n,i,j;double s,p,l,t;for(i=0;;i++){scanf("%d%d",&a[i],&b[i]);if(a[i]==0&&b[i]==0) break;}n=i;for(i=0;i<n;i++){p=10000;if(b[i]%a[i]==0){printf("0.0000\n");continue;};t=10000/((double)a[i]);for(j=1;j<a[i]+b[i];j++){l=10000/((double)(a[i]+b[i]));l=t-j*l;l=fabs(l);if(l<p) p=l;}s=(a[i]-1)*p;printf("%.4lf\n",s);}return 0;}15．Hailstone#include <stdio.h>#include <stdlib.h>#include <string.h>int f(int n){int s=1;while(1){if(n==1) return s;else if(n%2==0) n=n/2,s++;else n=3*n+1,s++;}}int main()int n,m,i,j=0,t;scanf("%d%d",&m,&n);printf("%d %d",m,n);if(m>n) t=m,m=n,n=t;for(i=m;i<=n;i++)if(f(i)>j) j=f(i);printf(" %d",j);return 0;}16．Hanoi Ⅱ#include <stdio.h>#include <stdlib.h>#define M 70int start[M], targe[M];long long f(int *p, int k, int fina){if(k==0) return 0;if(p[k]==fina) return f(p,k-1,fina); return f(p,k-1,6-fina-p[k])+(1LL<<(k-1));int main (){long long ans;int n;while(scanf("%d",&n),n){int i;for(i=1;i<=n;i++) scanf("%d",&start[i]);for(i=1;i<=n;i++) scanf("%d",&targe[i]);int c=n;for(;c>=1&&start[c]==targe[c];c--);if(c==0){printf("0\n"); continue;}int other=6-start[c]-targe[c];ans=f(start,c-1,other)+f(targe,c-1,other)+1;printf("%lld\n",ans);}return 0;}17．Houseboat#include <stdio.h>#include <stdlib.h>#include <math.h>#define pi 3.1415926int f(float x,float y){int i;for(i=0;;i++)if(50*i>sqrt(x*x+y*y)*sqrt(x*x+y*y)*pi/2) break;return i;}int main(){int n,i,a[100];float x,y;scanf("%d",&n);for(i=0;i<n;i++){scanf("%f%f",&x,&y);a[i]=f(x,y);}for(i=0;i<n;i++)printf("%d %d\n",i+1,a[i]);return 0;}18．Music Composer19．Redistribute wealth#include <stdio.h>#include <stdlib.h>#include <math.h>int main(){int a[1000],b[1000],n,i,j,s,sum,t,m,mid,c[100],k=0;while(1){scanf("%d",&n);if(n==0) break;{s=0;for(i=1;i<=n;i++){scanf("%d",&a[i]);s=s+a[i];}m=s/n;b[1]=a[1]-m;b[0]=0;for(i=2;i<n;++i)b[i]=b[i-1]+a[i]-m;for(i=0;i<n;i++)for(j=0;j<n-1-i;j++)if(b[j]>b[j+1])t=b[j],b[j]=b[j+1],b[j+1]=t;mid=b[n/2];sum=0;for(i=0;i<=n-1;++i) sum=sum+fabs(mid-b[i]);c[k]=sum;k++;}}for(i=0;i<k;i++) printf("%d\n",c[i]);return 0;}20．Road trip#include <stdio.h>#include <stdlib.h>#include <math.h>int f(int n){int a[100],b[100],i,s;for(i=0;i<n;i++)scanf("%d%d",&a[i],&b[i]);s=a[0]*b[0];for(i=1;i<n;i++)s=s+a[i]*(b[i]-b[i-1]);return s;}int main(){int n,c[100],i=0;while(1){scanf("%d",&n);if(n==-1) break;c[i]=f(n);i++;}n=i;for(i=0;i<n;i++)printf("%d\n",c[i]);return 0;}21．Scoring#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){int i,j,sum,min,c,count,n,a,b;char s1[50],s2[50];scanf("%d",&n);for(i=0;i<n;i++){count=sum=0;scanf("%s",s2);for(j=0;j<4;j++){scanf("%d%d",&a,&b);if(b!=0){sum+=(a-1)*20+b;count++;}}if(i==0){c=count,min=sum;strcpy(s1,s2);}else if(count>c||(count==c&&sum<min)){min=sum;c=count;strcpy(s1,s2);}}printf("%s %d %d\n",s1,c,min);return 0;}22．Specialized Numbers#include <stdio.h>#include <stdlib.h>int main(){int i,n,sum10,sum12,sum16;for(i=2992;i<3000;i++){n=i;sum10=0;while(n){sum10+=n%10;n/=10;}n=i;sum12=0;while(n){sum12+=n%12;n/=12;}n=i;sum16=0;while(n){sum16+=n%16;n/=16;}if(sum10==sum12&&sum12==sum16) printf("%d\n",i);}return 0;}23．Sticks#include <stdio.h>#include <string.h>#include <stdlib.h>int len[64], n, minlen, get;bool b[64];int cmp(const void *a, const void *b){return *(int *)a < *(int *)b ? 1 : -1;}bool dfs(int nowlen, int nowget, int cnt){if(cnt >= n) return false;if(get == nowget) return true;int i;bool f = false;if(nowlen == 0) f = true;for(i = cnt; i < n; i++){if(!b[i]){if(len[i] + nowlen == minlen){b[i] = true;if(dfs(0, nowget+1, nowget))return true;b[i] = false;return false;}else if(len[i] + nowlen < minlen){b[i] = true;if(dfs(nowlen+len[i], nowget, i+1))return true;b[i] = false;if(f) return false;while(i + 1 < n && len[i] == len[i+1]) i++;}}}return false;}int main(){int i, tollen;while(scanf("%d", &n), n){tollen = 0;int j = 0, p;for(i = 0; i < n; i++){scanf("%d", &p);if(p <= 50){len[j] = p;tollen += len[j];j++;}}n = j;if(n == 0){printf("0\n");continue;}qsort(len, n, sizeof(int), cmp);for(minlen = len[0]; ; minlen++) {if(tollen % minlen) continue;memset(b, 0, sizeof(b));get = tollen / minlen;if(dfs(0, 0, 0)){printf("%d\n", minlen);break;}}}return 0;}24．Sum of Consecutive#include <stdio.h>#include <stdlib.h>#include <string.h>int len[64],n,minlen,get;int b[64];int cmp(const void *a,const void *b) {return *(int *)a<*(int *)b?1:-1;}int dfs(int nowlen,int nowget,int cnt) {if(cnt>=n) return 0;if(get==nowget) return 1;int i,f=0;if(nowlen==0) f=1;for(i=cnt;i<n;i++){if(len[i]+nowlen==minlen){b[i]=1;if(dfs(0,nowget+1,nowget)) return 1;b[i]=0;return 0;}else if(len[i]+nowlen<minlen){b[i]=1;if(dfs(nowlen+len[i],nowget,i+1)) return 1;b[i]=0;if(f) return 0;while(i+1<n&&len[i]==len[i+1]) i++;}}return 0;}int main(){int i,tollen,q=0,c[100];while(scanf("%d",&n),n){tollen=0;int j=0,p;for(i=0;i<n;i++){scanf("%d",&p);if(p<=50){len[j]=p;tollen+=len[j];j++;}}n=j;if(n==0){printf("0\n");continue;}qsort(len,n,sizeof(int),cmp);for(minlen=len[0];;minlen++){if(tollen%minlen) continue;memset(b,0,sizeof(b));get=tollen/minlen;if(dfs(0,0,0)){c[q]=minlen;q++;break;}}}for(i=0;i<q;i++)printf("%d\n",c[i]);return 0;}25．Symmetric Sort#include <stdio.h>#include <stdlib.h>#include <math.h>int main(){double A[100];int i=0,j=0,k=0,l=0,sum=0;while(1){scanf("%lf",&A[i]);if(A[i]==0)break;i++;}for(j=0;j<i;j++){if(A[j]==2)printf("1\n");else{int B[10000],m=1,number=0;double n;B[0]=2;for(k=3;k<=A[j];k+=2){n=(double)k;for(l=2;l<=sqrt(n);l++){if(k%l==0)goto ai;}B[m]=k;m++;ai:;}for(k=0;k<m;k++){sum=0;for(l=k;l<m;l++){sum+=B[l];if(sum==A[j]){number++;break;}}}printf("%d\n",number);}}return 0;}26．The Clock#include <stdio.h>#include <stdlib.h>#include <string.h>int main(){char s[100][100],a[100];int i,j,n;scanf("%d",&n);for(i=0;i<n;i++) scanf("%s",s[i]);for(i=0;i<n-1;i++)for(j=0;j<n-1-i;j++)if(strlen(s[i])>strlen(s[i+1])) strcpy(a,s[i]),strcpy(s[i],s[i+1]),strcpy(s[i+1],a);if(n%2==0){for(i=0;i<n-1;i=i+2) printf("%s ",s[i]);printf("%s ",s[n-1]);for(i=i-3;i>0;i=i-2) printf("%s ",s[i]);}else{for(i=0;i<n-1;i=i+2) printf("%s ",s[i]);printf("%s ",s[n-1]);for(i=i-1;i>0;i=i-2) printf("%s ",s[i]);}return 0;}27．The Ratio of gainers to losers #include<stdio.h>int main(){char s[5];int i,sum=0;gets(s);for(i=0;s[i]!='\0';i++){switch(s[i]){case'I': sum+=1;break; case'V': sum=5-sum;break; case'X':sum=10-sum;break; }}printf("%d\n",sum);return 0;}28．VOL大学乒乓球比赛#include <stdio.h>#include <stdlib.h>int main(){printf("A=Z\nB=X\nC=Y\n");return 0;}29．毕业设计论文打印#include <stdio.h>#include <stdlib.h>int main(){int a[100],j=1,i,n,m;scanf("%d%d",&n,&m);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=0;i<n;i++)if(a[i]>a[m]) j++;printf("%d",j++);return 0;}30．边沿与内芯的差#include <stdio.h>#include <stdlib.h>int main(){int A[100][100],i,j,m,n,s=0,t=0;scanf("%d%d",&n,&m);for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&A[i][j]);}}for(i=2;i<m;i++)s=s+A[1][i];。

第一章绪论1.图灵测试一组人类裁判以敲击键盘的形式与电脑“对话”。

如果裁判认定电脑为人的比例超过30%，则电脑通过测试。

2.人类智能活动的能力是人类在认识世界和改造世界的活动中，由脑力劳动表现出来的能力。

•认识和理解世界环境的能力•提出概念、建立方法、进行演绎和归纳推理、做出决策的能力•学习取得经验、积累知识的能力•自我适应的能力•联想、推理、判断、决策的能力3.智能的本质感知能力、记忆和思维能力、学习能力、自适应能力、行为能力4.思维种类逻辑思维、形象思维、顿悟思维5.人工智能的含义用计算机来完成能表现出人类智能的任务学科模仿人脑所从事的推理、学习、思考、规划等思维活动关于知识的科学执行拟人的任务6.没有计算机的出现，人工智能就无法得到应用7.人类智能与人工智能本质区别:物质载体、逻辑模拟、活动规律、目的性、能动性、适应性8.研究方法符号主义、联结主义、行为主义9.计算智能是人工智能的深化与发展人工智能是以知识库为基础、那么计算智能则是以模型为基础、以分步、并行、仿生计算为特征含数据、算法和实现的信息系统。

前者强调规则的形式和表示，后者强调模型的建立和构成；前者依赖专家知识，后者强调系统的自组织、自学习和自适应。

10.计算智能的主要方法有人工神经网络、遗传算法、遗传程序、演化程序、局部搜索、模拟退火等等11.计算智能的特征与应用智能性：包括算法的自适应性，自组织性，算法不依赖于问题本身的特点，具有通用性并行性：算法基本上是群体协作的方式对问题进行优化求解，非常适合大规模并行处理鲁棒性:算法具有很好的容错性，同时对初始条件不敏感，能在不同条件下寻找最优解12.计算智能发展趋势分布式人工智能、Internet及数据库的挖掘、智能系统之间的交互与通信、智能系统之间的合作等13.第二章知识表示一.知识的基本概念1. 相关概念：数据：指为描述具体事物引入的数字、符号等信息：指不同数据组成的一种结构（如“建国50岁”）数据与信息的关系：数据是信息的载体和表示，信息是数据的语义知识：对信息进行智能性加工后形成的对客观世界的规律性认识*。