算法大全(C.C..)

C语言经典算法大全1.冒泡排序算法冒泡排序是一种简单但低效的排序算法，它通过多次遍历列表，比较相邻元素并交换位置，直到整个列表有序。

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

```void bubbleSort(int arr[], int n)for (int i = 0; i < n-1; i++)for (int j = 0; j < n-i-1; j++)if (arr[j] > arr[j+1])//交换元素int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}```2.选择排序算法选择排序是一种简单但高效的排序算法，它通过多次遍历列表，找到最小元素并将其放置在正确的位置上。

选择排序的时间复杂度也为O(n^2)。

```void selectionSort(int arr[], int n)int minIndex, temp;for (int i = 0; i < n-1; i++)minIndex = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[minIndex])minIndex = j;}}//交换元素temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}```3.插入排序算法插入排序是一种简单但高效的排序算法，它通过将未排序的元素插入到已排序的列表中，逐步构建排序好的列表。

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

```void insertionSort(int arr[], int n)int i, key, j;for (i = 1; i < n; i++)key = arr[i];j=i-1;while (j >= 0 && arr[j] > key)arr[j + 1] = arr[j];j=j-1;}arr[j + 1] = key;}```4.快速排序算法快速排序是一种高效的排序算法，它通过选择一个主元，将列表分割为两个子列表，其中一个子列表的所有元素都小于主元，另一个子列表的所有元素都大于主元。

高精度算法大全在一般的科学计算中,会经常算到小数点后几百位或者更多, 当然也可能是几千亿几百亿的大数字.一般这类数字我们统称为高精度数, 高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开放等运算.譬如一个很大的数字N >= 10A 100,很显然这样的数字无法在计算机中正常存储.于是, 我们想到了办法, 将这个数字拆开, 拆成一位一位的或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字. 这样这个数字就被称谓是高精度数.对于高精度数, 也要像平常数一样做加减乘除以及乘方的运算, 于是就有了高精度算法:由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最多只能输出1 6位有效数字，如果超过1 6位，则只能按浮点形式输出，另外，一般计算机实数表示的范围为1038，如果超过这个范围，计算机就无法表示了。

但是我们可以通过一些简单的办法来解决这个问题。

这就是我们要说的高精度计算机。

一、基本方法：在计算机上进行高精度计算，首先要处理好以下几个基本问题：1 、数据的接收与存储；2 、计算结果位数的确定；3、进位处理和借位处理；4 、商和余数的求法；下面我们逐一介绍一下这几个问题的解决方法。

1、数据的接收与存储：要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。

通常：①、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。

②、当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。

③ 、分离各位数字。

接收数据子模块 (字符型变量接收数据 ) ： prucedure readdata(var in:array[1..100] ofinteger); var ch:char; i,k:integer; begin read(ch);k:=0;while ch in['0'..'9'] do begin inc(k);int[k]:=ord(ch)-48; read(ch); end; end;2、计算结果位数的确定① 、两数之和的位数最大为较大的数的位数加 1 ② 、乘积的位数最大为两个因子的位数之和。

C语言算法大全( C，C++）一、数论算法1．求两数的最大公约数functiongcd(a,b:integer):integer; beginifb=0thengcd:=aelsegcd:=gcd(b,amodb);end;2．求两数的最小公倍数functionlcm(a,b:integer):integer; beginifa<bthenswap(a,b);lcm:=a;whilelcmmodb>0doinc(lcm,a);end;3．素数的求法A.小范围内判断一个数是否为质数：functionprime(n:integer):Boolean;varI:integer;beginforI:=2totrunc(sqrt(n))doifnmodI=0thenbeginprime:=false;exit;end;prime:=true;end;B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：proceduregetprime;vari,j:longint;p:array[1..50000]ofboolean;beginfillchar(p,sizeof(p),true);p[1]:=false;i:=2;whilei<50000dobeginifp[i]thenbeginj:=i*2;whilej<50000dobeginp[j]:=false;inc(j,i);end;end;inc(i);end;l:=0;fori:=1to50000doifp[i]thenbegininc(l);pr[l]:=i;end;end;{getprime}functionprime(x:longint):integer; vari:integer;beginprime:=false;fori:=1toldoifpr[i]>=xthenbreakelseifxmodpr[i]=0thenexit;prime:=true;end;{prime}二、图论算法1．最小生成树A.Prim算法：procedureprim(v0:integer);varlowcost,closest:array[1..maxn] ofinteger;i,j,k,min:integer;beginfori:=1tondobeginlowcost[i]:=cost[v0,i]; closest[i]:=v0;end;fori:=1ton-1dobegin{寻找离生成树最近的未加入顶点k}min:=maxlongint;forj:=1tondoif(lowcost[j]<min)and(lowcost[j]<>0)thenbeginmin:=lowcost[j];k:=j;end;lowcost[k]:=0;{将顶点k加入生成树}{生成树中增加一条新的边k到closest[k]}{修正各点的lowcost和closest值}forj:=1tondoifcost[k,j]<lwocost[j]thenbeginlowcost[j]:=cost[k,j];closest[j]:=k;end;end;end;{prim}B.Kruskal算法：(贪心)按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。

C语言十大滤波算法Company Document number：WTUT-WT88Y-W8BBGB-BWYTT-19998十大滤波算法程序大全(精心整理版)(转自网络)11、限幅滤波法*************************************************** *函数名称：AmplitudeLimiterFilter()-限幅滤波法*优点：能有效克服因偶然因素引起的脉冲干扰*缺点：无法抑制那种周期性的干扰，且平滑度差*说明：1、调用函数GetAD(),该函数用来取得当前值2、变量说明Value:最近一次有效采样的值，该变量为全局变量NewValue:当前采样的值ReturnValue:返回值3、常量说明A:两次采样的最大误差值，该值需要使用者根据实际情况设置*入口：Value,上一次有效的采样值，在主程序里赋值*出口：ReturnValue,返回值，本次滤波结果****************************************************/#defineA10unsignedcharValueunsignedcharAmplitudeLimiterFilter(){unsignedcharNewValue;unsignedcharReturnValue;NewValue=GatAD();if(((NewValue-Value)>A))||((Value-NewValue)>A)))ReturnValue=Value;elseReturnValue=NewValue;return(ReturnValue);}2、中位值滤波法/*****************************************************函数名称：MiddlevalueFilter()-中位值滤波法*优点：能有效克服因偶然因素引起的波动干扰；对温度、液位等变化缓慢的被测参数有良好的滤波效果*缺点：对流量，速度等快速变化的参数不宜*说明：1、调用函数GetAD(),该函数用来取得当前值Delay(),基本延时函数2、变量说明ArrDataBuffer[N]:用来存放一次性采集的N组数据Temp:完成冒泡法试用的临时寄存器i,j,k:循环试用的参数值3、常量说明N：数组长度*入口：*出口：value_buf[(N-1)/2],返回值，本次滤波结果*****************************************************/ #defineN11unsignedcharMiddlevalueFilter(){unsignedcharvalue_buf[N];unsignedchari,j,k,temp;for(i=0;i<N;i++){value_buf[i]=get_ad();delay();}for(j=0;j<N-1;j++){for(k=0;k<N-j;k++){if(value_buf[k]>value_buf[k+1]){temp=value_buf[k];value_buf[k]=value_buf[k+1];value_buf[k+1]=temp;}}}returnvalue_buf[(N-1)/2];}3、算术平均滤波法/*********************************************************说明：连续取N个采样值进行算术平均运算优点：试用于对一般具有随机干扰的信号进行滤波。

计算能力是小学数学学习的基础，今天小数详细整理了小学阶段关于四则运算的基础知识及运算过程中常用到的简便方法，趁着暑假帮孩子们查漏补缺，提高计算能力，扎实数学基础，助力孩子开学快速进步。

运算定律✍加法交换律两个数相加，交换加数的位置，它们的和不变，即a+b=b+a 。

✍加法结合律三个数相加，先把前两个数相加，再加上第三个数；或者先把后两个数相加，再和第一个数相加它们的和不变，即（a+b)+c=a+(b+c) 。

✍乘法交换律两个数相乘，交换因数的位置它们的积不变，即a×b=b×a。

✍乘法结合律三个数相乘，先把前两个数相乘，再乘以第三个数；或者先把后两个数相乘，再和第一个数相乘，它们的积不变，即(a×b)×c=a×(b×c)。

✍乘法分配律两个数的和与一个数相乘，可以把两个加数分别与这个数相乘再把两个积相加，即(a+b)×c=a×c+b×c 。

✍减法的性质从一个数里连续减去几个数，可以从这个数里减去所有减数的和，差不变，即a-b-c=a-(b+c) 。

运算法则✍整数加法计算法则相同数位对齐，从低位加起，哪一位上的数相加满十，就向前一位进一。

✍整数减法计算法则相同数位对齐，从低位加起，哪一位上的数不够减，就从它的前一位退一作十，和本位上的数合并在一起，再减。

✍整数乘法计算法则先用一个因数每一位上的数分别去乘另一个因数各个数位上的数，用因数哪一位上的数去乘，乘得的数的末尾就对齐哪一位，然后把各次乘得的数加起来。

✍整数除法计算法则先从被除数的高位除起，除数是几位数，就看被除数的前几位；如果不够除，就多看一位，除到被除数的哪一位，商就写在哪一位的上面。

如果哪一位上不够商1，要补“0”占位。

每次除得的余数要小于除数。

✍小数乘法法则先按照整数乘法的计算法则算出积，再看因数中共有几位小数，就从积的右边起数出几位，点上小数点；如果位数不够，就用“0”补足。

C语言经典算法大全老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）骑士走棋盘八个皇后八枚银币生命游戏字串核对双色、三色河内塔背包问题（Knapsack Problem）数、运算蒙地卡罗法求 PIEratosthenes筛选求质数超长整数运算（大数运算）长 PI最大公因数、最小公倍数、因式分解完美数阿姆斯壮数最大访客数中序式转后序式（前序式）后序式的运算关于赌博洗扑克牌（乱数排列）Craps赌博游戏约瑟夫问题（Josephus Problem）集合问题排列组合格雷码（Gray Code）产生可能的集合m元素集合的n个元素子集数字拆解排序得分排行选择、插入、气泡排序Shell 排序法 - 改良的插入排序Shaker 排序法 - 改良的气泡排序Heap 排序法 - 改良的选择排序快速排序法（一）快速排序法（二）快速排序法（三）合并排序法基数排序法搜寻循序搜寻法（使用卫兵）二分搜寻法（搜寻原则的代表）插补搜寻法费氏搜寻法矩阵稀疏矩阵多维矩阵转一维矩阵上三角、下三角、对称矩阵奇数魔方阵4N 魔方阵2(2N+1) 魔方阵1.河内之塔说明河内之塔(Towers of Hanoi)是法国人(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家 Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。

解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。

如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。

C语言常用算法大全1.排序算法-冒泡排序：依次比较相邻的两个元素，如果顺序不对则交换，每轮找出一个最大或最小的元素-选择排序：从未排序的元素中选择最小或最大的放到已排序的最后，以此类推-插入排序：将未排序的元素插入到已排序的合适位置，从后向前进行比较和交换-快速排序：选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后对左右两边递归地进行快速排序-归并排序：将待排序的序列不断划分为左右两部分，分别排序后再将排序好的左右两部分按顺序合并-堆排序：构建大顶堆，将堆顶元素与末尾元素交换，然后重新调整堆，重复这个过程直到排序完成2.查找算法-顺序查找：从给定的元素序列中逐个比较，直到找到目标元素或遍历完整个序列-二分查找：对于有序序列，在序列的中间位置比较目标元素和中间元素的大小关系，通过每次缩小一半的范围来查找目标元素-插值查找：根据目标元素与有序序列的最小值和最大值的比例推测目标元素所在的位置，然后递归地进行查找-斐波那契查找：根据斐波那契数列的性质来确定目标元素所在的位置，然后递归地进行查找3.图算法-深度优先（DFS）：从图的一些顶点出发，依次访问其未被访问过的邻接顶点，直到所有顶点都被访问过为止-广度优先（BFS）：从图的一些顶点出发，逐层遍历图的顶点，直到所有顶点都被访问过为止- 最小生成树算法：Prim算法和Kruskal算法，用于找到连接图中所有顶点的最小权值边，构成一棵包含所有顶点的生成树- 最短路径算法：Dijkstra算法和Floyd-Warshall算法，用于找到图中两个顶点之间的最短路径-拓扑排序：用于有向无环图（DAG）中的顶点排序，确保排序后的顶点满足所有依赖关系-关键路径算法：找出网络中的关键路径，即使整个工程完成的最短时间4.字符串算法- KMP算法：通过预处理模式串构建next数组，利用next数组在匹配过程中跳过一部分不可能匹配的子串- Boyer-Moore算法：从模式串的末尾开始匹配，利用坏字符和好后缀规则进行跳跃匹配- Rabin-Karp算法：利用哈希函数对主串和匹配串的子串进行哈希计算，然后比较哈希值是否相等- 字符串匹配算法：BM算法、Shift-And算法、Sunday算法等，用于寻找模式串在主串中的出现位置5.动态规划算法-最长公共子序列（LCS）：用于寻找两个序列中最长的公共子序列-最长递增子序列（LIS）：用于寻找给定序列中最长的递增子序列-0-1背包问题：将有限的物品放入容量为C的背包中，使得物品的总价值最大-最大子数组和：用于求解给定数组中连续子数组的最大和-最大正方形：在给定的0-1矩阵中，找出只包含1的最大正方形的边长这些算法是在C语言中常用的算法，它们涵盖了排序、查找、图、字符串和动态规划等多个领域。

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。

722Chapter 16.Integration of Ordinary Differential EquationsSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).(*rkqs)(y,dydx,nvar,&x,h,eps,yscal,&hdid,&hnext,derivs);if (hdid ==h)++(*nok);else ++(*nbad);if ((x-x2)*(x2-x1)>=0.0){Are we done?for (i=1;i<=nvar;i++)ystart[i]=y[i];if (kmax){xp[++kount]=x;Save final step.for (i=1;i<=nvar;i++)yp[i][kount]=y[i];}free_vector(dydx,1,nvar);free_vector(y,1,nvar);free_vector(yscal,1,nvar);return;Normal exit.}if (fabs(hnext)<=hmin)nrerror("Step size too small in odeint");h=hnext;}nrerror("Too many steps in routine odeint");}CITED REFERENCES AND FURTHER READING:Gear,C.W.1971,Numerical Initial Value Problems in Ordinary Differential Equations (EnglewoodCliffs,NJ:Prentice-Hall).[1]Cash,J.R.,and Karp,A.H.1990,ACM Transactions on Mathematical Software ,vol.16,pp.201–222.[2]Shampine,L.F .,and Watts,H.A.1977,in Mathematical Software III ,J.R.Rice,ed.(New York:Academic Press),pp.257–275;1979,Applied Mathematics and Computation ,vol.5,pp.93–121.Forsythe,G.E.,Malcolm,M.A.,and Moler,C.B.1977,Computer Methods for MathematicalComputations (Englewood Cliffs,NJ:Prentice-Hall).16.3Modified Midpoint MethodThis section discusses the modified midpoint method ,which advances a vector of dependent variables y (x )from a point x to a point x +H by a sequence of n substeps each of size h ,h =H/n(16.3.1)In principle,one could use the modified midpoint method in its own right as an ODE integrator.In practice,the method finds its most important application as a part of the more powerful Bulirsch-Stoer technique,treated in §16.4.You can therefore consider this section as a preamble to §16.4.The number of right-hand side evaluations required by the modified midpoint method is n +1.The formulas for the method arez 0≡y (x )z 1=z 0+hf (x,z 0)z m +1=z m −1+2hf (x +mh,z m )for m =1,2,...,n −1y (x +H )≈y n ≡12[z n +z n −1+hf (x +H,z n )](16.3.2)16.3Modified Midpoint Method 723Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).Here the z ’s are intermediate approximations which march along in steps of h ,while y n is the final approximation to y (x +H ).The method is basically a “centered difference”or “midpoint”method (compare equation 16.1.2),except at the first and last points.Those give the qualifier “modified.”The modified midpoint method is a second-order method,like (16.1.2),but with the advantage of requiring (asymptotically for large n )only one derivative evaluation per step h instead of the two required by second-order Runge-Kutta.Perhaps there are applications where the simplicity of (16.3.2),easily coded in-line in some other program,recommends it.In general,however,use of the modified midpoint method by itself will be dominated by the embedded Runge-Kutta method with adaptive stepsize control,as implemented in the preceding section.The usefulness of the modified midpoint method to the Bulirsch-Stoer technique (§16.4)derives from a “deep”result about equations (16.3.2),due to Gragg.It turns out that the error of (16.3.2),expressed as a power series in h ,the stepsize,contains only even powers of h ,y n −y (x +H )=∞ i =1αi h 2i(16.3.3)where H is held constant,but h changes by varying n in (16.3.1).The importance of this even power series is that,if we play our usual tricks of combining steps to knock out higher-order error terms,we can gain two orders at a time!For example,suppose n is even,and let y n/2denote the result of applying (16.3.1)and (16.3.2)with half as many steps,n →n/2.Then the estimatey (x +H )≈4y n −y n/23(16.3.4)is fourth-order accurate,the same as fourth-order Runge-Kutta,but requires only about 1.5derivative evaluations per step h instead of Runge-Kutta’s 4evaluations.Don’t be too anxious to implement (16.3.4),since we will soon do even better.Now would be a good time to look back at the routine qsimp in §4.2,and especially to compare equation (4.2.4)with equation (16.3.4)above.You will see that the transition in Chapter 4to the idea of Richardson extrapolation,as embodied in Romberg integration of §4.3,is exactly analogous to the transition in going from this section to the next one.Here is the routine that implements the modified midpoint method,which will be used below.#include "nrutil.h"void mmid(float y[],float dydx[],int nvar,float xs,float htot,int nstep,float yout[],void (*derivs)(float,float[],float[]))Modified midpoint step.At xs ,input the dependent variable vector y[1..nvar]and its deriva-tive vector dydx[1..nvar].Also input is htot ,the total step to be made,and nstep ,the number of substeps to be used.The output is returned as yout[1..nvar],which need not be a distinct array from y ;if it is distinct,however,then y and dydx are returned undamaged.{int n,i;float x,swap,h2,h,*ym,*yn;724Chapter 16.Integration of Ordinary Differential EquationsSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press. P rograms Copyright (C) 1988-1992 by Numerical Recipes Software. Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copying of machine-readable files (including this one) to any server c omputer, is strictly prohibited. To order Numerical Recipes books, d iskettes, or CDROMs visit website or call 1-800-872-7423 (North America only), o r send email to trade@ (outside North America).ym=vector(1,nvar);yn=vector(1,nvar);h=htot/nstep;Stepsize this trip.for (i=1;i<=nvar;i++){ym[i]=y[i];yn[i]=y[i]+h*dydx[i];First step.}x=xs+h;(*derivs)(x,yn,yout);Will use yout for temporary storage of deriva-tives.h2=2.0*h;for (n=2;n<=nstep;n++){General step.for (i=1;i<=nvar;i++){swap=ym[i]+h2*yout[i];ym[i]=yn[i];yn[i]=swap;}x +=h;(*derivs)(x,yn,yout);}for (i=1;i<=nvar;i++)Last step.yout[i]=0.5*(ym[i]+yn[i]+h*yout[i]);free_vector(yn,1,nvar);free_vector(ym,1,nvar);}CITED REFERENCES AND FURTHER READING:Gear,C.W.1971,Numerical Initial Value Problems in Ordinary Differential Equations (EnglewoodCliffs,NJ:Prentice-Hall),§6.1.4.Stoer,J.,and Bulirsch,R.1980,Introduction to Numerical Analysis (New York:Springer-Verlag),§7.2.12.16.4Richardson Extrapolation and theBulirsch-Stoer MethodThe techniques described in this section are not for differential equations containing nonsmooth functions.For example,you might have a differential equation whose right-hand side involves a function that is evaluated by table look-up and interpolation.If so,go back to Runge-Kutta with adaptive stepsize choice:That method does an excellent job of feeling its way through rocky or discontinuous terrain.It is also an excellent choice for quick-and-dirty,low-accuracy solution of a set of equations.A second warning is that the techniques in this section are not particularly good for differential equations that have singular points inside the interval of integration.A regular solution must tiptoe very carefully across such points.Runge-Kutta with adaptive stepsize can sometimes effect this;more generally,there are special techniques available for such problems,beyond our scope here.Apart from those two caveats,we believe that the Bulirsch-Stoer method,discussed in this section,is the best known way to obtain high-accuracy solutions to ordinary differential equations with minimal computational effort.(A possible exception,infrequently encountered in practice,is discussed in §16.7.)。