算法

注释非常详细，希望对你有所帮助。#include<stdio.h> #include<stdlib.h> #define M 15 #define N 15 struct mark //定义迷宫内点的坐标类型 { int x; int y; }; struct Element //"恋"栈元素，嘿嘿。。 { int x,y; //x行,y列 int d; //d下一步的方向 }; typedef struct LStack //链栈 { Element elem; struct LStack *next; }*PLStack; /*************栈函数****************/ int InitStack(PLStack &S)//构造空栈 { S=NULL; return 1; } int StackEmpty(PLStack S)//判断栈是否为空 { if(S==NULL) return 1; else return 0; } int Push(PLStack &S, Element e)//压入新数据元素 { PLStack p; p=(PLStack)malloc(sizeof(LStack)); p->elem=e; p->next=S; S=p; return 1; } int Pop(PLStack &S,Element &e) //栈顶元素出栈 { PLStack p; if(!StackEmpty(S)) { e=S->elem; p=S; S=S->next; free(p); return 1; } else return 0; } /***************求迷宫路径函数***********************/ void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) { int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitStack(S1); InitStack(S2); maze[start.x][start.y]=2; //入口点作上标记 elem.x=start.x; elem.y=start.y; elem.d=-1; //开始为-1 Push(S1,elem); while(!StackEmpty(S1)) //栈不为空 有路径可走 { Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; //下一个方向 while(d<4) //试探东南西北各个方向 { a=i+diradd[d][0]; b=j+diradd[d][1]; if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口 { elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); elem.x=a; elem.y=b; elem.d=886; //方向输出为-1 判断是否到了出口 Push(S1,elem); printf(" 0=东 1=南 2=西 3=北 886为则走出迷宫 通路为:(行坐标,列坐标,方向) "); while(S1) //逆置序列 并输出迷宫路径序列 { Pop(S1,e); Push(S2,e); } while(S2) { Pop(S2,e); printf("-->(%d,%d,%d)",e.x,e.y,e.d); } return; //跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴} if(maze[a][b]==0) //找到可以前进的非出口的点 { maze[a][b]=2; //标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); //当前位置入栈 i=a; //下一点转化为当前点 j=b; d=-1; } d++; } } printf("没有找到可以走出此迷宫的路径 "); } /*************建立迷宫*******************/ void initmaze(int maze[M][N]) { int i,j; int m,n; //迷宫行,列 [/M] printf("请输入迷宫的行数 m="); scanf("%d",&m); printf("请输入迷宫的列数 n="); scanf("%d",&n); printf(" 请输入迷宫的各行各列: 用空格隔开,0代表路,1代表墙 ",m,n); for(i=1;i<=m;i++) for(j=1;j<=n;j++) scanf("%d",&maze[i][j]); printf("你建立的迷宫为(最外圈为墙)... "); for(i=0;i<=m+1;i++) //加一圈围墙 { maze[i][0]=1; maze[i][n+1]=1; } for(j=0;j<=n+1;j++) { maze[0][j]=1; maze[m+1][j]=1; } for(i=0;i<=m+1;i++) //输出迷宫 { for(j=0;j<=n+1;j++) printf("%d ",maze[i][j]); printf(" "); } } void main() { int sto[M][N]; struct mark start,end; //start,end入口和出口的坐标 int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次为东西南北 [/M] initmaze(sto);//建立迷宫 printf("输入入口的横坐标,纵坐标[逗号隔开] "); scanf("%d,%d",&start.x,&start.y); printf("输入出口的横坐标,纵坐标[逗号隔开] "); scanf("%d,%d",&end.x,&end.y); MazePath(start,end,sto,add); //find path system("PAUSE"); } 测试数据，算法复杂度你就自己来写吧，如果你连这都不自己做，那你一定是在应付作业。劝你还是自己运行测试一下吧，免得答辩时老师问你，什么都不知道，那你就悲剧了。祝你好运！！

#include <stdio.h>#include <stdlib.h>#include <time.h>#include <memory.h>/* define the size of maze */#define MAX_COL 6#define MAX_ROW 6#define TRUE 1#define FALSE 0#define IS_USABLE(a, b) (a >= 0 && a < MAX_ROW) && (b >= 0 && b < MAX_COL) && maze[a][b] && (!my_maze[a][b])static int maze[MAX_ROW][MAX_COL];static int target_maze[MAX_ROW][MAX_COL];static void init_maze();static int move_to(int i, int j, int (*maze)[MAX_COL], int count);static void print_maze(int (*maze)[MAX_COL]);static void init_maze(){ int i, j; srand((unsigned) time(NULL)); for (i = 0; i < MAX_ROW; i++) for(j = 0; j < MAX_COL; j++) { maze[i][j] = (int) (rand() % 2); } maze[1][0] = 1; /* start point */ maze[MAX_ROW - 1][MAX_COL - 2] = 1; /* end point */}static int move_to(int _i,int _j, int (*in_maze)[MAX_COL], int count) { int my_maze[MAX_ROW][MAX_COL], i, j; if (!in_maze) { for (i = 0; i < MAX_ROW; i++) for(j = 0; j < MAX_COL; j++) { my_maze[i][j] = 0; } } else { for (i = 0; i < MAX_ROW; i++) for(j = 0; j < MAX_COL; j++) { my_maze[i][j] = in_maze[i][j]; } } my_maze[_i][_j] = count; /* reach the end point */ if (_i == MAX_ROW - 1 && _j == MAX_COL - 2) { for (i = 0; i < MAX_ROW; i++) for(j = 0; j < MAX_COL; j++) { target_maze[i][j] = my_maze[i][j]; } return TRUE; } if (IS_USABLE(_i - 1, _j)) { if (move_to(_i - 1, _j, my_maze, count + 1)) return TRUE; } if (IS_USABLE(_i + 1, _j)) { if (move_to(_i + 1, _j, my_maze, count + 1)) return TRUE; } if (IS_USABLE(_i, _j - 1)) { if (move_to(_i, _j - 1, my_maze, count + 1)) return TRUE; } if (IS_USABLE(_i, _j + 1)) { if (move_to(_i, _j + 1, my_maze, count + 1)) return TRUE; } return FALSE;}static void print_maze(int (*maze)[MAX_COL]) { int i, j; for (i = 0; i < MAX_ROW; i++) { for(j = 0; j < MAX_COL; j++) { if (maze[i][j] != 0) printf("%d ", maze[i][j]); else printf(" "); } printf(" "); }}int main(){ while(1) { init_maze(); printf("Out put the maze : "); print_maze(maze); if (move_to(1, 0, NULL, 1)) { printf("Out put the path : "); print_maze(target_maze); break; } else { printf("No way! "); } }}VC60下正常运行

Python基于递归算法实现的走迷宫问题本文实例讲述了Python基于递归算法实现的走迷宫问题。分享给大家供大家参考，具体如下：什么是递归?简单地理解就是函数调用自身的过程就称之为递归。什么时候用到递归？如果一个问题可以表示为更小规模的迭代运算，就可以使用递归算法。迷宫问题：一个由0或1构成的二维数组中，假设1是可以移动到的点，0是不能移动到的点，如何从数组中间一个值为1的点出发，每一只能朝上下左右四个方向移动一个单位，当移动到二维数组的边缘，即可得到问题的解，类似的问题都可以称为迷宫问题。在python中可以使用list嵌套表示二维数组。假设一个6*6的迷宫,问题时从该数组坐标[3][3]出发，判断能不能成功的走出迷宫。 maze=[[1,0,0,1,0,1], [1,1,1,0,1,0], [0,0,1,0,1,0], [0,1,1,1,0,0], [0,0,0,1,0,0], [1,0,0,0,0,0]]针对这个迷宫问题，我们可以使用递归的思想很好的解决。对于数组中的一个点，该点的四个方向可以通过横纵坐标的加减轻松的表示，每当移动的一个可移动的点时候，整个问题又变为和初始状态一样的问题，继续搜索四个方向找可以移动的点，知道移动到数组的边缘。所以我们可以这样编码： # 判断坐标的有效性，如果超出数组边界或是不满足值为1的条件，说明该点无效返回False，否则返回True。def valid(maze,x,y): if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1): return True else: return False# 移步函数实现def walk(maze,x,y): # 如果位置是迷宫的出口，说明成功走出迷宫 if(x==0 and y==0): print("successful!") return True # 递归主体实现 if valid(maze,x,y): # print(x,y) maze[x][y]=2 # 做标记，防止折回 # 针对四个方向依次试探，如果失败，撤销一步 if not walk(maze,x-1,y): maze[x][y]=1 elif not walk(maze,x,y-1): maze[x][y]=1 elif not walk(maze,x+1,y): maze[x][y]=1 elif not walk(maze,x,y+1): maze[x][y]=1 else: return False # 无路可走说明，没有解 return Truewalk(maze,3,3)递归是个好东西呀！

用python递归求解dirs=[(0,1),(1,0),(0,-1),(-1,0)] #当前位置四个方向的偏移量path=[] #存找到的路径def mark(maze,pos): #给迷宫maze的位置pos标"2"表示“倒过了” maze[pos[0]][pos[1]]=2def passable(maze,pos): #检查迷宫maze的位置pos是否可通行 return maze[pos[0]][pos[1]]==0def find_path(maze,pos,end): mark(maze,pos) if pos==end: print(pos,end=" ") #已到达出口，输出这个位置。成功结束 path.append(pos) return True for i in range(4): #否则按四个方向顺序检查 nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1] #考虑下一个可能方向 if passable(maze,nextp): #不可行的相邻位置不管 if find_path(maze,nextp,end):#如果从nextp可达出口，输出这个位置，成功结束 print(pos,end=" ") path.append(pos) return True return Falsedef see_path(maze,path): #使寻找到的路径可视化 for i,p in enumerate(path): if i==0: maze[p[0]][p[1]] ="E" elif i==len(path)-1: maze[p[0]][p[1]]="S" else: maze[p[0]][p[1]] =3 print(" ") for r in maze: for c in r: if c==3: print("33[0;31m"+"*"+" "+"33[0m",end="") elif c=="S" or c=="E": print("33[0;34m"+c+" " + "33[0m", end="") elif c==2: print("33[0;32m"+"#"+" "+"33[0m",end="") elif c==1: print("33[0;;40m"+" "*2+"33[0m",end="") else: print(" "*2,end="") print()if __name__ == "__main__": maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1], [1,0,0,0,1,1,0,0,0,1,0,0,0,1], [1,0,1,0,0,0,0,1,0,1,0,1,0,1], [1,0,1,0,1,1,1,1,0,1,0,1,0,1], [1,0,1,0,0,0,0,0,0,1,1,1,0,1], [1,0,1,1,1,1,1,1,1,1,0,0,0,1], [1,0,1,0,0,0,0,0,0,0,0,1,0,1], [1,0,0,0,1,1,1,0,1,0,1,1,0,1], [1,0,1,0,1,0,1,0,1,0,1,0,0,1], [1,0,1,0,1,0,1,0,1,1,1,1,0,1], [1,0,1,0,0,0,1,0,0,1,0,0,0,1], [1,1,1,1,1,1,1,1,1,1,1,1,1,1]] start=(1,1) end=(10,12) find_path(maze,start,end) see_path(maze,path)

#include <stdio.h>#include <stdlib.h>#define overflow -1#define ok 1#define error 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef struct { int x; int y;}PosType;//位置类型typedef struct{ int row,col; int a[50][50];}MazeType;//迷宫类型typedef struct{ int ord;//通道块在路径上的序号 PosType seat;//通道块在迷宫中的“坐标位置” int di;//从此通道块走向下一个通道块的方向}SElemType;//栈的元素类型typedef struct{ SElemType *base; SElemType *top; int Stacksize;}SqStack;//栈结构Status InitStack(SqStack &S)//初始化栈{ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit (overflow); S.top=S.base; S.Stacksize=STACK_INIT_SIZE; return ok;}Status Push(SqStack &S,SElemType e)//入栈{ if(S.top-S.base>=S.Stacksize) { S.base=(SElemType *)realloc(S.base,(S.Stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit (overflow); S.top=S.base+S.Stacksize; S.Stacksize+=STACKINCREMENT; } *S.top++=e; return ok;}Status Pop(SqStack &S,SElemType &e)//出栈{ if(S.top==S.base) return error; e=*--S.top; return ok;}bool StackEmpty(SqStack S)//判断栈是否为空{ if(S.top==S.base) return ok; else return error;}Status InitMaze(MazeType &maze)//初始化迷宫{ int i,j; for( j=0;j<maze.col+2;j++) maze.a[0][j]=1; for( i=1;i<maze.row+1;i++) { maze.a[i][0]=1; maze.a[i][maze.col+1]=1; for(int j=1;j<maze.col+1;j++) scanf("%d",&maze.a[i][j]); } for(j=0;j<maze.col+2;j++) maze.a[maze.row+1][j]=1;return ok;}//为了避免检查边界，把迷宫的外围都设成障碍，迷宫的内核是row行，col列的数组bool Pass(MazeType maze,PosType curpos)//判断是否可以通过{ return maze.a[curpos.x][curpos.y]==0;}Status FootPrint(MazeType &maze,PosType curpos)//留下足迹{ maze.a[curpos.x][curpos.y]=2; return ok;}SElemType CreatElem(int step,PosType pos,int di)//创造一个SElemType型的数据{ SElemType e; e.ord=step; e.seat=pos; e.di=di; return e;}bool IsEnd(PosType pos1,PosType pos2)//判断是否结束{ return pos1.x==pos2.x&&pos1.y==pos2.y;}PosType NextPos(PosType curpos,int di)//向下一步搜索{ PosType pos=curpos; switch(di) { case 1:pos.x++;break;//向东 case 2:pos.y++;break;//向南 case 3:pos.x--;break;//向西 case 4:pos.y--;break;//向北 } return pos;}Status MarkPrint(MazeType &maze,PosType curpos)//在死路处留下印迹{ maze.a[curpos.x][curpos.y]="*"; return ok;}Status MazePath(MazeType &maze,PosType start,PosType end)//寻找路径{ //若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶）， //并返回ture；否则返回false SqStack S; SElemType e; InitStack(S); PosType curpos=start;//设定当前位置为入口位置 int curstep=1;//探索第一步 do{ if(Pass(maze,curpos)) { FootPrint(maze,curpos);//留下足迹 e=CreatElem(curstep,curpos,1); Push(S,e);//加入路径 if(IsEnd(curpos,end)) return ok;//达到终点 curpos=NextPos(curpos,1);//下一步是当期位置的东邻 curstep++;//探索下一步 } else//当前位置不能通过 { if(!StackEmpty(S)) { Pop(S,e); while(e.di==4&&!StackEmpty(S)) { MarkPrint(maze,e.seat);//留下不能通过的标记，并退一步 Pop(S,e); } if(e.di<4) { e.di++;//换下一个方向 Push(S,e); curpos=NextPos(e.seat,e.di);//设定当前位置是新方向上的相邻块 } } } }while(!StackEmpty(S)); return error;}Status PrintMaze(MazeType maze)//输出迷宫{ int i,j; for(i=0;i<maze.row+2;i++) { for(j=0;j<maze.col+2;j++) printf("%d ",maze.a[i][j]); printf(" "); } return ok;}void main(){ MazeType maze; printf("请输入迷宫的行数row和列数col："); scanf("%d %d",&maze.row,&maze.col); printf("请输入迷宫数据，0表示通道，1表示障碍： "); InitMaze(maze); PosType start,end; start.x=1;start.y=1; end.x=maze.row;end.y=maze.col; if(MazePath(maze,start,end)) { printf("迷宫走法（2代表走法，*代表不通） "); PrintMaze(maze); } else printf("没有找到通路! ");}给你参考一下。

通过对脉搏血氧测量原理的研究，人们已经发现只要测量出两种波长的透射光在一个完整的脉搏波中光强度的变化量就可以计算氧饱和度。现代的光电和微电子技术为这种测量原理的实现提供了可能。根据脉搏血氧测量原理可以设计出各种各样的血氧测量计.血氧测量计的基本结构包括两部分：血氧传感器器和血氧电路。从理论上来看，血氧传感器的由简单的两部分组成：光发射和光接受部分组成。但是在临床上使用的血氧传感器除了包括这两个核心的器件外，还包括相应的机械部件、信号传输电缆、探头识别接口等。这些因素直接影响探头的可靠性、舒适性。探头能否在实际临床上被可靠的稳定的使用很大程度上取决于这些外围的部件。因此，在工程设计是，除了对传感器工作原理的分析外，对传感器其他部件的分析，寻求一个合适的解决方案是一项技术能否实现产品化的关键。信号处理电路对来自传感器的信号进行处理，信号经过放大、滤波，得到一定幅度的信号。这个信号送入到A/D转化电路，实现模拟到数字量的转化，被数字化之后的信号经过单片机按照血氧算法计算后得到血氧饱和度。在血氧测量原理我们提到，用两种特定的波长就可以实现脉搏血氧饱和度的测量。这两种光的波长是660nm和940nm。通过对人体生理波形的分析可以知道，人体的脉搏次数在30~250次/分钟，对应的频率是0.5~4.1HZ，。采样定理指出：对于一个具有有限频谱的连续信号进行采样，当采样频率大于信号频率的两倍是，有采样后得到的输出函数能无失真的恢复到原来的信号。在实际上，我们取采样频率为120HZ，可以保证信号的无失真。即使是120HZ，对单片机控制电路来讲，频率也是比较低的，因此对与红光和红外光的采样采用分时采样的方法，即对红光和红外光的采样在不同时刻，但是这两个信号的采样时刻非常的接近。此外，考虑到减少传感器电缆线的芯线数量，降低成本和增强电缆的可靠性，因此在设计红光和红外光的连接方式式采用的红光和红外光反向并联的方式。传感器采用发光二极管LED作为光源,以光电二极管作为光检测器件。在前面的讨论中我们提到采用660nm和940nm波长的LED时可以减少测量误差。因此最终确定选用660nm和940nm波长的LED作为光源。光源采用脉冲驱动。采用脉冲驱动的好处是两路光源可以交替发亮，检测电路可以采用对两路光响应电平一致的光敏元件接收。

在matlab的workspace里打editsfuntmpl(这是matlab自己提供的s函数模板)，我们看它来具体分析s函数的结构。它的第一行是这样的：function[sys,x0,str,ts]=sfuntmpl(t,x,u,flag)先讲输入与输出变量的含义：t是采样时间，x是状态变量，u是输入（是做成simulink模块的输入）,flag是仿真过程中的状态标志（以它来判断当前是初始化还是运行等）；sys输出根据flag的不同而不同（下面将结合flag来讲sys的含义），x0是状态变量的初始值，str是保留参数（mathworks公司还没想好该怎么用它，嘻嘻，一般在初始化中将它置空就可以了,str=[])，ts是一个1×2的向量，ts(1)是采样周期，ts(2)是偏移量。下面结合sfuntmpl.m中的代码来讲具体的结构：switchflag,%判断flag，看当前处于哪个状态case0,[sys,x0,str,ts]=mdlInitializeSizes;flag=0表示处于初始化状态，此时用函数mdlInitializeSizes进行初始化，此函数在sfuntmpl.m的149行我们找到他，在初始化状态下，sys是一个结构体，用它来设置模块的一些参数，各个参数详细说明如下size=simsizes;%用于设置模块参数的结构体用simsizes来生成sizes.NumContStates=0;%模块连续状态变量的个数sizes.NumDiscStates=0;%模块离散状态变量的个数sizes.NumOutputs=0;%模块输出变量的个数sizes.NumInputs=0;%模块输入变量的个数sizes.DirFeedthrough=1;%模块是否存在直接贯通（直接贯通我的理解是输入能%直接控制输出）sizes.NumSampleTimes=1;%模块的采样时间个数，至少是一个sys=simsizes(sizes);%设置完后赋给sys输出举个例子，考虑如下模型：dx/dt=fc(t,x,u)也可以用连续状态方程描述：dx/dt=A*x+B*ux(k+1)=fd(t,x,u)也可以用离散状态方程描述：x(k+1)=H*x(k)+G*u(k)y=fo(t,x,u)也可以用输出状态方程描述：y=C*x+D*u设上述模型连续状态变量、离散状态变量、输入变量、输出变量均为1个，我们就只需改上面那一段代码为：（一般连续状态与离散状态不会一块用，我这儿是为了方便说明）sizes.NumContStates=1;sizes.NumDiscStates=1;sizes.NumOutputs=1;sizes.NumInputs=1;其他的可以不变。继续在mdlInitializeSizes函数中往下看：x0=[];%状态变量设置为空，表示没有状态变量，以我们上面的假设，可改%为x0=[0,0](离散和连续的状态变量我们都设它初值为0)str=[];%这个就不用说了，保留参数嘛，置[]就可以了，反正没什么用，可%能7.0会给它一些意义ts=[00];%采样周期设为0表示是连续系统，如果是离散系统在下面的mdlGet%TimeOfNextVarHit函数中具体介绍嘻嘻，总算讲完了初始化，后面的应该快了在sfuntmpl的106行继续往下看：case1,sys=mdlDerivatives(t,x,u);flag=1表示此时要计算连续状态的微分，即上面提到的dx/dt=fc(t,x,u)中的dx/dt,找到mdlDerivatives函数（在193行）如果设置连续状态变量个数为0，此处只需sys=[];就可以了（如sfuntmpl中一样），按我们上述讨论的那个模型，此处改成sys=fc(t,x(1),u)或sys=A*x(1)+B*u%我们这儿x(1)是连续状态变量，而x(2)是离散的，这儿只用到连续的，此时的输出sys就是微分继续，在sfuntmpl的112行：case2,sys=mdlUpdate(t,x,u);flag=2表示此时要计算下一个离散状态，即上面提到的x(k+1)=fd(t,x,u)，找到mdlUpdate函数（在206行）它这儿sys=[];表示没有离散状态，我们这而可以改成sys=fd(t,x(2),u)或sys=H*x(2)+G*u;%sys即为x(k+1)看来后面几个一两句话就可了，呵呵，在sfuntmpl的118行case3,sys=mdlOutputs(t,x,u);flag=3表示此时要计算输出，即y=fo(t,x,u),找到mdlOutputs函数（在218行），如上，如果sys=[]表示没有输出，我们改成sys=fo(t,x,u)或sys=C*x+D*u%sys此时为输出y好像快完了，嘻嘻，在sfuntmpl的124行case4,sys=mdlGetTimeOfNextVarHit(t,x,u);flag=4表示此时要计算下一次采样的时间，只在离散采样系统中有用(即上文的mdlInitializeSizes中提到的ts设置ts(1)不为0)连续系统中只需在mdlGetTimeOfNextVarHit函数中写上sys=[];这个函数主要用于变步长的设置，具体实现大家可以用editvsfunc看vsfunc.m这个例子最后一个，在sfuntmpl的130行case9,sys=mdlTerminate(t,x,u);flag=9表示此时系统要结束，一般来说写上在mdlTerminate函数中写上sys=[]就可，如果你在结束时还要设置什么，就在此函数中写关于sfuntmpl这个s函数的模板讲完了。s函数还可以带用户参数，下面给个例子，和simulink下的gain模块功能一样，大伙自己看吧，我睡觉去了，累了function[sys,x0,str,ts]=sfungain(t,x,u,flag,gain)switchflag,case0,sizes=simsizes;sizes.NumContStates=0;sizes.NumDiscStates=0;sizes.NumOutputs=1;sizes.NumInputs=1;sizes.DirFeedthrough=1;sizes.NumSampleTimes=1;sys=simsizes(sizes);x0=[];str=[];ts=[0,0];case3,sys=gain*u;case{1,2,4,9},sys=[];end

1、打开Excel，输入X、Y两列数据。2、在空白的单元格输入函数公式Y=a*x+b，以及未知数a，b。3、斜率：用SLOPE函数，公式=SLOPE(Y轴数据,X轴数据)。在a后面的单元格输入=SLOPE(，然后用鼠标选取Y数据，键入英文状态的逗号，再用鼠标选取X数据，输入英文的)。4、点击enter键，得到斜率值。5、截距：INTERCEPT函数，公式=INTERCEPT(Y轴数据,X轴数据)。在b后面的单元格输入=INTERCEPT(，然后用鼠标选取Y数据，键入英文状态的逗号，再用鼠标选取X数据，输入英文的)。6、点击enter键，得到截距值。

最小二乘法

a=[11/4;41]a=1.00000.25004.00001.0000>>[v,d]=eig(a)v=0.2425-0.24250.97010.9701d=2000按照这道题的计算过程算就可以了，eig是求特征值和特征向量命令，v是特征向量，是列向量，d是特征值矩阵，主对角线元素就是特征值，与特征向量的列对应的

前段时间为准备百度面试恶补的东西，虽然最后还是被刷了，还是把那几天的“战利品”放点上来，算法一直是自己比较薄弱的地方，以后还要更加努力啊。下面用Python实现了几个常用的排序，如快速排序，选择排序，以及二路并归排序等等。 代码如下:#encoding=utf-8import randomfrom copy import copydef directInsertSort(seq): """ 直接插入排序 """ size = len(seq) for i in range(1,size): tmp, j = seq[i], i while j > 0 and tmp < seq[j-1]: seq[j], j = seq[j-1], j-1 seq[j] = tmp return seqdef directSelectSort(seq): """ 直接选择排序 """ size = len(seq) for i in range(0,size - 1): k = i;j = i+1 while j < size: if seq[j] < seq[k]: k = j j += 1 seq[i],seq[k] = seq[k],seq[i] return seqdef bubbleSort(seq): """冒泡排序""" size = len(seq) for i in range(1,size): for j in range(0,size-i): if seq[j+1] < seq[j]: seq[j+1],seq[j] = seq[j],seq[j+1] return seqdef _divide(seq, low, high): """快速排序划分函数""" tmp = seq[low] while low != high: while low < high and seq[high] >= tmp: high -= 1 if low < high: seq[low] = seq[high] low += 1 while low < high and seq[low] = high: return mid = _divide(seq, low, high) _quickSort(seq, low, mid - 1) _quickSort(seq, mid + 1, high)def quickSort(seq): """快速排序包裹函数""" size = len(seq) _quickSort(seq, 0, size - 1) return seqdef merge(seq, left, mid, right): tmp = [] i, j = left, mid while i < mid and j 运行结果如下： 代码如下:E:python_projectpractice>sorting.py[10, 47, 56, 76, 64, 84, 26, 8, 47, 51, 88, 81, 32, 95, 91, 29, 28, 69, 61, 45][8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95][8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95][8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95][8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95][8, 10, 26, 28, 29, 32, 45, 47, 47, 51, 56, 61, 64, 69, 76, 81, 84, 88, 91, 95]

【答案】：A零基预算编制过程中要划分不可避免费用项目和可避免费用项目。在编制预算时，不可避免费用项目必须保证资金供应；对可避免费用项目，则需要逐项进行成本与效益分析，尽量控制可避免项目纳入预算当中。

2011b可用symsx1x2f=x1^2+x2^2gradient(f)2009a以下，可用symsx1x2f=x1^2+x2^2[diff(f,x1);diff(f,x2)]

【答案】A【答案解析】零基预算编制过程中要划分不可避免费用项目和可避免费用项目。在编制预算时，对不可避免费用项目必须保证资金供应；对可避免费用项目，则需要逐项进行成本与效益分析，尽量控制不可避免项目纳入预算当中。

这个http://www.sfcode.cn/soft/001973243.htm或者这个输入时，将s,t,x,y,z五个点按照1,2,3,4,5起别名，输入格式按照下图例所示 当提示Please enter the vertex where Dijkstra algorithm starts:时输入算法的起始点 比如计算结果v1v4v2表示从点1到点2经过1，4，2为最短路径 Dijkstra算法的完整实现版本，算法的源代码 /* Dijkstra.c Copyright (c) 2002, 2006 by ctu_85 All Rights Reserved. */ #include "stdio.h" #include "malloc.h" #define maxium 32767 #define maxver 9 /*defines the max number of vertexs which the programm can handle*/ #define OK 1 struct Point { char vertex[3]; struct Link *work; struct Point *next; }; struct Link { char vertex[3]; int value; struct Link *next; }; struct Table /*the workbannch of the algorithm*/ { int cost; int Known; char vertex[3]; char path[3]; struct Table *next; }; int Dijkstra(struct Point *,struct Table *); int PrintTable(int,struct Table *); int PrintPath(int,struct Table *,struct Table *); struct Table * CreateTable(int,int); struct Point * FindSmallest(struct Table *,struct Point *);/*Find the vertex which has the smallest value reside in the table*/ int main() { int i,j,num,temp,val; char c; struct Point *poinpre,*poinhead,*poin; struct Link *linpre,*linhead,*lin; struct Table *tabhead; poinpre=poinhead=poin=(struct Point *)malloc(sizeof(struct Point)); poin->next=NULL; poin->work=NULL; restart: printf("Notice:if you wanna to input a vertex,you must use the format of number! "); printf("Please input the number of points: "); scanf("%d",&num); if(num>maxver||num<1||num%1!=0) { printf(" Number of points exception!"); goto restart; } for(i=0;i<num;i++) { printf("Please input the points next to point %d,end with 0: ",i+1); poin=(struct Point *)malloc(sizeof(struct Point)); poinpre->next=poin; poin->vertex[0]="v"; poin->vertex[1]="0"+i+1; poin->vertex[2]=""; linpre=lin=poin->work; linpre->next=NULL; for(j=0;j<num-1;j++) { printf("The number of the %d th vertex linked to vertex %d:",j+1,i+1); scanf("%d",&temp); if(temp==0) { lin->next=NULL; break; } else { lin=(struct Link *)malloc(sizeof(struct Link)); linpre->next=lin; lin->vertex[0]="v"; lin->vertex[1]="0"+temp; lin->vertex[2]=""; printf("Please input the value betwixt %d th point towards %d th point:",i+1,temp); scanf("%d",&val); lin->value=val; linpre=linpre->next; lin->next=NULL; } } poinpre=poinpre->next; poin->next=NULL; } printf("Please enter the vertex where Dijkstra algorithm starts: "); scanf("%d",&temp); tabhead=CreateTable(temp,num); Dijkstra(poinhead,tabhead); PrintTable(temp,tabhead); return OK; } struct Table * CreateTable(int vertex,int total) { struct Table *head,*pre,*p; int i; head=pre=p=(struct Table *)malloc(sizeof(struct Table)); p->next=NULL; for(i=0;i<total;i++) { p=(struct Table *)malloc(sizeof(struct Table)); pre->next=p; if(i+1==vertex) { p->vertex[0]="v"; p->vertex[1]="0"+i+1; p->vertex[2]=""; p->cost=0; p->Known=0; } else { p->vertex[0]="v"; p->vertex[1]="0"+i+1; p->vertex[2]=""; p->cost=maxium; p->Known=0; } p->next=NULL; pre=pre->next; } return head; } int Dijkstra(struct Point *p1,struct Table *p2) /* Core of the programm*/ { int costs; char temp; struct Point *poinhead=p1,*now; struct Link *linna; struct Table *tabhead=p2,*searc,*result; while(1) { now=FindSmallest(tabhead,poinhead); if(now==NULL) break; result=p2; result=result->next; while(result!=NULL) { if(result->vertex[1]==now->vertex[1]) break; else result=result->next; } linna=now->work->next; while(linna!=NULL) /* update all the vertexs linked to the signed vertex*/ { temp=linna->vertex[1]; searc=tabhead->next; while(searc!=NULL) { if(searc->vertex[1]==temp)/*find the vertex linked to the signed vertex in the table and update*/ { if((result->cost+linna->value)<searc->cost) { searc->cost=result->cost+linna->value;/*set the new value*/ searc->path[0]="v"; searc->path[1]=now->vertex[1]; searc->path[2]=""; } break; } else searc=searc->next; } linna=linna->next; } } return 1; } struct Point * FindSmallest(struct Table *head,struct Point *poinhead) { struct Point *result; struct Table *temp; int min=maxium,status=0; head=head->next; poinhead=poinhead->next; while(head!=NULL) { if(!head->Known&&head->cost<min) { min=head->cost; result=poinhead; temp=head; status=1; } head=head->next; poinhead=poinhead->next; } if(status) { temp->Known=1; return result; } else return NULL; } int PrintTable(int start,struct Table *head) { struct Table *begin=head; head=head->next; while(head!=NULL) { if((head->vertex[1]-"0")!=start) PrintPath(start,head,begin); head=head->next; } return OK; } int PrintPath(int start,struct Table *head,struct Table *begin) { struct Table *temp=begin->next,*p,*t; p=head; t=begin; if((p->vertex[1]-"0")!=start&&p!=NULL) { while(temp->vertex[1]!=p->path[1]&&temp!=NULL) temp=temp->next; PrintPath(start,temp,t); printf("%s",p->vertex); } else if(p!=NULL) printf(" %s",p->vertex); return OK; }

int visited[n] Graph g;DFS(i)int i;{int j;printf("node:%c ",g.vexs[i]);visited[i]=true;for(j=0;j<n;j++)if((g.arcs[i][j]==1)&&(!visited[j]))DFS(j);}vexnode g1[n]DFSL(i)int i;{int j;edgenode *p;printf("node:%c ",g1[i].vertex);visited[i]=true;p=g1[i].link;while(p!=NULL){if(!visited[p->adjvex])DFSL(p->adjvex);p=p->next;}}

//思路:先把邻接表转换成逆邻接表，这样问题简单多了。//数组out，保存各节点的入度voidcountindegree(AdjListgin,AdjListgout){//设有向图有n个顶点，建逆邻接表的顶点向量。for(inti=1;i<=n;i++){gin[i].vertex=gout[i].vertex;gin.firstarc=null;}//邻接表转为逆邻接表。for(i=1;i<=n;i++){p=gout[i].firstarc;//取指向邻接表的指针。while(p!=null){j=p->adjvex;s=(ArcNode*)malloc(sizeof(ArcNode));//申请结点空间。s->adjvex=i;s->next=gin[j].firstarc;gin[j].firstarc=s;p=p->next;//下一个邻接点。}//while}//endoffor//统计各节点的入度for(i=0;i<n;i++){p=gin[i].firstarc;while(p!=null){out[i]++;p=p->next;}//endofwhile}//endoffor}//endoffunction

#include<iostream>#include<string.h>#include<malloc.h>#include<stdlib.h>#include<string>using namespace std;#define OVERFLOW -2#define OK 1#define ERROR 0#define INFINITY 200//最大值#define MAX_VERTEX_NUM 20//最大顶点个数typedef char VertexType;//定义为char类型//以下是全局变量,用于保存弗洛伊德算法的路径和长度int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径长度int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径标记//以下是全局变量,用于保存迪杰斯特拉算法的路径和长度int Distance[MAX_VERTEX_NUM];VertexType former[MAX_VERTEX_NUM];//终点的前一个顶点bool final[MAX_VERTEX_NUM];//记录顶点是否在V-S中typedef struct ArcCell{int adj; //顶点关系类型int weight; //该弧相关信息的指针,在此记录为权值}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum; //顶点数int arcnum; //弧数}MGraph;void InitialMGraph(MGraph &G)//初始化{G.arcnum=G.vexnum=0; //初始化边数跟顶点数都为零for(int i=0;i<MAX_VERTEX_NUM;i++)for(int j=0;j<MAX_VERTEX_NUM;j++){if(i==j)G.arcs[i][j].weight=0;elseG.arcs[i][j].weight=INFINITY; //初始化为200,以200认为是无穷大}}void InsertVex(MGraph &G,VertexType v)//插入顶点{if(G.vexnum<=MAX_VERTEX_NUM)G.vexs[G.vexnum++]=v;}void InsertArc(MGraph &G,VertexType v1,VertexType v2)//插入边{int m,n;G.arcnum++;for(int k=0;k<G.vexnum;k++){if(G.vexs[k]==v1)m=k;if(G.vexs[k]==v2)n=k;}//插入ArcCell A;cout<<"请输入权值:";cin>>A.weight;G.arcs[m][n].weight=A.weight;}//迪杰斯特拉最短路径,假设始点就存储在数组中的第一个void ShortestPath_DIJ(MGraph G,int v0){//初始化距离for(int v=0;v<G.vexnum;++v){final[v]=false;Distance[v]=G.arcs[v0][v].weight;if(Distance[v]<INFINITY&&Distance[v]!=0){former[v]=G.vexs[v0];}elseformer[v]="#";}final[v0]=true;former[v0]=G.vexs[v0];for(int i=1;i<G.vexnum;++i)//剩余的G.vexnum-1个顶点{int w;int min=INFINITY;int v=-1;for(w=0;w<G.vexnum;++w){if(!final[w]&&Distance[w]<min){v=w;min=Distance[w];}}if(v!=-1){final[v]=true;//将离顶点V0最近的顶点v加入S集合中for(w=0;w<G.vexnum;++w)//更新当前的最短路径及距离{if(!final[w]&&(min+G.arcs[v][w].weight<Distance[w])&&G.arcs[v][w].weight<INFINITY){Distance[w]=min+G.arcs[v][w].weight;former[w]=G.vexs[v];}}}}}//输出迪杰斯特拉中的最短路径void output_ShortestPath_DIJ(MGraph G,int v0){int i;for(i=1;i<G.vexnum;i++){cout<<G.vexs[v0]<<"->"<<G.vexs[i]<<":";if(Distance[i]!=INFINITY){cout<<"最短路径长度为:"<<Distance[i]<<" 最短路径的前一个顶点为:"<<former[i];cout<<endl;}elsecout<<"此两顶点之间不存在路径"<<endl;}}//弗洛伊德最短路径void shortestPath_FLOYD(MGraph G){for(int v=0;v<G.vexnum;++v){for(int w=0;w<G.vexnum;++w){D[v][w]=G.arcs[v][w].weight;for (int k=0;k< G.vexnum;k++)P[v][w][k]=-1;if(D[v][w]<INFINITY) //从v到w有直接路径P[v][w][v]=w;}}for(int k=0;k<G.vexnum;++k){for(int v=0;v<G.vexnum;v++)for(int w=0;w<G.vexnum;++w)if(D[v][w]>D[v][k]+D[k][w]){D[v][w]=D[v][k]+D[k][w];for(int i=0;i<G.vexnum;i++){if(P[v][k][i]!=-1)//原来存了顶点P[v][w][i]=P[v][k][i];elseP[v][w][i]=P[k][w][i];}}}}//输出弗洛伊德中的最短路径void output_shortestPath_FLOYD(MGraph G){for(int i=0;i<G.vexnum;++i){for(int j=0;j<G.vexnum;++j){if(i!=j)//自己不能到达自己{cout<<G.vexs[i]<<"->"<<G.vexs[j]<<":";if(D[i][j]==INFINITY){cout<<"此两顶点之间不存在路径"<<endl;}else{cout<<"最短路径长度为:"<<" "<<D[i][j]<<" ";cout<<"最短路径为:";cout<<G.vexs[i]<<" ";for(int k=i;k!=-1;k=P[i][j][k]){if(k!=i)cout<<G.vexs[k];}cout<<endl;}}}}}int main(){int num1;//顶点个数int num2;//弧个数cout<<"请输入顶点个数:";cin>>num1;cout<<"请输入边的个数:";cin>>num2;VertexType v;MGraph G;InitialMGraph(G);cout<<"请输入顶点的信息（整型）:";for(int i=0;i<num1;++i){cin>>v;;InsertVex(G,v);}VertexType v1,v2;for(int j=0;j<num2;++j){cout<<"请输入两个结点数据来表示的边:";cin>>v1>>v2;InsertArc(G,v1,v2);}ShortestPath_DIJ(G,0);cout<<"迪杰斯特拉中的最短路径如下:"<<endl;output_ShortestPath_DIJ(G,0);shortestPath_FLOYD(G);cout<<"它中的最短路径如下:"<<endl;output_shortestPath_FLOYD(G);return 0;}

思路，穷举法

This paper presents an improved algorithm例句因此，本文提出一种改进算法（SAGA VSP），将模拟退火思想和遗传算法综合在一起，来解决查询代价视图选择问题。Therefore, improved algorithm ( SAGA_VSP) has been presented, which is the combination of simulated annealing algorithm and genetic algorithm "for the purpose of solving the query cost view selection problem.

1 青少年软件编程等级考试　　青少年软件编程等级考试是由中国电子学会发起的面向青少年软件编程能力水平的社会化评价项目，汲取外高校的人才选拔标准，支持创客教育的实践与工程化理念，全面考察青少年在软件编程的知识能力和实践能力，是青少年迈向人工智能应用领域的基础准备。 2 CCF非专业级软件能力认证（CSP-J/S） 　　CCF 面向社会非专业人士推出 CSP 非专业级别的能力认证，于2019年开设，参加一轮认证人数超过10万。非专业级别能力认证 CSP-J/S 分两个级别进行，分别为 CSP-J （入门级， Junior ）和 CSP-S （提， Senior ），均涉及算法和编程 3 中学信息技术创新与实践大赛（NOC）　　“中学信息技术创新与实践大赛”是一项运用信息技术，培养广大师生的创新精神和实践能力，面向青少年学生开展人工智能科学普及、引领科技创新的素质教育实践平台，简称NOC大赛（NOC为Novelty,Originality, Creativity的缩写）

本题示例及答案解析如下：答案解析：一、杨辉三角最大值公式如下：n为奇数时，C(n-1，(n-1)/2)，n为偶数时，C(n-1，n/2)。其中，C(M, N)表示从M个元素中任取N个的组合数。由于不好输入组合数公式，所以用C(M, N)替代。杨辉三角最本质的特征是，它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。其实，中国古代数学家在数学的许多重要领域中处于遥遥领先的地位。中国古代数学史曾经有自己光辉灿烂的篇章，而杨辉三角的发现就是十分精彩的一页。杨辉，字谦光，北宋时期杭州人。在他1261年所著的《详解九章算法》一书中，辑录了如上所示的三角形数表，称之为“开方作法本源”图。二、杨辉三角特点：前两列倒没什么特别的地方，第一列均为 1，第二列则为自然数。而第三列就是三角形数(Triangular number)。你可以想到，三角数就是能够组成大大小小等边三角形的点的数目。杨辉三角的美妙之处在于：它是如此足够简单，但本身在数学上却拥有丰富的魅力。这是数学中的最令人称奇的事物之一，随便取诸多数学性质中的某个，就能表明它是多么的精彩绝伦。

分类算法的目的就是根据训练集的特征将新的数据进行预测，当然能够找到特征之间的联系越多那么最后的分类结果也就应该越准确。但是有没有一个比较简单的算法，能够使用极少的特征就能够进行简单的分类呢？那就是OneR算法了。 OneR的全称为：One Rule，顾名思义也就是一条规则的意思。也就是说我们最终仅仅根据训练集中的一个特征就能够实现对数据的分类。如果只是使用一条规则的话，很显然这个分类的准确度不会很高，但是在某些特定的数据集中这个简单的算法也能够得到比较好的表现。 为了明白这个算法的工作原理，首先举一个比较简单的例子：就拿人的身高和眼睛大小以及肤色的数据对人进行分类是男是女。其中的编号不属于特征范畴，只是为了后续介绍数据使用。 编号 身高 眼睛大小 肤色 性别 1 180 正常 偏白 男 2 175 较大 偏黑 男 3 170 正常 偏黑 男 4 170 较大 偏黑 女 5 165 正常 偏白 女 6 160 较大 偏白 女 上述表格中随机写了一系列数据，我们来根据这些数据介绍一下OneR算法。 既然OneR算法是根据一个规则，也就是某一个特征来进行分类的，那么如何找到这个规则就比较重要了。 就拿上述的例子来看，我们有：身高、眼睛大小、肤色这三种特征，身高是属于连续值的范畴，眼睛大小是属于离散数据为：正常、较大，肤色也是离散数据：偏白、偏黑。 我们首先使用简单的方法将其转换为离散值，将大于（或等于）身高平均值的记为1，小于身高平均值的记为0，那么现在的数据就是这样。 编号 身高 眼睛大小 肤色 性别 1 1 正常 偏白 男 2 1 较大 偏黑 男 3 1 正常 偏黑 男 4 1 较大 偏黑 女 5 0 正常 偏白 女 6 0 较大 偏白 女 接下来我们就需要根据这些数据找到一个可以用来分类的特征规则。这个特征究竟是根据身高、眼睛大小、肤色呢？ 其实根据我们的生活常识，知道在这三种特征中身高的可靠性比较高的。但是如何根据计算找到身高这个特征呢？ 如何找到用来分类的规则（特征）。 其实简单的想一下就知道了，当然是使用这个特征之后我们的划分结果的正确率是最高的。我们需要进行一些简单的计算，要确保使用这个特征进行分类得到的准确率最高。因为只有准确率最高我们才能够得到比较正确的分类结果，所以我们的任务就可以转换为找到一个特征，根据这个特征进行分类的时候能够得到最高的正确率。 但是要明白，某个特征可能会有多个特征值，所以计算特征的准确率的话，需要包含其中的所有特征值可能性。也就是说这个特征的准确率是根据所有的特征值计算出来的。而对于某个特征对应的特征值来看，当然是选择分类最多的那个作为本次特征值的分类结果，然后再根据本次特征值的分类结果计算出错误个数。最后汇总到一起计算出该特征的准确率。 下面对上述样本集中的身高、眼睛大小、肤色分别计算准确率。 身高。 我们可以看到身高这个特征共有两种特征值：0和1。 如果身高特征值为1的话，那么符合特征值的数据编号为：{1,2,3,4}，对应的分类为：{男，男，男，女}。很明显如果身高这个特征值为1的话，在本次样本集中男生占了3/4，女生占了1/4。那么我们就选择分类结果最多的那个作为身高特征值为1的划分结果，也就是性别为男。所以现在可以简单的认为如果身高特征值为1的话，我们就简单的认为性别为男。但是很显然这个结论是有错误的，在本次样本集中这个结论的错误个数为1，因为在身高特征值为1的情况下有1样本的性别为女，与我们的结论不符。 如果身高特征值为0的话。那么符合特征值的数据编号为：{5,6}，对应的分类为：{女，女}。这个计算结果比较明显了。如果身高特征值为0的话，女生占了2/2。那么我们就选择性别为女作为身高特征值为0的分类结果。也就是说如果身高的特征值为0的话，我们就认为性别为女。这个结论可能有错误，但是在本次的数据集中是全部正确的。 在计算完身高的全部特征值之后就可以计算准确率了，我们在身高特征值为0的情况下，我们将其划分为女，这个准确率为百分之百。在身高特征值为1的情况下我们将其划分为男，有一个数据是错误的。所以如果按照身高进行划分的话，得到的准确率为：5/6=0.833。 眼睛大小。 眼睛大小这个特征共有两种特征值：正常、较大。 如果眼睛大小是正常的话，符合特征值的数据编号为：{1,3,5}，对应的分类结果为：{男，男，女}。同样的男生占了2/3，女生占了1/3，那么就简单的认为如果眼睛大小为正常的话，就认为性别为男性。同样的在本次数据集中，这个结论的错误个数为1，因为当前特征值分类结果中有一个是女性。 如果眼睛大小是较大的话，符合特征值的数据编号为：{2,4,6}，对应的分类结果为：{女，女，男}。同样的女生占了2/3，男生占了1/3，那么就简单的认为如果眼睛大小为较大的话，就认为性别为女性。同样的在本次数据集中，这个结论的错误个数为1。 有关眼睛大小的所有特征值计算完成之后就可以计算准确率了。我们在眼睛大小为正常的情况下，将其划分为男，这个结论在样本集中有一个数据是错误的；同样的在眼睛大小为较大的情况下，将其划分为女，这个结论在样本集中有一个数据是错误的。所以如果按照眼睛大小进行划分的话，准确率为：4/6=0.667。 肤色。 肤色特征共有两个特征值：偏黑、偏白。 如果肤色偏黑的话，符合特征值的数据编号为：{2,3,4}，对应的分类结果为：{男，男，女}。男生占了2/3，女生1/3。所以如果肤色偏黑的话，就简单认为是男生，这个结论的错误个数为1。 如果肤色偏白的话，符合特征值的数据编号为：{1,5,6}，对应的分类结果为：{男，女，女}。男生占了1/3，女生占了2/3,。所以如果肤色偏白的话，就简单的认为是女生，这个结论的错误个数为1。 所以肤色的准确率为：4/6=0.667。 现在得到了各个特征的准确率。身高的划分准确率为：0.833；肤色和眼睛大小的准确率都为：0.667。所以我们使用身高作为划分特征。 也就是如果有新的数据，我们只看身高这一项数据就将其进行分类。但是分类器的准确率的话是需要使用测试数据进行计算的，我们计算出来的0.833只是根据训练样本集的准确率，只是为了找出用来划分的规则。

是测距的单位。RSSI是射频信号理论术语，主要应用于发射机和接收机之间的距离测量。该方法是依据接收信号能量强度确定距离，对通信信道参数要求较高。其测距理论是：依据无线电波或声波在介质中传输，信号功率是随传播距离衰减的原理。通过接收到的信号强弱测定信号点与接收点的距离，进而根据相应数据进行定位计算的一种定位技术。如无线传感的ZigBee网络CC2431芯片的定位引擎就采用的这种技术、算法。接收机测量电路所得到的接收机输入的平均信号强度指示。这一测量值一般不包括天线增益或传输系统的损耗。

一般意义上的贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。Dijkstra算法显然是从整体最优考虑，求出的最短路径，一定是整体最优解，这是和一般意义上的贪心算法相悖的地方。而且Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在我看来，Dijkstra算法更接近动态规划。从维基百科也可以看到这样的说明：From a dynamic programming point of view, Dijkstra"s algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.

实际工程中动态规划往往很难实现，但是求解能得到全局最优。但是贪心算法虽然较易陷入局部最优，但是求解效率极高。若是决策量前后之间影响不是很大，且较大规模问题贪心法较好。

贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法求解背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。在最后一步包装不下时可能会分割物品，而0-1背包问题不能分割物品，故不一定得到最优解。取一反例即可说明

是prim算法普里姆算法(Prim算法)，图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点(英语：Vertex(graphtheory))，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语：VojtěchJarník)发现；并在1957年由美国计算机科学家罗伯特·普里姆(英语：RobertC.Prim)独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

可以去CSDN查查看

都是用C++写的，不建议只用纯C语言#include <iostream>#include <fstream>#include <algorithm>using namespace std;struct Riddle { int time; int money;};struct gt{ bool operator()(Riddle& opl, Riddle& opr){ return opl.money > opr.money; }};int main(){ int m, n; ifstream fin("riddle.in"); fin >> m >> n; Riddle * riddles = new Riddle[n]; for (int i=0; i<n; ++i) { fin >> riddles[i].time; } for (int i=0; i<n; ++i) { fin >> riddles[i].money; } sort(riddles, riddles+n, gt() ); int * ridorder = new int[n]; for (int i=0; i<n; ++i) { ridorder[i] = 0; } for (int i=0; i<n; ++i) { int j; for (j=riddles[i].time-1; j>=0 && ridorder[j]!=0; --j) {} if (j >= 0) ridorder[j] = 1; else m -= riddles[i].money; } cout << m << endl;}#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define maxn 55struct Peanut{ int x, y, num;}peanut[maxn * maxn];int n, m, t, pcount;bool operator < (const Peanut &a, const Peanut &b){ return a.num > b.num;}void input(){ pcount = 0; scanf("%d%d%d", &n, &m, &t); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { int a; scanf("%d", &a); if (a) { peanut[pcount].x = i + 1; peanut[pcount].y = j + 1; peanut[pcount].num = a; pcount++; } }}void work(){ int nowtime = peanut[0].x + 1; if (nowtime + peanut[0].x > t) { printf("0 "); return; } int ans = peanut[0].num; for (int i = 1; i < pcount; i++) { nowtime += abs(peanut[i].x - peanut[i - 1].x) + abs(peanut[i].y - peanut[i - 1].y) + 1; if (nowtime + peanut[i].x > t) break; ans += peanut[i].num; } printf("%d ", ans);}int main(){ //freopen("t.txt", "r", stdin); int t; scanf("%d", &t); while (t--) { input(); sort(peanut, peanut + pcount); work(); } return 0;}

程序员掌握核心算法，还不收录1、十大排序算法（1）简单排序:插入排序、选择排序、冒泡排序(必学)。（2）分治排序:快速排序、归并排序(必学，快速排序还要关注中轴的选取方式)。（3）分配排序:桶排序、基数排序。（4）树状排序:堆排序(必学)。（5）其他:计数排序(必学)、希尔排序。对干十大算法的学习，假如你不大懂的话，那么推荐你去看书，因为看了书，你可能不仅仅知道这个算法怎么写，还能知道他是怎么来的。推荐书籍是《算法第四版》，这本书讲的很详细，而且配了很多图演示，还是挺好懂的。2、搜索与回溯算法（1）贪心算法(必学)；（2）启发式搜索算法:A*寻路算法(了解)；（3）地图着色算法、N 皇后问题、最优加工顺序；（4）旅行商问题。这方便的只是都是一些算法相关的，像贪心算法的思想，就必须学的了。建议通过刷题来学习，leetcode 直接专题刷。3、动态规划（1）树形DP:01背包问题；（2）线性DP:最长公共子序列、最长公共子串；（3）区间DP:矩阵最大值(和以及积)；（4）数位DP:数字游戏；（5）状态压缩DP:旅行商。这里建议先了解动态规划是什么，之后 leetcode专题刷，反正就一般上面这几种题型。4、字符匹配算法（1）正则表达式；（2）模式匹配:KMP、Boyer-Moore。5、流相关算法（1）最大流:最短增广路、Dinic 算法。（2）最大流最小割:最大收益问题、方格取数问题。（3）最小费用最大流:最小费用路、消遣。

现有1g、2g、3g、5g、10g、20g的砝码各若干枚，问用这些砝码可以称出多少种不同的重量。（设砝码的总重量不超过1000克，且砝码只能放在天平的一端） 输入方式：a1 a2 a3 a4 a5 a6 (表示1g砝码有a1个，2g砝码有a2个，......20g砝码有a6个) 输出方式:Total=N (N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况) 如:输入:1 1 0 0 0 0 输出:Total=3 表示可以称出1g,2g,3g三种不同的重量。#include <stdio.h> int main( ) { int a[ 6 ], m[ 6 ], total = 0, i, j, k, f[ 1001 ]; for ( i = 0; i <= 1000; i++ ) f[ i ] = 0; f[ 0 ] = 1; m[ 0 ] = 1; m[ 1 ] = 2; m[ 2 ] = 3; m[ 3 ] = 5; m[ 4 ] = 10; m[ 5 ] = 20; for ( i = 0; i < 6; i++ ) scanf("%d", &a[ i ]); for ( i = 0; i < 6; i++ ) { for ( j = 0; j < a[ i ]; j++ ) { for ( k = 1000; k >= m[ i ]; k-- ) if ( f[ k - m[ i ] ] && !f[ k ] ) { f[ k ] = 1; total++; } } } printf("Total=%d ", total); return 0; }

shayisi?

题目链接 这道题的最佳解法是使用小根堆的贪心方法，但其正确性并不是显而易见的。这里，我们结合具体场景来对贪心方法的正确性进行分析。 不需要分裂工人，直接让他去建造街区就好了。花费时间 我们必须先把当前的工人分裂为两个工人，然后让他们分别去建造街区。花费时间 如果我们继续按照这样的正向思维来分析，最后得到的可能就是一个DFS的方法。因为我们每一步都需要去抉择将几个工人进行分裂，而这一抉择的优劣并不是显然的，因此好的剪枝策略不易找到。 我们不妨换一个角度来理解，如果我们不是分裂工人，而是合并街区呢？上面两个街区的情形中，分裂工人的操作，实际上就等价于把这两个街区合并为了一个建造时间为 的新街区。 考虑对 个街区进行合并。我们可以看到，选择任意两个街区 和 进行合并后，得到的“新”街区建造时间为： 看到这里，不知道大家有没有想到经典的Huffman Tree？在Huffman Tree中，两个节点合并后得到的新节点为 。为了让数值大的节点尽可能少参与到合并中，我们总是优先挑选两个最小的节点来进行合并。 本题中也是一样，为了让耗时长的街区尽可能少参与到合并中，我们总是优先挑选两个耗时最小的街区（这里的街区，可能是由之前操作合并得到的）进行合并。所以我们可以维护一个小根堆，每次取最上方两个街区进行合并，然后将合并得到的新街区重新加入堆中。 如何严格证明这一贪心策略的正确性呢？我们可以参考Huffman Tree的证明过程，使用归纳法来进行证明。 我们首先把对问题进行重述。根据前面的分析，将分裂工人转化为合并街区后，这一问题就可以重述为： 而我们解决这一问题的策略，即是上述的贪心策略：每次选取两个最小的数进行合并，直到只剩下一个数为止。 在证明贪心策略的正确性之前，我们首先需要证明一个引理。 引理 将合并过程表示为一棵节点的度为0或2的二叉树，其叶子节点为初始的数且至少有两个叶节点，父节点的值为 ，其中 为其两个子节点的值。假设 个数中最小的两个数为 ，则在最优合并对应的二叉树中， 对应的叶节点一定具有最大的深度，且为兄弟节点。 引理的证明 假设存在一个叶节点 ，其深度 大于 的深度 ，且 。假设 的深度为 的祖先节点为 ，则 。考虑所有深度为 的节点的最大值 ，可以得到 尝试交换 和 。交换后 ， 由 可知，交换后二叉树的根节点 。因此，我们总可以通过若干次交换，使得 具有最大深度，并且根节点的值不大于原本根节点的值。 由于二叉树的节点度不能为1，所以深度最深的叶节点至少有两个。因此，我们可以再通过若干次交换，使得 具有最大深度，并且根节点的值不大于原本根节点的值。由于 的深度不能超过 的深度，所以此时它们的深度一定相等。 若二叉树深度最深的一层只有两个叶节点，它们必定为 和 且为兄弟。 假设在二叉树深度最深的一层还有其他叶节点，则由节点的度为0或2可知，至少还有两个叶节点 ，且满足 。若 不为兄弟节点，不妨假设 和 为兄弟节点， 为兄弟节点。则 和 的父节点 ， 和 的父节点 。考虑倒数第二层的所有节点的最大值 ，可以得到 若将 和 交换，则 ，从而 因此这一交换可以得到更优的合并方案。从而， 和 一定为兄弟节点。 归纳基础 在 时，使用贪心策略可以得到最优合并。 归纳步骤 假设 时，使用贪心策略可以得到最优合并。我们需要证明：在 时，使用贪心策略可以得到最优合并。 归纳基础的证明 由前面对两个街区情形的分析可知，归纳基础成立。 归纳步骤的证明

个人认为dijkstra算法（单源最短路径)是贪心算法，因为每次都是贪心的选择具有最短距离的点，而且优化子结构与贪心选择性也能证明。但是，感觉也可以认为是动态规划，优化子结构显然（从贪心处得），因为记录了上一次找到的最近节点，保存了上一次的最短距离，并用于这一次的选择，所以也符合一般动态规划的思想，如果不用贪心选择，那么求最短问题一定要遍历所有的可行路径，由于存在分支，所以也可以认为存在重叠子问题，所以也可以看成是动态规划。主要是数据结构老师说这是贪心的（个人也是这么认为的），最近刚看一次算法设计的题，上面又讲是动态规划。分析起来好像都行。

这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。 (ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解

TSP属于NPC问题，一般只能靠近似算法求出近似解，问题规模小的时候，可以直接穷举问题空间，得出最优解，不过问题规模一大就不行了，问题空间是指数暴涨的，这时候只能退而求其次，求近似最优解，而对应的近似算法中会大量使用贪心策略，所以其实不是可不可行的问题，贪心牺牲了 解的精度（求得的不一定是最优解），但换来了时间上可观的节约（直接降到多项式）。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产

使用百度Hi可以第一时间收到“提问有新回答”“回答被采纳”“网友求助”的通知。查看详情您想在自己的网站上展示百度“知道”上的问答吗？来获取免费代码吧！ 投诉或举报，请到百度知道投诉吧反馈。功能意见建议，请到知道意见社吧反馈。

连通图： 在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。 强连通图（Strongly Connected Graph） 是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。 连通网： 在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。 生成树： 一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。 最小生成树： 在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。 示例： 分别使用 Kruskal算法 和 Prim算法 ，找出下图的最小生成树。 使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 具体步骤 1.将信源符号的概率按减小的顺序排队。 2.把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率1。 3.画出由概率1处到每个信源符号的路径，顺序记下沿路径的0和1，所得就是该符号的霍夫曼码字。 4.将每对组合的左边一个指定为0，右边一个指定为1（或相反）。 示例： 假设字符a,b,c,d,e出现的概率分别为1/2,1/4,1/8,1/16,1/16。 1.求出各字符哈夫曼编码表。 2.假设一个文件有1,000,000个字符，求出编码之后文件的字节长度。 A:0 B:10 C:110 D:1110 E:1111 a所占长度l1为：（1,000,000/2） 1 b所占长度l2为：（1,000,000/4） 2 c所占长度l3为：（1,000,000/8） 3 d所占长度l4为：（1,000,000/16） 4 e所占长度l5为：（1,000,000/16）*4 文件的总长度l = l1 + l2 + l3 + l4 + l5 = 1875000

对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 注意: 假设字符串的长度不会超过 1010。 示例 1: 输入: "abccccdd" 输出: 7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 请注意！！！ 题目的意思是：利用这个字符串中的所有字母来构造最长回文串，是构造！是可以改变字母出现的位置顺序的！字母位置可以任意移动。而不是在顺序不变的情况下找出最长的回文串。 作者一开始粗心大意没理解题意，直接上手做题吃大亏（捂脸。 现在来解释下，什么是回文？ 回文串是一个正着读和反着读都一样的字符串。 来看两个不同的回文例子： AB|BA。仅看字母，我们发现，AB和BA根据中心竖线|对称，这个回文串长度为4，每个字母出现的次数都是偶数。 ABCBA。我们发现，AB和BA根据字母C对称，这个回文串长度为5，除了对称中心的字母C仅出现过一次外，中心两边的字母出现次数都是偶数。 所以我们可以总结出，如果想要构造出一个回文串，除了回文串中心的字母只能出现一次外（如果有中心字母的话），中心两边的字母还需对称出现，即出现偶数次。 解决了构造回文串这一关键点，题目中还有一个特别之处：仅出现大写字母和小写字母。 如果对英文字母的Unicode编码熟悉的话，可以知道，字母A的Unicode编码是65（十进制），字母Z的Unicode编码是90（十进制），字母a的Unicode编码是97（十进制）,字母z的Unicode编码是122（十进制）。 可以发现它们是Unicode编码是连续（中间的91到96并不重要），即有序的，所以可以使用数组来存放它们，每个数组项的值就是每个字母出现的次数。 这种情况下，使用数组来存储，会比使用哈希表（Map）来存储来得更高性能，哪怕Unicode编码的91到97我们无需使用。 且，在JavaScript世界中，可以使用String.prototype.charCodeAt()这一API来获取Unicode编码单元。 所以，我们可以这样来统计每个字母出现的次数：

算法不同，都是一种递推算法。1、算法不同。贪心算法问题的最优解可以通过一系列局部最优的选择来达到，它仅在当前状态下做出最好选择，而动态规划的选择往往依赖相关子问题的解。2、都是一种递推算法。动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。

贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来得到。就是说，你需要证明当前问题可以通过选择最好的那个元素（比如01背包，总能够通过选择当前重量最小的物品来得到最优解）来解决问题证明：（每一步所做的贪心选择最终导致问题的整体最优解）//基本思路：考察一个问题的最优解，证明可修改该最优解，使得其从贪心选择开始，然后用数学归纳法证明每一步都可以通过贪心选择得到最优解1，假定首选元素不是贪心选择所要的元素，证明将首元素替换成贪心选择所需元素，依然得到最优解；2，数学归纳法证明每一步均可通过贪心选择得到最优解

克鲁斯卡尔算法是贪心算法。克鲁斯卡尔算法(Kruskal"s algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个部分：首先是带权图G中e条边的权值的排序；其次是判断新选取的边的两个顶点是否属于同一个连通分量。对带权图G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相同。对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以达到O（elge）。判断新选取的边的两个顶点是否属于同一个连通分量的问题是一个在最多有n个顶点的生成树中遍历寻找新选取的边的两个顶点是否存在的问题，此算法的时间复杂度最坏情况下为O（n）。

public getMin{public int MinNumber=0;public int findMax(int[] a){ for(int i=0;i<a.length;i++){ if(a[i]==0) return a[--i]; } return a[a.length-1];}public boolean Compare(int a,int b){ public boolean flag=true; if(a>b) flag=flase; return flag;}public int getMinNumber(int[] M,int Money){ int[] findM=new int[M.length]; int index=0; for(int i=0;i<M.length;i++){ boolean f = this.Compare(M[i],money) if(f) findM[index++]=M[i]; } int max = this.findMax(findM); MinNumber++; if((Money-max)!=0) { getMinNumber(M,Money-max) } return MinNumber;}public int[] Start(){ System.out.println("请输入查询组数"); int group=System.in.read(); int[] M={1,2,5,10,20,50,100}; int[] Result = new Int[group]; int index=0; while (group-- > 0){ System.out.println("请输入金额"); int money=System.in.read(); Result[index++] = getMinNumber(M,money); MinNumber=0; } }public void print(int[] MinNumber){ for(int i=0;i<MinNumber.length.i++){ System.out.println(MinNumber[i]+" "); }}}public static void main(String[] args){ new getMin().print(new getMin().Start());}没测试啊，有问题请勿喷，呵呵

这里主要是介绍一种证明贪心算法是最优的一种方法：Exchange Argument （不知道应该怎么翻译到中文，交换参数？感觉听起来挺别扭的，不像是一个方法的名字~o( □ )o）Exchange Argument的主要的思想也就是 先假设 存在一个最优的算法和我们的贪心算法最接近，然后通过交换两个算法里的一个步骤(或元素)，得到一个新的最优的算法，同时这个算法比前一个最优算法更接近于我们的贪心算法，从而得到矛盾，原命题成立。下面来看一个更为formal的解释：步骤：Step0: 给出贪心算法A的描述Step1: 假设O是和A最相似(假设O和A的前k个步骤都相同，第k+1个开始不同，通常这个临界的元素最重要)的最优算法Step2: [Key] 修改算法O(用Exchange Argument，交换A和O中的一个元素)，得到新的算法O"Step3: 证明O" 是feasible的，也就是O"是对的Step4: 证明O"至少和O一样，即O"也是最优的Step5: 得到矛盾，因为O" 比O 更和A 相似。证毕。当然上面的步骤还有一个变种，如下：Step0: 给出贪心算法A的描述Step1: 假设O是一个最优算法（随便选，arbitrary）Step2: 找出O和A中的一个不同。（当然这里面的不同可以是一个元素在O不再A，或者是一个pair的顺序在A的和在O的不一样。这个要根据具体题目）Step3：Exchange这个不同的东西，然后argue现在得到的算法O 不必O差。Step4: Argue 这样的不同一共有Polynomial个，然后我exchange Polynomial次就可以消除所有的不同，同时保证了算法的质量不比O差。这也就是说A 是as good as 一个O的。因为O是arbitrary选的，所以A是optimal的。证毕下面给几个例子：例 Maximum Cardinality Disjoint Interval Problem问题描述：给一些时间片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一个元素个数最多的子集S，子集中的每个元素的时间片段没有交叉。Greedy Algorithm: 每次都选所有interval 中bi最小的那个，把（ai，bi）加入S，然后把（ai，bi）在T中删除，同时把T中所有和（ai，bi）有交叉的interval删除，然后再在T中找最小的bj，循环上面的操作，直到没有可以在添加的。证明上面说的Greedy Algorithm是最优的。下面就用第一个证明的步骤来证。我们的Greedy Algorithm记为A，假设A不是最优的，那么就一定存在一个O，O是和A最相近的一个最优的算法，最相近是指和O和A的前K-1个选择都相同，第K个是不同的。假设对于A，A第k个选择的是（ai，bi）；而O第K个选择的是（aj，bj）。从A的定义我们可以直到，bi<=bj。

在现实生活中，经常遇到找零问题，假设有数目不限的面值为20,10,5,1的硬币。 给出需要找零数，求出找零方案，要求：使用数目最少的硬币。对于此类问题，贪心算法采取的方式是找钱时，总是选取可供找钱的硬币的最大值。比如，需要找钱数为25时，找钱方式为20+5，而不是10+10+5。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。本文我们就和大家分享JS使用贪心算法解决找零问题示例。可惜的是，它需要证明后才能真正运用到题目的算法中。结果是：需要说明的是，在一些情况下，找零钱问题使用贪心算法并不能得到整体最优解，其结果可能只是最优解的很好近似。比如，如果提供找零的面值是11，5，1，找零15。使用贪心算法找零方式为11+1+1+1+1，需要五枚硬币而最优解为5+5+5，只需要3枚硬币。

多塔问题？？可用动态规划试一下。。记录m台机器中使用时间最长的，时间为Tmax，以及其它m-1台机器所用时间为Ti。将Ti与Tmax时间差的和记录为St。则St越小时间Tmax越短。

是的；启发式算法是相对“最优算法”而言的，其目标是在某种启发原则的引导下搜寻解（这种解一般是局部最优，但可以很大程上接近最优）；贪心算法的核心——贪心准则就是一种启发原则。

没有太看明白你的意思

你的冒泡排序貌似不对，你自己看一下排序后价值数组的数据看看

　　马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口"最小的进行搜索，‘出口"的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子"结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死"结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。　　贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。　　贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式　　所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。其实很多的智能算法（也叫启发式算法），本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更靠近了最优解。例如遗传算法，模拟退火算法。

关于贪心算法，下面正确的是（）。 A.每个阶段总是做出在当前看来是最好的选择 B.贪心算法一定能够得到问题的最优解 C.原问题分解成若干阶段，如果当前无法得到问题的解，返回到上一阶段 D.任何问题都可以是使用贪心算法解决 正确答案：每个阶段总是做出在当前看来是最好的选择

问题一：贪心算法的例题分析 例题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 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重复2显然⑵是一个递归调用的过程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();输出一个解 return; } for(i=0; i> 问题二：收集各类贪心算法（C语言编程）经典题目 tieba.baidu/...&tb=on百度的C语言贴吧。 全都是关于C的东西。 问题三：几种经典算法回顾 今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | > 问题四：求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢 贪心算法的名词解释 baike.baidu/view/298415 第一个贪心算法 （最小生成树） baike.baidu/view/288214 第二个贪心算法 （Prim算法） baike.baidu/view/671819 第三个贪心算法 （kruskal算法） baike.baidu/view/247951 算法都有详细解释的 问题五：求 Java 一些经典例子算法 前n项阶乘分之一的和 public class jiecheng { public static void main(String[] args) { double sum=0; double j=1; int n=10; for(int i=1;i 问题六：关于编程的贪心法 定义 所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 [编辑本段]贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。 [编辑本段]例题分析 [背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析： 目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi> 问题七：求解一贪心算法问题 最快回答那个不懂别乱说，别误人子弟。 这题标准的贪心算法，甚至很多时候被当做贪心例题 要求平均等待时间，那么就得用 总等待时间 / 人数 所以只用关心总等待时间， 如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。 给你写了个，自己看吧。 #include stdafx.h #include #include #include using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int n; float arr[105]; cin >> n; for(int i = 0; i > arr[i]; sort(arr, arr+n); int tnow = 0; int tmax = 0; for(int i = 0; i 问题八：分治算法的应用实例 下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i] > 问题九：回溯算法的典型例题 八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 问题十：什么是算法，都什么，举个例子，谢谢 算法就是解决问题的具体的方法和步骤，所以具有以下性质： 1、有穷性： 一个算法必须保证执行有限步之后结束（如果步骤无限，问题就无法解决） 2、确切性：步骤必须明确，说清楚做什么。 3、输入：即解决问题前我们所掌握的条件。 4、输出：输出即我们需要得到的答案。 5、可行性：逻辑不能错误，步骤必须有限，必须得到结果。 算法通俗的讲：就是解决问题的方法和步骤。在计算机发明之前便已经存在。只不过在计算机发明后，其应用变得更为广泛。通过简单的算法，利用电脑的计算速度，可以让问题变得简单。

孔子曰：知之为知之，不知为不知。所以我不知道！

1.数论算法 求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; 求两数的最小公倍数 function lcm(a,b:integer):integer; begin if a< b then swap(a,b); lcm:=a; while lcm mod b >0 do inc(lcm,a); end; 素数的求法 A.小范围内判断一个数是否为质数： function prime (n: integer): Boolean; var I: integer; begin for I:=2 to trunc(sqrt(n)) do if n mod I=0 then begin prime:=false; exit; end; prime:=true; end; B.判断longint范围内的数是否为素数（包含求50000以内的素数表）： procedure getprime; var i,j:longint; p:array[1..50000] of boolean; begin fillchar(p,sizeof(p),true); p[1]:=false; i:=2; while i< 50000 do begin if p then begin j:=i*2; while j< 50000 do begin p[j]:=false; inc(j,i); end; end; inc(i); end; l:=0; for i:=1 to 50000 do if p then begin inc(l); pr[l]:=i; end; end;{getprime} function prime(x:longint):integer; var i:integer; begin prime:=false; for i:=1 to l do if pr >=x then break else if x mod pr=0 then exit; prime:=true; end;{prime} 2． 3． 4.求最小生成树 A.Prim算法： procedure prim(v0:integer); var lowcost,closest:array[1..maxn] of integer; i,j,k,min:integer; begin for i:=1 to n do begin lowcost:=cost[v0,i]; closest:=v0; end; for i:=1 to n-1 do begin {寻找离生成树最近的未加入顶点k} min:=maxlongint; for j:=1 to n do if (lowcost[j]< min) and (lowcost[j]< >0) then begin min:=lowcost[j]; k:=j; end; lowcost[k]:=0; {将顶点k加入生成树} {生成树中增加一条新的边k到closest[k]} {修正各点的lowcost和closest值} for j:=1 to n do if cost[k,j]< lwocost[j] then begin lowcost[j]:=cost[k,j]; closest[j]:=k; end; end; end;{prim} B.Kruskal算法：(贪心) 按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。 function find(v:integer):integer; {返回顶点v所在的集合} var i:integer; begin i:=1; while (i< =n) and (not v in vset) do inc(i); if i< =n then find:=i else find:=0; end; procedure kruskal; var tot,i,j:integer; begin for i:=1 to n do vset:=;{初始化定义n个集合，第I个集合包含一个元素I} p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针} sort; {对所有边按权值递增排序，存于e[I]中，e[I].v1与e[I].v2为边I所连接的两个顶点的序号，e[I].len为第I条边的长度} while p >0 do begin i:=find(e[q].v1);j:=find(e[q].v2); if i< >j then begin inc(tot,e[q].len); vset:=vset+vset[j];vset[j]:=[]; dec(p); end; inc(q); end; writeln(tot); end; 5.最短路径 A.标号法求解单源点最短路径： var a:array[1..maxn,1..maxn] of integer; b:array[1..maxn] of integer; {b指顶点i到源点的最短路径} mark:array[1..maxn] of boolean; procedure bhf; var best,best_j:integer; begin fillchar(mark,sizeof(mark),false); mark[1]:=true; b[1]:=0;{1为源点} repeat best:=0; for i:=1 to n do If mark then {对每一个已计算出最短路径的点} for j:=1 to n do if (not mark[j]) and (a[i,j] >0) then if (best=0) or (b+a[i,j]< best) then begin best:=b+a[i,j]; best_j:=j; end; if best >0 then begin b[best_j]:=best；mark[best_j]:=true; end; until best=0; end;{bhf} B.Floyed算法求解所有顶点对之间的最短路径： procedure floyed; begin for I:=1 to n do for j:=1 to n do if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0; {p[I,j]表示I到j的最短路径上j的前驱结点} for k:=1 to n do {枚举中间结点} for i:=1 to n do for j:=1 to n do if a[i,k]+a[j,k]< a[i,j] then begin a[i,j]:=a[i,k]+a[k,j]; p[I,j]:=p[k,j]; end; end; C. Dijkstra 算法： 类似标号法，本质为贪心算法。 var a:array[1..maxn,1..maxn] of integer; b,pre:array[1..maxn] of integer; {pre指最短路径上I的前驱结点} mark:array[1..maxn] of boolean; procedure dijkstra(v0:integer); begin fillchar(mark,sizeof(mark),false); for i:=1 to n do begin d:=a[v0,i]; if d< >0 then pre:=v0 else pre:=0; end; mark[v0]:=true; repeat {每循环一次加入一个离1集合最近的结点并调整其他结点的参数} min:=maxint; u:=0; {u记录离1集合最近的结点} for i:=1 to n do if (not mark) and (d< min) then begin u:=i; min:=d; end; if u< >0 then begin mark:=true; for i:=1 to n do if (not mark) and (a[u,i]+d< d) then begin d:=a[u,i]+d; pre:=u; end; end; until u=0; end; D.计算图的传递闭包 Procedure Longlink; Var T:array[1..maxn,1..maxn] of boolean; Begin Fillchar(t,sizeof(t),false); For k:=1 to n do For I:=1 to n do For j:=1 to n do T[I,j]:=t[I,j] or (t[I,k] and t[k,j]); End;

贪心算法的基本思路如下：　　1.建立数学模型来描述问题。　　2.把求解的问题分成若干个子问题。　　3.对每一子问题求解，得到子问题的局部最优解。　　4.把子问题的解局部最优解合成原来解问题的一个解。----------------------------------------------其实归纳起来也就一个类。其他的都是分支

longa,b,s,k,num,c[7]={100,50,20,10,5,2,1}//a,顾客付款;b,实际售价;num找钱数。for(s=a-b,k=0,num=0;k<7&&s>0;k++){num+=(long)s/c[k];s-=num*c[k];}printf("%d",num);//k可以不要

遍历算法是一种暴力搜索方法，它会枚举所有可能的解，然后从中选取最优解。但是，当问题规模非常大时，遍历算法的时间复杂度会非常高，计算时间过长，效率低下，甚至无法得到结果。因此，在这种情况下，采用贪心算法可以更加高效地解决问题。贪心算法是一种每一步都选择当前最优解的策略，从而得到全局最优解的方法。它通常比遍历算法更加高效，因为它只需要考虑当前步骤的最优解，而不需要考虑所有可能的解。因此，贪心算法的时间复杂度相对较低，计算速度较快。虽然贪心算法和遍历算法可能会得到相同的结果，但是在问题规模非常大的情况下，贪心算法更加实用。同时，需要注意的是，贪心算法得到的结果不一定是全局最优解，而可能只是局部最优解。

【答案】：D贪心法在一般情况下一定能够得到满意解，不一定能够得到最优解。贪心法能够获得最优解的前提是：（1）问题具有最优子结构，即规模为n的问题的最优解与规模为n-1的问题的解相关；（2）问题具有贪心选择性质，即问题的整体最优解可以通过一系列局部最优的选择得到。部分背包问题具有以上性质，故可以通过贪心算法得到最优解。

不能...见主教材的转载问题

递归，简单的重复，计算量大。分治，解决问题独立，分开计算，如其名。动态规划算法通常以自底向上的方式解各子问题，贪心算法则通常以自顶向下的方式进行；动态规划能求出问题的最优解，贪心不能保证求出问题的最优解

贪心算法基本要素有（）和最优子结构性质。 A.分解合并性质 B.独立子问题性质 C.贪心选择性质 D.重叠子问题性质 正确答案：C

从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。

是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部 最优解。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

很形象的说贪心算法，只注重当前利益最大化，即选择当前步骤的最优解。

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性：1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后，目标函数给出解的值。

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性：1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后，目标函数给出解的值。

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性：1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后，目标函数给出解的值。

贪心算法的基本思想就是分级处理。贪心算法是一种分级处理的方法。用贪心法设计算法的特点是一步一步的进行，根据某个优化测度（可能是目标函数，也可能不是目标函数），每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取应满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。贪心算法可解决的问题通常大部分都有如下的特性：1、随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。2、有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。3、还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。4、选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。5、最后，目标函数给出解的值。

因为贪心算法的正确性无法被证明，而且有反例

一般意义上的贪心算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。Dijkstra算法显然是从整体最优考虑，求出的最短路径，一定是整体最优解，这是和一般意义上的贪心算法相悖的地方。而且Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在我看来，Dijkstra算法更接近动态规划。从维基百科也可以看到这样的说明：From a dynamic programming point of view, Dijkstra"s algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.

先按结束时间从小到大排序，然后遍历一遍，能安排就安排就行了

题解(from USACO)三值排序问题 [IOI 1996]有一个由N个数值均为1、2或3的数构成的序列（N<= 1000），其值无序，现要求你用最少的交换次数将序列按升序顺序排列。算法：排序后的序列分为三个部分：排序后应存储1的部分，排序后应存储2的部分和排序后应存储3的部分，贪心排序法应交换尽量多的交换后位置正确的（2，1）、（3，1）和（3，2）数对。当这些数对交换完毕后，再交换进行两次交换后位置正确的（1，2，3）三个数。 分析：很明显，每一次交换都可以改变两个数的位置，若经过一次交换以后，两个数的位置都由错误变为了正确，那么它必定最优。同时我们还可发现，经过两次交换后，我们可以随意改变3个数的位置。那么如果存在三个数恰好为1，2和3，且位置都是错误的，那么进行两次交换使它们位置正确也必定最优。有由于该题具有最优子结构性质，我们的贪心算法成立程序：var a:array[1..1000] of integer; f:array[1..3,1..3] of integer; b:array[1..3] of integer; n,i,j,t,p:integer;begin readln(n); for i:=1 to n do readln(a[i]); fillchar(f,sizeof(f),0); for i:=1 to n do inc(b[a[i]]); b[2]:=b[2]+b[1]; b[3]:=n; t:=0; for i:=1 to n do if i<=b[1] then inc(f[1,a[i]]) else if i<=b[2] then inc(f[2,a[i]]) else if i<=b[3] then inc(f[3,a[i]]); for i:=1 to 2 do for j:=i+1 to 3 do begin if f[i,j]>f[j,i] then p:=f[j,i] else p:=f[i,j]; t:=t+p; if f[i,j]-p>=0 then f[i,j]:=f[i,j]-p; if f[j,i]-p>=0 then f[j,i]:=f[j,i]-p; end; t:=t+(f[1,2]+f[1,3]) shl 1; writeln(t);end.另外,站长团上有产品团购,便宜有保证

　　[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。　　要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。　　物品 A B C D E F G 　　重量 35 30 60 50 40 10 25 　　价值 10 40 30 50 35 40 30 　　分析：　　目标函数： ∑pi最大　　约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)　　（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？　　（2）每次挑选所占重量最小的物品装入是否能得到最优解？　　（3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?　　值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。　　贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。　　可惜的是，它需要证明后才能真正运用到题目的算法中。　　一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。　　对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：　　（1）贪心策略：选取价值最大者。反例：　　W=30　　物品：A B C　　重量：28 12 12　　价值：30 20 20　　根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。　　（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。　　（3）贪心策略：选取单位重量价值最大的物品。反例：　　W=30　　物品：A B C　　重量：28 20 10　　价值：28 20 10　　根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

动态规划和贪心算法的区别1、动态规划算法中，每步所做的选择往往依赖于相关子问题的解，因而只有在解出相关子问题时才能做出选择。而贪心算法，仅在当前状态下做出最好选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。2、动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常自顶向下的方式进行。共同点：两者都具有最优子结构性质　动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。

对于，大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题，首先要来聊聊他们的联系：1、都是一种推导算法；2、将它们分解为子问题求解，它们都需要有最优子结构。这两个特征师门的联系。然后，下面来说说他们的差别：贪心算法需要每一步的最优解必须包含前一步的最优解，前一步的最优解不保留；而动态规划是全局最优解必须包含一个局部最优解，而不是先前的局部最优解。因此，有必要记录所有以前的局部最优解。另一个不同是，贪心算法它如果所有子问题都被视为一棵树，贪婪从根开始，每次都遍历最优子树（通常这种“最优”基于当前情况下明显的“最优”）；这样，就不需要知道一个节点的所有子树，所以它不能形成一个完整的树；而动态规划是从下到上，从叶到根构造子问题的解决方案。对于每个子树的根，找到下面每个叶子的值。最后，得到一棵完整的树，最后选择最优值作为自己的值来得到答案。可见，根据以上描述，贪心算法不能保证最终的解决方案是最好的，总体复杂度较低；动态规划的本质是穷举法，它能保证最优的结果和较高的复杂性。特别是对于0-1背包问题，它应该比较选择项目和不选择项目所导致的最终方案，然后做出最佳选择。由此衍生出许多重叠子问题，因此使用了动态规划。拓展资料：贪婪算法是指在解决问题时，它总是在当前做出最佳选择。也就是说，在不考虑全局优化的情况下，该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。动态规划是运筹学的一个分支，是解决决策过程优化的过程。20世纪50年代初，美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时，提出了著名的最优化原理，建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用，在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显著的成果。

对于一名优秀的程序员来说，面对一个项目的需求的时候，一定会在脑海里浮现出最适合解决这个问题的方法是什么，选对了算法，就会起到事半功倍的效果，反之，则可能会使程序运行效率低下，还容易出bug。因此，熟悉掌握常用的算法，是对于一个优秀程序员最基本的要求。 那么，常用的算法都有哪些呢？一般来讲，在我们日常工作中涉及到的算法，通常分为以下几个类型：分治、贪心、迭代、枚举、回溯、动态规划。下面我们来一一介绍这几种算法。 一、分治算法 分治算法，顾名思义，是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治算法一般分为三个部分：分解问题、解决问题、合并解。 分治算法适用于那些问题的规模缩小到一定程度就可以解决、并且各子问题之间相互独立，求出来的解可以合并为该问题的解的情况。 典型例子比如求解一个无序数组中的最大值，即可以采用分治算法，示例如下： def pidAndConquer(arr,leftIndex,rightIndex): if(rightIndex==leftIndex+1 || rightIndex==leftIndex){ return Math.max(arr[leftIndex],arr[rightIndex]); } int mid=(leftIndex+rightIndex)/2; int leftMax=pidAndConquer(arr,leftIndex,mid); int rightMax=pidAndConquer(arr,mid,rightIndex); return Math.max(leftMax,rightMax); 二、贪心算法 贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法的基本思路是把问题分成若干个子问题，然后对每个子问题求解，得到子问题的局部最优解，最后再把子问题的最优解合并成原问题的一个解。这里要注意一点就是贪心算法得到的不一定是全局最优解。这一缺陷导致了贪心算法的适用范围较少，更大的用途在于平衡算法效率和最终结果应用，类似于：反正就走这么多步，肯定给你一个值，至于是不是最优的，那我就管不了了。就好像去菜市场买几样菜，可以经过反复比价之后再买，或者是看到有卖的不管三七二十一先买了，总之最终结果是菜能买回来，但搞不好多花了几块钱。 典型例子比如部分背包问题：有n个物体，第i个物体的重量为Wi，价值为Vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。 贪心策略就是，每次都先拿性价比高的，判断不超过C。 三、迭代算法 迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值。最终得到问题的结果。 迭代算法适用于那些每步输入参数变量一定，前值可以作为下一步输入参数的问题。 典型例子比如说，用迭代算法计算斐波那契数列。 四、枚举算法 枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。枚举法的本质就是从所有候选答案中去搜索正确地解。 枚举算法适用于候选答案数量一定的情况。 典型例子包括鸡钱问题，有公鸡5，母鸡3，三小鸡1，求m钱n鸡的所有可能解。可以采用一个三重循环将所有情况枚举出来。代码如下： 五、回溯算法 回溯算法是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 典型例子是8皇后算法。在8 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。 回溯法是求解皇后问题最经典的方法。算法的思想在于如果一个皇后选定了位置，那么下一个皇后的位置便被限制住了，下一个皇后需要一直找直到找到安全位置，如果没有找到，那么便要回溯到上一个皇后，那么上一个皇后的位置就要改变，这样一直递归直到所有的情况都被举出。 六、动态规划算法 动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。 动态规划算法适用于当某阶段状态给定以后，在这阶段以后的过程的发展不受这段以前各段状态的影响，即无后效性的问题。 典型例子比如说背包问题，给定背包容量及物品重量和价值，要求背包装的物品价值最大。