→ trashprince:話說這裡只有期中的十頁 期末十頁還有 07/18 10:38
噓 hi5705:未看先噓 07/18 11:06
→ flarecutter:end*1000 07/18 11:36
→ jjformosa:你放這種東西在這裡到底想幹麻= = 07/18 16:33
大家幫看一下
這是繼蔡胖之後 最為驚人的史前遺物
絕對和程設無關 想要和笨笨助教一樣傻傻看完的
絕對歡迎喔`
Preface & History
We human beings used to figure out the shortcut, the easiest way to solve the
problems. That is, along task resolving, we analysis the original point, then
separated them by parts. It is called,” Top down design”, between
programmers.
This time, the class was handed out two special topics, "SUDOKU" and
"To find the longest circuit, with there is no equal numbers meets.” or, in
short, the “Path in a matrix.”
As a hardworking student, we take the last topic at once, without denying.
In our point of view, the fastest way to get better is to face the task, to
announce declaration of war to the task. To fight it, defeat it, therefore,
the basket of knowledge will be filled with the sweet fruits of victory.
Hence, we start up to analysis the problem and get ready for separate it by
parts. To conquer the topic, we shall not scare, to obtain the highest goal,
we shall dare.
Let’s take a look at the program. Well, we can figure out that the simply
way to find the longest circuit is to detect the errors. Rumor has it that we
can use stacks to simplify the code. Along week’s discussion, we attempt to
compose miscellaneous thoughts, to conclude various minds. Finally, we decide
to quote the “mouse in maze” problem to our code. Thanks to rapid dorm net,
we quickly grasp the point of it. In a long run, the code writing work starts.
The first topic: Hamiltonian path
In the mathematical field of graph theory, a “Hamiltonian path” is a path
in an undirected graph which visits each vertex exactly once. A Hamiltonian
cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits
each vertex exactly once and also returns to the starting vertex. It provides
two points to our group.
First, it is say to be” visits each vertex exactly once”. In case study, we
had found that each number would meet itself exactly once. Thus, the way to
find the” longest circuit which that two equal numbers never meet each other
at the time.” was form by a typical statue, which Hamiltonian path
supported.
Preface & History
We human beings used to figure out the shortcut, the easiest way to solve the
problems. That is, along task resolving, we analysis the original point, then
separated them by parts. It is called,” Top down design”, between
programmers.
This time, the class was handed out two special topics, "SUDOKU" and
"To find the longest circuit, with there is no equal numbers meets.” or, in
short, the “Path in a matrix.”
As a hardworking student, we take the last topic at once, without denying.
In our point of view, the fastest way to get better is to face the task, to
announce declaration of war to the task. To fight it, defeat it, therefore,
the basket of knowledge will be filled with the sweet fruits of victory.
Hence, we start up to analysis the problem and get ready for separate it by
parts. To conquer the topic, we shall not scare, to obtain the highest goal,
we shall dare.
Let’s take a look at the program. Well, we can figure out that the simply
way to find the longest circuit is to detect the errors. Rumor has it that we
can use stacks to simplify the code. Along week’s discussion, we attempt to
compose miscellaneous thoughts, to conclude various minds. Finally, we decide
to quote the “mouse in maze” problem to our code. Thanks to rapid dorm net,
we quickly grasp the point of it. In a long run, the code writing work starts.
The first topic: Hamiltonian path
In the mathematical field of graph theory, a “Hamiltonian path” is a path
in an undirected graph which visits each vertex exactly once. A Hamiltonian
cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits
each vertex exactly once and also returns to the starting vertex. It provides
two points to our group.
First, it is say to be” visits each vertex exactly once”. In case study, we
had found that each number would meet itself exactly once. Thus, the way to
find the” longest circuit which that two equal numbers never meet each other
at the time.” was form by a typical statue, which Hamiltonian path
supported.
Problem solving
To compose our project, we must insert these concepts, and raise up the
issues and questions.
a. Trying wrong ways
In this section, we have to determine the way we differentiate the wrong way
from the right way. The method we choose to store the elements, the type we
use to store the movements. To rewrite the numbers that had been passed
through, what kind of tool should we take for storing the original number?
How to put them back to the former position?
b. Testing errors
We could have the numbers we had passed through become a block, that the
mouse would take another way following the shortest path.
It seems to be the simply way to blank those blocks which haven’t be passed
through, to filled those over paced with “Walls”, and, simultaneously, “
walled” their equal numbers. Thus, the problem would be simplified to the
common work, the well known one, the “Mouse in the Maze” in 4 directions.
c. The shortcut
If longest path exist, there must be a shortcut. Despite the fact that it
takes lots time to inverse the shortcut, we gathered as many theorem as we
could, build up our back stands step by step. The famous theorem about
finding shortcut must be the familiar one to the students, traceable path,
or, in another form, the Hamiltonian path.
Besides, the Euclidean shortest path would do our great favor while solving
the problems.
On one hand, we follow the tips, moving our mouse, the object that walks
through each number, cell by cell. On the other hand, we might be confused
about how to record the path it had taken, how to show the details to the
screen, how to inverse the final result to correct our answer. However, many
of these problems would be discuss in detail.
d. Others
How to input data of the matrix?
How to check them row by row, or column by column?
How to trace the path the target had been move?
How can we do to avoid bugs?
And, additionally, how to speed up the program?
Data requirement
A simple matrix with random numbers
Many include by *.TXT files?
Arrays to store the information
The storage of path for comparison
Define
MAX_SIZE_X 9
MAX_SIZE_Y 9
MAX_SRORAGE 64
Variables
Global Variable:
Int start_I, start_J: the start point(1,1)
Int endI, endJ: the end point(when every out port were rounded by walls)
Local Variable:
Int i, j, m, n: in use of FOR LOOP
Int equivalent: a set of numbers that had been passed through
Matrices
maze[MAX_SIZE_X][ MAX_SIZE_Y]:
from the stage we start this program
pace[MAX_SIZE_X][ MAX_SIZE_Y]
store x & y that we had passed through currently
Sub programs
Void Visit (int i, int j):
Display the path one by one, or just run them each other?
The usage of recursion (for detecting errors)
if(maze[i][j+1] == eqt) visit(i, j+1);
if(maze[i+1][j] == eqt) visit(i+1, j);
if(maze[i][j-1] == eqt) visit(i, j-1);
if(maze[i-1][j] == eqt) visit(i-1, j);
Structure define
Typedefine struct{
int val;
Int vert;
Int hori;
} path_t
path_t passed_by[MAX_SRORAGE]
Analysis & Design
We chop the program into parts as follow:
1. Insert the map with numbers in matrix form
Open file and read the matrix store in *.DAT or *.TXT.
Or burn them down as the inner assuming.
2. Produce the walls around the matrix or what other else?
Place the numbers to there site, and build up the walls around the maze, by
turning walls to the number “0”.
Or build them before inserting
3. Graph the matrix
Graph the whole matrix again, filled “0’s” with block.
Show up the very details of the maze
4. Target set. The pick up of original point
Set up from the first vertex, then test them one another.
5. Target’s pace. Record the path it have taken
Store every step it takes to “pace”
Array to array
6. Mark the numbers and their equivalents that have been passed through.
Store the numbers and their vertical and horizontal position to path, store
them in
Path.val, Path.vert, Path.hori.
7. Use sub program to find each path
Call function, Visit (), to search for the circuit.
8. The usage of recursion (for detecting errors)
Applied in Visit ()
9. compare each pace, determine the longest one
Use the information stored in the array, “passed_by”, which defined as
10. display the result
========================================================================
很聰明直接end的送批幣1塊
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.113.132.153