问题1：马尔科夫（HMM）的特征是什么？
问题2：有两个有序整数集合a和b，写一个函数找出它们的交集？
题目的意思应该是这样的，第一道题不会做，第二道题直接写不算难，我觉得应该是考写出比较高效的算法
大家帮忙回答。
------解决方案--------------------
- Java code
import java.util.Arrays;public class Test { public static void main(String args[]){ int[] b = {4, 6, 7, 7, 7, 7, 8, 8, 9, 10, 100, 130, 130, 140, 150}; int[] a = {2, 3, 4, 4, 4, 4, 7, 8, 8, 8, 8, 9, 100, 130, 150, 160}; int[] c = intersect(a, b); System.out.println(Arrays.toString(c)); } public static int[] intersect(int[] a, int[] b) { if(a[0] > b[b.length - 1] || b[0] > a[a.length - 1]) { return new int[0]; } int[] intersection = new int[Math.max(a.length, b.length)]; int offset = 0; for(int i = 0, s = i; i < a.length && s < b.length; i++) { while(a[i] > b[s]) { s++; } if(a[i] == b[s]) { intersection[offset++] = b[s++]; } while(i < (a.length - 1) && a[i] == a[i + 1]) { i++; } } if(intersection.length == offset) { return intersection; } int[] duplicate = new int[offset]; System.arraycopy(intersection, 0, duplicate, 0, offset); return duplicate; }}
------解决方案--------------------
[code=Java][/code]
第二道题
import java.util.ArrayList;
public class Compare {
/**假设两个有序整数集合a和b是两个数组。
* @param a 有序整数集合a
* @param b 有序整数集合b
*/
public ArrayList<Integer> compareTwo(int a[],int []b){
ArrayList<Integer> list=new ArrayList<Integer>();
int numOfStart=0;
boolean isEnd=false;
if(a[0]>b[0]){
if(a[0]>b[b.length-1]){
System.out.println("有序整数集合a和b没有交集");
}else{
for(int i=1;i<b.length;i++){
if(a[0]>b[i-1]&&a[0]<=b[i]){
numOfStart=i;
}
}
for(int j=0;j<a.length;j++){
for(int n=numOfStart;n<b.length;n++){
if(a[j]==b[n]){
list.add(a[j]);
numOfStart=n+1;
break;
}
}
}
}
}else if(a[a.length-1]<b[0]){
System.out.println("有序整数集合a和b没有交集");
}else {
for(int i=1;i<a.length;i++){
if(b[0]>a[i-1]&&b[0]<=a[i]){
numOfStart=i;
}
}
for(int j=0;j<b.length;j++){
for(int n=numOfStart;n<a.length;n++){
if(b[j]==a[n]){
list.add(b[j]);
numOfStart=n+1;
break;
}
}
}
}
return list;
}
public static void main(String[] args) {
Compare com=new Compare();
int b[] ={1,2,4,5,7,8,9,10};
int a[]={5,6,7,8,9,10};
ArrayList<Integer> list=com.compareTwo(a, b);
for(Integer in:list)
System.out.print(in+" ");
}
}
------解决方案--------------------
一个隐马尔可夫模型 (HMM) 是一个五元组：
(ΩX , ΩO, A, B, π )
其中：
ΩX = {q1,...qN}：状态的有限集合
ΩO = {v1,...,vM}：观察值的有限集合
A = {aij}，aij = p(Xt+1 = qj |Xt = qi)：转移概率
B = {bik}，bik = p(Ot = vk | Xt = qi)：输出概率
π = {πi}， πi = p(X1 = qi)：初始状态分布
2 解决问题：
令 λ = {A,B,π} 为给定HMM的参数，
令 σ = O1,...,OT 为观察值序列，
隐马尔可夫模型（HMM）的三个基本问题：
2.1评估问题：对于给定模型，求某个观察值序列的概率p(σ|λ) ；
2.2解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；
2.3学习问题：对于给定的一个观察值序列，调整参数λ，使得观察值出现的概率p(σ|λ)最大
------解决方案--------------------