高手帮忙看看,我出啥问题了?!
微软面试题:
教授选出两个从2到9的数,把它们的和告诉学生甲,把它们的积告诉学生乙,让他们轮流猜这两个数
甲说:“我猜不出”
乙说:“我猜不出”
甲说:“我猜到了”
乙说:“我也猜到了”
问这两个数是多少
我写的代码如下:
-------------------------------
create table #tb(id int)
insert #tb values(2)
insert #tb values(3)
insert #tb values(4)
insert #tb values(5)
insert #tb values(6)
insert #tb values(7)
insert #tb values(8)
insert #tb values(9)
--求和组合
select cast(a.id as char(1))+ '+ '+cast(b.id as char(1))+ '= '+cast(a.id+b.id as char(2)) as
expression,a.id+b.id as result
,a.id as id1,b.id as id2
into #amount
from #tb a,#tb b
where a.id <> b.id and a.id <b.id
--求积组合
select cast(a.id as char(1))+ '* '+cast(b.id as char(1))+ '= '+cast(a.id*b.id as char(2)) as
expression,a.id*b.id as result
,a.id as id1,b.id as id2
into #multiply
from #tb a,#tb b
where a.id <> b.id and a.id <b.id
--甲说:我猜不出---------------------------------------------
--删除求和表中两数相加的和只出现过一次的记录
delete a
from #amount a
where not exists(select 1 from #amount where result=a.result and id1 <> a.id1 and id2 <> a.id2)
--删除求积表中和中不存在的数据(可不要)
--delete a
--from #multiply a
--where not exists(select 1 from #amount where id1=a.id1 and id2=a.id2)
--乙说:我猜不出---------------------------------------------
--删除求积表中两数相乘的积只出现过一次的记录
delete a
from #multiply a
where not exists(select 1 from #multiply where result=a.result and id1 <> a.id1 and id2 <> a.id2)
--删除求和表中和中不存在的数据(可不要)
--delete a
--from #amount a
--where not exists(select 1 from #multiply where id1=a.id1 and id2=a.id2)
--甲说:我猜到了---------------------------------------------
--删除求和表中两数相加的和出现过一次以上的记录
delete #amount
where result in
(select a.result
from #amount a,#multiply b
where a.id1=b.id1 and a.id2=b.id2
group by a.result having count(*)> 1)
--删除求积表中和中不存在的数据(可不要)
--delete a
--from #multiply a
--where not exists(select 1 from #amount where id1=a.id1 and id2=a.id2)
--乙说:我也猜到了---------------------------------------------
--删除求积表中两数相加的和出现过一次以上的记录
delete #multiply
where result in
(select b.result
from #amount a,#multiply b
where a.id1=b.id1 and a.id2=b.id2
group by b.result having count(*)> 1)
--删除求和表中和中不存在的数据(可不要)
--delete a
--from #amount a
--where not exists(select 1 from #multiply where id1=a.id1 and id2=a.id2)
--最后结果
select *
from #amount a,#multiply b
where a.id1=b.id1 and a.id2=b.id2
drop table #tb,#amount,#multiply
-------------------------------
可是我算出来的答案却是这两个:3和6,4和6。
网上搜到答案居然是3和4:
------------------------------
3和4(可严格证明)
设两个数为n1,n2,n1> =n2,甲听到的数为n=n1+n2,乙听到的数为m=n1*n2
证明n1=3,n2=4是唯一解
证明:要证以上命题为真,不妨先证n=7
1)必要性:
i) n> 5 是显然的,因为n <4不可能,n=4或者n=5甲都不可能回答不知道
ii) n> 6 因为如果n=6的话,那么甲虽然不知道(不确定2+4还是3+3)但是无论是2,4还是3,3乙都不可能说不知道(m=8或者m=9的话乙说不知道是没有道理的)
iii) n <8 因为如果n> =8的话,就可以将n分解成 n=4+x 和 n=6+(x-2),那么m可以是4x也可以是6(x-2)而4x=6(x-2)的必要条件是x=6即n=10,那样n又可以分解成8+2,所以总之当n> =8时,n至少可以分解成两种不同的合数之和,这样乙说不知道的时候,甲就没有理由马上说知道。
以上证明了必要性
2)充分性
当n=7时,n可以分解成2+5或3+4
显然2+5不符合题意,舍去,容易判断出3+4符合题意,m=12,证毕
于是得到n=7 m=12 n1=3 n2=4是唯一解
------------------------
大家帮忙看看,我是不是理解出问题了?!
[解决办法]
iii) n <8 因为如果n> =8的话,就可以将n分解成 n=4+x 和 n=6+(x-2),那么m可以是4x也可以是6(x-2)而4x=6(x-2)的必要条件是x=6即n=10,那样n又可以分解成8+2,所以总之当n> =8时,n至少可以分解成两种不同的合数之和,这样乙说不知道的时候,甲就没有理由马上说知道
这个......我也上网找了找
[解决办法]
按你的证明,你写sql明显漏掉了两个相同的数,因此where a.id <> b.id and a.id <b.id中的a.id <> b.id and 应去掉.所以甲能猜的数据为:3/4.3/6.6/6.4/9按这4组的积符合条件只有前两组,因为后两组积相同,但3/6怎么排队我不知道。
[解决办法]
create table #tb(id int)
insert #tb values(2)
insert #tb values(3)
insert #tb values(4)
insert #tb values(5)
insert #tb values(6)
insert #tb values(7)
insert #tb values(8)
insert #tb values(9)
select a.id as id1,b.id as id2
into #t1
from #tb a inner join #tb b
on a.id <=b.id
where a.id+b.id in (select c from ( select a.id,b.id as id2, a.id+b.id as c from #tb a inner join #tb b on a.id <=b.id ) t
group by c
having count(*) > 1)
order by a.id
select a.id as id3,b.id as id4
into #t2
from #tb a inner join #tb b
on a.id <=b.id
where a.id*b.id in (select c from ( select a.id,b.id as id2, a.id*b.id as c from #tb a inner join #tb b on a.id <=b.id ) t
group by c
having count(*) > 1)
and a.id+b.id in (select c from ( select a.id,b.id as id2, a.id+b.id as c from #tb a inner join #tb b on a.id <=b.id ) t
group by c
having count(*) > 1)
order by a.id
select id1 as id5,id2 as id6 into #t3 from #t1,#t2 where id1=id3 and id2=id4
select id5,id6
from #t3
where id5+id6 in (select c from ( select a.id,b.id as id2, a.id+b.id as c from #tb a inner join #tb b on a.id <=b.id ) t
group by c
having count(*) =2)
/*
id5 id6
----------- -----------
3 4
*/
drop table #tb,#t1,#t2, #t3
[解决办法]
playwarcraft(时间就像乳沟,挤挤还是有的) ( )
的最后一句从#tb 中取数是有问题的,就拿3/6和是9来说吧,虽然分组的count(9)是3 但经过第一轮猜测甲能排除2*7及4*5,因为它们都是唯一的乙能马上猜到,所以只剩3/6(第一次报9甲猜不出,报18乙也猜不出,第二次如上所述)
这样取数,会把第一次猜测后的部分有利条件漏掉
[解决办法]
呵呵,偶上面的不的.
想想,符合的合有
3,4
3,6
4,9
6,6
[解决办法]
mark