思维训练

很饶的数列题

2008年10月15日 阅读(139)

老徐听他们实验室参加面试的人出的,有点像ms的那个选择题,具有很强的自描述性

i = 0, … n(n为自然数)

数列:A(0), A(1), …, A(i), … A(n)
A(i)表示i在上述数列中i出现的个数

比如n=3时,2 0 2 0就是一个满足条件的数列

给定n,请计算出数列,如果不存在请说明。

 

这是我给的解法,。。。没睡午觉想的。copy,聊天记录,懒得整理了,哈哈

星矢 13:24:15
是不是我又看错了
 
星矢 13:24:31
果然我看错了
 
星矢 13:40:09
发现规律了
 
许雅明 13:40:15

星矢 13:40:26
有点像鸽巢原理
 
许雅明 13:40:32
dui
星矢 13:40:39
总是 剩下n个位置分n+1
 
许雅明 13:40:52

许雅明 13:40:55
然后呢
星矢 13:40:55
并且保证每个位置不为0
 
星矢 13:41:03
又几种分法?
 
星矢 13:41:08
是不是只有一种
 
星矢 13:41:15
1 1 1 ….2
 
星矢 13:41:48
好像不是
 
许雅明 13:42:17
你是不是没考虑A(0)呢
星矢 13:42:25
n=3时 是一个位置分2
 
星矢 13:42:31
所以是 0 0 2 2
 
许雅明 13:42:46

许雅明 13:43:02
不是 2 0 2 0?
星矢 13:43:24
设0的个数
 
星矢 13:45:07
我再 想象
 
星矢 13:45:14
可能我又想错了
 
星矢 13:45:17
 
 
许雅明 13:45:20
ok
星矢 13:45:37
你发哪了?
 
许雅明 13:45:57
正在发
许雅明 13:46:13
等你想出来就不发了
星矢 13:49:32
你看看
 
星矢 13:49:37
如果假设0的个数
 
星矢 13:49:52
是不是只有一种方法放?
 
星矢 13:50:07
比如
0 0 2 2这个
 
星矢 13:50:30
假设只有2个0
则必含有 0 0 2这三个元素
 
星矢 13:50:47
这样还剩下2只有一个位置可以放
 
星矢 13:50:57
同时保证该位置不能为1
 
星矢 13:51:07
所以只有一种方法方
 
许雅明 13:51:09
嗯,有道理
星矢 13:51:19
当x个0时
 
星矢 13:51:31
好像都会产生一种放法
 
星矢 13:51:41
就是 1 1。。。 2
 
星矢 13:51:49
然后证明这些放法都不对
 
星矢 13:52:14
思路是这样的
 
许雅明 13:52:18

星矢 13:52:23
不知道还有漏洞没
 
许雅明 13:52:33
也就是说只有3有解?
星矢 13:52:38
不是
 
星矢 13:52:40
4也有
 
星矢 13:53:01
要去验证
是不是那样放就不是合法的
 
星矢 13:53:07
我没验证
 
许雅明 13:53:12

许雅明 13:53:16
我看看

You Might Also Like