ACM 马周游解题报告

 

 

 

简单的马周游问题

 

 

 

 
Description
 
在一个5 * 6的棋盘中的某个位置有一只马,如果它走29步正好经过除起点外的其他位置各一次,这样一种走法则称马的周游路线,试设计一个算法,从给定的起点出发,找出它的一条周游路线。
 
为了便于表示一个棋盘,我们按照从上到下,从左到右对棋盘的方格编号,如下所示:
 
1     2     3       4     5     6
 
7     8     9       10    11       12
 
13    14       15    16       17    18
 
19    20       21    22       23    24
 
25    26       27    28       29    30
 
马的走法是“日”字形路线,例如当马在位置15的时候,它可以到达2、4、7、11、19、23、26和28。但是规定马是不能跳出棋盘外的,例如从位置1只能到达9和14。
 
Input
 
输入有若干行。每行一个整数N(1<=N<=30),表示马的起点。最后一行用-1表示结束,不用处理。
 
Output
 
对输入的每一个起点,求一条周游线路。对应地输出一行,有30个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
 
Sample Input
 
4
-1
Sample Output
 
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。
 
 
(1)原题中文大意
 
中国象棋的马按照象棋的规则在5 x 6 的棋盘上跑30步跑完所有的格子。
 
 
 
(2)算法思想及解题用到的主要数据结构
 
 
 
从每一个点往下走第二步,会有几点有效的行走位置。 把当前位置记在栈里面,以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过,则从栈顶弹出上一位置,恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别,用函数递归调用即可解决问题。
 
 
 
(3)详细解题思路
 
1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.
 
2. 写一个一般的递归调用自己的函数,表示马在走第几步时到了哪个位置,然后尝试走余下的所有可走位置。
 
3. 递归函数有两个退出条件。要么下一个要尝试的点已经走过了,要么走到了最后一步,即得解!
 
 
 
(4)逐步求精算法描述
 
用一个数组记下来经过的点。
 
 
 
(5)程序注释清单
 
#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

using namespace std;

const static char row_num = 5;   // 5行

const static char column_num = 6;  // 6列



// 这个全局数组在初始化后会记下每30个有效位置的下一步可走位置.

// elocution[x][0]记个数。最多8个有效可走位置。

char elocution[30][9];

struct coordinate  // 坐标.

{

char _x;  // start from zero.

char _y;

};

// 坐标转序号的函数。

char coordinate2serial_num(coordinate co)

{

char num = co._x * column_num + co._y + 1;

return num;

}

// 序号转坐标的函数。

coordinate serial_num2coordinate(char sn)

{

coordinate co;

co._x = (sn - 1) / column_num;

co._y = sn - co._x * column_num - 1;

return co;

}

// 增量数组.

char increments[8][2] =

{

1, -2, 2, -1, 2, 1, 1, 2,

-1, 2, -2, 1, -2, -1, -1, -2

};

// 得用增量数组来计算每一个位置的下一步有效位置。记到steps里面.

void next_step(char pos, char steps[])

{

char valid_count = 0;

coordinate co = serial_num2coordinate(pos);

coordinate tmp;

char serial_num;

for ( int i = 0; i < 8; i++ )

{

tmp._x = co._x + increments[i][0];

tmp._y = co._y + increments[i][1];

if ( tmp._x < 0 || tmp._x > 4 || tmp._y < 0 || tmp._y > 5 )

{

continue;

}

serial_num = coordinate2serial_num(tmp);

if ( serial_num >= 1 && serial_num <= 30 )

{

valid_count++;

steps[valid_count] = serial_num;

}

else

{

cerr << "Not expected to reach here.\n";

}

}

steps[0] = valid_count;

}

// 初始化记载所有点的下一步可走点的全局表。

void init_elocution()

{

for ( int i = 1; i <= 30; i++ )

{

next_step(i, elocution[i-1]);

}

}



char track[30];   // 记走过的路径.

bool quit_run_horse;

// 上文提高的递归函用函数.

void run_horse(char start_pos, char step_count)

{

if ( quit_run_horse ) // 用来快速退出深嵌套递归调用函数.

{

return;

}

for ( int i = 0; i < step_count; i++ )

{

// 已?经-经-过y这a点?了?.

if ( track[i] == start_pos )

{

return;

}

}

track[step_count] = start_pos; // 记下新走过的位置



if ( step_count == 29 )  // 最后一步则打印出结果。

{

for ( int i = 0; i < sizeof(track); i++ )

{

cout << (int)track[i];

if ( i + 1 != sizeof(track) )

{

cout << " ";

}

}

cout << endl;

quit_run_horse = true;

return;

}



for ( int i = 0; i < elocution[start_pos-1][0]; i++ )

{

run_horse(elocution[start_pos-1][i+1], step_count+1);

}

}

int main(int argc, char* argv[])

{

init_elocution();

int pos;

vector<int> vec;



while(true)

{

cin >> pos;

if (pos==-1)

{

break;

}

vec.push_back(pos);

}



for ( int i = 0; i < vec.size(); i++ )

{

quit_run_horse = false;

run_horse(vec[i], 0);

}

return 0;

}

 

 
 
 

knowledge gained from learning git.

# If you inadvertently remove a file of your working copy. Don't worry. Git are good at recovering old versions of files, such as:
$git checkout HEAD — data

 

# show what the file looks like in a certain branch.
$git show branch_name:file_name

# In newer versions of Git, git diff –ours is a synonym for git diff HEAD, because it shows the differences between "our" version and the merged version. Similarly, git diff MERGE_HEAD can be written as git diff –theirs. You can use git diff –base to see the combined set of changes since the merge base, which would otherwise be rather awkwardly written as:
git diff $(git merge-base HEAD MERGE_HEAD)

# While you are in the process of resolving a conflict, you can use some special git log options to help you figure out exactly where the changes came from and why. Try this:
$git log –merge –left-right -p
–merge shows only commits related to files that produced a conflict.
–left-right displays < if the commit was from the "left" side of the merge("our version", the one you started with), or > if the commit was from the "right" side of the merge("their" version, the one you're merging in).
-p shows the commit message and the patch associated with each commit.

If your repository were more complicated and several files had conflicts, you could also provide the exact file names you are interested in as a command line option, like this:
$git log –merge –left-right -p hello

# The -s option to git ls-files shows all the files with all stages. If you want to see only conflicted files, use the -u option instead.

# $ git checkout -m branch_name
If possible or if specifically requested with the -m option, Git attempts to carry your local change into the new working directory by performing a merge operation between your local modifications and the target branch.

# $ git reset –hard ORIG_HEAD
If you want to abort or discard the merge after it has finished(that is,after it has introduced a new merge commit), use the above command. Prior to beginning the merge operation, Git saves your original branch HEAD in the ORIG_HEAD ref for just this sort of purpose.
You should be very careful here, though. If you did not start the merge with a clean working directory and index, you could geet in trouble and lose any uncommitted changes you have in your directory.

# Just show what the file looks like in a branch.
$ git show branch_name:file_name

# The command for manipulating remotes is git remote. This operation introduces a few new settings in the .git/config file.

Diff, Patch, and Friends(diff, patch和他们的相关工具)(第二篇)

原文 http://www.linuxjournal.com/article/1237
翻译: www.ykyi.net zausiu
接上篇

Use the diff program to avoid eyestrain and insanity:
使用diff程序来避免会令人发疯的肉眼查找。

diff -u 1 2
— 1 Sat Apr 20 22:11:53 1996
+++ 2 Sat Apr 20 22:12:01 1996
-1,9 +1,9
Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
-modus gradibus desendendi, non nunquam autem
+modus gradibus descendendi, nonnunquam autem
sentit, etiam alterum modum exstare, dummodo
-pulsationibus desinere et de no modo meditari
+pulsationibus desinere et de eo modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

There are several things to notice here:
这里有几个东西要提一下:

*

The file names and last dates of modification are shown in a “header” at the top. The dates may not mean anything if you are comparing files that have been passed back and forth by e-mail, but they become very useful in other circumstances.
文件名和上交更新时间在输出中前面部分显示。如果你只是比较由电子邮件发来发去的文件的话,更新时间可能并不重要。但是在某些情况下,确实还是很有用的。
*

The file names (in this case, 1 and 2—are preceded by — and +++.
文件名(在这个例子中,有两个文件,一个名为1,另一个名为2)加上了 — 和 +++ 的前缀。
*

After the header comes a line that includes numbers. We will discuss that line later.
在头部之后有一行包括了一些数字。我们将在之后讨论它。
*

The lines that did not change between files are shown preceded by spaces; those that are different in the different files are shown preceded by a character which shows which file they came from. Lines which exist only in a file whose name is preceded by — in the header are preceded by a – character, and vice-versa for lines preceded by a + character. Another way to remember this is to see that the lines preceded by a – character were removed from the first (—) file, and those preceded by a + character were added to the second (+++) file.
所有没有更改的行显示出来时仅仅加上空格作前缀。如果是不同的行呢,则在每一行前加上指示它们出处的前缀。加上-前缀表示来自头部标志的 — 文件,如果加上 + 前缀则表示来自头部标志的 +++ 文件。另外你也可以理解成: 有 – 前缀的行表示从第一个文件(—)中删除了,而有 + 前缀的行表示是在(+++)文件中添加的。
*

Three spelling changes have been made: “desendendi” has been corrected to “descendendi”, “non nunquam” has been corrected to “nonnunquam”, and “no” has been corrected to “eo”.
发现三个拼写改动。

Perhaps the main thing to notice is that you didn't need this description of how to interpret diff's output in order to find the differences. It is rather easy to compare two adjacent lines and see the differences.
可能你最关心的不是怎么解析diff的输入来找到分别。比较两个相邻的行来找区别是相当容易的。

It's not always this easy
但事实上并不总是如此。

Unfortunately, if too many adjacent lines have been changed, interpretation isn't as immediately obvious; but by knowing that each marked line has been changed in some way, you can figure it out. For instance, in this comparison, where the file 3 contains the damaged contents, and file 4 (identical to file 2 in the previous example) contains the correct contents, three lines in a row are changed, and now each line with a difference is not shown directly above the corrected line:
很不幸的是。如果太多的相邻行有改动的话,就不是那么明显啦。但是如果知道每行是怎么改动的,你就被轻易找到区别。比如这个例子,文件3包含了受损的内容,而文件4(其实和上个例子中的文件2一模一样)包含了正确的内容,连续三行被改变了,现在每个有改动的行没有在正确的行上面直接显示出来。

diff -u 3 4
— 3 Sun Apr 21 18:57:08 1996
+++ 4 Sun Apr 21 18:56:45 1996
-1,9 +1,9
Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
-modus gradibus desendendi, non nunquam autem
-sentit, etiam alterum nodum exitare, dummodo
-pulsationibus desinere et de no modo meditari
+modus gradibus descendendi, nonnunquam autem
+sentit, etiam alterum modum exstare, dummodo
+pulsationibus desinere et de eo modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

It takes a little more work to find the added mistakes; “nodum” for “modum” and “exitare” for “exstare”. Imagine if 50 lines in a row had each had a one-character change, though. This begins to resemble the old job of going through the whole file, character-by-character, looking for changes. All we've done is (potentially) shrink the amount of comparison you have to do.
这就需要花费更多的工作来找到错误啦。“nodum” for “modum” and “exitare” for “exstare”。想象一下,如果连续50行,每行都有一个字母的改变,那么你要做的工作又和使用diff前一样嘞。逐字逐字的查找!diff仅仅帮你把更改范围限定了而已。

Fortunately, there are several tools for finding these kinds of differences more easily. GNU Emacs has “word diff” functionality. There is also a GNU “wdiff” program which helps you find these kinds of differences without using Emacs.
好有好些工具帮助你很容易定位到这些差异。GNU Emacs就有一个"word diff"的功能。还有一个叫wdiff的GNU工具也能帮助你查找这种类型的错误。

Let's look first at GNU Emacs. For this example, files 5 and 6 are exactly the same, respectively, as files 3 and 4 before. I bring up emacs under X (which provides me with colored text), and type:
让我们先看看GNU Emacs。

M-x ediff-files RET
5 RET
6 RET

In the new window which pops up, I press the space bar, which tells Emacs to highlight the differences. Look at Figure 1 and see how easy it is to find each changed word.

Figure 1. ediff-files 5 6

GNU wdiff is also very useful, especially if you aren't running X. A pager (such as less) is all that is required—and that is only required for large differences. The exact same set of files (5 and 6), compared with the command wdiff -t 5 6, is shown in Figure 2.
GNU wdiff也很有用,特别是你没有运行X服务的时候。一个分屏工具(比如 less)就足够用来查找大范围的差异了。

Figure 2. wdiff -t 5 6

///////
好辛苦。不想译了~~不译了。自己去看原文吧。累死哥了。

copyright blog.ykyi.net

Syntax Highlight in DDD DDD的语法高亮

这几天用DDD调试linux下的程序.发现DDD没有语法高亮~
于是google了一下。悲剧地发现一个贴子:

Hello!

Is it possible to enable syntax highlighting in DDD?
I searched through the Google and found this answer:
可以在DDD里开启语法高亮吗?我用谷歌搜索后发现这个答案。

Sorry, no, this isn’t possible.
The biggest problem is that Motif’s text widget doesn’t
support multiple colours, and would have to be replaced.
That would be an enormous job.
不好意思。没有!这不可能.
最大的问题是Motif的文本控件不支持多彩显示,必须把motif替换掉.
这不是一个普通的/简单的任务.

/////////////////////
悲剧啊!!!在黑白的Linux世界。………..

Is it still impossible (post date is Thu, 10 Feb 2005)?
Are there any workarounds/patches/forks?

Diff, Patch, and Friends(diff, patch和他们的相关工具)(第一篇)

原文 http://www.linuxjournal.com/article/1237
翻译: blog.ykyi.net

“Kernel patches” may sound like magic, but the two tools used to create and apply patches are simple and easy to use—if they weren't, some Linux developers would be too lazy to use them…
"内核补丁"听起来相当之神奇,但是有两个用来创建补丁和应用补丁的工具却简单易用。如果它们很难用的话,一些Linux开发者才懒得用它们呢。

Diff is designed to show you the differences between files, line by line. It is fundamentally simple to use, but takes a little practice. Don't let the length of this article scare you; you can get some use out of diff by reading only the first page or two. The rest of the article is for those who aren't satisfied with very basic uses.
diff这个工具设计成可以向你展示文件之间行与行的区别。它使用起来是相当的简单,但需要一点练习才习。你千万不要让长长的介绍文档把你吓住。你可以先只读前一两页文档,这样你就可以使用diff来开展一些工作了。余下的diff介绍文档是写给那些对基本用法非常不满的奇异人士的。 http://blog.ykyi.net

While diff is often used by developers to show differences between different versions of a file of source code, it is useful for far more than source code. For example, diff comes in handy when editing a document which is passed back and forth between multiple people, perhaps via e-mail. At Linux Journal, we have experience with this. Often both the editor and an author are working on an article at the same time, and we need to make sure that each (correct) change made by each person makes its way into the final version of the article being edited. The changes can be found by looking at the differences between two files.
diff被开发者用来同一个源文件的比较不同版本之间的区别。这还可以有很多其它的用途。比如,当编辑一个在很多人之间通过email传递的文档时,diff工具非常方便。在Linux Journal网站,我们经历过这些。编辑和作者同时修改同一个文章的情况非常常 见,我们需要确保每个人所作的修改都被正确应用到这篇文章的正确位置。被修改的部分可以通过比较两个文件的区别得到。

However, it is hard to show off how helpful diff can be in finding these kinds of differences. To demonstrate with files large enough to really show off diff's capabilities would require that we devote the entire magazine to this one article. Instead, because few of our readers are likely to be fluent in Latin, at least compared to those fluent in English, we will give a Latin example from Winnie Ille Pu, a translation by Alexander Leonard of A. A. Milne's Winnie The Pooh (ISBN 0-525-48335-7). This will make it harder for the average reader to see differences at a glance and show how useful these tools can be in finding changes in much larger documents.
但是,要让你清楚的知道diff工具在查找文件之间的区别方面是多么有用是用点难度的。要向你清楚展示diff的所有所有功能,需要整个Linux Journal杂志这么大的篇幅来介绍(zausiu: 这句话我不太确定有没有译对)。我不这样做,由于比较少一部分人可以流利读懂拉丁文,至少同能够读英文的人数相比可以读拉丁文的是少数派,我给出一个用拉丁文的例子。这样一来,一般人就不太能一眼看出不同之处来,你就能够理解diff用来查找大文件之间的区间是多么有用了。http://blog.ykyi.net

Quickly now, find the differences between these two passages:
废话少说,找找下面两段话的区别:

Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
modus gradibus desendendi, non nunquam autem
sentit, etiam alterum modum exstare, dummodo
pulsationibus desinere et de no modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

Ecce Eduardus Ursus scalis nunc tump-tump-tump
occipite gradus pulsante post Christophorum
Robinum descendens. Est quod sciat unus et solus
modus gradibus descendendi, nonnunquam autem
sentit, etiam alterum modum exstare, dummodo
pulsationibus desinere et de eo modo meditari
possit. Deinde censet alios modos non esse. En,
nunc ipse in imo est, vobis ostentari paratus.
Winnie ille Pu.

You may be able to find one or two changes after some careful comparison, but are you sure you have found every change? Probably not: tedious, character-by-character comparison of two files should be the computer's job, not yours.
如果你仔仔细细,认认真真地比较,你能够发现一到两个不同之处。但是你可以保证你找到了所有的不同之处了吗?不!逐字的比较文件之间的不同是电脑的专长,而不是你--humanbeing ! 

请看第二篇。

copyright blog.ykyi.net

fsockopen真好用,PHP的高级别网络函数!

今天用Burp工具分析了一个网站的大致功能后打算写程序把该网站我感兴趣的内容全抓下来。
一开始用java写了一小段,但哥对Java不熟悉哇,而且哥觉得Java的那么多流的类,如果仅仅操作文本文件,就显得封装的太厚了。又想,用C/C++写。虽然用C/C++写的最多代码,但事实上C/C++的字符串操作一想起来就嫌烦,而且正则式也烂得可以,数组不支持用字符串索引也真够麻烦,虽然可用C++的std::map容器。最后决定用PHP写…PHP真是太好用了~~~犹赞超强大的正则式,同perl的正则式有得一拼啊。如果换用标准C字符串函数和GNU的一个超难用的C正则式库,那要写死人啊~~~

最开始的思维定势就是要先开一个socket(N多参数要填入), 省略bind(操作系统自已选一个本地端口绑定),第二步 connect 到主机,第三步往 socket 里写东西… 虽然只几个简单函数,但要填的几个参数也真够难记的。嘿,偶像发现事实上PHP提供了high-level的socket函数 fsockopen()。哇,太方便了。

fsockopen()
returns a file pointer which may be used together with the other file functions (such as fgets(), fgetss(), fwrite(), fclose(), and feof())
fsocketopen返回一个文件指针,然后就可以用常用的文件函数操作它啦!!!和操作文本一件一样~~~ 比 Java 的 java.io.socket 类还要方便~~虽然java也抽象的不错,但我就是嫌流对象封装太厚了。人生苦短,何必自找麻烦呢。
用完以后用 fclose 把它fsockopen返回的文件指针关掉!

看个例程:
$fp = fsockopen(“udp://127.0.0.1”, 13, $errno, $errstr);
if (!$fp) {
echo “ERROR: $errno – $errstr
\n”;
} else {
fwrite($fp, “\n”);
echo fread($fp, 26);
fclose($fp);
}
?>
上面的例程从本机的UDP时间服务器里读取当时的时间和日期。如果你本机开了标准的时间服务的话~~~

copyright blog.ykyi.net