C++算法设计(完整版)

C语言算法设计与分析排序查找和算法C语言算法设计与分析：排序、查找和算法C语言作为一门广泛应用于计算机领域的编程语言，算法设计与分析是每个程序员都需要掌握的重要技能之一。

本文将介绍C语言中常用的排序算法、查找算法以及一些常见的算法技巧，并详细分析它们的原理和实现方法。

一、排序算法1. 冒泡排序（Bubble Sort）冒泡排序是最简单的排序算法之一。

它的基本思想是通过相邻元素之间的比较和交换来将序列中的较大元素逐步向右移动。

具体实现时，从待排序序列的左侧开始，将较大的元素向右冒泡，直至序列有序。

冒泡排序的时间复杂度为O(n^2)。

2. 插入排序（Insertion Sort）插入排序的思想是将待排序序列分为已排序和未排序两部分，从未排序序列中选择元素并插入到已排序序列的适当位置。

具体实现时，从待排序序列的左侧开始，逐个将元素插入到已排序序列中的正确位置，直至序列有序。

插入排序的时间复杂度为O(n^2)，但在部分有序的序列中具有较好的性能。

3. 快速排序（Quick Sort）快速排序是一种高效的排序算法，它的基本思想是通过每一趟排序将待排序序列分割成独立的两部分，其中一部分的所有元素小于另一部分的所有元素，并分别对这两部分进一步排序。

具体实现时，选择一个基准元素，将小于基准的元素放到左侧，大于基准的元素放到右侧，然后对左右两部分分别进行递归排序。

快速排序的平均时间复杂度为O(nlogn)。

二、查找算法1. 顺序查找（Sequential Search）顺序查找是一种简单直观的查找算法。

它的基本思想是从待查找的序列的左侧开始，逐个比较序列中的元素和待查找元素，直到找到匹配的元素或查找结束。

顺序查找的时间复杂度为O(n)。

2. 二分查找（Binary Search）二分查找是一种高效的查找算法，但要求待查找序列必须是有序的。

它的基本思想是通过每一次查找将待查找序列划分为两部分，并将中间元素与待查找元素进行比较，进而确定下一次查找的范围。

排列组合c的算法排列组合是组合数学中的经典概念，也是计算机科学中常用的算法之一。

在算法设计中，排列组合算法可以用于解决很多实际问题，比如密码破解、图形排列等。

本文将介绍排列组合的基本概念和常见的算法。

排列是指从给定的n个元素中，按照一定顺序选取k个元素的方式。

对于有序的排列，我们可以使用递归或者循环的方法来实现。

递归方法可以通过以下步骤来完成：1. 若k=0，则返回一个空列表。

2. 若k=1，则将n个元素依次加入列表中，并返回。

3. 若k>1，则从n个元素中选取第一个元素，然后递归地选取剩下的n-1个元素中的k-1个，将两部分结果合并。

以下是一个使用递归方法实现排列的伪代码：```function permute(list, k):if k = 0:return []if k = 1:return [[x] for x in list]result = []for i in range(len(list)):rest = permute(list[:i] + list[i+1:], k-1)for p in rest:result.append([list[i]] + p)return result```循环方法可以通过以下步骤来完成：1. 创建一个二维数组result，用于存储所有的排列结果。

2. 创建一个长度为n的布尔类型的数组used，用于标记元素是否已经被选取。

3. 创建一个列表p，用于存储当前的排列。

4. 使用循环遍历数组中的每一个元素，对于每个元素，检查是否已经被选取。

5. 如果元素已经被选取，则跳过该元素。

6. 如果元素未被选取，则将其加入当前的排列p中，并标记元素为已选取。

7. 如果k=1（即已选取了k个元素），则将当前排列加入结果result中。

8. 否则，递归地调用自身，进入下一层递归。

9. 在递归返回后，将当前元素标记为未选取，将其从排列p中移除，以便进行下一个元素的选择。

c课程设计迭代算法一、教学目标本课程旨在让学生掌握迭代算法的基本概念、设计和分析方法，培养他们运用迭代算法解决实际问题的能力。

具体目标如下：1.知识目标：（1）了解迭代算法的定义、特点和应用领域。

（2）掌握常见迭代算法的设计方法和分析技巧。

（3）熟悉迭代算法在实际问题中的应用案例。

2.技能目标：（1）能够运用迭代算法解决简单数学问题。

（2）能够运用迭代算法优化程序性能。

（3）能够分析迭代算法的收敛性和时间复杂度。

3.情感态度价值观目标：（1）培养学生对迭代算法的兴趣，提高他们学习编程的积极性。

（2）培养学生独立思考、合作交流的能力。

（3）培养学生勇于探索、创新的精神。

二、教学内容本课程的教学内容主要包括以下几个部分：1.迭代算法的基本概念：迭代算法的定义、特点和应用领域。

2.迭代算法的设计方法：常见的迭代算法设计方法，如递推、迭代递推、迭代加速等。

3.迭代算法的分析方法：迭代算法的收敛性、时间复杂度和空间复杂度分析。

4.迭代算法在实际问题中的应用：线性代数、数值计算、优化问题等领域中的应用案例。

5.编程实践：运用迭代算法解决实际问题，提高编程能力。

三、教学方法为了提高教学效果，本课程将采用以下教学方法：1.讲授法：讲解迭代算法的基本概念、设计方法和分析技巧。

2.案例分析法：分析迭代算法在实际问题中的应用案例，让学生加深理解。

3.实验法：让学生通过编程实践，掌握迭代算法的应用和优化。

4.讨论法：学生进行小组讨论，培养合作交流的能力。

四、教学资源为了支持教学内容和教学方法的实施，我们将准备以下教学资源：1.教材：《迭代算法导论》等。

2.参考书：《算法导论》、《数值计算方法》等。

3.多媒体资料：PPT、教学视频等。

4.实验设备：计算机、编程环境等。

5.在线资源：相关论坛、博客、教程等。

五、教学评估本课程的教学评估将采用多元化评价方式，全面、客观地评价学生的学习成果。

评估方式包括：1.平时表现：考察学生在课堂上的参与度、提问回答、小组讨论等，占总评的20%。

C语言中的算法实现算法是计算机科学中非常重要的概念，它是解决问题的一系列步骤或指令集。

在C语言中，我们可以使用不同的方法来实现算法。

本文将介绍一些常见的C语言算法实现方式。

一、排序算法1. 冒泡排序冒泡排序是一种简单但效率较低的排序算法。

它通过不断比较相邻的元素，并按照规则交换它们的位置，直到整个序列排序完成。

2. 选择排序选择排序是一种简单而直观的排序算法。

它每次从未排序的序列中选择最小（或最大）的元素，并将其放置在已排序序列的末尾。

3. 插入排序插入排序是一种简单且高效的排序算法。

它通过构建有序序列，对未排序的元素逐个插入到已排序的序列中，直到所有元素都被插入完成。

二、查找算法1. 顺序查找顺序查找是一种简单的查找算法。

它从列表的开头开始逐个比较元素，直到找到目标元素或查找完整个列表。

2. 二分查找二分查找是一种高效的查找算法，但要求列表必须是有序的。

它通过将待查找区域分成两部分，判断目标元素落在哪一部分，从而缩小查找范围，直到找到目标元素或确定不存在。

三、递归算法递归是一种常用的算法设计技巧。

它通过在函数内调用自身来解决相同问题的不同实例。

在C语言中，递归函数需要定义出口条件，以避免无限递归。

四、动态规划算法动态规划是一种用于解决具有重叠子问题和最优子结构性质的问题的方法。

它将问题分解为一系列子问题，并以自底向上的方式求解子问题，最终得到整体问题的解。

在C语言中，可以使用循环、数组和指针等特性来实现动态规划算法，从而有效地解决问题。

五、图算法图是一种用于描述对象之间关系的数据结构，图算法是解决图相关问题的一类算法。

常见的图算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

六、字符串算法字符串算法用于处理字符串相关的问题，如字符串匹配、编辑距离等。

C语言提供了一系列字符串处理函数，如strlen、strcpy等，可以方便地实现字符串算法。

七、数学算法C语言在数学算法方面提供了丰富的库函数支持，如求平方根、对数、指数等。

习题2.1什么是算法？是从日常生活中找三个例子，描述他们的算法？答：对操作的描述，即操作步骤，就是算法。

广义的说；为解决一个问题而采取的方法和步骤，就称为“算法”。

例：（略）2.2什么叫结构化的算法？为什么要提倡结构化的算法？答：由基本节构所构成的算法属于“结构化”的算法。

结构化的算法便于编写、阅读、便于修改和维护。

这就减少了程序出错的机会、提高了程序的可靠性，保证了程序的质量。

2.3试述三种基本结构的特点，你能否自己另外设计两种基本结构（要符合基本结构的特点）。

答：基本结构有以下共同点：1：只有一个入口。

图2-14-------2-17中的a点为入口。

2：只有一个出口。

图2-14-------2-17中的b点为出口。

注意，一个判断框有两个出口，但一个选择结构只有一个出口。

不能混淆。

3：结构内的每一部分都有被执行到的机会。

也就是说，对每一个框来说，都应当有一条到出口的路径通过它。

图2-20中就没有一条从入口到出口的路径通过A框。

4：结构内不存在死循环（无终止的循环）。

图2-21就是一个死循环。

需要说明的是基本结构并不一定只限于以上3中，只要有以上四种特点就可以。

人们可以自己定义之。

例：如下两图2.4用传统流程图表示求解一下问题的算法。

(1)有两个瓶子A和B，分别放醋和酱油，要求将他们互换。

#include<stdio.h>void main(){int a;int b;int c;a=10;b=5;printf("%d,%d\n",a,b);c=a;a=b;b=c;printf("%d,%d\n",a,b);}(2)一次将10个数输入，要求将将其中最大的数输出。

#include<stdio.h>void main(){int a[10];int i;int max;printf("input 10 numbers.\n");for(i=0;i<10;i++)scanf("%d",&a[i]);printf("\n");max=a[0];for(i=1;i<10;i++)if(max<a[i]) max=a[i];printf("the max is: %d\n",max) ;}(3)有3个数a b c,要求安大小顺序把他们输出。

C语言程序设计的常用算法1.排序算法-冒泡排序：通过多次比较和交换来将最大（小）的数移到最后（前），时间复杂度为O(n^2)。

适用于数据较少、数据基本有序的情况。

- 快速排序：通过一趟排序将待排序序列分隔成独立的两部分，其中一部分的所有元素都比另一部分的所有元素小。

然后递归地对两部分进行排序，时间复杂度为O(nlogn)。

适用于大规模数据的排序。

-插入排序：将待排序序列分为已排序和未排序两部分，每次从未排序部分取一个元素插入到已排序部分的适当位置，时间复杂度为O(n^2)。

适用于数据量较小的排序场景。

- 归并排序：将待排序序列分为若干个子序列，分别进行排序，然后再将排好序的子序列合并成整体有序的序列，时间复杂度为O(nlogn)。

适用于需要稳定排序且对内存空间要求不高的情况。

2.查找算法-顺序查找：从头到尾依次对每个元素进行比较，直到找到目标元素或者遍历完整个序列。

时间复杂度为O(n)。

- 二分查找：对于有序序列，将序列的中间元素与目标元素进行比较，根据比较结果缩小查找范围，直到找到目标元素或者查找范围为空。

时间复杂度为O(logn)。

3.图算法-广度优先（BFS）：从给定的起始顶点开始，按照“先访问当前顶点的所有邻接顶点，再依次访问这些邻接顶点的所有未访问过的邻接顶点”的顺序逐层访问图中的所有顶点。

适用于寻找最短路径、连通性等问题。

-深度优先（DFS）：从给定的起始顶点开始，按照“先递归访问当前顶点的一个邻接顶点，再递归访问这个邻接顶点的一个邻接顶点，直到无法再继续递归”的方式遍历图中的所有顶点。

适用于寻找路径、判断连通性等问题。

4.动态规划算法-背包问题：给定一个背包容量和一组物品的重量和价值，选择一些物品装入背包，使得装入的物品总重量不超过背包容量，且总价值最大。

利用动态规划的思想可以通过构建二维数组来解决该问题。

-最长公共子序列（LCS）：给定两个序列，找出一个最长的子序列，且该子序列在两个原序列中的顺序保持一致。

C语言经典算法大全C语言经典算法大全老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官一老鼠走迷官二骑士走棋盘八个皇后八枚银币生命游戏字串核对双色三色河内塔背包问题Knapsack Problem数运算蒙地卡罗法求 PIEratosthenes筛选求质数超长整数运算大数运算长 PI最大公因数最小公倍数因式分解完美数阿姆斯壮数最大访客数中序式转后序式前序式后序式的运算关于赌博洗扑克牌乱数排列Craps赌博游戏约瑟夫问题Josephus Problem 集合问题排列组合格雷码Gray Code产生可能的集合m元素集合的n个元素子集数字拆解排序得分排行选择插入气泡排序Shell 排序法 - 改良的插入排序Shaker 排序法 - 改良的气泡排序Heap 排序法 - 改良的选择排序快速排序法一快速排序法二快速排序法三合并排序法基数排序法搜寻循序搜寻法使用卫兵二分搜寻法搜寻原则的代表插补搜寻法费氏搜寻法矩阵稀疏矩阵多维矩阵转一维矩阵上三角下三角对称矩阵奇数魔方阵4N 魔方阵2 2N1 魔方阵 1河内之塔说明河内之塔 Towers of Hanoi 是法国人MClaus Lucas 于1883年从泰国带至法国的河内为越战时北越的首都即现在的胡志明市1883年法国数学家 Edouard Lucas曾提及这个故事据说创世纪时Benares有一座波罗教塔是由三支钻石棒Pag所支撑开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘Disc并命令僧侣将所有的金盘从第一根石棒移至第三根石棒且搬运过程中遵守大盘子在小盘子之下的原则若每日仅搬一个盘子则当盘子全数搬运完毕之时此塔将毁损而也就是世界末日来临之时解法如果柱子标为ABC要由A搬至C在只有一个盘子时就将它直接搬至C当有两个盘子就将B当作辅助柱如果盘数超过2个将第三个以下的盘子遮起来就很简单了每次处理两个盘子也就是A- BA - CB- C这三个步骤而被遮住的部份其实就是进入程式的递回处理事实上若有n个盘子则移动完毕所需之次数为2n - 1所以当盘数为64时则所需次数为264- 1 1XXXXXXXXXX709551615为505390248594782e16年也就是约5000世纪如果对这数字没什幺概念就假设每秒钟搬一个盘子好了也要约5850亿年左右includevoid hanoi int n char A char B char Cif n 1printf "Move sheet d from c to c\n" n A Celsehanoi n-1 A C Bprintf "Move sheet d from c to c\n" n A Chanoi n-1 B A Cint mainint nprintf "请输入盘数"scanf "d" nhanoi n A B Cfn fn-1 fn-2 if n 1fn n if n 0 1includeinclude define N 20 int main voidint Fib[N] 0int i Fib[0] 0Fib[1] 1 for i 2 i N iFib[i] Fib[i-1] Fib[i-2] for i 0 i N i printf "d " Fib[i]printf "\n"return 03 巴斯卡三角形 includedefine N 12long combi int n int rint ilong p 1for i 1 i r ip p n-i1 ireturn pvoid mainint n r tfor n 0 n N nfor r 0 r n rint i 排版设定开始if r 0for i 0 i N-n i printf " "elseprintf " "排版设定结束printf "3d" combi n rprintf "\n"4Algorithm Gossip 三色棋说明三色旗的问题最早由EWDijkstra所提出Dutch Nation Flag Dijkstra为荷兰人 Three-Color Flag来称之假设有一条绳子上面有红白蓝三种颜色的旗子起初绳子上的旗子颜色并没有顺序您希望将之分类并排列为蓝白红的顺序要如何移动次数才会最少注意您只能在绳子上进行这个动作而且一次只能调换两个旗子解法在一条绳子上移动在程式中也就意味只能使用一个阵列而不使用其它的阵列来作辅助问题的解法很简单您可以自己想像一下在移动旗子从绳子开头进行遇到蓝色往前移遇到白色留在中间遇到红色往后移如下所示只是要让移动次数最少的话就要有些技巧如果图中W所在的位置为白色则W1表示未处理的部份移至至白色群组如果W部份为蓝色则B与W的元素对调而B与W必须各1表示两个群组都多了一个元素如果W所在的位置是红色则将W与R交换但R要减1表示未处理的部份减1 注意BWR并不是三色旗的个数它们只是一个移动的指标什幺时候移动结束呢一开始时未处理的R指标会是等于旗子的总数当R的索引数减至少于W的索引数时表示接下来的旗子就都是红色了此时就可以结束移动如下所示 includeincludeinclude define BLUE bdefine WHITE wdefine RED r define SWAP x y char temp \temp color[x] \color[x] color[y] \color[y] temp int main char color[] r w b w wb r b w r \0 int wFlag 0 int bFlag 0int rFlag strlen color - 1int i for i 0 i strlen color iprintf "c " color[i]printf "\n" while wFlag rFlagif color[wFlag] WHITEwFlagelse if color[wFlag] BLUESWAP bFlag wFlagbFlag wFlagelsewhile wFlag rFlag color[rFlag] REDrFlag--SWAP rFlag wFlagrFlag--for i 0 i strlen color i printf "c " color[i]printf "\n" return 05Algorithm Gossip 老鼠走迷官说明老鼠走迷宫是递回求解的基本题型我们在二维阵列中使用2表示迷宫墙壁使用1来表示老鼠的行走路径试以程式求出由入口至出口的路径解法老鼠的走法有上左下右四个方向在每前进一格之后就选一个方向前进无法前进时退回选择下一个可前进方向如此在阵列中依序测试四个方向直到走到出口为止这是递回的基本题请直接看程式应就可以理解includeinclude int visit int int int maze[7][7] 2 2 2 22 2 22 0 0 0 0 0 22 0 2 0 2 0 22 0 0 2 0 2 22 2 0 2 0 2 22 0 0 0 0 0 22 2 2 2 2 2 2 int startI 1 startJ 1 入口int endI 5 endJ 5 出口int success 0 int main voidint i j printf "显示迷宫\n"for i 0 i 7 ifor j 0 j 7 jif maze[i][j] 2printf "█"elseprintf " "printf "\n"if visit startI startJ 0 printf "\n没有找到出口\n"elseprintf "\n\n"for i 0 i 7 ifor j 0 j 7 jif maze[i][j] 2printf "█"else if maze[i][j] 1 printf "◇"elseprintf " "printf "\n"return 0int visit int i int jmaze[i][j] 1 if i endI j endJsuccess 1 if success 1 maze[i][j1]0 visit i j1if success 1 maze[i1][j] 0 visit i1 jif success 1 maze[i][j-1] 0 visit i j-1if success 1 maze[i-1][j] 0 visit i-1 j if success 1maze[i][j] 0 return success6Algorithm Gossip 老鼠走迷官说明由于迷宫的设计老鼠走迷宫的入口至出口路径可能不只一条如何求出所有的路径呢解法求所有路径看起来复杂但其实更简单只要在老鼠走至出口时显示经过的路径然后退回上一格重新选择下一个位置继续递回就可以了比求出单一路径还简单我们的程式只要作一点修改就可以了includeinclude void visit int int int maze[9][9] 2 2 2 22 2 2 2 22 0 0 0 0 0 0 0 22 0 2 2 0 2 2 0 22 0 2 0 0 2 0 0 22 0 2 0 2 0 2 0 22 0 0 0 0 0 2 0 22 2 0 2 2 0 2 2 22 0 0 0 0 0 0 0 22 2 2 2 2 2 2 2 2 int startI 1 startJ 1 入口int endI 7 endJ 7 出口 int main voidint i j printf "显示迷宫\n"for i 0 i 7 ifor j 0 j 7 jif maze[i][j] 2printf "█"elseprintf " "printf "\n"visit startI startJ return 0void visit int i int jint m n maze[i][j] 1 if i endI j endJprintf "\n显示路径\n"for m 0 m 9 mfor n 0 n 9 nif maze[m][n] 2printf "█"else if maze[m][n] 1printf "◇"elseprintf " "printf "\n"if maze[i][j1] 0 visit i j1if maze[i1][j] 0 visit i1 jif maze[i][j-1] 0 visit i j-1if maze[i-1][j] 0 visit i-1 j maze[i][j] 07Algorithm Gossip 骑士走棋盘说明骑士旅游Knight tour[所有的位置include int board[8][8] 0 int main voidint startx startyint i jprintf "输入起始点"scanf "d d" startx starty if travel startx starty printf "\n"elseprintf "\n"for i 0 i 8 ifor j 0 j 8 jprintf "2d " board[i][j]putchar \nreturn 0int travel int x int yint ktmove1[8] -2 -1 1 2 2 1 -1 -2int ktmove2[8] 1 2 2 1 -1 -2 -2 -1 测试下一步的出路int nexti[8] 0int nextj[8] 0记录出路的个数int exists[8] 0int i j k m lint tmpi tmpjint count min tmp i xj yboard[i][j] 1 for m 2 m 64 mfor l 0 l 8 lexists[l] 0 l 0 试探八个方向for k 0 k 8 ktmpi i ktmove1[k]tmpj j ktmove2[k] 如果是边界了if tmpi 0 tmpj 0 tmpi 7 tmpj 7 continue 如果这个方向可走 if board[tmpi][tmpj] 0nexti[l] tmpinextj[l] tmpj可走的方向加一个lcount l如果可走的方向为0个if count 0return 0else if count 1只有一个可走的方向所以直接是最少出路的方向min 0else找出下一个位置的出路数for l 0 l count lfor k 0 k 8 ktmpi nexti[l] ktmove1[k] tmpj nextj[l] ktmove2[k] if tmpi 0 tmpj 0tmpi 7 tmpj 7continueif board[tmpi][tmpj] 0 exists[l]tmp exists[0]min 0从可走的方向中寻找最少出路的方向 for l 1 l count lif exists[l] tmptmp exists[l]min l走最少出路的方向i nexti[min]j nextj[min]board[i][j] mreturn 18Algorithm Gossip 八皇后说明西洋棋中的皇后可以直线前进吃掉遇到的所有棋子如果棋盘上有八个皇后则这八个皇后如何相安无事的放置在棋盘上1970年与1971年 EWDijkstra与NWirth曾经用这个问题来讲解程式设计之技巧解法关于棋盘的问题都可以用递回求解然而如何减少递回的次数在八个皇后的问题中不必要所有的格子都检查过例如若某列检查过该该列的其它格子就不用再检查了这个方法称为分支修剪includeincludedefine N 8 int column[N1] 同栏是否有皇后1int rup[2N1] 右上至左下是否有皇后int lup[2N1] 左上至右下是否有皇后int queen[N1] 0int num 解答编号 void backtrack int 递回求解 intmain voidint inum 0 for i 1 i N icolumn[i] 1 for i 1 i 2N irup[i] lup[i] 1 backtrack 1 return 0void showAnswerint x yprintf "\n解答 d\n" numfor y 1 y N yfor x 1 x N xif queen[y] xprintf " Q"elseprintf " "printf "\n"void backtrack int iint j if i NshowAnswerelsefor j 1 j N jif column[j] 1rup[ij] 1 lup[i-jN] 1 queen[i] j设定为占用column[j] rup[ij] lup[i-jN] 0 backtrack i1column[j] rup[ij] lup[i-jN] 19Algorithm Gossip 八枚银币说明现有八枚银币a b c d e f g h已知其中一枚是假币其重量不同于真币但不知是较轻或较重如何使用天平以最少的比较次数决定出哪枚是假币并得知假币比真币较轻或较重解法单就求假币的问题是不难但问题限制使用最少的比较次数所以我们不能以单纯的回圈比较来求解我们可以使用决策树decision tree使用分析与树状图来协助求解一个简单的状况是这样的我们比较abc与def 如果相等则假币必是g或h我们先比较g或h哪个较重如果g较重再与a比较a是真币如果g等于a则g为真币则h为假币由于h比g轻而 g是真币则h假币的重量比真币轻 include includeinclude void compare int[] int int intvoid eightcoins int[] int main voidint coins[8] 0int i srand time NULL for i 0 i 8 icoins[i] 10 printf "\n输入假币重量比10大或小 "scanf "d" icoins[rand 8] i eightcoins coins printf "\n\n"for i 0 i 8 iprintf "d " coins[i] printf "\n"return 0void compare int coins[] int i int j int kif coins[i] coins[k]printf "\n d 较重" i1elseprintf "\n假币 d 较轻" j1void eightcoins int coins[]if coins[0]coins[1]coins[2]coins[3]coins[4]coins[5]if coins[6] coins[7]compare coins 6 7 0elsecompare coins 7 6 0else if coins[0]coins[1]coins[2]coins[3]coins[4]coins[5]if coins[0]coins[3] coins[1]coins[4]compare coins 2 5 0else if coins[0]coins[3] coins[1]coins[4] compare coins 0 4 1if coins[0]coins[3] coins[1]coins[4]compare coins 1 3 0else if coins[0]coins[1]coins[2]coins[3]coins[4]coins[5]if coins[0]coins[3] coins[1]coins[4]compare coins 5 2 0else if coins[0]coins[3] coins[1]coins[4] compare coins 3 1 0if coins[0]coins[3] coins[1]coins[4]compare coins 4 0 110Algorithm Gossip 生命游戏说明生命游戏game of life1970年由英国数学家J H Conway所提出includeincludeinclude define ROW 10define COL 25define DEAD 0define ALIVE 1int map[ROW][COL] newmap[ROW][COL] void initint neighbors int intvoid outputMapvoid copyMap int mainint row colchar ansinitwhile 1outputMapfor row 0 row ROW rowfor col 0 col COL colswitch neighbors row colcase 0case 1case 4case 5case 6case 7case 8newmap[row][col] DEADbreakcase 2newmap[row][col] map[row][col] breakcase 3newmap[row][col] ALIVEbreakcopyMapprintf "\nContinue next Generation "getcharans toupper getcharif ans Y breakreturn 0void initint row col for row 0 row ROW rowfor col 0 col COL colmap[row][col] DEAD puts "Game of life Program"puts "Enter x y where x y is living cell"printf "0 x d 0 y d\n"ROW-1 COL-1puts "Terminate with x y -1 -1" while 1scanf "d d" row colif 0 row row ROW0 col col COLmap[row][col] ALIVEelse if row -1 col -1breakelseprintf " x y exceeds map ranage"int neighbors int row int colint count 0 c rfor r row-1 r row1 rfor c col-1 c col1 cif r 0 r ROW c 0 c COL continueif map[r][c] ALIVEcountif map[row][col] ALIVEcount--return countvoid outputMapint row colprintf "\n\n20cGame of life cell status\n" for row 0 row ROW rowprintf "\n20c"for col 0 col COL colif map[row][col] ALIVE putchar else putchar -void copyMapint row colfor row 0 row ROW rowfor col 0 col COL colmap[row][col] newmap[row][col]11Algorithm Gossip 字串核对说明今日的一些高阶程式语言对于字串的处理支援越来越强大例如JavaPerl等不过字串搜寻本身仍是个值得探讨的课题在这边以Boyer- Moore法来说明如何进行字串说明这个方法快且原理简洁易懂解法字串搜寻本身不难使用暴力法也可以求解但如何快速搜寻字串就不简单了传统的字串搜寻是从关键字与字串的开头开始比对例如 Knuth-Morris-Pratt 演算法字串搜寻这个方法也不错不过要花时间在公式计算上Boyer-Moore字串核对改由关键字的后面开始核对字串并制作前进表如果比对不符合则依前进表中的值前进至下一个核对处假设是p好了然后比对字串中p-n1至p的值是否与关键字相同如果关键字中有重复出现的字元则前进值就会有两个以上的值此时则取前进值较小的值如此就不会跳过可能的位置例如texture 这个关键字t的前进值应该取后面的3而不是取前面的7 includeincludeinclude void table char 建立前进表int search int char char 搜寻关键字void substring char char int int 取出子字串int skip[256] int main voidchar str_input[80]char str_key[80]char tmp[80] \0int m n pprintf "请输入字串"gets str_inputprintf ""gets str_keym strlen str_inputn strlen str_keytable str_keyp search n-1 str_input str_key while p -1 substring str_input tmp p mprintf "s\n" tmpp search pn1 str_input str_keyprintf "\n"return 0void table char keyint k nn strlen keyfor k 0 k 255 kskip[k] nfor k 0 k n - 1 kskip[key[k]] n - k - 1int search int p char input char keyint i m nchar tmp[80] \0m strlen inputn strlen key while p msubstring input tmp p-n1 pif strcmp tmp key 比较两字串是否相同return p-n1p skip[input[p]]return -1void substring char text char tmp int s int e int i jfor i s j 0 i e i jmp[j] text[i]tmp[j] \012Algorithm Gossip 双色三色河内塔说明双色河内塔与三色河内塔是由之前所介绍过的河内塔规则衍生而来双色河内塔的目的是将下图左上的圆环位置经移动成为右下的圆环位置而三色河内塔则是将下图左上的圆环经移动成为右上的圆环解法无论是双色河内塔或是三色河内塔其解法观念与之前介绍过的河内塔是类似的同样也是使用递回来解不过这次递回解法的目的不同我们先来看只有两个盘的情况这很简单只要将第一柱的黄色移动至第二柱而接下来第一柱的蓝色移动至第三柱再来是四个盘的情况首先必须用递回完成下图左上至右下的移动接下来最底层的就不用管它们了因为它们已经就定位只要再处理第一柱的上面两个盘子就可以了那么六个盘的情况呢一样首先必须用递回完成下图左上至右下的移动接下来最底层的就不用管它们了因为它们已经就定位只要再处理第一柱上面的四个盘子就可以了这又与之前只有四盘的情况相同接下来您就知道该如何进行解题了无论是八个盘十个盘以上等都是用这个观念来解题那么三色河内塔呢一样直接来看九个盘的情况首先必须完成下图的移动结果接下来最底两层的就不用管它们了因为它们已经就定位只要再处理第一柱上面的三个盘子就可以了双色河内塔 C 实作include void hanoi int disks char source char temp char targetif disks 1printf "move disk from c to c\n" source targetprintf "move disk from c to c\n" source target elsehanoi disks-1 source target temphanoi 1 source temp targethanoi disks-1 temp source targetvoid hanoi2colors int diskschar source Achar temp Bchar target Cint ifor i disks 2 i 1 i--hanoi i-1 source temp targetprintf "move disk from c to c\n" source temp printf "move disk from c to c\n" source temp hanoi i-1 target temp sourceprintf "move disk from c to c\n" temp targetprintf "move disk from c to c\n" source tempprintf "move disk from c to c\n" source targetint mainint nprintf "请输入盘数"scanf "d" n hanoi2colors n return 0C 实作include void hanoi int disks char source char temp char targetif disks 1printf "move disk from c to c\n" source target printf "move disk from c to c\n" source target printf "move disk from c to c\n" source target elsehanoi disks-1 source target temphanoi 1 source temp targethanoi disks-1 temp source targetvoid hanoi3colors int diskschar source Achar temp Bchar target Cint iif disks 3printf "move disk from c to c\n" source tempprintf "move disk from c to c\n" source tempprintf "move disk from c to c\n" source targetprintf "move disk from c to c\n" temp targetprintf "move disk from c to c\n" temp sourceprintf "move disk from c to c\n" target tempelsehanoi disks3-1 source temp targetprintf "move disk from c to c\n" source tempprintf "move disk from c to c\n" source tempprintf "move disk from c to c\n" source temp hanoi disks3-1 target temp sourceprintf "move disk from c to c\n" temp targetprintf "move disk from c to c\n" temp targetprintf "move disk from c to c\n" temp target hanoi disks3-1 source target tempprintf "move disk from c to c\n" target sourceprintf "move disk from c to c\n" target source hanoi disks3-1 temp source targetprintf "move disk from c to c\n" source temp for i disks 3 - 1 i 0 i--if i 1hanoi i-1 target source tempprintf "move disk from c to c\n"target source printf "move disk from c to c\n"target source if i 1hanoi i-1 temp source targetprintf "move disk from c to c\n" source tempint mainint nprintf "请输入盘数"scanf "d" n hanoi3colors nreturn 013Algorithm Gossip 背包问题Knapsack Problem说明假设有一个背包的负重最多可达8公斤而希望在背包中装入负重范围内可得之总价物品假设是水果好了水果的编号单价与重量如下所示0 李子 4KG NT4500 1 苹果 5KG NT57002 橘子 2KG NT22503 草莓 1KG NT1100 4甜瓜 6KG NT6700解法背包问题是关于最佳化的问题要解最佳化问题可以使用「动态规划」Dynamic programming从空集合开始每增加一个元素就先求出该阶段的最佳解直到所有的元素加入至集合中最后得到的就是最佳解以背包问题为例我们使用两个阵列value与itemvalue表示目前的最佳解所得之总价item表示最后一个放至背包的水果假设有负重量 1～8的背包8个并对每个背包求其最佳解逐步将水果放入背包中并求该阶段的最佳解放入李子背包负重 1 2 3 4 5 6 7 8 value ０００4500 4500 4500 4500 9000 item －－－０００００放入苹果背包负重 1 2 3 4 5 6 7 8 value ０００4500 5700 5700 5700 9000 item －－－０ 1 1 1 ０放入橘子背包负重 1 2 3 4 5 6 7 8 value ０2250 2250 4500 5700 6750 7950 9000 item －2 2 ０ 1 2 2 ０放入草莓背包负重 1 2 3 4 5 6 7 8 value 11002250 3350 4500 5700 6800 7950 9050 item 3 23 ０ 1 3 2 3放入甜瓜背包负重 1 2 3 4 5 6 7 8 value 11002250 3350 4500 5700 6800 7950 9050 item 3 23 ０ 1 3 2 3由最后一个表格可以得知在背包负重8公斤时最多可以装入9050元的水果而最后一个装入的水果是3号也就是草莓装入了草莓背包只能再放入7公斤8-1的水果所以必须看背包负重7公斤时的最佳解最后一个放入的是2号也就是橘子现在背包剩下负重量5公斤7-2所以看负重5公斤的最佳解最后放入的是1号也就是苹果此时背包负重量剩下0公斤5-5无法再放入水果所以求出最佳解为放入草莓橘子与苹果而总价为9050元实作 Cincludeinclude define LIMIT 8 重量限制define N 5 物品种类define MIN 1 最小重量 struct bodychar name[20]int sizeint pricetypedef struct body object int main voidint item[LIMIT1] 0int value[LIMIT1] 0int newvalue i s p object a[] "李子" 4 4500 "苹果" 5 5700"橘子" 2 2250"草莓" 1 1100"甜瓜" 6 6700 for i 0 i N i for s a[i]size s LIMIT sp s - a[i]sizenewvalue value[p] a[i]priceif newvalue value[s] 找到阶段最佳解value[s] newvalueitem[s] iprintf "物品\t价格\n"for i LIMIT i MIN i i - a[item[i]]sizeprintf "s\td\n"a[item[i]]name a[item[i]]priceprintf "合计\td\n" value[LIMIT] returnJavaclass Fruitprivate String nameprivate int sizeprivate int price public Fruit String name int size int pricethisname namethissize sizethisprice pricepublic String getNamereturn namepublic int getPricereturn pricepublic int getSizereturn sizepublic class Knapsackpublic static void main String[] argsfinal int 8final int MIN 1int[] item new int[1]int[] value new int[1] Fruit fruits[]new Fruit "李子" 4 4500new Fruit "苹果" 5 5700new Fruit "橘子" 2 2250new Fruit "草莓" 1 1100new Fruit "甜瓜" 6 6700 fo。