这是一个创建于 3470 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近做一个算法脑袋短路卡了半天了，其实不能严格说是一个排序问题
大致问题如下：
有一串数组：0 0 0 0 0... 0 0 0（n个0）
现在插入1~n个1进去
如：插入一个1
1 0 0... 0 0 0
0 1 0... 0 0 0
...
0 0 0... 0 0 1
插入两个1
1 1 0... 0 0 0
1 0 1... 0 0 0
...
0 0 0... 0 1 1
求所有情况
万能的V友能给个解决思路么
 |
1
Gonster 2015-05-27 20:44:23 +08:00
这是数学问题C n+1, 2
|
 |
2
batman2010 2015-05-27 20:47:29 +08:00
把数组视为一个二进制数，之后做二进制减法。不过，这样的话顺序就和你给的有点不一样了。
|
 |
3
nevin47 OP @batman2010 好像是个思路！我试试python二进制减法怎么做
顺序其实无所谓的，只要把所有情况求出来就行了 |
|
4
Gonster 2015-05-27 21:18:56 +08:00
刚刚说错了....
如果如果只是求没每种插入的组合数 那么n个零插入k个1号最后会有n+k位 从n+k个位置中选出k个放1 组合数为C(n+k,k) |
|
6
Gonster 2015-05-27 21:32:20 +08:00
|
 |
8
linhua 2015-05-27 21:35:56 +08:00
分析一下：输入两个参数，循环嵌套数目（乘号数目）取决于k，估计要用到递归。
如有不正，请指出。 |
|
9
Gonster 2015-05-27 21:36:31 +08:00
win8.1自带的输入法怎么这么诡异 .... 输入数字以后按空格一定会补一个号字....
|
 |
10
comicfans44 2015-05-27 21:59:30 +08:00
如果不要求顺序的话
这不就是把 000到 111 所有二进制数字列一遍吗... 000 001 010 100 101 110 111 所有情况就是 2^n次方 |
 |
11
linxy 2015-05-27 22:02:18 +08:00
设F(i)为插入第i个时的情况总数
有F(i)=F(i-1)×(C (1,n+i+1) / i ! ) 以上 如果是要输出所有的情况…我再想想 有误之处请指正 |
|
12
comicfans44 2015-05-27 22:03:13 +08:00
...少写了一个011
|
|
13
linxy 2015-05-27 22:03:42 +08:00
对了，上面i不等1.因为没有定义0个1插入并没有实际意义
|
|
14
linxy 2015-05-27 22:05:26 +08:00
不对，递推式要有个初值才行，实际上还要给出F(0)=1
|
 |
15
liuhaotian 2015-05-27 22:14:05 +08:00
恩 @Gonster 的这个是对的... 半年不做数学题了，差点连这道题也解不来
|
 |
16
black 2015-05-27 22:20:24 +08:00
是插入吧？n 个 0, 插入 m 个 1 的话，可能的组合是 C(n + m, m)，m是上标
|
|
17
black 2015-05-27 22:27:52 +08:00
另外我觉得既然限定条件 1~n 个1，那么这题可能不是 “插入”，而是将 n 个 0 的某 m 位 “置为” 1，如果是这种情况，那么可能的组合数是 C(n, m)，m是上标
|
|
18
nevin47 OP |
Select Language