| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1716 人关注过本帖
标题:再出一题(祭祀广场)
只看楼主 加入收藏
gupiao175
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:40
帖 子:1787
专家分:7527
注 册:2007-6-27
收藏
得分:0 
太牛了。20分钟就把算法和代码整出来了。厉害!

我看了20分钟只知道大概的题目要求!看来我真的是大菜鸟!向高人学习!

高人都是卧虎藏龙啊。下次不敢再用版主号上了,下次我改用小号上,不然看到此帖也只好略过,当没看见!不好意思回!

Q:1428196631,百度:开发地 即可找到我,有事请留言!
2011-06-05 23:34
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
回复 10楼 beyondyf
恩,虽然输入输出格式不对,内存占用也较大,不过核心算法是对的,分都给你吧。

My life is brilliant
2011-06-05 23:58
laznrbfe
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
帖 子:482
专家分:1599
注 册:2011-5-22
收藏
得分:0 
嗯嗯~端午节快乐~晚安~
2011-06-06 00:01
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 lz1091914999
呵呵,我猜你也会说我格式不对的。不过首先还是感谢赠分本来昨晚想等你回信的,可洗完澡后突然停电了,真是不好意思。
有一个问题你一直没有回答我,你这是ACM试题么?
关于格式,我必须解释一下。你认为不对是因为你希望先看到所有的输入,然后是所有的输出。我猜你还不理解什么是流。在控制台程序中,scanf从输入流是读取数据,printf向输出流写入数据。请注意,这是两个不同的流。一般标准的输入流是键盘,标准输出流是屏幕。但控制台会回显键盘输入,它和输出流按时间顺序混合在了一起。当你分离了两个流之后你就会看到标准的结果了。一个简单的方法是重定向流。比如重定向输入流。教你点东西。
假设在你的机器上我的解题程序编译为a.exe。
建立一个文本文件t.txt(和a.exe同目录)。将你的测试数据复制进去。
输入:a<t.txt
看看结果是什么。
上面将输入流重定向到文件。
你还可以试试这样:a<t.txt>t2.txt
执行完后你的目录下会多出t2.txt这个文件,打开看看。
这是将输出流重定向到文件。
举一反三,它们也都可以重定向到程序,由此也可以实现进程之间的信息交互,这就是传说中的管道通信技术,在unix中使用的很多。
scanf, printf这两个函数的强大功能就体现在这里。键盘屏幕的应用对这两个函数实在是太小儿科了。
以后你该知道如何测试大量数据了吧
当然你非要按你的想法做也没什么问题,只不过需要自己维护一个数据缓存区来缓存输出,也就是你代码中realloc部分。这个函数要慎用,这种练习类的编程我就不说什么了,当你做一个规模较的项目时一定要注意检查分配是否成功。

关于占用内存再谈谈我的看法。
时间和空间一直是编程的一对矛盾。想速度快就要消耗空间,想占地少就要牺牲速度。早期的电脑内存往往只有几十K,这一情况下,编程考虑空间的因果会比较多。而现在,我的电脑内存是4G。
就这一题为了存储地图信息,我用了2K的内存,每一个点有一个字节表示。你使用的是位,并且动态分配,所以在地图存储上你消耗的内存最多是我的1/8,确实比我少。但为这点内存你付出的代价是时间。动态分配内存需要时间就不说了。在基于位的运算中消耗了太多的时间。在获取一个位信息的过程中,你要调用一次函数,该函数有两个参数,需要做两次参数赋值,两次压栈,在函数体内需要做两次移位运算和一次与运算。而这些步骤需要在每次查询位时都重复一遍。对于置位操作你使用了参数宏,但只是增加了可读性,效率的改善并不大。
在我价值观下这样的代价过高。我原本考虑过用整型来保存点信息的,这样可以实现字段的对齐,可以进一步提高查询效率,但空间的消耗要再扩大4倍。所以用字节已经是一个折中的选择。
谈谈程序的可扩展性。你选择了一个很合适的变量类型__int64,每一位都没有浪费。
如果我们修改一下题目要求你会怎么做?
现在将地图的范围扩大到100 X 100。
我的代码只需要将那两个宏的数值改成100。你会怎么做?
最后的建议。
将功能部分单独建立函数,别混在main函数里。不便于阅读,也不便于修改。

重剑无锋,大巧不工
2011-06-06 09:11
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 11楼 gupiao175
在论坛发贴就是为了看回贴的。要是都飘过那我以后就不来这个论坛了。如果觉得我的贴子还有点用,就留下你的意见吧!

重剑无锋,大巧不工
2011-06-06 10:22
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
回复 14楼 beyondyf
关于流你不用教我,我并不是这个意思,Java里的IO和C里的IO在我头里都有一个模型,关于重定向更不用说,C Primer Plus里讲得很清楚。

My life is brilliant
2011-06-06 11:08
好孩子好宝贝
Rank: 1
等 级:新手上路
帖 子:35
专家分:2
注 册:2011-7-26
收藏
得分:0 
。。。。。浮云,要是数据到三千了。。你们的都不行。
而且在ACM上的数据就是3000*3000;
#include<stdio.h>
#define MAXN 3000
#define MAXM 3000

int i,j,n,m,temp,max,a[MAXN][MAXM];

int min(int x,int y,int z)
{
    int temp;
    if (x<y) temp=x; else temp=y;
    if (z<temp) temp=z;
    return temp;
}

int fun()
{
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            scanf("%d",&temp);
            if (temp==1) a[i][j]=0;
            else a[i][j]=min(a[i-1][j-1],a[i][j-1],a[i-1][j])+1;
        }
        
    max=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (a[i][j]>max) max=a[i][j];
            
    printf("%d\n",max);
    scanf("%d %d",&n,&m);
    return 0;
}

int main()
{
    scanf("%d %d",&n,&m);
    while (n!=0) fun();
    return 0;
}
2011-07-26 19:43
好孩子好宝贝
Rank: 1
等 级:新手上路
帖 子:35
专家分:2
注 册:2011-7-26
收藏
得分:0 
http://www.
2011-07-26 19:46
好孩子好宝贝
Rank: 1
等 级:新手上路
帖 子:35
专家分:2
注 册:2011-7-26
收藏
得分:0 
http://www.
2011-07-26 19:47
好孩子好宝贝
Rank: 1
等 级:新手上路
帖 子:35
专家分:2
注 册:2011-7-26
收藏
得分:0 
上面那位写那么多的先生,一看你的代码就错啦。。。
不信你用测试数据
3 4
0 0 0 0
1 1 1 1
0 0 0 0

还有好多数据都错啦,那个不过你运气好碰对啦。
3 4
0 0 0 0
0 0 0 0
1 1 1 1
2011-07-26 20:20
快速回复:再出一题(祭祀广场)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.091429 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved