[CPyUG] 谁看懂了算法导论第二版,16.1 的证明

classic Classic list List threaded Threaded
22 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
麻烦解释一下这个定理的证明过程, 尤其是第一点。

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Rujia Liu
贴一下相关文字呗,手头没书。。。

2010/8/24 Zhang Jiawei <[hidden email]>:
> 麻烦解释一下这个定理的证明过程, 尤其是第一点。
>
> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
不太好贴,里面有些公式是图片,复制不过来。

麻烦手头有书的看看。

在 2010年8月24日 上午10:06,Rujia Liu <[hidden email]>写道:
贴一下相关文字呗,手头没书。。。

2010/8/24 Zhang Jiawei <[hidden email]>:
> 麻烦解释一下这个定理的证明过程, 尤其是第一点。
>
> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Kermit Mei
On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


    你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
    我觉得这是个态度问题……


> 在 2010年8月24日 上午10:06,Rujia Liu <[hidden email]>写道:
>         贴一下相关文字呗,手头没书。。。
>        
>         2010/8/24 Zhang Jiawei <[hidden email]>:
>         > 麻烦解释一下这个定理的证明过程, 尤其是第一点。
>         >
>         > --
>         > 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发
>         言:[hidden email]
>         > 退订: http://tinyurl.com/45a9tb //针对163/qq邮
>         箱:http://tinyurl.com/4dg6hc
>         > 详情: https://groups.google.com/group/python-cn
>         > 严正: 理解列表! 智慧提问!
>         http://wiki.woodpecker.org.cn/moin/AskForHelp
>         >
>        
>         --
>         来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发
>         言:[hidden email]
>         退订: http://tinyurl.com/45a9tb //针对163/qq邮
>         箱:http://tinyurl.com/4dg6hc
>         详情: https://groups.google.com/group/python-cn
>         严正: 理解列表! 智慧提问!
>         http://wiki.woodpecker.org.cn/moin/AskForHelp
>
>
>
> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮
> 箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问!
> http://wiki.woodpecker.org.cn/moin/AskForHelp


--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

amingsc


在 2010年8月24日 上午10:33,Kermit Mei <[hidden email]>写道:
On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


   你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
   我觉得这是个态度问题……
哈哈哈。。把我想说的话说了~ 唉 不过每个人都有自己不同的想法吧,或许人家也根本没想要我们给什么帮助,所以咱局外人也别太着急了 :D 

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

机械唯物主义 : linjunhalida
大哥,算法问题请去toplanguage,不要在python社区里面发。


2010/8/24 amingsc <[hidden email]>


在 2010年8月24日 上午10:33,Kermit Mei <[hidden email]>写道:

On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


   你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
   我觉得这是个态度问题……
哈哈哈。。把我想说的话说了~ 唉 不过每个人都有自己不同的想法吧,或许人家也根本没想要我们给什么帮助,所以咱局外人也别太着急了 :D 

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻烦,我也没义务让您看是不是?
能帮忙看看就看看,帮不到捧个人场,谢谢。

我在toplanguage错发了个帖子,被禁言了,发不过去了。

在 2010年8月24日 上午10:50,机械唯物主义 : linjunhalida <[hidden email]>写道:
大哥,算法问题请去toplanguage,不要在python社区里面发。


2010/8/24 amingsc <[hidden email]>



在 2010年8月24日 上午10:33,Kermit Mei <[hidden email]>写道:

On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


   你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
   我觉得这是个态度问题……
哈哈哈。。把我想说的话说了~ 唉 不过每个人都有自己不同的想法吧,或许人家也根本没想要我们给什么帮助,所以咱局外人也别太着急了 :D 

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

机械唯物主义 : linjunhalida
还是建议你去找管理员认错,而不是在不相干的maillist发不相关的东西。

2010/8/24 Zhang Jiawei <[hidden email]>
有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻烦,我也没义务让您看是不是?
能帮忙看看就看看,帮不到捧个人场,谢谢。

我在toplanguage错发了个帖子,被禁言了,发不过去了。

在 2010年8月24日 上午10:50,机械唯物主义 : linjunhalida <[hidden email]>写道:

大哥,算法问题请去toplanguage,不要在python社区里面发。


2010/8/24 amingsc <[hidden email]>



在 2010年8月24日 上午10:33,Kermit Mei <[hidden email]>写道:

On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


   你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
   我觉得这是个态度问题……
哈哈哈。。把我想说的话说了~ 唉 不过每个人都有自己不同的想法吧,或许人家也根本没想要我们给什么帮助,所以咱局外人也别太着急了 :D 

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
呃。。。

我和莫管理员沟通过了,他说一周以后开禁。

我也没啥错,就是敲错了一个快捷键发了个垃圾邮件。

再者,python 论坛为啥不能发算法问题?

请指教,谢谢。

在 2010年8月24日 上午11:16,机械唯物主义 : linjunhalida <[hidden email]>写道:
还是建议你去找管理员认错,而不是在不相干的maillist发不相关的东西。

2010/8/24 Zhang Jiawei <[hidden email]>
有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻烦,我也没义务让您看是不是?

能帮忙看看就看看,帮不到捧个人场,谢谢。

我在toplanguage错发了个帖子,被禁言了,发不过去了。

在 2010年8月24日 上午10:50,机械唯物主义 : linjunhalida <[hidden email]>写道:

大哥,算法问题请去toplanguage,不要在python社区里面发。


2010/8/24 amingsc <[hidden email]>



在 2010年8月24日 上午10:33,Kermit Mei <[hidden email]>写道:

On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


   你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
   我觉得这是个态度问题……
哈哈哈。。把我想说的话说了~ 唉 不过每个人都有自己不同的想法吧,或许人家也根本没想要我们给什么帮助,所以咱局外人也别太着急了 :D 

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

机械唯物主义 : linjunhalida
至少也要和python相关吧。。。。
比如用python实现某个算法之类。
不然长此以往,大家都发其他的贴,
那maillist的价值就不存在了。这也是为什么toplanguage那么严格的原因。我也因为被linkin黑过一次被禁言一周。
python-cn要求不那么严格,结果就是现在这么水。

2010/8/24 Zhang Jiawei <[hidden email]>
呃。。。

我和莫管理员沟通过了,他说一周以后开禁。

我也没啥错,就是敲错了一个快捷键发了个垃圾邮件。

再者,python 论坛为啥不能发算法问题?

请指教,谢谢。

在 2010年8月24日 上午11:16,机械唯物主义 : linjunhalida <[hidden email]>写道:

还是建议你去找管理员认错,而不是在不相干的maillist发不相关的东西。

2010/8/24 Zhang Jiawei <[hidden email]>
有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻烦,我也没义务让您看是不是?

能帮忙看看就看看,帮不到捧个人场,谢谢。

我在toplanguage错发了个帖子,被禁言了,发不过去了。

在 2010年8月24日 上午10:50,机械唯物主义 : linjunhalida <[hidden email]>写道:

大哥,算法问题请去toplanguage,不要在python社区里面发。


2010/8/24 amingsc <[hidden email]>



在 2010年8月24日 上午10:33,Kermit Mei <[hidden email]>写道:

On Tue, 2010-08-24 at 10:15 +0800, Zhang Jiawei wrote:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。


   你想一下,你既然说公式是图片,那别人怎么回复你?你都懒得打字,还要别
人给你打吗?
   我觉得这是个态度问题……
哈哈哈。。把我想说的话说了~ 唉 不过每个人都有自己不同的想法吧,或许人家也根本没想要我们给什么帮助,所以咱局外人也别太着急了 :D 

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Kermit Mei
In reply to this post by Zhang Jiawei
On Tue, 2010-08-24 at 11:13 +0800, Zhang Jiawei wrote:
> 有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻
> 烦,我也没义务让您看是不是?
> 能帮忙看看就看看,帮不到捧个人场,谢谢。

    如果回复您的人也需要这些符合,那别人怎么回复?
    我倒是不觉得您发算法问题在这里不合适,但到底也用Python修饰下吧,呵
呵:)
    找个电子版,切个小图(千万不能往列表里发大附件)发过来,可能都比您在这
里要求别人“捧场”好吧,社区毕竟不是路边的人堆儿吧。
    我没有指责您的意思,只是希望您能认识到,遵守一些提问的规则,对我们大
家都有好处。


B.R
Kermit


--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Rujia Liu
同意Kermit。本来我很有欲望回复lz的,可是手里真没书,也没电子版,就没办法了,呵呵。
算法导论第二版我中学的时候就看完了(看的英文pdf),就算你只贴个小图片我也基本能想起来是啥,不过确实不记得16.1是什么了。
如果求知欲够强烈的话,不管是找电子版、扫描、照相或者用手敲,总会有办法把它发出来的。

另外,要发和python无关的东西也没关系,但请加OT。不然管理员会很郁闷的

2010/8/24 Kermit Mei <[hidden email]>:

> On Tue, 2010-08-24 at 11:13 +0800, Zhang Jiawei wrote:
>> 有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻
>> 烦,我也没义务让您看是不是?
>> 能帮忙看看就看看,帮不到捧个人场,谢谢。
>
>    如果回复您的人也需要这些符合,那别人怎么回复?
>    我倒是不觉得您发算法问题在这里不合适,但到底也用Python修饰下吧,呵
> 呵:)
>    找个电子版,切个小图(千万不能往列表里发大附件)发过来,可能都比您在这
> 里要求别人"捧场"好吧,社区毕竟不是路边的人堆儿吧。
>    我没有指责您的意思,只是希望您能认识到,遵守一些提问的规则,对我们大
> 家都有好处。
>
>
> B.R
> Kermit
>
>
> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
In reply to this post by Kermit Mei
我这么发,因为基于我的判断,没有书,只发字是说不清楚这个问题的。

theorem 16.1 要解释这个证明,前后大概要翻4,5页纸,我只贴一段或者截图,远远不够。

再者,如果没有读过这本书的朋友,估计只看这个章节也还不够,还需要前面后面的章节也翻翻,那涉及的页数更多。

这个定理前后,我已经翻过很多遍,估计知道答案的朋友只需要提点一下,即可理解,所以不需要贴大段公式和图片来回复我,如果我还不能理解,那可以私下交流,电话,当面都可以。

那我只能在这里澄清一下,希望读过这本书,而且手头有这本书的朋友,麻烦看一下。

在 2010年8月24日 上午11:37,Kermit Mei <[hidden email]>写道:
On Tue, 2010-08-24 at 11:13 +0800, Zhang Jiawei wrote:
> 有些集合符号,我用键盘敲不出来,如果手头有书就麻烦看看,没有书,您嫌麻
> 烦,我也没义务让您看是不是?
> 能帮忙看看就看看,帮不到捧个人场,谢谢。

   如果回复您的人也需要这些符合,那别人怎么回复?
   我倒是不觉得您发算法问题在这里不合适,但到底也用Python修饰下吧,呵
呵:)
   找个电子版,切个小图(千万不能往列表里发大附件)发过来,可能都比您在这
里要求别人“捧场”好吧,社区毕竟不是路边的人堆儿吧。
   我没有指责您的意思,只是希望您能认识到,遵守一些提问的规则,对我们大
家都有好处。


B.R
Kermit


--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Elias Soong-2
In reply to this post by Zhang Jiawei

于 10-8-24 上午10:15, Zhang Jiawei 写道:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。
>

手机照一下弄上来,大致能看清也就得了。。手头确实没书。。

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
http://download.csdn.net/source/1030057

这里可以下载。Page 320


在 2010年8月24日 下午12:04,Elias Soong <[hidden email]>写道:

于 10-8-24 上午10:15, Zhang Jiawei 写道:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。
>

手机照一下弄上来,大致能看清也就得了。。手头确实没书。。

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Eric Miao-2

好吧,我很无聊的帮忙帖一下吧


Theorem 16.1

Consider any nonempty subproblem Sij, and let am be the activity in Sij with the earliest finish

time:

fm = min {fk : ak _ Sij}.

Then

1. Activity am is used in some maximum-size subset of mutually compatible activities of

Sij.

2. The subproblem Sim is empty, so that choosing am leaves the subproblem Smj as the

only one that may be nonempty.

Proof We shall prove the second part first, since it's a bit simpler. Suppose that Sim is

nonempty, so that there is some activity ak such that fi sk < fk sm < fm. Then ak is also in Sij

and it has an earlier finish time than am, which contradicts our choice of am. We conclude that

Sim is empty.

To prove the first part, we suppose that Aij is a maximum-size subset of mutually compatible

activities of Sij, and let us order the activities in Aij in monotonically increasing order of finish

time. Let ak be the first activity in Aij. If ak = am, we are done, since we have shown that am is

used in some maximum-size subset of mutually compatible activities of Sij. If ak am, we

construct the subset The activities in are disjoint, since the activities in Aij

are, ak is the first activity in Aij to finish, and fm fk. Noting that has the same number of

activities as Aij, we see that is a maximum-size subset of mutually compatible activities of

Sij that includes am.


2010/8/24 Zhang Jiawei <[hidden email]>
http://download.csdn.net/source/1030057

这里可以下载。Page 320


在 2010年8月24日 下午12:04,Elias Soong <[hidden email]>写道:


于 10-8-24 上午10:15, Zhang Jiawei 写道:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。
>

手机照一下弄上来,大致能看清也就得了。。手头确实没书。。

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Rujia Liu
哦,原来是这个啊。

说直白点,就是:任取一个不包含a_m的最优方案,把这个方案中**最早**的一个activity替换成a_m后仍然是合法方案。

- Rujia

2010/8/24 Eric Miao <[hidden email]>:

> 好吧,我很无聊的帮忙帖一下吧
>
> Theorem 16.1
>
> Consider any nonempty subproblem Sij, and let am be the activity in Sij with
> the earliest finish
>
> time:
>
> fm = min {fk : ak _ Sij}.
>
> Then
>
> 1. Activity am is used in some maximum-size subset of mutually compatible
> activities of
>
> Sij.
>
> 2. The subproblem Sim is empty, so that choosing am leaves the subproblem
> Smj as the
>
> only one that may be nonempty.
>
> Proof We shall prove the second part first, since it's a bit simpler.
> Suppose that Sim is
>
> nonempty, so that there is some activity ak such that fi ≤ sk < fk ≤ sm <
> fm. Then ak is also in Sij
>
> and it has an earlier finish time than am, which contradicts our choice of
> am. We conclude that
>
> Sim is empty.
>
> To prove the first part, we suppose that Aij is a maximum-size subset of
> mutually compatible
>
> activities of Sij, and let us order the activities in Aij in monotonically
> increasing order of finish
>
> time. Let ak be the first activity in Aij. If ak = am, we are done, since we
> have shown that am is
>
> used in some maximum-size subset of mutually compatible activities of Sij.
> If ak ≠ am, we
>
> construct the subset The activities in are disjoint, since the activities in
> Aij
>
> are, ak is the first activity in Aij to finish, and fm ≤ fk. Noting that has
> the same number of
>
> activities as Aij, we see that is a maximum-size subset of mutually
> compatible activities of
>
> Sij that includes am.
>
> 2010/8/24 Zhang Jiawei <[hidden email]>
>>
>> http://download.csdn.net/source/1030057
>>
>> 这里可以下载。Page 320
>>
>>
>> 在 2010年8月24日 下午12:04,Elias Soong <[hidden email]>写道:
>>>
>>> 于 10-8-24 上午10:15, Zhang Jiawei 写道:
>>> > 不太好贴,里面有些公式是图片,复制不过来。
>>> >
>>> > 麻烦手头有书的看看。
>>> >
>>>
>>> 手机照一下弄上来,大致能看清也就得了。。手头确实没书。。
>>>
>>> --
>>> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
>>> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
>>> 详情: https://groups.google.com/group/python-cn
>>> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>>
>> --
>> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
>> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
>> 详情: https://groups.google.com/group/python-cn
>> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>
> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
In reply to this post by Eric Miao-2
多谢您贴了,不过喽了文字描述里的公式。。。 哎。。。

在 2010年8月24日 下午1:20,Eric Miao <[hidden email]>写道:

好吧,我很无聊的帮忙帖一下吧


Theorem 16.1

Consider any nonempty subproblem Sij, and let am be the activity in Sij with the earliest finish

time:

fm = min {fk : ak _ Sij}.

Then

1. Activity am is used in some maximum-size subset of mutually compatible activities of

Sij.

2. The subproblem Sim is empty, so that choosing am leaves the subproblem Smj as the

only one that may be nonempty.

Proof We shall prove the second part first, since it's a bit simpler. Suppose that Sim is

nonempty, so that there is some activity ak such that fi sk < fk sm < fm. Then ak is also in Sij

and it has an earlier finish time than am, which contradicts our choice of am. We conclude that

Sim is empty.

To prove the first part, we suppose that Aij is a maximum-size subset of mutually compatible

activities of Sij, and let us order the activities in Aij in monotonically increasing order of finish

time. Let ak be the first activity in Aij. If ak = am, we are done, since we have shown that am is

used in some maximum-size subset of mutually compatible activities of Sij. If ak am, we

construct the subset The activities in are disjoint, since the activities in Aij

are, ak is the first activity in Aij to finish, and fm fk. Noting that has the same number of

activities as Aij, we see that is a maximum-size subset of mutually compatible activities of

Sij that includes am.


2010/8/24 Zhang Jiawei <[hidden email]>
http://download.csdn.net/source/1030057


这里可以下载。Page 320


在 2010年8月24日 下午12:04,Elias Soong <[hidden email]>写道:


于 10-8-24 上午10:15, Zhang Jiawei 写道:
> 不太好贴,里面有些公式是图片,复制不过来。
>
> 麻烦手头有书的看看。
>

手机照一下弄上来,大致能看清也就得了。。手头确实没书。。

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Zhang Jiawei
In reply to this post by Rujia Liu
A'ij = Aij - {ak} U {am}

请问这个表达式为什么是你说的替换的意思。

再者,如果已经有 最优方案 Aij, 为何还会有 A'ij ,他这里是想反证 A'ij = Aij 吗?

在 2010年8月24日 下午1:54,Rujia Liu <[hidden email]>写道:
哦,原来是这个啊。

说直白点,就是:任取一个不包含a_m的最优方案,把这个方案中**最早**的一个activity替换成a_m后仍然是合法方案。

- Rujia

2010/8/24 Eric Miao <[hidden email]>:
> 好吧,我很无聊的帮忙帖一下吧
>
> Theorem 16.1
>
> Consider any nonempty subproblem Sij, and let am be the activity in Sij with
> the earliest finish
>
> time:
>
> fm = min {fk : ak _ Sij}.
>
> Then
>
> 1. Activity am is used in some maximum-size subset of mutually compatible
> activities of
>
> Sij.
>
> 2. The subproblem Sim is empty, so that choosing am leaves the subproblem
> Smj as the
>
> only one that may be nonempty.
>
> Proof We shall prove the second part first, since it's a bit simpler.
> Suppose that Sim is
>
> nonempty, so that there is some activity ak such that fi ≤ sk < fk ≤ sm <
> fm. Then ak is also in Sij
>
> and it has an earlier finish time than am, which contradicts our choice of
> am. We conclude that
>
> Sim is empty.
>
> To prove the first part, we suppose that Aij is a maximum-size subset of
> mutually compatible
>
> activities of Sij, and let us order the activities in Aij in monotonically
> increasing order of finish
>
> time. Let ak be the first activity in Aij. If ak = am, we are done, since we
> have shown that am is
>
> used in some maximum-size subset of mutually compatible activities of Sij.
> If ak ≠ am, we
>
> construct the subset The activities in are disjoint, since the activities in
> Aij
>
> are, ak is the first activity in Aij to finish, and fm ≤ fk. Noting that has
> the same number of
>
> activities as Aij, we see that is a maximum-size subset of mutually
> compatible activities of
>
> Sij that includes am.
>
> 2010/8/24 Zhang Jiawei <[hidden email]>
>>
>> http://download.csdn.net/source/1030057
>>
>> 这里可以下载。Page 320
>>
>>
>> 在 2010年8月24日 下午12:04,Elias Soong <[hidden email]>写道:
>>>
>>> 于 10-8-24 上午10:15, Zhang Jiawei 写道:
>>> > 不太好贴,里面有些公式是图片,复制不过来。
>>> >
>>> > 麻烦手头有书的看看。
>>> >
>>>
>>> 手机照一下弄上来,大致能看清也就得了。。手头确实没书。。
>>>
>>> --
>>> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
>>> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
>>> 详情: https://groups.google.com/group/python-cn
>>> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>>
>> --
>> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
>> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
>> 详情: https://groups.google.com/group/python-cn
>> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>
> --
> 来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
> 退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
> 详情: https://groups.google.com/group/python-cn
> 严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
>

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
Reply | Threaded
Open this post in threaded view
|

Re: [CPyUG] 谁看懂了算法导论第二版,16.1 的证明

Rujia Liu
2010/8/24 Zhang Jiawei <[hidden email]>:
> A'ij = Aij - {ak} U {am}
>
> 请问这个表达式为什么是你说的替换的意思。
ak就是我说的“最早的一个activity”
"let us order the activities in Aij in monotonically increasing order
of finish time. Let ak be the first activity in Aij."
减去ak加上am,就相当于用am替换ak

> 再者,如果已经有 最优方案 Aij, 为何还会有 A'ij ,他这里是想反证 A'ij = Aij 吗?
A'ij是啥?刚才的转帖没有啊。我懒得去csdn看了。不管怎样,我觉得你不必拘泥于这些表达式。稍微画画就能想明白了。

- Rujia

--
来自: `python-cn`:CPyUG ~ 华蟒用户组 | 发言:[hidden email]
退订: http://tinyurl.com/45a9tb //针对163/qq邮箱:http://tinyurl.com/4dg6hc
详情: https://groups.google.com/group/python-cn
严正: 理解列表! 智慧提问! http://wiki.woodpecker.org.cn/moin/AskForHelp
12