欧拉计划746:聚餐

newkid

按我的理解是N个家庭总共4N人，每两人之间留出一个空位，总共4N个空位。第N+1个家庭的四人就从这4N个空位中选择入座。
但是题目说M(2)=896 就不知道是怎么排出来的了。
如果你没办法去掉乱码就别贴出来，没人看得懂。

〇〇

newkid 发表于 2021-2-9 00:01
按我的理解是N个家庭总共4N人，每两人之间留出一个空位，总共4N个空位。第N+1个家庭的四人就从这4N个空位中 ...

意思是必须一家4个人都挨着才算挨着.二楼已经算出来2家的

〇〇

如果规定第一个座位需要奇数人坐，然后结果*2就可以了

〇〇

with t0(a) as(values(0),(1),(2),(3),(4),(5),(6),(7)) --,(8),(9),(10),(11))
,t(a,f)as(select a,a/4 +1 f from t0)
,s(lv,b,c) as(select 1,1<<a,f from t  where a%2=1
union all
select lv+1,b+(1<<a),c||f from s,t
where lv<8 and b &(1<<a) =0
and a%2=(lv+1)%2
and not ( lv>=4 and
c%10000 % 1111=0
)
)
select 2*count(*) from s where lv=8;

〇〇

with t0(a) as(values(0),(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11))
,n(n) as(values(1),(2),(3))
,t(a,f)as(select a,a/4 +1 f from t0)
,s(lv,b,c) as(select 1,1<<a,f from t  where a%2=1
union all
select lv+1,b+(1<<a),c||f from s,t
where lv<12 and b &(1<<a) =0
and a%2=(lv+1)%2
and not ( lv>=3 and
(c||f)%10000 % 1111=0
)
)
select 2*count(*) from s where lv=12
and not exists(select 1 from n where (substr(c,n-4)||substr(c,1,n)) % 1111=0)
;
890880

newkid

我原先没看到要求男女隔开的要求，这样的话，N+1的情形就不能从N的排法来插入新人得到。
SQL的做法是模拟出所有可能的情形最后来COUNT, 这在小数量是可行的，N再大一点就算不动了。解决这种问题必须用公式。
这个题目的方向可以用排除法，先不管家庭找出所有男女隔开的总数，这个很好算，在减去其中1个家庭在一起，2个家庭在一起，...N个家庭在一起的数字。
1个家庭在一起的情形可以用到N-1的结论。2个家庭则可以用到N-2的结论。
可以从N=2, 3开始算，捋清思路。
由于男女对称，只需考虑其中一种，比如规定男性永远坐单数，最后总数乘以2。

话说，你顶贴发那堆乱码是几个意思？你相信别人有特异功能？如果拷贝粘贴不行，先打印成PDF再拷贝行不行？

〇〇

newkid 发表于 2021-2-9 23:16
我原先没看到要求男女隔开的要求，这样的话，N+1的情形就不能从N的排法来插入新人得到。SQL的做法是模拟出 ...

7楼就是用公式，2家男女间隔全排列=1152，一家挨着（另一家也必然挨着）=64，但结果是896，还算漏了什么？

〇〇

newkid 发表于 2021-2-9 23:16
我原先没看到要求男女隔开的要求，这样的话，N+1的情形就不能从N的排法来插入新人得到。SQL的做法是模拟出 ...

打印出来看清了，两家都挨着还有不同的组合。1种对应4种，所以1172-64*4=1172-256=896

with t(a) as(values(0),(1),(2),(3),(4),(5),(6),(7))
,s(lv,b,s) as(select 1,a,cast(a as text) from t
union all
select lv+1,a,s||a from s,t
where instr(s,a)=0
and a%2<>b%2

)
select * from s where lv=8
and ( lv>=4 and
substr(s,-1,1)/4=substr(s,-2,1)/4
and
substr(s,-1,1)/4=substr(s,-3,1)/4
and
substr(s,-1,1)/4=substr(s,-4,1)/4
);
lv|b|s
8|7|01234567
8|5|01234765
8|7|01236547
8|5|01236745
8|7|03214567
8|5|03214765
8|7|03216547
8|5|03216745