Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

哈哈哈哈哈.又是这种经典题目......我来弱弱滴给大家讲解一下~~~

Posted by sgxiao at 2008-02-14 04:14:22 on Problem 2696

首先清大家注意一下审题...

1 .题目里面的mod运算并不是C语言里面的% ,并不是单纯的取余数.我写一下mod的伪代码

mod( p, q) {
	int r;
	
	for r = 0 to q - 1 {
		if  (p - r) 可以被 q 整除  {
                         返回 r
                }
	}
}

具体代码我就不写了...其实这个地方我使用了一个for循环...其实在这里还是可以使用别的方式优化的,只是因为我偷懒,所以就穷举所有r的可能了.


所以很多人按照题目所写的 mod运算符使用 %当然是错的....这点希望同学们认真审题.


2 这题看似要我们用递归解决....但是题目已经很明显滴提示了...直接使用递归的话,当i相当大,接近于1000的时候,程序运行的时间接近forever!!!!!!! 为什么呢?

    我们来仔细分析一下,现在假设我的函数名称称作d();
则当i = 4的时候;
    递归函数的执行情况如下
/********************/
    d(4)
             d(3)
             d(2)
             d(1)
/********************/


这个情况下面貌似速度影响不大,,,,,,但是..要是i = 999的时候,问题就来了
/*******************/
    d(999)
               d(998)
                           d(997)                                                         d(4)
                           d(996)                                                                  d(3)
                           d(995)                                                                  d(2)
               d(997)                                                                              d(1)
                           d(996)                      ................                      . 
                           d(995)               (中间这里历尽千山万水)            . (这里有很多很多的d(4) )
                           d(994)                                                            .
               d(996)
                           d(995)                                                        d(4)       ......
                           d(994)                                                        d(4)       ......
                           d(993)                                                        d(4)       ......
/******************/


我相信大家已经对这个过程有了一个更加深刻的了解了,我们就从上图用手指来算.....d(997)的结果都调用了至少两次, 这两次,虽然返回的结果一样...但是往下还是继续往下递归.....这样子.是不是相当于重复做了两次吃力不讨好的事情呢?d(997)尚如此,那么d(4)谁可以告诉我做了多少次吃力不讨好的劳动?呵呵.......那么如果我们在第一次运算的时候把d(i)的结果保存起来,那么下次要用到的时候直接从这里面取出来,是不是就会很多了呢?没错...这正是这题的精妙所在.....
            
那么,这个保存的结果我应该放哪里呢?我们来看看i的范围....0 ~ 1000....很明显...一个普通的int足以存放i......每个i对应一个d(i)的结果.太明显了我们应该开一个i大小的数组...我称做dp[]....
把每个d(i)的结果保存在 dp[i]里面.....是不是如果我要拿结果的时候,取d(i)的结果是不是直接就可以从对应下标的dp[i]里面取出来了呢?没错了....所以我自己写的函数d如下:

int d(int i) {
      return dp[i];
}



哈哈哈哈哈哈哈.....太简单,太有才了是不是?有些人第一反应就是"打表",hoho.....其实,这个跟所谓的"打表"可是有本质的区别....首先,打表本身就是一种非常无耻的做法..我个人认为....其次...就算这个是打表,这个表也是在程序执行的过程中,边执行边"打"的,绝对比事先打好表的那种情况技术含靓要高.

我们以上所说的这些结果,实际上, 采用了一种叫做动态规划的策略(dynamic programming   简称dp,,,,,所以我的数组也用这个命名). 而实际上dp的策略有更加复杂的情况,这里就先不说了....本题目出现的情况是dp中最简单的一种......简单到甚至有一些高手都不认为这是一种dp...

dp的经典问题是(0-1背包问题)....这个问题我们如果要采用一个数组保存中间结果的话.....至少开的是一个三维的数组.....相比之下...本题目我们开一维数组的情况就可以算是相当滴简单了....更加详细的关于dp的内容欢迎大家参阅<Introduction to algorithms>里面的相关内容.

Followed by:

这个人太有才啦！拖出去斩了！ (0) shuaia 2008-02-15 18:05:18
楼主码了很多字，其中还有山水画，这个要顶起~ (0) iShowFun 2009-03-14 22:43:03
Re:哈哈哈哈哈.又是这种经典题目......我来弱弱滴给大家讲解一下~~~ (11) chenweiwei 2009-06-24 14:11:14
Re:哈哈哈哈哈.又是这种经典题目......我来弱弱滴给大家讲解一下~~~ (9) zuqiuxiaozi0402 2009-08-13 19:19:36
Re:哈哈哈哈哈.又是这种经典题目......我来弱弱滴给大家讲解一下~~~ (17) Rieman 2009-10-12 16:19:27
Re:哈哈哈哈哈.又是这种经典题目......我来弱弱滴给大家讲解一下~~~ (12) new_begin 2009-11-03 22:15:47
Re:中间这里历尽千山万水 (52) tzkq 2010-06-06 20:33:37
鉴定完毕~~兰州拖出去枪毙5分钟……害得我以为是什么难题呢！！！ (2) wsj19911101 2010-11-30 12:48:27

Post your reply here:

User ID:
Password:
Title:

Content:

> 首先清大家注意一下审题...
> 
> 1 .题目里面的mod运算并不是C语言里面的% ,并不是单纯的取余数.我写一下mod的伪代码
> 
> mod( p, q) {
> 	int r;
> 	
> 	for r = 0 to q - 1 {
> 		if  (p - r) 可以被 q 整除  {
>                          返回 r
>                 }
> 	}
> }
> 
> 具体代码我就不写了...其实这个地方我使用了一个for循环...其实在这里还是可以使用别的方式优化的,只是因为我偷懒,所以就穷举所有r的可能了.
> 
> 
> 所以很多人按照题目所写的 mod运算符使用 %当然是错的....这点希望同学们认真审题.
> 
> 
> 2 这题看似要我们用递归解决....但是题目已经很明显滴提示了...直接使用递归的话,当i相当大,接近于1000的时候,程序运行的时间接近forever!!!!!!! 为什么呢?
> 
>     我们来仔细分析一下,现在假设我的函数名称称作d();
> 则当i = 4的时候;
>     递归函数的执行情况如下
> /********************/
>     d(4)
>              d(3)
>              d(2)
>              d(1)
> /********************/
> 
> 
> 这个情况下面貌似速度影响不大,,,,,,但是..要是i = 999的时候,问题就来了
> /*******************/
>     d(999)
>                d(998)
>                            d(997)                                                         d(4)
>                            d(996)                                                                  d(3)
>                            d(995)                                                                  d(2)
>                d(997)                                                                              d(1)
>                            d(996)                      ................                      . 
>                            d(995)               (中间这里历尽千山万水)            . (这里有很多很多的d(4) )
>                            d(994)                                                            .
>                d(996)
>                            d(995)                                                        d(4)       ......
>                            d(994)                                                        d(4)       ......
>                            d(993)                                                        d(4)       ......
> /******************/
> 
> 
> 我相信大家已经对这个过程有了一个更加深刻的了解了,我们就从上图用手指来算.....d(997)的结果都调用了至少两次, 这两次,虽然返回的结果一样...但是往下还是继续往下递归.....这样子.是不是相当于重复做了两次吃力不讨好的事情呢?d(997)尚如此,那么d(4)谁可以告诉我做了多少次吃力不讨好的劳动?呵呵.......那么如果我们在第一次运算的时候把d(i)的结果保存起来,那么下次要用到的时候直接从这里面取出来,是不是就会很多了呢?没错...这正是这题的精妙所在.....
>             
> 那么,这个保存的结果我应该放哪里呢?我们来看看i的范围....0 ~ 1000....很明显...一个普通的int足以存放i......每个i对应一个d(i)的结果.太明显了我们应该开一个i大小的数组...我称做dp[]....
> 把每个d(i)的结果保存在 dp[i]里面.....是不是如果我要拿结果的时候,取d(i)的结果是不是直接就可以从对应下标的dp[i]里面取出来了呢?没错了....所以我自己写的函数d如下:
> 
> int d(int i) {
>       return dp[i];
> }
> 
> 
> 
> 哈哈哈哈哈哈哈.....太简单,太有才了是不是?有些人第一反应就是"打表",hoho.....其实,这个跟所谓的"打表"可是有本质的区别....首先,打表本身就是一种非常无耻的做法..我个人认为....其次...就算这个是打表,这个表也是在程序执行的过程中,边执行边"打"的,绝对比事先打好表的那种情况技术含靓要高.
> 
> 我们以上所说的这些结果,实际上, 采用了一种叫做动态规划的策略(dynamic programming   简称dp,,,,,所以我的数组也用这个命名). 而实际上dp的策略有更加复杂的情况,这里就先不说了....本题目出现的情况是dp中最简单的一种......简单到甚至有一些高手都不认为这是一种dp...
> 
> dp的经典问题是(0-1背包问题)....这个问题我们如果要采用一个数组保存中间结果的话.....至少开的是一个三维的数组.....相比之下...本题目我们开一维数组的情况就可以算是相当滴简单了....更加详细的关于dp的内容欢迎大家参阅<Introduction to algorithms>里面的相关内容.
> 
> 
>

Home Page Go Back To top