请教,用时间和空间两种算法,为什么得出的答案不一样?
题目:
俗话说“谣言止于智者”,谣言就像瘟疫一样,传播的速度非常快,只有智者才能不信谣不传谣。本题就来模拟一次谣言的传播,假设如下:有1万人排列成100*100的正方形队伍中,1代表普通人(听到谣言后就会传播给前后左右的相邻者,不能斜向传播),0代表智者(不会传播谣言,假定有1/3的人是智者),某个时间有1个人制造了1个谣言并开始传播,经过足够长时间的谣言传播后,问在智者的庇护下最后有多少普通人没有听到谣言。
请勿改动主函数main和其它函数中的任何内容,仅在函数fun的花括号中填入你编写的若干语句。只允许有一个源代码文件test2.c
空间算法:
#include <stdlib.h>
#include <stdio.h>
// 参数x,y表示造谣人的位置
unsigned int fun(int map[100][100], unsigned int x, unsigned int y)
{
int i,j,n=0,p=0;
// WRITE YOUR CODES HEAR
map[x][y]=2;
if((x-1>=0)&&(map[x-1][y]==1))
fun(map,x-1,y);
if((x+1<100)&&(map[x+1][y]==1))
fun(map,x+1,y);
if((y-1>=0)&&(map[x][y-1]==1))
fun(map,x,y-1);
if((y+1<100)&&(map[x][y+1]==1))
fun(map,x,y+1);
for(i=0;i<100;i++)
{
for(j=0;j<100;j++)
{
if(map[i][j]==1)
n++;
}
}
return n;
}
void main(void)
{
int map[100][100];
unsigned int person;
int x, y;
for (x = 0; x < 100; x++)
for (y = 0; y < 100; y++)
map[x][y] = ((rand() % 3) != 0) ? 1 : 0;
person = fun(map, rand() % 100, rand() % 100);
printf("Person: %d\n", person);
}
时间算法:
#include <stdlib.h>
#include <stdio.h>
// 参数x,y表示造谣人的位置
unsigned int fun(int map[100][100], unsigned int x, unsigned int y)
{
// WRITE YOUR CODES HEAR
int i=0,j=0;
int no=0;
static int cur=0;
static int flag = 200;
map[x][y]=-1;
for (i=0;i<100;i++)
{
for(j=0;j<100;j++)
{
if(map[i][j]==-1){
if(i>0&&map[i-1][j]==1){
map[i-1][j]=-1;
cur++;
}
if(i<99&&map[i+1][j]==1){
map[i+1][j]=-1;
cur++;
}
if(j>0&&map[i][j-1]==1){
map[i][j-1]=-1;
cur++;
}
if(j<99&&map[i][j+1]==1){
map[i][j+1]=-1;
cur++;
}
}
}
}
flag--;
if(flag!=0){
return fun(map,x,y);
}else{
for(i=0;i<100;i++){
for(j=0;j<100;j++){
if(map[i][j]==1)
{no++;}
}
}
return no;
}
}
void main(void)
{
int map[100][100];
unsigned int person;
int x, y;
for (x = 0; x < 100; x++)
for (y = 0; y < 100; y++)
map[x][y] = ((rand() % 3) != 0) ? 1 : 0;
person = fun(&map, rand() % 100, rand() % 100);
printf("Person: %d\n", person);
}
答案第一种算法是328,第二种是323,想了很久就是想不通为什么两种算法的结果不一样,希望有哪位大神可以帮我解惑,谢谢!
[解决办法]
fun(int map[100][100], unsigned int x, unsigned int y),x,y都是无符号的,因此即使减1后变成-1,也会变成一个很大的正值!!!
所以接下来的判断都是无效的!所以第一个程序是错的
请问,用时间和空间两种算法,为什么得出的答案不一样
请教,用时间和空间两种算法,为什么得出的答案不一样?题目:俗话说“谣言止于智者”,谣言就像瘟疫一样,传播的
