[今天我们思考09]涉及到n的问题
28 views
Skip to first unread message
pongba
Apr 21, 2008, 4:08:34 AM4/21/08
to TopLanguage
不知不觉这个主题讨论已经进行到第9期了:-) 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
1. 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j] 最小。
下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
3. 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
==============
附录1：上传了科朗的经典之作，《What is Mathematics》的完美高清无码OCR版。
附录2：附上sanachilleus老大上次提供的好几道自己的题目。
首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba
希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
1. 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j] 最小。
下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
3. 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
==============
附录1：上传了科朗的经典之作，《What is Mathematics》的完美高清无码OCR版。
附录2：附上sanachilleus老大上次提供的好几道自己的题目。
首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
数列的秩就是这一行数的个数；
一个数列中任意去掉几个元素，剩下的就是一个子数列；
把一个数列分成互不相交的"几份"，就是数列的一个拆分。
我的问题是：
1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
最小值。
2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
sanachilleus老大自己的思考在这里。一个数列中任意去掉几个元素，剩下的就是一个子数列；
把一个数列分成互不相交的"几份"，就是数列的一个拆分。
我的问题是：
1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
最小值。
2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba
hayate
Apr 21, 2008, 7:24:00 AM4/21/08
to pon...@googlegroups.com
zan 高清无码
第一题我看到以后首先想抽象一下，把这种认识关系抽象成有向图，题目就变成n个节点的有向图(邻接矩阵表示)，一个O(n)的算法找出是否存在一个节点的入度为n-1，出度为0。
第一题我看到以后首先想抽象一下，把这种认识关系抽象成有向图，题目就变成n个节点的有向图(邻接矩阵表示)，一个O(n)的算法找出是否存在一个节点的入度为n-1，出度为0。
2008/4/21 pongba <pon...@gmail.com>:
heave...@gmail.com
Apr 21, 2008, 8:15:06 AM4/21/08
to TopLanguage
关于第一题，有一个疑问，
如果是n个人，那么他们之间的关系就是n2的数量级，
如果遍历一边这些关系，那算法就是o(n2)了？
> 第一题我看到以后首先想抽象一下，把这种认识关系抽象成有向图，题目就变成n个节点的有向图(邻接矩阵表示)，一个O(n)的算法找出是否存在一个节点的入度为 n-1，出度为0。
> > 。
> > 。
如果是n个人，那么他们之间的关系就是n2的数量级，
如果遍历一边这些关系，那算法就是o(n2)了？
> 第一题我看到以后首先想抽象一下，把这种认识关系抽象成有向图，题目就变成n个节点的有向图(邻接矩阵表示)，一个O(n)的算法找出是否存在一个节点的入度为 n-1，出度为0。
> 2008/4/21 pongba <pon...@gmail.com>:
>
> > 不知不觉这个主题讨论已经进行到第9期了:-)
> > 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> > 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> > 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> > 1.
> > 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的 ）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
>
> > 再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
> > 2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j]
> > 最小。
>
> > 下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
> > 3.
> > 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
>
> > ==============
> > 附录1：上传了科朗的经典之作，《What is Mathematics》的完美高清无码OCR版<http://groups.google.com/group/pongba/web/What+is+Mathematics+2ed+Per...>
>
> > 不知不觉这个主题讨论已经进行到第9期了:-)
> > 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> > 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> > 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> > 1.
> > 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的 ）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
>
> > 再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
> > 2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j]
> > 最小。
>
> > 下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
> > 3.
> > 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
>
> > ==============
> > 。
>
> > 附录2：附上sanachilleus老大上次提供的好几道自己的题目。
>
> > 首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
> > 数列的秩就是这一行数的个数；
> > 一个数列中任意去掉几个元素，剩下的就是一个子数列；
> > 把一个数列分成互不相交的"几份"，就是数列的一个拆分。
>
> > 我的问题是：
> > 1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
> > 最小值。
> > 2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
> > 设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
> > 3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
> > 4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
> > 列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
>
> > sanachilleus老大自己的思考在这里<http://groups.google.com/group/pongba/tree/browse_frm/thread/8410bf55...>
> > 附录2：附上sanachilleus老大上次提供的好几道自己的题目。
>
> > 首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
> > 数列的秩就是这一行数的个数；
> > 一个数列中任意去掉几个元素，剩下的就是一个子数列；
> > 把一个数列分成互不相交的"几份"，就是数列的一个拆分。
>
> > 我的问题是：
> > 1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
> > 最小值。
> > 2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
> > 设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
> > 3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
> > 4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
> > 列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
>
> > 。
silwile
Apr 21, 2008, 8:29:01 AM4/21/08
to pon...@googlegroups.com
hayate
Apr 21, 2008, 8:42:49 AM4/21/08
to pon...@googlegroups.com
Justin L
Apr 23, 2008, 2:24:46 AM4/23/08
to TopLanguage
看了下找最小数组的这个题，从题目要求来考虑。一般来说，有两个办法：
1）找出所有负数数组，然后再慢慢增大，尝试连接子数组以便找到和最小的。这样比较麻烦。
2）最小数组满足一个条件就是：和最小。言外之意，只要将整个数组中所有导致和增大的部分剔除，剩下的就是最小和数组了。
剔除的时候，总是有限考虑剔除最大的正数，并且考虑剔除的时候，不要把太多的负数也给剔除出去。
我的思路是：
1）i和j分别从队列的头和尾开始遍历。当找到第一个负数时，i和j停止移动。（即把一个数组首位的正数部分都跳过）
变换后，i和j的位置如图：
==============================
++++ i j+++++
下面做一个设定：将相邻的一组正数用+表示，将相邻的一组负数用-表示。则剩下的数组（称为数组A）：
[+]i-+-+-+- … +-j[+]
可以描述为，描述为：
-+…+-
2）下面在这个数组A中，找到最大的+，然后比较其左右的子数组（不算+本身）
如果+的绝对值大于左右子数组和，则从+处将现有数组一分为二，对左右两个数组分别从1）开始计算，进行迭代计算后，将数组和最小的作为结果。
如果+的绝对值小于左右子数组和，则当前的数组A即为所有。
如果+的绝对值在中间，则从左右子数组中取和最小子数组继续从1）运算。
On 4月21日, 下午4时08分, pongba <pon...@gmail.com> wrote:
> 不知不觉这个主题讨论已经进行到第9期了:-)
> 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
>
1）找出所有负数数组，然后再慢慢增大，尝试连接子数组以便找到和最小的。这样比较麻烦。
2）最小数组满足一个条件就是：和最小。言外之意，只要将整个数组中所有导致和增大的部分剔除，剩下的就是最小和数组了。
剔除的时候，总是有限考虑剔除最大的正数，并且考虑剔除的时候，不要把太多的负数也给剔除出去。
我的思路是：
1）i和j分别从队列的头和尾开始遍历。当找到第一个负数时，i和j停止移动。（即把一个数组首位的正数部分都跳过）
变换后，i和j的位置如图：
==============================
++++ i j+++++
下面做一个设定：将相邻的一组正数用+表示，将相邻的一组负数用-表示。则剩下的数组（称为数组A）：
[+]i-+-+-+- … +-j[+]
可以描述为，描述为：
-+…+-
2）下面在这个数组A中，找到最大的+，然后比较其左右的子数组（不算+本身）
如果+的绝对值大于左右子数组和，则从+处将现有数组一分为二，对左右两个数组分别从1）开始计算，进行迭代计算后，将数组和最小的作为结果。
如果+的绝对值小于左右子数组和，则当前的数组A即为所有。
如果+的绝对值在中间，则从左右子数组中取和最小子数组继续从1）运算。
On 4月21日, 下午4时08分, pongba <pon...@gmail.com> wrote:
> 不知不觉这个主题讨论已经进行到第9期了:-)
> 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
>
Justin L
Apr 23, 2008, 2:40:00 AM4/23/08
to TopLanguage
只是一个想法，还没有形成对应的解决方案。
另外，对于上面第2)部分的处理，有些问题。
如果+的绝对值在中间，则从左右子数组中取和最小子数组继续从1）运算。
这里可能有些不当，应该还是对左右两个数组分别从1）开始计算，进行迭代计算后，将数组和最小的作为结果。
另外，对于上面第2)部分的处理，有些问题。
如果+的绝对值在中间，则从左右子数组中取和最小子数组继续从1）运算。
这里可能有些不当，应该还是对左右两个数组分别从1）开始计算，进行迭代计算后，将数组和最小的作为结果。
Yiming Zhang
Apr 23, 2008, 3:04:23 AM4/23/08
to pon...@googlegroups.com
看到部分朋友会的答案不是太对，也是我第一眼看到想到的思路
这个是我来微软的时候的一道面试题。
当时想到了一个积分的思路。
将数列 a1 a2 a3 a4 ......a(n-1) a(n)
变换成s1 s2 s3 s4 ......s(n-1) s(n)
其中sk = a0+a1...+ak
大家可以沿着想一下，时间效率是O(n)
我用反证法这证明了算法正确
Best regards!
Zhang yiming
Justin L
Apr 23, 2008, 3:28:48 AM4/23/08
to TopLanguage
> 将数列 a1 a2 a3 a4 ......a(n-1) a(n)
> 变换成s1 s2 s3 s4 ......s(n-1) s(n)
这个不就是：
> 变换成s1 s2 s3 s4 ......s(n-1) s(n)
s1 = a1
s2 = s1 + a2
...
s(n) = s(n-1) + a(n)
Justin L
Apr 23, 2008, 3:28:57 AM4/23/08
to TopLanguage
> 将数列 a1 a2 a3 a4 ......a(n-1) a(n)
> 变换成s1 s2 s3 s4 ......s(n-1) s(n)
> 变换成s1 s2 s3 s4 ......s(n-1) s(n)
这个不就是：
s1 = a1
s2 = s1 + a2
...
s(n) = s(n-1) + a(n)
On 4月23日, 下午3时04分, "Yiming Zhang" <oneb...@gmail.com> wrote:
s1 = a1
s2 = s1 + a2
...
s(n) = s(n-1) + a(n)
On 4月23日, 下午3时04分, "Yiming Zhang" <oneb...@gmail.com> wrote:
Yiming Zhang
Apr 23, 2008, 3:43:54 AM4/23/08
to pon...@googlegroups.com
是的。
其中 s(k)- s(t) = a(t+1).... a(k)
所以求出 s(max) s(min) 可以求解
On 4/23/08, Justin L <ice...@gmail.com> wrote:
--
Best Regards
Zhang Yiming
Jiansen Liu
Apr 23, 2008, 5:48:50 AM4/23/08
to pon...@googlegroups.com
> 3. 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他> 的敌人。所谓旁边就是指左右手边不能使他的敌人。
想了会完全没有思路，归纳法也似不好搞，恳请给点提示呢
windstorm
Apr 23, 2008, 8:54:05 AM4/23/08
to pon...@googlegroups.com
想题之前先说一句，What is Mathematics的下载貌似有问题......
2008/4/23 Jiansen Liu <jiansen.l...@gmail.com>:
hayate
Apr 23, 2008, 12:25:03 PM4/23/08
to pon...@googlegroups.com
Eric
Apr 23, 2008, 1:40:51 PM4/23/08
to TopLanguage
我前几天还刚想写博客说这个问题，结果就发现在这儿了，索性就写下来吧
名人问题的关键是理解任意取两个人 看看两个人的认识关系，都可以至少淘汰掉一个人：
比如 A B
A 认识 B, 排除 A
B 认识 A, 排除 B
互相认识 都排除
都不认识 都排除
与此相关的一个问题叫做选总统问题
找出一个数组里面出现次数超过 n/2 的元素
想想，和这个思路是一样的.
这个总统问题可以推广到数据流里面找 Top k 频率的元素的问题
想想怎么用 O(k) 的空间完成这个事情。
http://www.cs.ucsb.edu/~suri/cs130a/Celebrity.txt
题目2 Yiming Zhang 是正解 遇到局部连续求和一般都是找出前缀和
On 4月21日, 上午3时08分, pongba <pon...@gmail.com> wrote:
> 不知不觉这个主题讨论已经进行到第9期了:-)
> 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> 1.
> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
>
> 再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
> 2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j] 最小。
>
> 下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
> 3.
> 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
>
> ==============
> 附录1：上传了科朗的经典之作，《What is
> 。
>
> 附录2：附上sanachilleus老大上次提供的好几道自己的题目。
>
> 首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
> 数列的秩就是这一行数的个数；
> 一个数列中任意去掉几个元素，剩下的就是一个子数列；
> 把一个数列分成互不相交的"几份"，就是数列的一个拆分。
>
> 我的问题是：
> 1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
> 最小值。
> 2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
> 设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
> 3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
> 4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
> 列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
>
> sanachilleus老大自己的思考在这里<http://groups.google.com/group/pongba/tree/browse_frm/thread/8410bf55...>
> 附录2：附上sanachilleus老大上次提供的好几道自己的题目。
>
> 首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
> 数列的秩就是这一行数的个数；
> 一个数列中任意去掉几个元素，剩下的就是一个子数列；
> 把一个数列分成互不相交的"几份"，就是数列的一个拆分。
>
> 我的问题是：
> 1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
> 最小值。
> 2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
> 设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
> 3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
> 4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
> 列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
>
> 。
>
> --
> 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> TopLanguagehttp://groups.google.com/group/pongba
sanachilleus
Apr 24, 2008, 12:55:48 AM4/24/08
to TopLanguage
请问Yiming Zhang老大，当：
Smax = S(m), Smin = S(n),且 m > n的时候怎么处理呢？
On 4月24日, 上午1时40分, Eric <xu.math...@gmail.com> wrote:
> 我前几天还刚想写博客说这个问题，结果就发现在这儿了，索性就写下来吧
>
> 名人问题的关键是理解任意取两个人 看看两个人的认识关系，都可以至少淘汰掉一个人：
>
> 比如 A B
> A 认识 B, 排除 A
> B 认识 A, 排除 B
> 互相认识 都排除
> 都不认识 都排除
>
> 与此相关的一个问题叫做选总统问题
>
> 找出一个数组里面出现次数超过 n/2 的元素
>
> 想想，和这个思路是一样的.
>
> 这个总统问题可以推广到数据流里面找 Top k 频率的元素的问题
> 想想怎么用 O(k) 的空间完成这个事情。
>
> http://www.cs.ucsb.edu/~suri/cs130a/Celebrity.txt
>
> 题目2 Yiming Zhang 是正解 遇到局部连续求和一般都是找出前缀和
>
> On 4月21日, 上午3时08分, pongba <pon...@gmail.com> wrote:
>
>
>
> > 不知不觉这个主题讨论已经进行到第9期了:-)
> > 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> > 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> > 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> > 1.
> > 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的-）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
>
> - 显示引用的文字 -
Smax = S(m), Smin = S(n),且 m > n的时候怎么处理呢？
On 4月24日, 上午1时40分, Eric <xu.math...@gmail.com> wrote:
> 我前几天还刚想写博客说这个问题，结果就发现在这儿了，索性就写下来吧
>
> 名人问题的关键是理解任意取两个人 看看两个人的认识关系，都可以至少淘汰掉一个人：
>
> 比如 A B
> A 认识 B, 排除 A
> B 认识 A, 排除 B
> 互相认识 都排除
> 都不认识 都排除
>
> 与此相关的一个问题叫做选总统问题
>
> 找出一个数组里面出现次数超过 n/2 的元素
>
> 想想，和这个思路是一样的.
>
> 这个总统问题可以推广到数据流里面找 Top k 频率的元素的问题
> 想想怎么用 O(k) 的空间完成这个事情。
>
> http://www.cs.ucsb.edu/~suri/cs130a/Celebrity.txt
>
> 题目2 Yiming Zhang 是正解 遇到局部连续求和一般都是找出前缀和
>
> On 4月21日, 上午3时08分, pongba <pon...@gmail.com> wrote:
>
>
>
> > 不知不觉这个主题讨论已经进行到第9期了:-)
> > 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> > 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> > 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> > 1.
>
> > 再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
> > 2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j] 最小。
>
> > 下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
> > 3.
> > 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
>
> > ==============
> > 附录1：上传了科朗的经典之作，《What is
> > Mathematics》的完美高清无码OCR版<http://groups.google.com/group/pongba/web/What+is+Mathematics+2ed+Per...>
> > 。
>
> > 附录2：附上sanachilleus老大上次提供的好几道自己的题目。
>
> > 首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
> > 数列的秩就是这一行数的个数；
> > 一个数列中任意去掉几个元素，剩下的就是一个子数列；
> > 把一个数列分成互不相交的"几份"，就是数列的一个拆分。
>
> > 我的问题是：
> > 1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
> > 最小值。
> > 2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
> > 设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
> > 3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
> > 4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
> > 列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
>
> > sanachilleus老大自己的思考在这里<http://groups.google.com/group/pongba/tree/browse_frm/thread/8410bf55...>
> > 。
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
> > TopLanguagehttp://groups.google.com/group/pongba- 隐藏被引用文字 -
> > 再下面是一个也许很多人都做过的问题，但是也许有人没有做过或没有仔细思考过就看了答案了。这道题目的思路也非常有价值。
> > 2. 有n个数，有负数有正数，求出和最小的一组紧邻的数。即这样的i,j使得a[i] + a[i+1] + ... + a[j-1] + a[j] 最小。
>
> > 下面一个数学奥赛的题目我也不能判断算不算好题目，但是里面有一步思路是非常典型的，因为当时没有想出来，不然可以向结果迈出一大步的，所以也贴出来：
> > 3.
> > 2n个人，其中每个人最多有n-1个敌人。要证明可以将这2n个人围着一个圆桌坐下来，使得没有人旁边坐着他的敌人。所谓旁边就是指左右手边不能使他的敌人。
>
> > ==============
> > 附录1：上传了科朗的经典之作，《What is
> > Mathematics》的完美高清无码OCR版<http://groups.google.com/group/pongba/web/What+is+Mathematics+2ed+Per...>
> > 。
>
> > 附录2：附上sanachilleus老大上次提供的好几道自己的题目。
>
> > 首先是几个简单的说明：（去掉了几个显然的，免得有人还没看到问题就闪了:P）
> > 数列的秩就是这一行数的个数；
> > 一个数列中任意去掉几个元素，剩下的就是一个子数列；
> > 把一个数列分成互不相交的"几份"，就是数列的一个拆分。
>
> > 我的问题是：
> > 1）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。设m是a[n]秩最大的单调子列的秩。对于1、2、3...n的所有排列，求m的
> > 最小值。
> > 2）对于给定正整数n，数列a[n]是1、2、3...n的一个排列。数列a[n]可以被拆分成有限多个单调数列。对于其中单调子列数最少的一种拆分，
> > 设其单调子列数为m。对于1、2、3...n的所有排列，求m的最大值。
> > 3）对于问题2)中的m，设m = f(n)。那么是否存在正整数M，使得对于任意n，M > f(n)？
> > 4）对于问题2)增强条件：假设拆分出来P个左增数列和Q个右增数列，如果给定正整数X，称使得|P - Q| < X的拆分为合法拆分，对于使单调子
> > 列数最少的拆分，其单调子列数为m'。对于1、2、3...n的所有排列，求m'的最大值。
>
> > sanachilleus老大自己的思考在这里<http://groups.google.com/group/pongba/tree/browse_frm/thread/8410bf55...>
> > 。
>
> > --
> > 刘未鹏(pongba)|C++的罗浮宫http://blog.csdn.net/pongba
>
> - 显示引用的文字 -
Yiming Zhang
Apr 24, 2008, 11:20:57 AM4/24/08
to pon...@googlegroups.com
这个时候 a1到a(n) 就是所求。
上班时间回的 没有说明清楚 只说了思路。
btw 我年纪不大J
sanachilleus
Apr 24, 2008, 11:58:12 AM4/24/08
to TopLanguage
为什么呢？还是想不明白阿。
On 4月24日, 下午11时20分, "Yiming Zhang" <oneb...@gmail.com> wrote:
> 这个时候 a1到a(n) 就是所求。
> 上班时间回的 没有说明清楚 只说了思路。
>
> btw 我年纪不大J
>
> > > > TopLanguagehttp://groups.google.com/group/pongba-隐藏被引用文字 -
>
> - 显示引用的文字 -
On 4月24日, 下午11时20分, "Yiming Zhang" <oneb...@gmail.com> wrote:
> 这个时候 a1到a(n) 就是所求。
> 上班时间回的 没有说明清楚 只说了思路。
>
> btw 我年纪不大J
>
> On 4/24/08, sanachilleus <sanachill...@gmail.com> wrote:
>
>
>
>
>
>
>
> > 请问Yiming Zhang老大，当：
> > Smax = S(m), Smin = S(n),且 m > n的时候怎么处理呢？
>
> > On 4月24日, 上午1时40分, Eric <xu.math...@gmail.com> wrote:
> > > 我前几天还刚想写博客说这个问题，结果就发现在这儿了，索性就写下来吧
>
> > > 名人问题的关键是理解任意取两个人 看看两个人的认识关系，都可以至少淘汰掉一个人：
>
> > > 比如 A B
> > > A 认识 B, 排除 A
> > > B 认识 A, 排除 B
> > > 互相认识 都排除
> > > 都不认识 都排除
>
> > > 与此相关的一个问题叫做选总统问题
>
> > > 找出一个数组里面出现次数超过 n/2 的元素
>
> > > 想想，和这个思路是一样的.
>
> > > 这个总统问题可以推广到数据流里面找 Top k 频率的元素的问题
> > > 想想怎么用 O(k) 的空间完成这个事情。
>
> > >http://www.cs.ucsb.edu/~suri/cs130a/Celebrity.txt
>
> > > 题目2 Yiming Zhang 是正解 遇到局部连续求和一般都是找出前缀和
>
> > > On 4月21日, 上午3时08分, pongba <pon...@gmail.com> wrote:
>
> > > > 不知不觉这个主题讨论已经进行到第9期了:-)
> > > > 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> > > > 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> > > > 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> > > > 1.
>
> > 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的--）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
>
>
>
>
>
>
>
> > 请问Yiming Zhang老大，当：
> > Smax = S(m), Smin = S(n),且 m > n的时候怎么处理呢？
>
> > On 4月24日, 上午1时40分, Eric <xu.math...@gmail.com> wrote:
> > > 我前几天还刚想写博客说这个问题，结果就发现在这儿了，索性就写下来吧
>
> > > 名人问题的关键是理解任意取两个人 看看两个人的认识关系，都可以至少淘汰掉一个人：
>
> > > 比如 A B
> > > A 认识 B, 排除 A
> > > B 认识 A, 排除 B
> > > 互相认识 都排除
> > > 都不认识 都排除
>
> > > 与此相关的一个问题叫做选总统问题
>
> > > 找出一个数组里面出现次数超过 n/2 的元素
>
> > > 想想，和这个思路是一样的.
>
> > > 这个总统问题可以推广到数据流里面找 Top k 频率的元素的问题
> > > 想想怎么用 O(k) 的空间完成这个事情。
>
> > >http://www.cs.ucsb.edu/~suri/cs130a/Celebrity.txt
>
> > > 题目2 Yiming Zhang 是正解 遇到局部连续求和一般都是找出前缀和
>
> > > On 4月21日, 上午3时08分, pongba <pon...@gmail.com> wrote:
>
> > > > 不知不觉这个主题讨论已经进行到第9期了:-)
> > > > 大家感觉怎样？我个人的收获非常大。感谢所有提供思路的老大们给我的启发。感谢silwile提供大量题目以及容忍我经常揪着他唠叨的讨论。
>
> > > > 希望大家多多提供好问题，把这个讨论继续下去。大家可以自己发帖，每次一般两三个好问题，记得将上次的编号+1:-)
>
> > > > 下面是一个上次发出来，没人给出完整解答思路的问题。这是个非常好的问题，思路很典型很有价值。所以再次贴出来：
>
> > > > 1.
>
>
> > > - 显示引用的文字 -
>
> --
> Best Regards
> Zhang Yiming- 隐藏被引用文字 -
> > > - 显示引用的文字 -
>
> --
> Best Regards
>
> - 显示引用的文字 -
Yiming Zhang
Apr 24, 2008, 12:38:20 PM4/24/08
to pon...@googlegroups.com
你可以假设不成立， 答案不是a1 ..a（n） 是 a(k)...a(k+t)
则Smax 或 Smin 不是 max或min
On 4/24/08, sanachilleus <sanach...@gmail.com> wrote:
Yiming Zhang
Apr 24, 2008, 12:43:19 PM4/24/08
to pon...@googlegroups.com
你要有兴趣你可以证明一下（应该可以有比反证法更好理解的方法）
将数列 a1 a2 a3 a4 ......a(n-1) a(n)
变换成s1 s2 s3 s4 ......s(n-1) s(n)
变换成s1 s2 s3 s4 ......s(n-1) s(n)
中sk = a0+a1...+ak
Best Regards
Zhang Yiming
Yiming Zhang
Apr 24, 2008, 12:34:20 PM4/24/08
to pon...@googlegroups.com
就按照你说的归纳法证明的 感觉可能有漏洞啊
我以下证明每个都有n-1个敌人的更严格情况下成立（最多有n-1个敌人的情况可反推）
n=2 的情况可证（略）
假设n=k-1成立
当n=k时 假设新增两个人为 xy
先分两种情况
x 和 y 是 敌人
如果x和y是敌人，那么原来全重肯定有两个y的朋友连续，则y可插入（因为y在原圈中只有n-2个敌人），同理x也有这样的位置可插入。（不会出现连续的两个人都是x和y的朋友的情况，因为每个人至少n-1个敌人）
x 和 y 是 朋友
如果原圈子中有两个x连续的敌人则必有x两个连续的朋友，x插入，这两个朋友中如都是y的敌人，则原圈子必有两个y的连续朋友，如果不都是y的朋友，y可插入x与其中一人中间
如果原圈子中没有x两个连续的敌人和朋友也即一个敌人一个朋友交替，则敌人是y的朋友，朋友是的敌人也可插入
Yiming Zhang
Apr 24, 2008, 9:51:33 PM4/24/08
to pon...@googlegroups.com
不好意思 ，这个我说错了
m>n的时候 数组要从右到左按相同方法求
2008/4/25 Yiming Zhang <one...@gmail.com>:
--
Best Regards
Zhang Yiming
--
Best Regards
Zhang Yiming
sanachilleus
Apr 24, 2008, 11:57:49 PM4/24/08
to TopLanguage
这样好象还是有问题呀。从右到左重新求和指的应该是:
建立数组T[n]，其中T[k] = a[k] + ... + a[n]了吧。
我们给数组a[n]增加两项a[0] = a[n+1] = 0，然后重新定义S[n] 和 T[n]：
S[k] = a[0] + a[1] + ... + a[k]
T[k] = a[k] + a[k+1] + ... + a[n+1]
这样S[n] 和 T[n] 都只是比原来多了一项，别的项不变。
而且有：对任意0 <= k < n + 1， S[k] + T[k+1] = a[1] + ... + a[n]为定值。
那么当Smax = S[p], Smin = S[q] 且 p > q时，
Tmin = T[p+1], Tmax = T[q+1]，问题还是和原来一样......
On 4月25日, 上午9时51分, "Yiming Zhang" <oneb...@gmail.com> wrote:
> 不好意思 ，这个我说错了
>
> m>n的时候 数组要从右到左按相同方法求
>
> 2008/4/25 Yiming Zhang <oneb...@gmail.com>:
> >>> 名人问题：一个名人A是指所有其他人都认识A，A不认识任何其他人。现在给定n个人，以及n个人之间的认识关系（单向的，即"A认识B"和"B认识A"是不同的---）。要求一个O(n)的算法能确定是否存在一个名人，如果存在，给出这个名人。
> >>> > > > > TopLanguagehttp://groups.google.com/group/pongba-隐藏被引用文字<http://groups.google.com/group/pongba-%E9%9A%90%E8%97%8F%E8%A2%AB%E5%...>-
建立数组T[n]，其中T[k] = a[k] + ... + a[n]了吧。
我们给数组a[n]增加两项a[0] = a[n+1] = 0，然后重新定义S[n] 和 T[n]：
S[k] = a[0] + a[1] + ... + a[k]
T[k] = a[k] + a[k+1] + ... + a[n+1]
这样S[n] 和 T[n] 都只是比原来多了一项，别的项不变。
而且有：对任意0 <= k < n + 1， S[k] + T[k+1] = a[1] + ... + a[n]为定值。
那么当Smax = S[p], Smin = S[q] 且 p > q时，
Tmin = T[p+1], Tmax = T[q+1]，问题还是和原来一样......
On 4月25日, 上午9时51分, "Yiming Zhang" <oneb...@gmail.com> wrote:
> 不好意思 ，这个我说错了
>
> m>n的时候 数组要从右到左按相同方法求
>
>
>
>
>
>
> > 你要有兴趣你可以证明一下（应该可以有比反证法更好理解的方法）
>
> > 将数列 a1 a2 a3 a4 ......a(n-1) a(n)
> > 变换成s1 s2 s3 s4 ......s(n-1) s(n)
> > 中sk = a0+a1...+ak
>
>
>
>
>
> > 你要有兴趣你可以证明一下（应该可以有比反证法更好理解的方法）
>
> > 将数列 a1 a2 a3 a4 ......a(n-1) a(n)
> > 变换成s1 s2 s3 s4 ......s(n-1) s(n)
> > 中sk = a0+a1...+ak
>
> > On 4/25/08, Yiming Zhang <oneb...@gmail.com> wrote:
>
> >> 你可以假设不成立， 答案不是a1 ..a（n） 是 a(k)...a(k+t)
> >> 则Smax 或 Smin 不是 max或min
>
>
> >> 你可以假设不成立， 答案不是a1 ..a（n） 是 a(k)...a(k+t)
> >> 则Smax 或 Smin 不是 max或min
>
Yiming Zhang
Apr 25, 2008, 12:17:44 AM4/25/08
to pon...@googlegroups.com
bipe...@gmail.com
Apr 25, 2008, 11:20:56 AM4/25/08
to TopLanguage
怎么实现O（n）呢？
我是实现
维护两个数组， A存放名人，B存放其他人。对每个元素都需要扫描两个数组，所以O(n)是指只扫描一次文件吗？如果不是可以描述下具体算法吗。
我是实现
维护两个数组， A存放名人，B存放其他人。对每个元素都需要扫描两个数组，所以O(n)是指只扫描一次文件吗？如果不是可以描述下具体算法吗。
windstorm
Apr 26, 2008, 5:32:34 AM4/26/08
to pon...@googlegroups.com
第二题不知道可不可以这样
算a[i] + a[i+1] + ... + a[j-1] + a[j] ，用一个for循环算i=0 ===> i=j 的和
sum = min = 0;
for( i=0; i<j; i++ )
{
sum += a[i];
if( sum >0 )
sum = 0;
if( sum < min)
min = sum;
}
2008/4/25 bipe...@gmail.com <bipe...@gmail.com>:
Hongzhang Liu
Apr 27, 2008, 2:30:46 AM4/27/08
to pon...@googlegroups.com
名人问题是不是应该分成两部分？在O(n)的时间内确定不存在名人可能是可行的，但要确定存在名人还是需要遍历所有关系吧？
部洪波
Apr 30, 2008, 3:24:19 AM4/30/08
to pon...@googlegroups.com
按照前面有人提到的排除法的话，那么就每排除一个人的同时完全删除这个人的认识关系（他到其它人的认识关系）。可是如果删除了这些关系，最后又怎么判断所有人都认识这个名人呢？
2008/4/27 Hongzhang Liu <hongzh...@gmail.com>:
名人问题是不是应该分成两部分？在O(n)的时间内确定不存在名人可能是可行的，但要确定存在名人还是需要遍历所有关系吧？
天地之灵
May 6, 2008, 8:33:05 AM5/6/08
to TopLanguage
重新看了一遍，确认了一个问题：
第一道题，说得是N个人，同时要有O(N)的算法，那么，我们是不能遍历这至多N*(N-1)条关系的
不知道是题目描述不够细致，还是我们大家全都想错了。
以上。
第一道题，说得是N个人，同时要有O(N)的算法，那么，我们是不能遍历这至多N*(N-1)条关系的
不知道是题目描述不够细致，还是我们大家全都想错了。
以上。
Reply all
Reply to author
Forward
0 new messages