Learn Algorithms with
ARDEN
First day
And the Arden learning algorithm, just ARDEN's own algorithm reading notes. Because you are also in the study stage, there is an error inevitable, just hope to give a sharing of friends who want to learn the algorithm, maybe a day, my algorithm is a bit found, I can modify it into a primary tutorial.
At the time of study, Arden's main reference materials is the first two volumes of Robert Sedgewick's "Algorithms IN C". (Volume III, I haven't sent it), the roughly algorithm book is in this order, so I didn't choose the algorithm for the classic Sedgewick teacher Knuth. The main reason is that I didn't see it when I went to the bookstore. this. In addition, the reference is mainly from the search on Google. From what is relatively messy, if you really don't know who you write, please contact me if you see my article for your article. Please contact me. , License or reject my reference.
So I will probably write notes like this one day, then there is an important chapter to spend more time.
That is, when I started to see this reference book, I was hit. Just in this group. A connectivity problem:
Q: An integer pair, where each integer represents some type of object, and the P-Q is explained into "P and Q". It is assumed that the communication is deliverable: if P is connected to the Q, while Q is connected to R, P and R communicate.
Requirements: Write a program, filter additional connection from the collection. This pair is output only when the program enters integers to P-Q, which is only output when the program has been visible at this time.
Still have some data abstraction concept, the discrete mathematics and data structure of the university tell me, this is a chart's connectivity problem, but there is no need, I am going to define a picture structure for it? I haven't said ADT yet, I will say later. First start from scratch.
Think: We need to store all the input to records, new pairs, traverse them and judge.
Here is my initial idea:
1. Save integers to the array IPAIR [M] [N] (the matrix and the map always have a lot of contacts), 1 is connected, 0 is different.
2. Accept the new input pair P-Q, check whether the corresponding position IPAIR [P] [q] is 1, to determine the connectivity.
3, if it is not connected, IPAIR [P] [q] = 1.
Self feeling is feasible, so I turned to see Sedgewick's suggestion:
This sentence gives me a blow: No simple method can immediately determine if the two objects are connected according to all connected sets, even if we save them all. What do you mean? Is the time complexity of the time complexity? Is it wrong? I have enough extravagant use of N ^ 2 for input N to improve efficiency.
Whether, look at the procedures he gives:
>> Equipment - Quick-Find Algorithm:
/ * File name qufd.c
This algorithm is based on one-dimensional array ID [N], this array has the following properties: when and only when the first and the number of numbers are equal, P and Q are connected. The i-th number group is initialized to i, of which 0
* /
#include #define n 10000 Main () { INT i, T, P, Q, ID [N]; for (i = 0; i While (Scanf ("% D% D / N", & P, & Q) == 2) { IF (id [p] == id [q]) continued; For (t = id [p], i = 0; i IF (ID [i] == t) ID [i] == id [q]; Printf ("% D% D / N", & P, & Q); } } Then not addiction, but also give a quick and set, fast and aggressive, and some methods such as biling compression. Then I was on the time, do I still see this book? What is the so embarrassing of the stomach? Fortunately, I will adhere to it, the more I get more and more. The practice of learning C can be traced back to the university era, but my C language level is completely seen in Baobao's code and learning Socket, the Java level is more generally to the symptom. Still playing CPP, rewriting this program according to your own understanding (C and CPP basically don't have a big difference): #include Using namespace std; Const int N = 10; void main () { INT I, P, Q, T, D [N]; For (i = 0; i While (CIN >> P >> Q) { IF (d [p] == d [q]) Continue; For (i = 0, t = d [p]; i { IF (t == d [i]) d [i] = d [q]; } Cout << p << "" << q << Endl; } } Today's main purpose is to identify, we don't go deeply, the following will understand the following procedures: Let's talk about this sentence first: The algorithm is based on a certain object. Like not like a fart? I also want to see it. But it is true that you look at the above program, the most basic implementation is actually that ID [i]. The problem is completely solved by the relationship between I and ID [i]. In the future, it always emphasizes the importance of the data structure. On the one hand, the data structure determines the use of the algorithm. In a specific data structure, some algorithms are unable! The program has begun to define an id [n] and initialize it: for (...) id [i] = i; after understanding this sentence, you understand this program. No one in the beginning, we will connect, let each ID [i] and it connect themselves. Then we enter P, Q; After receiving the input pair, id [n] is traversed. Locate the position ID [Q] equal to Q to see if its value is less, give T. The location of all the arrays in the group will be replaced by Q. why? P-Q is now connected, this is a data abstraction of the transfer. It should now be understood, it doesn't matter if it doesn't matter, I have understood it on both sides, you can't do it. For example, a N is 10 array we initialize it: 0123456789 Enter an integer pair: 3 4 Program display: 3 4 The array becomes: 0124456789 Enter a 4 5 Program display 4 5 The array becomes: 0125556789 Input 3 5 The program is not displayed, and the 3 and 5 have been connected to the transfer of 3-4 and 4-5, i.e., Id [3] == ID [5]. End the first day of learning, we have a long way to go, first is the data structure, then see sorting and searching.
