算法描述例题
① 10分求动态规划算法的形式化描述
动态规划算法没有一个能表示所有情况的为代码，动态规划是解决多阶段决策最优化问题的一种思想方法，万能伪代码估计很难说出来。
使用动态规划的动机有两种，一种是利用递归的重叠子问题进行记忆化求解，这样的问题一般有比较明显的递归特性，利用递归求解后可以发现其中重叠计算的部分，利用重叠子问题转化成动态规划。还有一种是多阶段决策，所谓决策就对应着状态转移。多阶段最优决策问题也就是使得最后的转移是最优的，对于满足最优子结构和无后效性的问题，都可以分析第i
个状态到i+1状态转移的决策，而且这个决策应该是所有可以选的决策中最优的，这就是动态规划更直观的想法。
有这么一种取巧的方法，如果一个题目说明可以采用动态规划的话，而你却没有动态规划的思路，可以首先考虑用递归的方法来求解，一旦有了递归的思路来解决他，那么一定能够通过逆推求出动态规划的算法。
比如
例题1，已知两个字符串，长为L，求他们的最长的公共子串。'abacad'和'bcaaca'的最长公共子串窜就是'baca'
如果题目要求用动态规划求解，很可能根本没有思路，但是考虑用递归怎么能解决这个问题呢？
比较A[1...L]和B[1...L]这两个字符串的公共子串是不是可以变成求A[1...L-1]和B[1...L-1]的公共子串呢？貌似可以，但是好像少考虑情况了，还应该包括A[1...L]和B[1...L-1]的公共子串以及A[1...L-1]和B[1...L]这两种情况呀。这样就分析出了递归的子结构。而这个递归的子结构就是动态规划的基础。
考虑 如果A〔L〕＝＝B〔L〕那么 LCS( A[1...L] , B[1...L]) = LCS( A[1...L-1], B[1...L-1] ) + 1
否则 LCS( A[1...L] , B[1...L]) =MAX (LCS( A[1...L-1], B[1...L] )，LCS( A[1...L], B[1...L－1] ))
这样就由递推的算法得到动态规划的状态转移方程了。有了状态转移方程，动态规划算法就变成了一个添矩阵算法了，这个伪代码还是很简单的。
② 请教一道数据结构的算法题算法具体描述如下： 设以带头结点的双向循环链表L=（a1,a2,....,an).试写一个时
有两种思想供参考：（1）
整体思想
（2）化整为零
先来说说整体思想，我们可以发现序号为奇数的元素的前后相对位置未变，只是偶数位置有变化。这样的话，我们可以将偶数按序号
逆序
（由大到小）插入到
链表
尾部。考虑到
时间复杂度
问题，在搜索偶数的过程中，可以先找到最大的偶数序号+1的位置（是个奇数，奇数相对位置不动），记下它的位置为L，L向前指的那个位置是偶数位置。这样再找下一个时，直接用L-2，直至k-2等于3为止即可找到所有序号为偶数的位置。
怎么化整为零呢？先来看看下面这个过程：
null
1
2
（1是从head的后面插入链表，2是从tail的前面插入链表）
1
3
2
（3是从1的后面插入链表）
1
3
4
2（4是从2的前面插入链表）
1
3
5
4
2（5是从3的后面插入链表）
......
1
3
5
...
n
...
6
4
2
由此，我们可以设置2个指针p，q，分别指向刚刚序号为奇数的元素插入的位置和刚刚序号为奇数的元素插入的位置，下一个序号为奇数的元素插入到p后，为偶数的插入到q前，并随着插入的过程实时变化p，q，最后再将q和q指向的元素之间的2个指针接上就OK了。
程序交给你来写吧，应该不太难。
③ 求c语言算法例题祥解。
给你下一个中文的框架
开始肯定是
while(第一个判断) //就是年份2000到2500
{
if(第一个判断条件) //能被4整除
{
if(第二个判断条件) //不能被100整除
{
s6；
}
else //不能被100整除的
if(第三个判断) //能被400整除的
{
s6；
}
}
else
{ s5； } //这里就是你所指的s5 当前面的判断都不成立时 他就会到这
}
这是具体思路 要是要代码的话再写。
④ 秦九韶算法例题大全
f(x)=x^6+2x^5+3x^4+5x^2+6x+7
=x(x^5+2x^4+3x^3+5x+6)+7
=x(x(x^4+2x^3+3x^2+5)+6)+7
=x(x(x*x(x^2+2x+3)+5)+6)+7
=x(x(x*x(x(x+2)+3)+5)+6)+7
加法与乘法各5次,其中乘法有连续两次相乘
⑤ 算法时间复杂度的计算例题
第一题：
int i=1,k=100这条语句算法步数是2步,执行频率是1；
循环中, k=k+1;这条语句每次算法步数是1；执行频率是n/2-1; i+=2这条语句每次算法步数是1；执行频率是n/2-1;
所以算法复杂度为1*（n/2-1）+1*（n/2-1）+2=n=o(n);
⑥ c语言问题： 什么是算法试从日常生活中找3个例子，描述它们的算法。 详细点，谢谢！
c语言中的算法是指：一系列解决问题的清晰指令，用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。通俗说就是解决问题的方法和步骤。
描述算法的例子：
问题：从上海去到北京。
其中的算法：做汽车、做飞机、或者徒步。
问题：喝茶。
其中的算法：先找到茶叶，再烧一壶开水，然后将茶叶放到杯子里，将开水倒入杯中，等茶叶泡好。
问题：开车。
其中的算法：首先要打开车门，驾驶员坐好，插上车钥匙，发动汽车。
⑦ 算法题目描述：编程： 定义两个大于2的偶数之间的距离，为这两个数之间质数的个数。
算法如下：
package fileTest;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
public class ZhiShu {
public static boolean t(int n) {
boolean t = true;
if(n!=1){
for(int i = 2;i<=n/2;i++)
{
if (n%i != 0){
t = true;}
else{
t = false;
break;
}
}
}else {t = false;}
return t;
}
public static void main(String[] args) {
while(true){
System.out.println("结束计算输入：0");
Scanner sc=new Scanner(System.in);
System.out.println("请输入你需要计算的偶数个数");
int n=sc.nextInt();
if(n==0){
break;
}
Map<Integer,Integer> map=new LinkedHashMap<Integer, Integer>();
for(int i=0;i<n;i++){
System.out.println("请输入第"+(i+1)+"个偶数");
int m=sc.nextInt();
if(i!=0){
if(m%2!=0||m<4||m<=map.get(i-1)){
i--;
System.out.println("输入的不是大于4的偶数或者小于上一次输入数字，请重新输入！");
continue;
}
}
map.put(i, m);
}
Set<Integer> set = map.keySet();
System.out.println("你输入的偶数为：");
for(int i:set){
System.out.print(map.get(i)+",");
}
System.out.println("");
int count=0;
for(int i=0;i<map.size();i++){
for(int j=1;j<=map.size()-i-1;j++){
int a=map.get(i);
int b=map.get(i+j);
for(int m=1;m<b-a;m++){
int c=a+m;
if(t(c)){
count++;
}
}
}
}
System.out.println("距离之和为："+count);
}
}
}
⑧ 第12题： 以下对算法描述不正确的是_____。
你好！
很显然
第三个是错的
算法是你解决一个题目,如何去解题的思路总称.
是步骤的集合.
例如我们要给班上10个人每人一个苹果.
那么可以有这样一种算法.将这10人编号1到10,从1发到10,每人一个苹果.
你可能觉得这是什么思路,但如果这要让计算机实现呢~你如果安排计算机去做呢~~就得使用某种算法~例如我刚才说的.
如有疑问，请追问。
⑨ 贪心算法的例题分析
例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。