Archive for November, 2011

熬夜完成 sicily1153 马周游解题报告。困死哥了.

唉!!! 上次交作业写错题目了,做了简单的马周游 sicily 1152。补上新的,应该是sicily 1153.为了解决规模太大的问题。加上了优化算法。

 
中大ACM实验题。
 
(1)原题中文大意
 
中国象棋的马按照象棋的规则在8 x 8 的棋盘上跑64步跑完所有的格子。
 
 
 
(2)算法思想及解题用到的主要数据结构
 
 
 
从每一个点往下走第二步,会有几点有效的行走位置。 把当前位置记在栈里面,以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过,则从栈顶弹出上一位置,恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别,用函数递归调用即可解决问题。
 
软之简单的马周游,8 x 8 棋盘的规模非常大。需要在可选下一步中找到最接近正确路线的点。求该点的办法是把所以的可选点先找出,再给这些可选点按权重排序,从最优的解依次向次优,次次优.....的点试探。重点在权重的算法。这里的权重的计算法则是指一个点的下一次可走的点的个数。
 
主要的数据结构有:
 
// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位

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

char elocution[ELEM_COUNT][9];

// stamps数组记每个点是否已经走过了。0表示没走过,1表示走过了。

char stamps[ELEM_COUNT];

// track数组记路径的顺序。

char track[ELEM_COUNT];

通过结合stamps数组和elocution数组可以算出下一步的每个点的权重。



(3)详细解题思路

1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.

2. 写一个一般的递归调用自己的函数,表示马在走第几步时到了哪个位置,然后求出余下的所有可走位置。

3. 余下的所有位置按照上文提到的权重排序。

4. 对于排序后的可选点数组,按顺序依次用递归函数尝试。

5. 递归函数有三个退出条件。1.下一个要尝试的点已经走过了,2.试完了所有的可选下一步无解。3.走到了最后一步,即得解!



(4)算法描述

初如化上文提到的elocution数组,清空stamps和tracks.从起点开始调用递归函数。

http://blog.ykyi.net  zausiu's blog.



(5)程序注释清单

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <csetjmp>

//#include <cassert>



using namespace std;



#define  ROW_NUM     8

#define  COLUMN_NUM  8

#define  ELEM_COUNT ROW_NUM * COLUMN_NUM



jmp_buf jmpbuffer;  // 很深的函数递归调用时用longjmp快速退出.



// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位

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

char elocution[ELEM_COUNT][9];



// stamps数组记每个点是否已经走过了。0表示没走过,1表示走过了。

char stamps[ELEM_COUNT];



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;

}



// ((x:1;y:-2),(x:2;y:-1),(x:2;y:1),(x:1;y:2) (x:-1;y:2),(x:-2;y:1),(x:-2;y:-1),(x:-1;y:-2));

char increments[8][2] =

{

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

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

};

void next_step(char pos, char steps[])  // 把位置在pos序号的点的每一个下一个可选位置记在数组中。

{

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 >= ROW_NUM || tmp._y < 0 || tmp._y >= COLUMN_NUM )  // 保证位置有效

{

continue;

}

serial_num = coordinate2serial_num(tmp);

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

{

valid_count++;

steps[valid_count] = serial_num;

}

else

{

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

}

}

steps[0] = valid_count;

}



// 下面的逻辑以每个点的下一步可跳点的数目作为权重排序。

struct pos_weight

{

char _pos;

char _weight;

};

// 又是用递归。这里为了实现快速排序

int partition(pos_weight poses[], int low, int high)

{

pos_weight pivot = poses[low];

while (low < high)

{

while (low < high && pivot._weight < poses[high]._weight)

high--;

poses[low] = poses[high];

while (low < high && pivot._weight >= poses[low]._weight)

low++;

poses[high] = poses[low];

}

poses[low] = pivot;

return low;

}

// 快速排序。

void quick_sort_steps(pos_weight poses[], int low, int high)

{

if ( low < high )

{

int pivot_loc = partition(poses, low, high);

quick_sort_steps(poses, low, pivot_loc-1);

quick_sort_steps(poses, pivot_loc+1, high);

}

}

void rearrage_steps(char poses[], int len) // poese里放置了下一个位置数组。Len是数组长度。

{

char weight, pos, next_step_count;

vector<pos_weight> vec(len);

for ( int i = 0; i < len; i++ ) // 计算权重.

{

weight = 0;

pos = poses[i];

next_step_count = elocution[pos-1][0];

for ( int j = 0; j < next_step_count; j++ )

{

char next_step_pos = elocution[pos-1][j+1];

if ( 0 == stamps[next_step_pos-1] )

{

weight++;  // 如果有一下一跳点没走过则权重加1.

}

}

vec[i]._pos = pos;

vec[i]._weight = weight;

}

quick_sort_steps(&vec[0], 0, len-1);  // 根据权重排序.

for ( int i = 0; i < len; i++ ) // 把排序后的位置写回原始数组.

{

poses[i] = vec[i]._pos;

}

}



void init_elocution()

{

memset(stamps, 0, sizeof(stamps));

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

{

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

}

}



char track[ELEM_COUNT];

void run_horse(char start_pos, char step_count) // step_count [0 -- 64)

{

// 如果已经经过这点就立即退出函数。

if ( 1 == stamps[start_pos-1] )

{

return;

}



track[step_count] = start_pos;



if ( step_count == COLUMN_NUM * ROW_NUM - 1 )  // 是不是最后一步。

{

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

{

cout << (int)track[i];

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

{

cout << " ";

}

}

cout << endl;

longjmp(jmpbuffer, 0x1);

return;

}



// 记下已经走了这一步。

stamps[start_pos-1] = 1;   rearrage_steps(elocution[start_pos-1]+1, elocution[start_pos-1][0]);

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

{

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

}

stamps[start_pos-1] = 0;  // 试完了所有可走步.退出这个函数.重置这个位置为没有走过。

}



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

{

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++ )

{

if(setjmp(jmpbuffer) == 0)  // 为了很深的递归函数快速回退到这里。

{

init_elocution();

memset(track, 0, sizeof(track));

memset(stamps, 0, sizeof(stamps));

run_horse(vec[i], 0);

}

}



return 0;

}

 

(6)该算法的时间复杂度是 O(8 ^ (m * n))   m,n分别为棋盘的长和宽。
 
 
 
/////////////////// 原题目如下:
 
 
 
1153. 马的周游问题
 
 
 
Description
 
和题目C同样的任务,这里只是把棋盘扩大到标准的国际象棋。对这样一个8 * 8的棋盘用同样的方法编号如下:
 
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       31    32
 
33    34       35    36       37    38       39    40
 
41    42       43    44       45    46       47    48
 
49    50       51    52       53    54       55    56
 
57    58       59    60       61    62       63    64
 
Input
 
输入有若干行。每行一个整数N(1<=N<=64),表示马的起点。最后一行用-1表示结束,不用处理。
 
Output
 
对输入的每一个起点,求一条周游线路。对应地输出一行,有64个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
 
Sample Input
 
4
-1
Sample Output
 
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。
 
 
 

 

Be the first to comment - What do you think?  Posted by zausiu - November 30, 2011 at 02:11

Categories: Tech Articles   Tags:

又是数组越界造成的bug.

又一次遇到数组越界造成的奇怪的,难以调试的,诡异的bug.

前几天做ACM题。‘简单的马周游’。

http://blog.ykyi.net/2011/11/acm-%E9%A9%AC%E5%91%A8%E6%B8%B8%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

因为我的解法用了函数递归调用,函数求到最终解的栈的调用层次非常深。第一版用置一个全局变量的方式让这么深调用的函数快速依次退出。但我也知道还有另外一种解法就是用C语言的setjmp 和 longjmp。用这两个函数可以快速退栈。

 

今天晚上就想用setjmplongjmp改写一下。本来以为是非常简单的事情。结果改完以的程序只能正确求解第一个请求,然后程序看起来就像是死了。Debug时发现程序似乎跑飞了。哎(脑子不灵光,发现程序跑飞竟然没有立即想到是数组越界把堆栈写坏了)。因为我改动的代码非常少,只是用setjmplongjmp快速退出递归取代之前的稍微比较慢的做法。而其它的代码改动的非常之少。于是我当时分析错误的出发点就是比较两份代码的异同。比较来比较去,就只有退出方式不同而已。相当相当地困惑。费了很多时间都没有找到原因。

实在搞不定了。冲了个热水澡,又回来看代码。还是没有发现这个改动在哪里引入了错误。不断反复地看代码,突然灵光一现看到写一个全局数组的语句,下标变量越界!越界!越界!!!啊~~惊喜!于是把数组下标的相关的代码纠正了,于是setjmp版本的代码也运行正常啊。

这次的经验是。操作数组的时候一定要一定要一定要非常非常非常之小心~~在调试程序发现程序跑飞的情况下马上要意识到是写坏了堆栈。

 

另外还有一个疑问是第一版的代码也有写坏栈的问题为什么就一切正常呢。这就是C/C++程序数组危险的地方啊~~第一版本的代码退栈的方式和第二版不一样,于是这个bug就在第一版隐藏了起来。于是第二版出问题时我的思路集中在比较代码差异是如何引入问题的。而这个bug并不是新代码引入的,而是在旧代码隐藏起来的,第二代的新代码让触发了这个bug

总结下经验:

一定要一定要非常小心C/C++的数组越界问题啊!!!操作很多数组时,有很多下标要计算时。千万要注意是从0还是从1开始计算下标。要根据约定多下诊断!!!及时发现隐藏的错误。越界写数组的bug有时发生,可能在引入的当时被隐藏,隐藏的很深很深。但越界读数组的bug隐藏得更深更深更深啊。

copyright blog.ykyi.net

 

Be the first to comment - What do you think?  Posted by zausiu - November 29, 2011 at 23:19

Categories: Tech Articles   Tags:

中大ACM题.商人的宣传解题报告.

Description

Bruce是K国的商人,他在A州成立了自己的公司,这次他的公司生产出了一批性能很好的产品,准备宣传活动开始后的第L天到达B州进行新品拍卖,期间Bruce打算将产品拿到各个州去做推销宣传,以增加其影响力。

K国有很多个州,每个州都与其他一些州相邻,但是K国对商人作宣传却有一些很奇怪的规定:
1、 商人只能从某些州到达另外一些州,即连通路线是单向的,而且有些州可能是到达不了的。
2、 商人不允许在同一个州连续宣传两天或以上,每天宣传完必须离开该州。
3、 商人可以多次来到同一个州进行宣传。

"我必须找出一条影响力最大的路线才行",Bruce想,"但我首先必须知道到底有多少这种符合规定的宣传路线可供我选择。"现在Bruce把任务交给了你。并且出于考虑以后的需要,你还要帮他算出给出的两州之间的路线的总数。

 

Input

输入文件第一行包含三个整数n,m,L(1≤n,L≤100),分别表示K国的州数、连通路线的数量,以及多少天后必须到达B州。接下来有m行,每行一队整数x,y(1≤x,y≤n),表示商人能从x州到达y州。
第m+2行为一个整数q(1≤q≤100),表示Bruce有q个询问。下面q行每行两个整数A,B(1≤A,B≤n),即A、B州的位置。

Output

输出文件包含q行,每行一个整数t,为所求的从A州到B州满足上述规定的路线总数。
输入数据中的询问将保证答案t在长整数范围内,即t<231

Sample Input

4 5 6
1 2
2 3
3 4
4 1
2 4
2
1 4
4 2

Sample Output

2 1

1. 原题中文大意.

商人的宣传即是一个有向图的问题。有一个有向图。该图的每条件权重一样,从图中任意一点a刚好通过L步到达另一点b有多少条路线。

 

 

2. 算法思想及解题思路.

使用了动态规划算法。令 dp[num][dest] 表示从起点通过 num 条边到达终点共有多少种走法。

先由已经知条件易得从起点通过一条它的邻接边到达它的所有邻接点共有一条路线。即 dp[1][邻接点易求得。而 dp[x][y] = sum( dp[x-1][可以一条邻接边到达y的点] )

 

3. 主要数数据结构.

主要数据结构为三个数组。这本个数组都不用下标为0的元素。

char odgree[MAX_VERTICES_NUM+1];

下标为每个顶点的编号.表示每个顶点的出度

int routine[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];

‘路由表’ routine[x][n] = y 表示从顶点x经它的第n条邻接边可以到达顶点y.

int dp[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];

这个数组即第二节提到的dp数组,dp[L][x] = num从起点开始经L条边走到顶点 共有 num 种走法。

 

4. 逐步求精算法描述(含过程及变量说明);

从已知条件初始化 odgree 和 routine 数组.

bzero(odgree, sizeof(odegree));

for(int x,y, i = 0; i < m; i++)

{

scanf("%d %d", &x, &y);

odgree[x]++;

routine[x][ odgree[x] ] = y;

}



下面的cal函数输入起点顶点和终点顶点,返回共有多少种走法。

int cal(char start, char dest)

{

memset(dp, 0, sizeof(dp));



for ( int i = 1; i <= odgree[start]; i++ )  // 遍历起点的每一条邻接边

{

dp[1][ routine[start][i] ]++;  //  初始时经过一邻接边到达别一点的走法有几种.



}



for ( int i = 2; i <= L; i++ )   // 一直走到第L步.

{

for ( int j = 1; j <= n; j++ )  // 遍历每一个顶点.

{

for ( int k = 1; k <= odgree[j]; k++ )  // 该顶点的第一条邻接边

{

// 上文提到的递推公式。

dp[i][ routine[j][k] ] += dp[i-1][j];

}

}

}



return dp[L][dest];  // 返回结果

}

 

5. 程序注释清单

#include <cstdio>

#include <cstdlib>

#include <memory>

#include <cstring>

#include <vector>



using namespace std;



const int MAX_VERTICES_NUM = 100;  // 最多多少个顶点. 

int n, m, L, q;  // 实际n个点、m条边,L 为期限.q为有多少个询问. 

static char odgree[MAX_VERTICES_NUM+1];  // 记每个点的出度.不用下标为0的元素.

static int routine[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];  // table[x][y] 表示x点经它的第y条边可以去到哪个点.

static int dp[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];  // dp[x][y] 表示经x条边,可以从某点到 y 点.



int cal(char start, char dest)

{

memset(dp, 0, sizeof(dp));



for ( int i = 1; i <= odgree[start]; i++ )  // 遍历起点的每一条邻接边. 

{

dp[1][ routine[start][i] ]++;  // 初始时经过一步到达别一点的走法. 

}



for ( int i = 2; i <= L; i++ )   // 一直走到第 L 步. 

{

for ( int j = 1; j <= n; j++ )  // 遍历每一个点. 

{

for ( int k = 1; k <= odgree[j]; k++ )  // 该点的每一个邻接点. 

{

dp[i][ routine[j][k] ] += dp[i-1][j];

}

}

}



return dp[L][dest];

}



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

{

while ( EOF != scanf("%d %d %d", &n, &m, &L) )

{

memset(odgree, 0, sizeof(odgree));

for(int x,y, i = 0; i < m; i++)

{

scanf("%d %d", &x, &y);

odgree[x]++;

routine[x][ odgree[x] ] = y;

}



scanf("%d", &q);

vector<int> results;

for ( int start,dest, i = 0; i < q; i++)

{

scanf("%d %d", &start, &dest);

results.push_back(cal(start, dest));

}

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

{

printf("%d\n", results[i]);

}



}

return 0;

}

 

6. 测试数据

4 5 6

1 2

2 3

3 4

4 1

2 4

5

1 4

4 2

2 1

1 3

3 4

2

1

2

1

0

 

 

7. 对时间复杂度,空间复杂度方面的分析、估算及程序优化的分析和改进.

本解决方法的时间复杂度为O(L*n*n),空间复杂度为O(n*n).

用动态规划解此题的时间复杂度优于用邻接矩阵表示图然后用图的乘法解出。后者的时间复杂志为O(L*n*n*n)

Be the first to comment - What do you think?  Posted by zausiu - November 26, 2011 at 18:35

Categories: Tech Articles   Tags:

Next Page »