某车企笔试题解答（1）

目录

题目：

答：

1建立数学模型

2求解

---

题目：

一个简易吃豆人游戏，假设有一个m*n的棋盘（0

答：

解答本题分如下两步：1建立数学模型；2求解。

1建立数学模型

将这个m*n的棋盘（左图）抽象为图论中的有向无环图（缩写为DAG，右图）。

棋盘中的每个格子对应有向无环图的一个顶点，指向该顶点的边的权重等于该顶点的豆子数（比如，指向棋盘格子b的边，权重等于b，以此类推）。由于吃豆人只能向右或者向下移动，所以水平方向的边只能从左向右，垂直方向的边只能从上到下，如上图所示。由于这个限制，导致从任何一点出发，不论采取何种路径，都不会回到出发点，所以这个图是无环图。

由于棋盘中的每个格子对应有向无环图的一个顶点，所以有向无环图的水平方向的顶点数等于棋盘水平方向的格子数m，而水平方向的边数比顶点数少1，所以是m-1；有向无环图的垂直方向的顶点数等于棋盘垂直方向的格子数n，所以有向无环图的垂直方向的顶点数是n,垂直方向的边数是n-1。顶点总数为m*n。而边总数为(m-1)*(n-1)。

搜索吃豆人吃豆最多路线的问题就变成了搜索DAG最长路径的问题。此类问题的复杂度是O(边数+顶点数),故为O(m*n)

2求解

Longest Path in a Directed Acyclic Graph - GeeksforGeeks提供了示例代码解决此类问题。在此示例基础上略作修改，考虑如下棋盘，其格子中的数字代表格子内豆子数目：

 

根据前面的分析，数学模型对应一个顶点数为4 * 3= 12的DAG。

采用如下代码求解：

// A C++ program to find single source longest distances
 
// in a DAG
 
#include 
 
#include 
 
#include 
 
#include 
 
#define NINF INT_MIN
 
using namespace std;
 
 
 
// Graph is represented using adjacency list. Every
 
// node of adjacency list contains vertex number of
 
// the vertex to which edge connects. It also
 
// contains weight of the edge
 
class AdjListNode {
 
    int v;
 
    int weight;
 
 
 
public:
 
    AdjListNode(int _v, int _w)
 
    {
 
        v = _v;
 
        weight = _w;
 
    }
 
    int getV() { return v; }
 
    int getWeight() { return weight; }
 
};
 
 
 
// Class to represent a graph using adjacency list
 
// representation
 
class Graph {
 
    int V; // No. of vertices'
 
 
 
    // Pointer to an array containing adjacency lists
 
    list* adj;
 
    list<int>        *   pPath;
 
 
 
    // A function used by longestPath
 
    void topologicalSortUtil(int v, bool visited[],
        stack<int>& Stack);
 
 
 
public:
 
    Graph(int V); // Constructor
 
    ~Graph(); // Destructor
 
 
 
    // function to add an edge to graph
 
    void addEdge(int u, int v, int weight);
 
 
 
    // Finds longest distances from given source vertex
 
    void longestPath(int s);
 
};
 
 
 
Graph::Graph(int V) // Constructor
 
{
 
    this->V = V;
 
    adj = new list[V];
 
    pPath = new list<int>[V];
 
}
 
 
 
Graph::~Graph() // Destructor
 
{
 
    delete[] adj;
 
    delete[] pPath;
 
}
 
 
 
 
 
void Graph::addEdge(int u, int v, int weight)
 
{
 
    AdjListNode node(v, weight);
 
    adj[u].push_back(node); // Add v to u's list
 
}
 
 
 
// A recursive function used by longestPath. See below
 
// link for details
 
// https:// www.geeksforgeeks.org/topological-sorting/
 
void Graph::topologicalSortUtil(int v, bool visited[],
    stack<int>& Stack)
 
{
 
    // Mark the current node as visited
 
    visited[v] = true;
 
 
 
    // Recur for all the vertices adjacent to this vertex
 
    list::iterator i;
 
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
 
        AdjListNode node = *i;
 
        if (!visited[node.getV()])
 
             topologicalSortUtil(node.getV(), visited, Stack);
 
    }
 
 
 
    // Push current vertex to stack which stores topological
 
    // sort
 
    Stack.push(v);
 
}
 
 
 
// The function to find longest distances from a given vertex.
 
// It uses recursive topologicalSortUtil() to get topological
 
// sorting.
 
void Graph::longestPath(int s)
 
{
 
    stack<int> Stack;
 
    int * dist = new int[V];
 
 
 
    // Mark all the vertices as not visited
 
    bool* visited = new bool[V];
 
    for (int i = 0; i < V; i++)
 
        visited[i] = false;
 
 
 
    // Call the recursive helper function to store Topological
 
    // Sort starting from all vertices one by one
 
    for (int i = 0; i < V; i++)
 
        if (visited[i] == false)
 
             topologicalSortUtil(i, visited, Stack);
 
 
 
    // Initialize distances to all vertices as infinite and
 
    // distance to source as 0
 
    for (int i = 0; i < V; i++)
 
    {
 
        pPath[s].clear();
 
        dist[i] = NINF;
 
    }
 
       
 
    dist[s] = 0;
 
    pPath[s].push_back(s);
 
 
 
    // Process vertices in topological order
 
    while (Stack.empty() == false) {
 
        // Get the next vertex from topological order
 
        int u = Stack.top();
 
        Stack.pop();
 
 
 
        // Update distances of all adjacent vertices
 
        list::iterator i;
 
        if (dist[u] != NINF) {
 
             for (i = adj[u].begin(); i != adj[u].end(); ++i)
 
             {
 
                 if (dist[i->getV()] < dist[u] + i->getWeight())
 
                 {
 
                     //更新与u相连的各个顶点到s的距离
 
                     dist[i->getV()] = dist[u] + i->getWeight();
 
                     //更新具体路径
 
                     pPath[i->getV()].assign(pPath[u].begin(), pPath[u].end());
 
                     pPath[i->getV()].push_back(i->getV());
 
                 }  
 
             }
 
        }
 
    }
 
 
 
    // Print the calculated longest distances
 
    for (int i = 0; i < V; i++)
 
    {
 
        cout << "length: ";
 
        (dist[i] == NINF) ? cout << "unReachable" : cout << dist[i];
 
        cout<< endl;
 
        cout << "path: ";
 
        for (const auto & item : pPath[i])
 
        {
 
             cout << item << " ";
 
        }
 
        cout << endl;
 
    }
 
       
 
 
 
    delete [] visited;
 
    delete [] dist;
 
    delete [] pPath;
 
}
 
 
 
// Driver program to test above functions
 
int main()
 
{
 
    // Create a graph given in the above diagram.
 
 
 
    Graph g(12);
 
    g.addEdge(0, 1, 1);
 
    g.addEdge(0, 4, 3);
 
    g.addEdge(1, 2, 2);
 
    g.addEdge(1, 5, 5);
 
    g.addEdge(2, 3, 4);
 
    g.addEdge(2, 6, 1);
 
    //g.addEdge(3, 4, 0);//3号顶点处于棋盘最右
 
    g.addEdge(3, 7, 2);
 
 
 
    g.addEdge(4, 5, 5);
 
    g.addEdge(4, 8, 1);
 
    g.addEdge(5, 6, 1);
 
    g.addEdge(5, 9, 1);
 
    g.addEdge(6, 7, 2);
 
    g.addEdge(6, 10, 3);
 
    //g.addEdge(7, 8, 0);//7号顶点处于棋盘最右，不能再向右了
 
    g.addEdge(7, 11, 2);
 
 
 
    g.addEdge(8, 9, 1);
 
    //g.addEdge(8, 8, 1);
 
    g.addEdge(9, 10, 3);
 
    //g.addEdge(9, 9, 1);
 
    g.addEdge(10, 11, 2);
 
    //g.addEdge(10, 10, 3);
 
    //g.addEdge(11, 8, 0);//11号顶点处于棋盘最右，不能再向右了
 
    //g.addEdge(11, 11, 2); //11号顶点处于棋盘最下
 
 
 
    int s = 0;
 
    cout << "Following are longest distances from "
 
        "source vertex "
 
        << s << " \n";
 
    g.longestPath(s);
 
    cin.get();
 
 
 
    return 0;
 
}

在上面的问题中，采用0-11标记棋盘的格子：

 

结果：

可见，最长路径是0-4-5-9-10-11，长度为14

 

算法的时间复杂度为O(顶点数+边数)。这里也就是O(m*n)