Slowing down is exactly what is needed to go fast! The careful, thoughtful and verified work leads to higher quality.
– James Grenning, "Test Driven Development for Embedded C"
The greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum.
Please see details of the greedy algorithm on wikipedia.
Coins problem in "Problem contest challenge book" is an example of a greedy algorithm. The point is that you use the largest amount of coin preferentially.
---
Problem:
You have coins as bellow.
A number of 1 yen coin is C1
A number of 5 yen coin is C5
A number of 10 yen coin is C10
A number of 50 yen coin is C50
A number of 100 yen coin is C100
A number of 500 yen coins is C500
You want to pay A yen with the minimum number of coins. How many coins do you have to pay? There is at least one solution for this.
You can use the breadth-first search to process every state like the depth-first search.
When you want to search the shortest path for search space like a maze, the breadth-first search is a good solution for you because you have to search the same state so many times with the depth first-search.
The breadth-first search has a weak point. It needs memory that is proportional to a number of state.
This is an example of the breadth-first search:
- Description
You have a maze which size is M * N. The maze consists of path and wall.
You can move 4 direction (up, down, right and left) in one turn.
Solve the shortest path from the start to the goal.
#include
#include
#include
using namespace std;
const int INF = 1000000;
const int MAX_N = 100;
const int MAX_M = 100;
typedef pair P;
char maze[MAX_N][MAX_M+1]; // maze
int n, m; // size of maze
int sx, sy; // start position
int gx, gy; // goal position
//shortest path for each point
int d[MAX_N][MAX_M];
//vector for for moving direction
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
//solve the shortest path from (sx, sy) to (gx, gy)
int bfs() {
queue
q;
//initialize every point with INF before search
for(int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
d[i][j] = INF;
}
}
q.push(P(sx,sy));
d[sx][sy] = 0;
while(q.size()) {
P tmp = q.front();
q.pop();
//if you find goal then you finish search
if ((tmp.first == gx)&&(tmp.second == gy)){
break;
}
for(int i = 0; i < 4; i++) {
int nx = tmp.first + dx[i];
int ny = tmp.second + dy[i];
if ((0 <= nx) && (nx < n) &&
(0 <= ny) && (ny < m) &&
(maze[nx][ny] != '#') &&
(d[nx][ny] == INF)) {
// if d[nx][ny] == INF then it is a position that
// you have already visited.
q.push(P(nx,ny));
d[nx][ny] = d[tmp.first][tmp.second] + 1;
}
}
}
return d[gx][gy];
}
void solve() {
int res = bfs();
cout << res << endl;
}
int main(int argc, char* argv[]) {
if (argc != 2) {
cout << "./a.out ";
return 1;
}
ifstream ifs(argv[1]);
if (!ifs) {
cout << "can't open file:" << argv[1] << endl;
return 1;
}
string buf;
getline(ifs, buf);
sscanf(buf.c_str(), "%d %d", &n, &m);
for(int i = 0; i < n; i++) {
getline(ifs, buf);
for (int j = 0; j < m; j++) {
maze[i][j] = buf[j];
if (maze[i][j] == 'S') {
sx = i;
sy = j;
}
if (maze[i][j] == 'G') {
gx = i;
gy = j;
}
}
}
solve();
return 0;
}
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.
Output
* Line 1: The number of ponds in Farmer John's field.
I found below error when I compiling C++ program with g++:
declaration of "XXX" shadows a parameter
Acording to the forum in cprogramming.com, which titile is "declaration of "blah" shadows a parameter??", you see this when you make derived class and don't initialize it with a constructor initialization list.
While I was attempting to use the repo init command for downloading Android source code, it threw an error about importing the readline module like this:
Traceback (most recent call last):
File "/Users/xxx/bin/repo", line 91, in <module> import readline
ImportError: No module named readline
I found the same problem on Issue 1032 of Android open source project.
This happend because the python readline module was not included as part of OSX. To fix this problem, you have to install the python readline module.
sudo port install py25-readline
If you are using Python that is contained in OSX, you have to change it to MacPort's Python.
sudo port select python python25
I am using Mac OS X as a UNIX with better UI. I like Mac OS BUT Mac OS X has a lot of problem for programming environment as I mentioned before ><
When I was compiling my Android app, I couldn't do it. I found this message in Problem view.
Error generating final archive: Debug certificate expired on XXX
I found same problem in android web site. According to the site, the Android build tools local debug key but it is already expired. To fix this problem, I had to regenerate my debug key.
Here is the step.
delete the debug keystore/key already generated by the Android build tools. Specifically, delete the debug.keystore file. On Linux/Mac OSX, the file is stored in~/.android. On Windows XP, the file is stored in C:\Documents and Settings\<user>\.android. On Windows Vista, the file is stored in C:\Users\<user>\.android
generate new debug keysore file with this command: keytool -genkey -v -keystore <PATH_TO_FILE>/debug.keystore -alias androiddebugkey -keyalg RSA -validity 10000 -dname "CN=Android Debug,O=Android,C=US"
Note: <PATH_TO_FILE> is a path to the debug keystore file. Please set appropriate path for your environment.
