当前位置：文档之家› C语言设计之回溯算法

C语言设计之回溯算法

C语言设计之回溯算法（24点）

姚铸

问题叙述：

24点：

从键盘输入4个数字进行加减乘除，要求结果为24

输入要求

第一行：4 3 2 1

输出

24=12*2

2=2*1

12=4*3

问题分析：这个问题是我们小时候都应该玩过。问题的重点在于输入的数据要进行运算后得到24这个值是问题的难点。4个数之间无序的运算有很多种情况。用程序去实现24点，就需要4个数之间进行每一种的讨论。用穷举是能够计算出来的。但是时间复杂度值太大。

算法设计：这类型问题的解决方案重点在于4个数算出的结果如果不能在该步运算出24能否后悔还原会

上一次循环或递归。这里的后悔就联想到回溯算法。

算法思想：从算法设计得到了回溯算法。后悔正是回溯算法的中心思想。在得不到真正的结果的时候退回上一步。在结果计算的时候运用if或while语言对程序结束进行控制。

特殊测试：5 5 5 1 这组数据计算24点是成立的。在运算的过程中会出现小数。

参考程序（这是我自己写出的程序代码，经过测试没有问题。）：

递归算法实现回溯：

#include

int i=0;

void dian(float a,float b,float c,float d,int j); /*回朔声明*/

void jia(float a,float b,float c,float d,int j) /*进行加的运算*/

{if ((a*b!=0)&&(j<4)&&(i!=1))

{dian(a+b,c,d,0,j+1);

if (i==1)

printf("%g=%g+%g\n",a+b,a,b);}

}

void jian(float a,float b,float c,float d,int j) /*进行减的运算*/

{if ((a*b!=0)&&(j<4)&&(i!=1))

{dian(a-b,c,d,0,j+1);

dian(b-a,c,d,0,j+1);

if (i==1)

printf("%g=%g-%g\n",a-b,a,b);}

}

void cheng(float a,float b,float c,float d,int j) /*进行乘的运算*/

{if ((a*b!=0)&&(j<4)&&(i!=1))

{dian(a*b,c,d,0,j+1);

if (i==1)

printf("%g=%g*%g\n",a*b,a,b);}

}

void chu(float a,float b,float c,float d,int j) /*进行除的运算*/

{if ((a*b!=0)&&(j<4)&&(i!=1))

{dian(a/b,c,d,0,j+1);

if (i==1)

printf("%g=%g/%g\n",a/b,a,b);}

}

void dian(float a,float b,float c,float d,int j) /*进行回朔*/

{

jia(a,b,c,d,j);

cheng(a,b,c,d,j);

jian(a,d,b,c,j);

chu(a,d,b,c,j);

jia(a,c,b,d,j);

cheng(a,c,b,d,j);

jia(a,d,c,b,j);

cheng(a,d,c,b,j);

jian(a,b,c,d,j);

chu(a,b,c,d,j);

jian(b,a,c,d,j);

chu(b,a,c,d,j);

jian(d,a,b,c,j);

chu(d,a,b,c,j);

jian(a,c,b,d,j);

chu(a,c,b,d,j); /*进行交换（这里可以用程序嵌套简化）*/

if ((j==3)&&(a+b+c+d==24)) /*运算的结果是否是24，如果为24将记号改为1*/

i=1;

}

void main()

{float a,b,c,d;

printf("input 4 num");

scanf("%f%f%f%f",&a,&b,&c,&d);

if (i==0) dian(a,b,c,d,0);

if (i==0) dian(b,a,c,d,0);

if (i==0) dian(c,b,a,d,0);

if (i==0) dian(d,a,b,c,0);

}

c语言经典算法

C语言的学习要从基础，100个经典的算法题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ________________________________________________________________ 程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... __________________________________________________________________ 程序源代码： main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出，每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理，you try! 题目：判断101-200之间有多少个素数，并输出所有素数。 _________________________________________________________________ 程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。 ___________________________________________________________________ 程序源代码： #include "math.h" main() { int m,i,k,h=0,leap=1; printf("\n"); for(m=101;m<=200;m++) { k=sqrt(m+1); for(i=2;i<=k;i++) if(m%i==0) {leap=0;break;} if(leap) {printf("%-4d",m);h++; if(h%10==0) printf("\n"); } leap=1; } printf("\nThe total is %d",h); } 题目：打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个“水仙花数”，因为153=1的三次方＋5的三次方＋3的三次方。 __________________________________________________________________ 程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。 ___________________________________________________________________ 程序源代码：

子集和数的回溯算法

设计四子集和数的回溯算法班级通信08-2BF 学号1408230929 姓名杨福成绩分一、设计目的 1.掌握回溯法解题的基本思想； 2.掌握子集和数问题的回溯算法； 3.进一步掌握子集和数问题的回溯递归算法、迭代算法的基本思想和算法设计方法；二、设计内容 a) 任务描述 1）子集和数问题简介子集和数问题是假定有n 个不同的正数（通常称为权），要求找出这些数中所有事的某和数为M 的组合。 2）设计任务简介设计、编程、测试求解子集和数问题的回溯算法。 1．子集和数问题的表示方案本设计利用大小固定的元组来研究回溯算法，在此情况下，解向量的元素X （i ）取1或0值，它表示是否包含了权数W （i ）. 生成图中任一结点的儿子是很容易的。对于i 级上的一个结点，其左儿子对应于X （i ）=1，右儿子对应于X(i)=0。对于限界函数的一种简单选择是，当且仅当∑∑+==≥+ n k i k i M i W i X i W 11)()()(时，B(X(1),〃〃〃，X （k ）)=true 。显然，如果这个条件不满足，X(1),〃〃〃，X （k ）就不能导致一个答案结点。如果假定这些W （i ）一开始就是按非降次序列排列的，那么这些限界函数可以被强化。在这种情况下，如果M k W i X i W k i >++∑=)1()()(1 ,则X(1),〃〃〃，X （k ）就不能导致一个答案结点。因此，将要使用的限界函数是B k （X （1），〃〃〃，X （k ））=true,当且仅当 M i W i X i W n k i k i =+∑∑+==11)()()(。 2．主要数据类型与变量 int M ; // 表示要求得到的子集和； int s; // 表示所选当前元素之前所选的元素和；

算法设计与分析复习题目及答案

一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ B ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ）

C语言经典算法100例题目

看懂一个程序，分三步：1、流程；2、每个语句的功能；3、试数；小程序：1、尝试编程去解决他；2、看答案；3、修改程序，不同的输出结果； 4、照答案去敲； 5、调试错误； 6、不看答案，自己把答案敲出来； 7、实在不会就背会。。。。。周而复始，反复的敲。。。。。【程序1】题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ ============================================================== 【程序2】题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ ============================================================== 【程序3】题目：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？============================================================== 【程序4】题目：输入某年某月某日，判断这一天是这一年的第几天？ ============================================================== 【程序5】题目：输入三个整数x,y,z，请把这三个数由小到大输出。 ============================================================== 【程序6】题目：用*号输出字母C的图案。 ============================================================== 【程序7】题目：输出特殊图案，请在c环境中运行，看一看，Very Beautiful! ============================================================== 【程序8】题目：输出9*9口诀。 ============================================================== 【程序9】题目：要求输出国际象棋棋盘。 ============================================================== 【程序10】题目：打印楼梯，同时在楼梯上方打印两个笑脸。 -------------------------------------------------------------------------------- 【程序11】题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ==============================================================

算法分析与程序设计动态规划及回溯法解背包问题

动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

C语言经典算法100例(1---30)

2008-02-18 18:48 【程序1】题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000)

回溯算法的应用(DOC)

回溯算法的应用课程名称：算法设计与分析院系：************************ 学生姓名：****** 学号：************ 专业班级：***************************** 指导教师：****** 2013年12月27日

回溯法的应用摘要：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法，其意义是在递归直到可解的最小问题后，逐步返回原问题的过程。而这里所说的回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。全排列和求最优解问题是比较经典的问题，我们可以采用多种算法去求解此问题，比如动态规划法、分支限界法、回溯法。在这里我们采用回溯法来解决这个问题。关键词：回溯法全排列最优值枚举

回溯搜索算法

补充2 回溯法解回溯法的深度优先搜索策略 z理解回溯法的深度优先搜索策略。 z掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架通过应用范例学习回溯法的设计策略 z通过应用范例学习回溯法的设计策略。

Sch2-1z Sch2-1 方法概述搜索算法介绍（1）穷举搜索（2）盲目搜索 —深度优先(DFS)或回溯搜索( Backtracking); —广度优先搜索( BFS ); (Branch &Bound) —分支限界法(Branch & Bound)；—博弈树搜索( α-βSearch) （3）启发式搜索 —A* 算法和最佳优先( Best-First Search ) —迭代加深的A*算法 —B*AO*SSS*等算法B , AO , SSS 等算法 —Local Search, GA等算法

Sch2-1z Sch2-1 方法概述搜索空间的三种表示： —表序表示：搜索对象用线性表数据结构表示； —显示图表示：搜索对象在搜索前就用图（树）的数据结构表示； —隐式图表示：除了初始结点，其他结点在搜索过程中动态生成。缘于搜索空间大，难以全部存储。 z 搜索效率的思考：随机搜索 —上世纪70年代中期开始，国外一些学者致力于研究随机搜索求解困难的组合问题，将随机过程引入搜索； —选择规则是随机地从可选结点中取一个从而可以从统计角度分析搜选择规则是随机地从可选结点中取一个，从而可以从统计角度分析搜索的平均性能； —随机搜索的一个成功例子是：判定一个很大的数是不是素数，获得了第个多式时算法第一个多项式时间的算法。

算法设计与分析：回溯法-实验报告

应用数学学院信息安全专业班学号姓名实验题目回溯算法实验评分表

实验报告一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。二、实验内容【实验内容】最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。三、算法思想和实现【实现代码】

【实验数据】假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。部件重量表：部件价格表：【运行结果】

实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。四、问题与讨论影响回溯法效率的因素有哪些？答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。五、总结这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井

搜索与回溯算法介绍

搜索与回溯算法介绍一、概述：计算机常用算法大致有两大类：一类叫蛮干算法，一类叫贪心算法。前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。后者在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解。二、搜索与回溯：这里着重介绍搜索与回溯。当很多问题无法根据某种确定的计算法则来求解时可以利用搜索与回溯的技术求解。回溯是搜索算法中既带有系统性又带有跳跃性的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索。在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进。如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。【建立解空间】问题的解应该如何描述，如何建立呢？问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。借助图论的思想，可以用图来描述，图的定义为G，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向

回溯算法实验

中原工学院信息商务学院实验报告实验项目名称回溯划算法的应用课程名称算法设计与分析学院(系、部)中原工学院信息商务学院学科专业计算机科学与技术系班级学号计科132班17号姓名程一涵任课教师邬迎日期2014年12月9日

实验五回溯算法的应用一、实验目的 1．掌握回溯算法的基本概念 2．熟练掌握回溯算法解决问题的基本步骤。 3．学会利用回溯算法解决实际问题。二．问题描述题目一：N皇后问题要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数n (n ≤ 13) 输出有多少种放置方法输入输出实例：

三．算法设计首先，确定第一行皇后的位置，再确定第二行的位置，并且要注意不能同行同列同对角线，若是发现有错则返回上一层，继续判断。满足约束条件时，则开始搜索下一个皇后的位置，直到找出问题的解。四.程序调试及运行结果分析五.实验总结通过这次试验，使得我们面对问题时的解题思路变得更加灵活和多变，并且使我们的编写能力稍稍的提高一些。初步了解了回溯算法，回溯算法实际是一个类似枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。他特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题

附录：程序清单（程序过长，可附主要部分） #include #include using namespace std; int a[20],n; backdate(int n); int check(int k); void output(int n); int main() { int n; cout<<"请输入皇后的个数："; cin>>n; cout<<"位置排列是："<0) { a[k]=a[k]+1; while((a[k]<=n) && (check(k)==0)) a[k]=a[k]+1; if(a[k]<=n) if(k==n) { num++; output(n); } else { k=k+1; a[k]=0; } else k=k-1; } cout<<"一共有"<

回溯法

回溯法回溯法也是搜索算法中的一种控制策略，但与枚举法不同的是，它是从初始状态出发，运用题目给出的条件、规则，按照深度优秀搜索的顺序扩展所有可能情况，从中找出满足题意要求的解答。回溯法是求解特殊型计数题或较复杂的枚举题中使用频率最高的一种算法。一、回溯法的基本思路何谓回溯法，我们不妨通过一个具体实例来引出回溯法的基本思想及其在计算机上实现的基本方法。【例题12.2.1】n皇后问题一个ｎ×ｎ（1≤n≤100）的国际象棋棋盘上放置ｎ个皇后，使其不能相互攻击，即任何两个皇后都不能处在棋盘的同一行、同一列、同一条斜线上，试问共有多少种摆法？输入： n 输出：所有分案。每个分案为n+1行，格式：方案序号以下n行。其中第i行（1≤i≤n）行为棋盘i行中皇后的列位置。在分析算法思路之前，先让我们介绍几个常用的概念： 1、状态（state）状态是指问题求解过程中每一步的状况。在ｎ皇后问题中，皇后所在的行位置i(1≤i≤n)即为其时皇后问题的状态。显然，对问题状态的描述，应与待解决问题的自然特性相似，而且应尽量做到占用空间少，又易于用算符对状态进行运算。 2、算符（operater）算符是把问题从一种状态变换到另一种状态的方法代号。算符通常采用合适的数据来表示，设为局部变量。n皇后的一种摆法对应1．．ｎ排列方案（a1，…，a n）。排列中的每个元素a i对应ｉ行上皇后的列位置（1≤i≤n）。由此想到，在ｎ皇后问题中，采用当前行的列位置i(1≤i≤n)作为算符是再合适不过了。由于每行仅放一个皇后，因此行攻击的问题自然不存在了，但在试放当前行的一个皇后时，不是所有列位置都适用。例如(l，ｉ)位置放一个皇后，若与前1．．l-1行中的j行皇后产生对角线攻击(｜ｊ－l｜=｜a j －i｜)或者列攻击(ｉ≠a j)，那么算符ｉ显然是不适用的，应当舍去。因此，不产生对角线攻击和列攻击是ｎ皇后问题的约束条件，即排列（排列a1，…，a i，…，a j，…，a n）必须满足条件(｜ｊ－ｉ｜≠｜a j－a i｜) and (a i≠a j) (1≤i，j≤n)。 3、解答树（analytic tree）现在让我们先来观察一个简单的ｎ皇后问题。设ｎ＝4，初始状态显然是一个空棋盘。此时第一个皇后开始从第一行第一列位置试放，试放的顺序是从左至右、自上而下。每个棋盘由４个数据表征相应的状态信息（见下图）：（××××）

C语言经典算法大全

C语言经典算法大全老掉牙河内塔费式数列巴斯卡三角形三色棋老鼠走迷官（一）老鼠走迷官（二）骑士走棋盘八个皇后八枚银币生命游戏字串核对双色、三色河内塔背包问题（Knapsack Problem）数、运算蒙地卡罗法求PI Eratosthenes筛选求质数超长整数运算（大数运算）长PI 最大公因数、最小公倍数、因式分解完美数阿姆斯壮数最大访客数中序式转后序式（前序式）后序式的运算关于赌博洗扑克牌（乱数排列） Craps赌博游戏约瑟夫问题（Josephus Problem）集合问题排列组合格雷码（Gray Code）产生可能的集合

m元素集合的n个元素子集数字拆解排序得分排行选择、插入、气泡排序 Shell 排序法- 改良的插入排序Shaker 排序法- 改良的气泡排序Heap 排序法- 改良的选择排序快速排序法（一）快速排序法（二）快速排序法（三）合并排序法基数排序法搜寻循序搜寻法（使用卫兵）二分搜寻法（搜寻原则的代表）插补搜寻法费氏搜寻法矩阵稀疏矩阵多维矩阵转一维矩阵上三角、下三角、对称矩阵奇数魔方阵 4N 魔方阵 2(2N+1) 魔方阵

1.河内之塔说明河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家Edouard Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。解法如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：264- 1 = 18446744073709551615为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什幺概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 #include void hanoi(int n, char A, char B, char C) { if(n == 1) { printf("Move sheet %d from %c to %c\n", n, A, C); } else { hanoi(n-1, A, C, B); printf("Move sheet %d from %c to %c\n", n, A, C); hanoi(n-1, B, A, C); } } int main() { int n; printf("请输入盘数："); scanf("%d", &n); hanoi(n, 'A', 'B', 'C'); return 0; }

回溯算法实例一培训讲学

回溯算法实例一

【问题】填字游戏问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，使得所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。回溯法找一个解的算法： { int m=0,ok=1; int n=8; do{ if (ok) 扩展; else 调整; ok=检查前m个整数填放的合理性; } while ((!ok||m!=n)&&(m!=0)) if (m!=0) 输出解; else 输出无解报告； } 如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下：回溯法找全部解的算法： { int m=0,ok=1; int n=8; do{ if (ok) { if (m==n) { 输出解；调整； } else 扩展; } else 调整; ok=检查前m个整数填放的合理性; } while (m!=0);

算法分析复习题目及答案

内部资料，转载请注明出处，谢谢合作。一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。

C语言必背18个经典程序

C语言必背18个经典程序 (总10页) -CAL-FENGHAI.-(YICAI)-Company One1 -CAL-本页仅作为文档封面，使用请直接删除

C语言必背18个经典程序 1、/*输出9*9口诀。共9行9列，i控制行，j控制列。*/ #include "stdio.h" main() {int i,j,result; for (i=1;i<10;i++) { for(j=1;j<10;j++) { result=i*j; printf("%d*%d=%-3d",i,j,result);/*-3d表示左对齐，占3位*/ } printf("\n");/*每一行后换行*/ } system("pause"); } 2、/*古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？兔子的规律为数列1,1,2,3,5,8,13,21....*/ main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出，每行四个*/ f1=f1+f2; /*前两个月加起来赋值给第三个月*/ f2=f1+f2; /*前两个月加起来赋值给第三个月*/ } } 3、/*判断101-200之间有多少个素数，并输出所有素数及素数的个数。程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。*/ #include "math.h" main() { int m,i,k,h=0,leap=1; printf("\n"); for(m=101;m<=200;m++) { k=sqrt(m); for(i=2;i<=k;i++)

回溯算法实例一

【问题】填字游戏问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。回溯法找一个解的算法： { int m=0,ok=1; int n=8; do{ if (ok) 扩展; else 调整; ok=检查前m个整数填放的合理性; } while ((!ok||m!=n)&&(m!=0)) if (m!=0) 输出解; else 输出无解报告； } 如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下：回溯法找全部解的算法： { int m=0,ok=1; int n=8; do{ if (ok) { if (m==n) { 输出解；调整； } else 扩展; } else 调整; ok=检查前m个整数填放的合理性; } while (m!=0); }

C语言经典算法题目及答案

题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000) bonus=i*0.1; else if(i<=200000) bonus=bonus1+(i-100000)*0.075; else if(i<=400000) bonus=bonus2+(i-200000)*0.05; else if(i<=600000) bonus=bonus4+(i-400000)*0.03;

文档之家

C语言设计之回溯算法

c语言经典算法

子集和数的回溯算法

算法设计与分析复习题目及答案

C语言经典算法100例题目

算法分析与程序设计动态规划及回溯法解背包问题

C语言经典算法100例(1---30)

回溯算法的应用(DOC)

回溯搜索算法

算法设计与分析：回溯法-实验报告

搜索与回溯算法介绍

回溯算法实验

最新《算法分析与设计》期末考试复习题纲(完整版)

回溯法

C语言经典算法大全

回溯算法实例一培训讲学

算法分析复习题目及答案

C语言必背18个经典程序

回溯算法实例一

C语言经典算法题目及答案