class Solution {
public:
/**
* @param n: the number of disks
* @return: the order of moves
*/
vector<string> towerHelper(int n, string from, string to){
vector<string> steps;
if (n==0){
return steps;
}
else{
// find the intermediate bottom...
string intermediate;
if (from != "A" && to != "A"){
intermediate = "A";
}
else if (from != "B" && to != "B"){
intermediate = "B";
}
else {
intermediate = "C";
}
// recursively get the first set of operations : move the small plates to intermediate
vector<string> first;
first = towerHelper(n-1, from, intermediate); //
// action at this level: move the biggest plate from "from" to "to"
first.push_back("from " + from + " to " + to);
// recursively get the last set of operations : move the small plates to destination
vector<string> last;
last = towerHelper(n-1, intermediate, to);
// append operations together
first.insert(first.end(), last.begin(), last.end());
return first;
}
}
vector<string> towerOfHanoi(int n) {
// write your code here
vector<string> v = towerHelper(n, "A", "C");
return v;
}
};
Base case: n = 0. Do nothing.
Recursion:
- The function should take into : n, from, to
- If we want to know Hanoi(n, A, C)
- Suppose we know Hanoi(n, A, B) --- this is going to be complete the same except for string specifics
- We first call Hanoi(n-1, A, B). This puts all plates smaller than n from A to B.
- We then print "from A to C" so that the last plate is on C.
- We then call Hanoi(n-1, B, C) and puts all plates smaller than n from B to c.
ummm...
Recursion:
- The function should take into : n, from, to
- If we want to know Hanoi(n, A, C)
- Suppose we know Hanoi(n, A, B) --- this is going to be complete the same except for string specifics
- We first call Hanoi(n-1, A, B). This puts all plates smaller than n from A to B.
- We then print "from A to C" so that the last plate is on C.
- We then call Hanoi(n-1, B, C) and puts all plates smaller than n from B to c.
ummm...
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.