5。
G. 右圖是一個演算法的流程圖，最後輸出的k=______
首先給循環變數k和累加變數S賦值1和0，
判斷0＜20，執行S=0+1=1，k=1+2=3；
判斷1＜20，執行S=1+3=4，k=3+2=5；
判斷4＜20，執行S=4+5=9，k=5+2=7；
判斷9＜20，執行S=9+7=16，K=7+2=9；
判斷16＜20，執行S=16+9=25，k=9+2=11；
判斷25＞20，輸出k的值為11，演算法結束．
故答案為11． |
H. K近鄰演算法的理論基礎
從理論基礎、手寫數字識別演算法、手寫數字識別實例等角度介紹K近鄰演算法。
K近鄰演算法的本質是將指定對象根據已知特徵值分類。
例如，看到一對父子，一般情況下，通過判斷他們的年齡，能夠馬上分辨出哪位是父親，哪位是兒子。這是通過年齡屬性的特徵值來劃分的。
上述例子是最簡單的根據單個特徵維度做的分類，在實際場景中，情況可能更復雜，有多個特徵維度。
例如，為一段運動視頻分類，判斷這段視頻是乒乓球比賽還是足球比賽。
為了確定分類，需要定義特徵。這里定義兩個特徵，一個是運動員「揮手」的動作，另一個是運動員「踢腳」的動作。當然，我們不能一看到「揮手」動作就將視頻歸類為「乒乓球比賽」，因為我們知道某些足球運動員習慣在運動場上通過揮手來跟隊友進行交流。同樣，我們也不能一看到「踢腳」動作就將視頻歸類為「足球比賽」，因為有些乒乓球運動員會通過「踢腳」動作來表達自己的感情。
我們分別統計在某段特定時間內，視頻中「揮手」和「踢腳」動作的次數，發現如下規律：
● 在乒乓球比賽的視頻中，「揮手」的次數遠多於「踢腳」的次數。
● 在足球比賽的視頻中，「踢腳」的次數遠多於「揮手」的次數。
根據對一組視頻的分析，得到如表20-1所示的數據。
為了方便觀察，將上述數據繪制為散點圖，如圖20-1所示。
從圖20-1中可以看到，數據點呈現聚集特徵：
● 乒乓球比賽視頻中的數據點聚集在x軸坐標為[3000, 5000], y軸坐標為[1,500]的區域。
● 足球比賽視頻中的數據點聚集在y軸坐標為[3000, 5000], x軸坐標為[1,500]的區域。
此時，有一個視頻Test，經過統計得知其中出現2000次「揮手」動作，100次「踢腳」動作。如果在圖20-1中標注其位置，可以發現視頻Test的位置最近的鄰居是乒乓球比賽視頻，因此可判斷該視頻是乒乓球比賽視頻。
上面的例子是一個比較極端的例子，非黑即白，而實際的分類數據中往往參數非常多，判斷起來也不會如此簡單。因此，為了提高演算法的可靠性，在實施時會取k個近鄰點，這k個點中屬於哪一類的較多，然後將當前待識別點劃分為哪一類。為了方便判斷，k值通常取奇數，這和為了能得到明確的投票結果通常將董事會成員安排為奇數的道理是一樣的。
例如，已知某知名雙胞胎藝人A和B長得很像，如果要判斷一張圖像T上的人物到底是藝人A還是藝人B，則採用K近鄰演算法實現的具體步驟如下：
以上所述就是K近鄰演算法的基本思想。
I. 農夫過河的圖演算法
#include<iostream>
using namespace std;
#define VertexNum 16 //最大頂點數
typedef struct // 圖的頂點
{
int farmer; // 農夫
int wolf; // 狼
int sheep; // 羊
int veget; // 白菜
}Vertex;
typedef struct
{
int vertexNum; // 圖的當前頂點數
Vertex vertex[VertexNum]; // 頂點向量（代表頂點）
bool Edge[VertexNum][VertexNum]; // 鄰接矩陣. 用於存儲圖中的邊，其矩陣元素個數取決於頂點個數，與邊數無關
}AdjGraph; // 定義圖的鄰接矩陣存儲結構
bool visited[VertexNum] = {false}; // 對已訪問的頂點進行標記（圖的遍歷）
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路徑，即與某頂點到下一頂點的路徑
// 查找頂點（F，W，S，V）在頂點向量中的位置
int locate(AdjGraph *graph, int farmer, int wolf, int sheep, int veget)
{
// 從0開始查找
for (int i = 0; i < graph->vertexNum; i++)
{
if ( graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf
&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget )
{
return i; //返回當前位置
}
}
return -1; //沒有找到此頂點
}
// 判斷目前的（F，W，S，V）是否安全
bool isSafe(int farmer, int wolf, int sheep, int veget)
{
//當農夫與羊不在一起時，狼與羊或羊與白菜在一起是不安全的
if ( farmer != sheep && (wolf == sheep || sheep == veget) )
{
return false;
}
else
{
return true; // 安全返回true
}
}
// 判斷狀態i與狀態j之間是否可轉換
bool isConnect(AdjGraph *graph, int i, int j)
{
int k = 0;
if (graph->vertex[i].wolf != graph->vertex[j].wolf)
{
k++;
}
if (graph->vertex[i].sheep != graph->vertex[j].sheep)
{
k++;
}
if (graph->vertex[i].veget != graph->vertex[j].veget)
{
k++;
}
// 以上三個條件不同時滿足兩個且農夫狀態改變時，返回真, 也即農夫每次只能帶一件東西過橋
if (graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1)
{
return true;
}
else
{
return false;
}
}
// 創建連接圖
void CreateG(AdjGraph *graph)
{
int i = 0;
int j = 0;
// 生成所有安全的圖的頂點
for (int farmer = 0; farmer <= 1; farmer++)
{
for (int wolf = 0; wolf <= 1; wolf++)
{
for (int sheep = 0; sheep <= 1; sheep++)
{
for (int veget = 0; veget <= 1; veget++)
{
if (isSafe(farmer, wolf, sheep, veget))
{
graph->vertex[i].farmer = farmer;
graph->vertex[i].wolf = wolf;
graph->vertex[i].sheep = sheep;
graph->vertex[i].veget = veget;
i++;
}
}
}
}
}
// 鄰接矩陣初始化即建立鄰接矩陣
graph->vertexNum = i;
for (i = 0; i < graph->vertexNum; i++)
{
for (j = 0; j < graph->vertexNum; j++)
{
// 狀態i與狀態j之間可轉化，初始化為1，否則為0
if (isConnect(graph, i, j))
{
graph->Edge[i][j] = graph->Edge[j][i] = true;
}
else
{
graph->Edge[i][j] = graph->Edge[j][i] = false;
}
}
}
return;
}
// 判斷在河的那一邊
char* judgement(int state)
{
return ( (0 == state) ? "左岸" : "右岸" );
}
// 輸出從u到v的簡單路徑，即頂點序列中不重復出現的路徑
void printPath(AdjGraph *graph, int start, int end)
{
int i = start;
cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl;
while (i != end)
{
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
i = retPath[i];
}
cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf)
<< ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")";
cout << endl;
}
// 深度優先搜索從u到v的簡單路徑 //DFS--Depth First Search
void dfsPath(AdjGraph *graph, int start, int end)
{
int i = 0;
visited[start] = true; //標記已訪問過的頂點
if (start == end)
{
return ;
}
for (i = 0; i < graph->vertexNum; i++)
{
if (graph->Edge[start][i] && !visited[i])
{
retPath[start] = i;
dfsPath(graph, i, end);
}
}
}
int main()
{
AdjGraph graph;
CreateG(&graph);
int start = locate(&graph, 0, 0, 0, 0);
int end = locate(&graph, 1, 1, 1, 1);
dfsPath(&graph, start, end);
if (visited[end]) // 有結果
{
printPath(&graph, start, end);
return 0;
}
return -1;
}
