⑴ 求會km演算法，且會使用matlab算出最優匹配的大神幫忙，最好懂編程的
KM演算法：其實感覺它的最基本得思想就是逐漸接近最優匹配，每次向最有匹配邁出最小的一步，直到達到最優為止（到最後，sigma(lx[i]+ly[i])剛好等於最優匹配值）
演算法開始，初始化LX[I]為等點I的最大的邊的權值，LY[I]初始為0，在這個時候如果各個定點所對應得最大權值得邊終點剛剛沒有重合的話，顯然，目前的匹配狀況既是最優的。
演算法進行的過程中不斷的更新頂標（LX[I],LY[I]）的值來進行匹配。
每次尋找增廣路徑，找到的話繼續尋找下一個點，找不到的話更改目前的頂標值，由於（sigma(lx[i]+ly[i])）是最優匹配的估計值，如果找不到當前節點的匹配的話，說明目前的最優匹配的估計值不能實現，需要調整，而KM演算法的核心就是如何實現一個有效同時又正確的調整的方法。
以最小的調整逐漸靠近答案是必須的，其次就是需要知道要調整哪些頂標，首先，調整不能破壞目前的匹配狀況（因為匹配是在尋找增廣路徑中實現的）
⑵ 什麼是最優適應分配演算法
最佳適應演算法是從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區的一種計算方法，這種方法能使碎片盡量小。
最佳適應演算法（Best Fit）：
它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此演算法，空閑分區表（空閑區鏈）中的空閑分區要按從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。該演算法保留大的空閑區，但造成許多小的空閑區。
Best fit演算法等價於裝箱問題，舉例如下：
裝箱問題：有體積為V的箱子N個，體積為Vi的物品M個，求使得物品全部能夠裝入箱子，箱子數量的最小值。
假設 V=6 N=10，V1，V2，...,V10分別為：3 4 4 3 5 1 2 5 3 1。計算過程如下：
第一步按物品體積降序排序：5 5 4 4 3 3 3 2 1 1
第二步：取未裝箱的最大值5裝入第一個箱子。
第三步：判斷第一個箱子是否已滿，不滿且剩餘空間為1，搜尋剩下體積小於等於1的物品填入箱子1，箱子1填滿。
第四步：重復第二，第三步，直到所有物品裝入箱子為止，得到箱子數量為6.
6即時本例N的最小值。
⑶ 什麼是最優適應分配演算法
分區分配演算法(Partitioning Placement Algorithm) ，共有3種。分別為最佳適應演算法、首次適應演算法、循環首次適應演算法。
1、最佳適應演算法（Best Fit）：
它從全部空閑區中找出能滿足作業要求的、且大小最小的空閑分區，這種方法能使碎片盡量小。為適應此演算法，空閑分區表（空閑區鏈）中的空閑分區要按大小從小到大進行排序，自表頭開始查找到第一個滿足要求的自由分區分配。該演算法保留大的空閑區，但造成許多小的空閑區。
2、首次適應演算法（First Fit）：
從空閑分區表的第一個表目起查找該表，把最先能夠滿足要求的空閑區分配給作業，這種方法目的在於減少查找時間。為適應這種演算法，空閑分區表（空閑區鏈）中的空閑分區要按地址由低到高進行排序。該演算法優先使用低址部分空閑區，在低址空間造成許多小的空閑區，在高地址空間保留大的空閑區。
3、循環首次適應演算法(Next Fit)：
該演算法是首次適應演算法的變種。在分配內存空間時，不再每次從表頭（鏈首）開始查找，而是從上次找到空閑區的下一個空閑開始查找，直到找到第一個能滿足要求的的空閑區為止，並從中劃出一塊與請求大小相等的內存空間分配給作業。該演算法能使內存中的空閑區分布得較均勻。
⑷ 求用C語言寫出首次適應分配演算法的分配過程~
/********************************
內存管理模擬程序
*******************************/
#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <time.h>
#include <windows.h>
/*定義宏*/
#define TotalMemSize 1024 /*劃分的物理塊的大小，地址范圍0~1023*/
#define MinSize 2 /*規定的不再分割的剩餘分區的大小*/
#define getpch(type) (type*)malloc(sizeof(type))
/*定義內存塊*/
typedef struct memBlock
{
struct memBlock *next;/*指向下一個塊*/
int stAddr; /*分區塊的初始地址*/
int memSize; /*分區塊的大小*/
int status; /*分區塊的狀態，0：空閑，1：以被分配*/
}MMB;
/*定義全局變數*/
MMB *idleHead=NULL; /*空閑分區鏈表的頭指針*/
MMB *usedHead=NULL; /*分配分區鏈表的頭指針*/
MMB *usedRear=NULL; /*分配分區鏈表的鏈尾指針*/
MMB *np; /*循環首次適應演算法中指向即將被查詢的空閑塊*/
int idleNum=1;/*當前空閑分區的數目*/
int usedNum=0;/*當前已分配分區的數目*/
MMB *memIdle=NULL; /*指向將要插入分配分區鏈表的空閑分區*/
MMB *memUsed=NULL; /*指向將要插入空閑分區鏈表的已分配分區*/
int flag=1;/*標志分配是否成功，1：成功*/
/*函數聲明*/
void textcolor (int color);/*輸出著色*/
void InitMem();/*初始化函數*/
int GetUseSize(float miu,float sigma); /*獲得請求尺寸*/
MMB *SelectUsedMem(int n);/*選擇待釋放的塊*/
void AddToUsed();/*將申請到的空閑分區加到分配分區鏈表中*/
int RequestMemff(int usize); /*請求分配指定大小的內存,首次適應演算法*/
int RequestMemnf(int usize); /*請求分配指定大小的內存,循環首次適應演算法*/
void AddToIdle();/*將被釋放的分配分區加到空閑分區鏈表中(按地址大小）*/
void ReleaseMem(); /*釋放指定的分配內存塊*/
/*主函數*/
void main()
{
int sim_step;
float miu,sigma; /*使隨機生成的請求尺寸符合正態分布的參數*/
int i;
int a;
MMB *p;
/* double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;
double aveStep=0,aveSize=0,aveRatio=0;
int step=0,usesize=0; */
textcolor(11);
printf("\n\t\t內存管理模擬程序\n\n");
/* InitMem();*/
while(true)
{
double TotalStep=0,TotalSize=0,TotalRatio=0,TotalUSize=0,Ratio=0,n=0;
double aveStep=0,aveSize=0,aveRatio=0;
int step=0,usesize=0;
InitMem();
textcolor(12);
printf("\n\n首次適應演算法： 0");
printf("\n循環首次適應演算法： 1\n");
textcolor(11);
printf("\n請選擇一種演算法：");
scanf("%d",&a);
textcolor(15);
printf("\n輸入一定數量的步數：(sim_step)");
scanf("%d",&sim_step);
printf("\n 輸入使隨機生成的請求尺寸符合正態分布的參數：miu,sigma ");
scanf("%f,%f",&miu,&sigma);
for(i=1;i<=sim_step;i++)
{
textcolor(10);
printf("\n\n#[%d]\n",i);
do{
usesize=GetUseSize(miu,sigma);
while((usesize<0)||(usesize>TotalMemSize))
{
usesize=GetUseSize(miu,sigma);
}
textcolor(13);
printf("\n\n申請的內存尺寸為：%d",usesize);
printf("\n此時可用的空閑分區有 %d 塊情況如下：",idleNum);
p=idleHead;
textcolor(15);
while(p!=NULL)
{
printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
TotalSize+=usesize;
if(a==0)
step=RequestMemff(usesize);
else
step=RequestMemnf(usesize);
TotalStep+=step;
n++;
}while(flag==1);
p=usedHead;
while(p!=NULL)
{
TotalUSize+=p->memSize;
printf("\n始址:%d\t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
textcolor(11);
if(TotalUSize!=0)
{
Ratio=TotalUSize/TotalMemSize;
TotalUSize=0;
printf("\n內存利用率NO.%d :%f%c",i,100*Ratio,'%');
}
else
{
Ratio=0;
printf("\n內存利用率NO.%d :%c%c",i,'0','%');
}
TotalRatio+=Ratio;
ReleaseMem();
}
if(n!=0)
{
textcolor(10);
aveStep=TotalStep/n;
aveSize=TotalSize/n;
aveRatio=TotalRatio/sim_step;
printf("\n平均搜索步驟：%f",aveStep);
printf("\n平均請求尺寸：%f",aveSize);
printf("\n平均內存利用率：%f",aveRatio);
}
}
}
// 輸出著色 /////////////////////////////////////////
void textcolor (int color)
{
SetConsoleTextAttribute (GetStdHandle (STD_OUTPUT_HANDLE), color );
}
/******************************
函數名：InitMem()
用途：把內存初始化為一整塊空閑塊
****************************************/
void InitMem()
{
MMB *p;
p=getpch(MMB);
p->memSize=TotalMemSize;
p->stAddr=0;
p->status=0;
p->next=NULL;
idleHead=p;
np=idleHead;
usedHead=NULL;
usedRear=NULL;
idleNum=1;
usedNum=0;
flag=1;
memIdle=NULL;
memUsed=NULL;
}
/******************************
函數名：GetUseSize(float miu,float sigma)
用途：獲得請求尺寸；
參數說明：float miu,float sigma ：正態分布的參數
返回值:申請尺寸的大小；
****************************************************/
int GetUseSize(float miu,float sigma)
{
float r1,r2;
float u,v,w;
float x,y;
do
{
r1=rand()/32767.0;
r2=rand()/32767.0;
u=2*r1-1;
v=2*r2-1;
w=u*u+v*v;
}while(w>1);
x=u*sqrt(((-log(w))/w));
y=v*sqrt(((-log(w))/w));
return miu+sigma*x;
}
/******************************
函數名：*SelectUsedMem(int n)
用途：選擇待釋放的塊(0~n-1)
返回值：指向待釋放的塊的指針；
****************************************************/
MMB *SelectUsedMem(int n)
{
MMB *p;
int i,j;
if(n>0)
{
i = rand()%n ;
textcolor(5);
printf("\n\n當前已分配分區總數為：%d",n);
printf("\n待釋放塊的序號為：%d\n",i );
p=usedHead;
if(p!=NULL)
{
for(j=i;j>0;j--)
p=p->next;
return(p);
}
else
return(NULL);
}
else
{
printf("\n當前沒有可釋放的資源！\n");
}
}
/******************************
函數名：AddToUsed()
用途：將申請到的空閑分區加到分配分區鏈表中
***************************************************************/
void AddToUsed()
{
MMB *p;
memIdle->status=1;
if(usedHead==NULL)
{
usedHead=memIdle;
usedRear=usedHead;
}
else
{
usedRear->next=memIdle;
usedRear=memIdle;
}
usedNum++;
printf("\n當前分配分區共有%d塊！",usedNum);
p=usedHead;
while(p!=NULL)
{
printf("\n始址:%d \t 尺寸：%d",p->stAddr,p->memSize);
p=p->next;
}
}
/******************************
函數名：RequestMemff(int usize)
參數說明：usize：請求尺寸的大小；
用途：請求分配指定大小的內存,首次適應演算法
返回值：搜索步驟
***************************************************************/
int RequestMemff(int usize)
{
MMB *p1,*p2,*s;
int step;
int suc=0;
int size1,size2;
if(idleHead==NULL)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
return 0;
}
else
{
if((idleHead->memSize)>usize)
{
size1=(idleHead->memSize)-usize;
if(size1<=MinSize)
{
memIdle=idleHead;
idleHead=idleHead->next;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=idleHead->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
idleHead->memSize=idleHead->memSize-usize;
idleHead->stAddr=idleHead->stAddr+usize;
}
step=1;
flag=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
}
else
{
p1=idleHead;
step=1;
p2=p1->next;
while(p2!=NULL)
{
if((p2->memSize)>usize)
{
size2=(p2->memSize)-usize;
if(size2<=MinSize)
{
p1->next=p2->next;
memIdle=p2;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=p2->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
p2->memSize=p2->memSize-usize;
p2->stAddr=p2->stAddr+usize;
}
flag=1;
suc=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
p2=NULL;
}
else
{
p1=p1->next;
p2=p2->next;
step++;
}
}
if(suc==0)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
}
}
}
return step;
}
/******************************
函數名：AddToIdle()
用途：將被釋放的分配分區加到空閑分區鏈表中(按地址遞增順序排列）
***************************************************************/
void AddToIdle()
{
MMB *p1,*p2;
int insert=0;
if((idleHead==NULL))
{
idleHead=memUsed;
idleNum++;
np=idleHead;
}
else
{
int Add=(memUsed->stAddr)+(memUsed->memSize);
if((memUsed->stAddr<idleHead->stAddr)&&(Add!=idleHead->stAddr))
{
memUsed->next=idleHead;
idleHead=memUsed;
idleNum++;
}
else
{
if((memUsed->stAddr<idleHead->stAddr)&&(Add==idleHead->stAddr))
{
idleHead->stAddr=memUsed->stAddr;
idleHead->memSize+=memUsed->memSize;
}
else
{
p1=idleHead;
p2=p1->next;
while(p2!=NULL)
{
if(memUsed->stAddr>p2->stAddr)
{
p1=p1->next;
p2=p2->next;
}
else
{
int Add1=p1->stAddr+p1->memSize;
int Add2=p2->stAddr-memUsed->memSize;
if((Add1==memUsed->stAddr)&&(memUsed->stAddr!=Add2))
{
p1->memSize=p1->memSize+memUsed->memSize;
}
if((Add1!=memUsed->stAddr)&&(memUsed->stAddr==Add2))
{
p2->memSize=p2->memSize+memUsed->memSize;
p2->stAddr=memUsed->stAddr;
}
if((Add1!=memUsed->stAddr)&&(memUsed->stAddr!=Add2))
{
memUsed->next=p2;
p1->next=memUsed;
if(np->stAddr==p2->stAddr)
np=p1->next;
idleNum++;
}
if((Add1==memUsed->stAddr)&&(memUsed->stAddr==Add2))
{
p1->memSize=p1->memSize+memUsed->memSize+p2->memSize;
p1->next=p2->next;
if((np->stAddr)==(p2->stAddr))
np=p1;
idleNum--;
}
p2=NULL;
insert=1;
}
}
if(insert==0)
{
p1->next=memUsed;
idleNum++;
}
}
}
}
}
/******************************
函數名：ReleaseMem()
用途：釋放指定的分配內存塊
***************************************************************/
void ReleaseMem()
{
MMB *q1,*q2;
MMB *s;
if(usedNum==0)
{
printf("\n當前沒有分配分區!");
return;
}
else
{
s=SelectUsedMem(usedNum);
if(s!=NULL)
{
if(s->stAddr==usedHead->stAddr)
{
memUsed=usedHead;
usedHead=usedHead->next;
memUsed->next=NULL;
AddToIdle();
usedNum--;
}
else
{
q1=usedHead;
q2=q1->next;
while(q2!=NULL)
{
if(q2->stAddr!=s->stAddr)
{
q1=q1->next;
q2=q2->next;
}
else
{
q1->next=q2->next;
memUsed=q2;
memUsed->next=NULL;
if(q1->next==NULL)
usedRear=q1;
AddToIdle();
usedNum--;
q2=NULL;
}
}
}
}
}
}
/******************************
函數名：RequestMemnf(int usize)
參數說明：usize：請求尺寸的大小；
用途：請求分配指定大小的內存,循環首次適應演算法
返回值：搜索步驟
***************************************************************/
int RequestMemnf(int usize)
{
MMB *p2,*p,*s;
int step;
int iNum=0;
int suc=0;
int size1,size2,size3;
if(idleHead==NULL)
{
flag=0;
printf("\n分配失敗！");
return 0;
}
else
{
iNum=idleNum;
while(iNum>0)
{
iNum--;
if((np->memSize)>usize)
{
/*指針指向的空閑塊滿足條件,且正好為頭指針*/
if(np->stAddr==idleHead->stAddr)
{
size1=(idleHead->memSize)-usize;
if(size1<=MinSize)
{
memIdle=idleHead;
idleHead=idleHead->next;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=idleHead->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
idleHead->memSize=idleHead->memSize-usize;
idleHead->stAddr=idleHead->stAddr+usize;
}
if((idleHead==NULL)||(idleHead->next==NULL))
np=idleHead;
else
np=idleHead->next;
}
else/*指針指向的空閑塊滿足條件,不為頭指針*/
{
size2=(np->memSize)-usize;
if(size2<=MinSize) /*從空閑鏈表中刪除*/
{
p=idleHead;
while(p->next->stAddr!=np->stAddr)
p=p->next;
p->next=np->next;
memIdle=np;
memIdle->next=NULL;
np=p;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=np->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
np->memSize=np->memSize-usize;
np->stAddr=np->stAddr+usize;
}
if(np->next==NULL)
np=idleHead;
else
np=np->next;
}
step=1;
flag=1;
suc=1;
textcolor(12);
printf("\n分配成功！");
AddToUsed();
iNum=0;
}
else /*當前指針指向的空閑區不滿足條件*/
{
step=1;
p2=np->next;
if(p2==NULL)
{
np=idleHead;
iNum--;
}
else
{
if((p2->memSize)>usize)
{
size3=(p2->memSize)-usize;
if(size3<=MinSize)
{
np->next=p2->next;
memIdle=p2;
memIdle->next=NULL;
idleNum--;
}
else
{
s=getpch(MMB);
s->memSize=usize;
s->stAddr=p2->stAddr;
s->status=1;
s->next=NULL;
memIdle=s;
p2->memSize=p2->memSize-usize;
p2->stAddr=p2->stAddr+usize;
}
flag=1;
suc=1;
printf("\n分配成功！");
AddToUsed();
if(p2->next==NULL)
np=idleHead;
else
np=p2->next;
p2=NULL;
iNum=0;
}
else
{
np=np->next;
p2=p2->next;
iNum--;
step++;
}
}
}
// iNum--;
}
if(suc==0)
{
flag=0;
textcolor(12);
printf("\n分配失敗！");
}
}
return step;
}
⑸ 串模式匹配演算法（C語言）100分懸賞
第一個樸素演算法:
1.普通的串模式匹配演算法:
int index(char s[],char t[],int pos)
/*查找並返回模式串T在S中從POS開始的位置下標,若T不是S的子串.則返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分別指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //計算主串和模式串的長度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}
第二個KMP演算法.該演算法支持從主串的任意位置開始搜索.
2.KMP演算法:
//求模式串的next函數.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}
//KMP模式匹配演算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函數,求P在主串S中從第POS個字元開始的位置*/
/*若匹配成功.則返回模式串在主串中的位置下標.否則返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];
⑹ 求kM演算法和匈牙利演算法的程序代碼
//二分圖最佳匹配,kuhn munkras演算法,鄰接陣形式,復雜度O(m*m*n)
//返回最佳匹配值,傳入二分圖大小m,n和鄰接陣mat,表示權值
//match1,match2返回一個最佳匹配,未匹配頂點match值為-1
//一定注意m<=n,否則循環無法終止
//最小權匹配可將權值取相反數
#include <string.h>
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i<m;i++)
for (l1[i]=-inf,j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i<n;l2[i++]=0);
for (_clr(match1),_clr(match2),i=0;i<m;i++){
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j<n;j++)
if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}