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分钟
Answer
The answer is slow by exia.huang. If there are any problem, please tell me. Thank you.
問題１
\[a_n = a_0 + \sum_{i=0}^nx_n\]問題2
\[max\{a_n\} = a_0 + n \\ min\{a_n\} = a_0 - n\]問題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年，意大利数学家
1
2
3
4
function fib（n）
if n = 0 or n = 1
return n
return fib(n − 1) + fib（n − 2）
Knapsack problem
Floyd–Warshall algorithm
Dijkstra’s algorithm
Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph
