one examination questions from Tokyo Institute of Technology

Posted by ExiaHuang on September 28, 2018

Overview

  • I will talk about one examination questions from Tokyo Institute of Technology (東京工業大学) OA exam.
  • Extra Analysis : About Floyd, DP( Dynamic programming)

試験問題

Tokyo Institute of Technology (東京工業大学) OA exam 这题来自今年东京工业大学AO考试的机械学科

**Please answer this question in 60 minutes. **

本题答题时间为60分钟

img

img

img

Answer

The answer is slow by exia.huang. If there are any problem, please tell me. Thank you.

問題1

問題2

問題3

x1 x2 f(x1, x2)
0 0 8
0 -1 6
0 1 14
1 0 19
1 -1 15
1 1 27
-1 0 3
-1 -1 3
-1 1 7

obviously, the answer is (-1, 0) or (-1, -1)

問題4

Extra Analysis

Dynamic programming

动态规划

动态规划的本质,是对问题状态的定义和状态转移方程的定义。

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

Fibonacci polynomial

斐波那契数列

斐波那契 ,1175年-1250年,意大利数学家

1539010082295

1
2
3
4
   function fib(n)
       if n = 0 or n = 1
           return n
       return fib(n − 1) + fib(n − 2)

Knapsack problem

Knapsack problem

1539010978404

Knapsack problem

Floyd–Warshall algorithm

Floyd–Warshall algorithm

1539012147510

1539012157125

Dijkstra’s algorithm

Dijkstra’s algorithm

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph