又是数组越界造成的bug.

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

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

http://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 ykyi.net

 

中大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)