一道微软公司的面试题目的算法实现
題目:??????? 已知兩個數(shù)字為1~30之間的數(shù)字，甲知道兩數(shù)之和，乙知道兩數(shù)之積，甲問乙：“你知道是? 哪兩個數(shù)嗎？”乙說：“不知道”。乙問甲：“你知道是哪兩個數(shù)嗎？”甲說：“也不知道”。于是，乙說：“那我知道了”，隨后甲也說：“那我也知道了”，這兩個數(shù)是什么？
?
?
?
下邊是最佳答案:
1和4 或者1和7
推理1:允許兩數(shù)重復的情況下
答案為x=1，y=4；甲知道和A=x+y=5，乙知道積B=x*y=4
不允許兩數(shù)重復的情況下有兩種答案
答案1：為x=1，y=6；甲知道和A=x+y=7，乙知道積B=x*y=6
答案2：為x=1，y=8；甲知道和A=x+y=9，乙知道積B=x*y=8
解：
設這兩個數(shù)為x，y.
甲知道兩數(shù)之和 A=x+y；
乙知道兩數(shù)之積 B=x*y；
該題分兩種情況 ：
允許重復， 有(1 <= x <= y <= 30)；
不允許重復，有(1 <= x < y <= 30)；
當不允許重復，即(1 <= x < y <= 30)；
1)由題設條件：乙不知道答案
<=> B=x*y 解不唯一
=> B=x*y 為非質數(shù)
又∵ x ≠ y
∴ B ≠ k*k (其中k∈N)
結論(推論1)：
B=x*y 非質數(shù)且 B ≠ k*k (其中k∈N)
即：B ∈(6，8，10，12，14，15，18，20...)
證明過程略。
2)由題設條件：甲不知道答案
<=> A=x+y 解不唯一
=> A >= 5；
分兩種情況：
A=5，A=6時x，y有雙解
A>=7 時x，y有三重及三重以上解
假設 A=x+y=5
則有雙解
x1=1，y1=4；
x2=2，y2=3
代入公式B=x*y：
B1=x1*y1=1*4=4；(不滿足推論1，舍去)
B2=x2*y2=2*3=6；
得到唯一解x=2，y=3即甲知道答案。
與題設條件："甲不知道答案"相矛盾 ，
故假設不成立，A=x+y≠5
假設 A=x+y=6
則有雙解。
x1=1，y1=5；
x2=2，y2=4
代入公式B=x*y：
B1=x1*y1=1*5=5；(不滿足推論1，舍去)
B2=x2*y2=2*4=8；
得到唯一解x=2，y=4
即甲知道答案
與題設條件："甲不知道答案"相矛盾
故假設不成立，A=x+y≠6
當A>=7時
∵ x，y的解至少存在兩種滿足推論1的解
B1=x1*y1=2*(A-2)
B2=x2*y2=3*(A-3)
∴ 符合條件
結論(推論2)：A >= 7
3)由題設條件：乙說"那我知道了"
=>乙通過已知條件B=x*y及推論(1)(2)可以得出唯一解
即：
A=x+y， A >= 7
B=x*y， B ∈(6，8，10，12，14，15，16，18，20...)
1 <= x < y <= 30
x，y存在唯一解
當 B=6 時：有兩組解
x1=1，y1=6
x2=2，y2=3 (∵ x2+y2=2+3=5 < 7∴不合題意，舍去)
得到唯一解 x=1，y=6
當 B=8 時：有兩組解
x1=1，y1=8
x2=2，y2=4 (∵ x2+y2=2+4=6 < 7∴不合題意，舍去)
得到唯一解 x=1，y=8
當 B>8 時：容易證明均為多重解
結論：
當B=6時有唯一解 x=1，y=6當B=8時有唯一解 x=1，y=8
4)由題設條件：甲說"那我也知道了"
=> 甲通過已知條件A=x+y及推論(3)可以得出唯一解
綜上所述，原題所求有兩組解：
x1=1，y1=6
x2=1，y2=8
當x<=y時，有(1 <= x <= y <= 30)；
同理可得唯一解 x=1，y=4
推理2:只有1和7
分析
因為乙先說知道，說明乙通過這個乘積可以確定一組唯一的數(shù)，而甲后說知道了，說明甲通過乙提供的信息及兩數(shù)之和也能確定唯一的一組數(shù)
先看乘積
如果是1和4，則乘積為4，可分解為1*4，2*2，不是唯一的一組
如果是1和7，則乘積為7是質數(shù)，可以分解為1*7，是唯一的一組
如果是4和7，則乘積為28，可分解為，4*7，2*14，1*28，不是唯一的一組
如果是1和17，則乘積為17是質數(shù)，可分解為1*17，是唯一的一組
如果是4和17，則乘積為68，可分解為2*34（不符合條件），和4*17，是唯一的一組
如果是7和14，則乘積為98，可分解為49*2（不符合條件），和7*14，是唯一的一組
由此篩選出1和7，1和17，4和17，7和14
在看兩數(shù)之和
如果是1和7，則和為8，可分解為，1+7，2+6，3+5，4+4
1、如果分解為2+6，則乘積為12，不能確定唯一的一組數(shù)相乘
2、如果分解為3+5，則乘積為15，不能確定唯一的一組數(shù)相乘
3、如果分解為4+4，則乘積為16，不能確定唯一的一組數(shù)相乘
4、如果分解為1+7，則乘積為7，能確定唯一的一組數(shù)相乘
因此1和7成立
如果是1和17，則和為18，可分解為1+17，2+16，3+15....9+9
其中，如果分解為1+17，則乘積為17，能確定唯一的一組數(shù)相乘
如果分解為5+13，則乘積為65，能確定唯一的一組數(shù)相乘
這樣至少有兩組解符合條件
因此1和17不成立
如果是4和17，則和為21
其中
如果分解為2+19，則乘積為38，能確定唯一的一組數(shù)相乘
如果分解為4+17，則乘積為68，能確定唯一的一組數(shù)相乘
這樣至少有兩組解符合條件
因此4和17不成立
如果是7和14，則和為21
其中
如果分解為2+19，則乘積為38，能確定唯一的一組數(shù)相乘
如果分解為4+17，則乘積為68，能確定唯一的一組數(shù)相乘
這樣至少有兩組解符合條件
因此4和17不成立
總上，只有1和7符合條件
推理3:由乙開始推理：2*2=4或1*4=4 假設是2和2的話，甲所得的數(shù)是4，那么甲就會想“2+2=4， 1+3=4，那么他（乙）就會認為我所的數(shù)是3或4，如果是3的話，那么我（甲）就知道結果 1*3=3，現(xiàn)在他（乙）不知道，那么只能是2*2=4，相信他（乙）現(xiàn)在也得出了這個結果。可是他（乙）還要反問我（甲）知不知道，那么就是說2*2=4這個結果不成立，那么只能是1*4=4
以下用VB。NET實現(xiàn)：
??? Dim NUM, SUM, PRODUCT As Int32
??? Dim Product1()() As Int32
??? Dim i, m, n, Sum1(3)() As Int32
??? Private Sub MyMain()
??????? Product1 = Nothing
??????? NUM = CInt(Me.TextBox1.Text)
??????? GetSum1()
??????? GetProduct1()
??????? For m = 1 To NUM
??????????? For n = m To NUM
??????????????? If SumOnly(m, n) Or ProductOnly(m, n) Then GoTo NextItem '不好意思用了個ＧＯＴＯ
??????????????? SUM = m + n
??????????????? PRODUCT = m * n
??????????????? '甲的和產(chǎn)生的積中最多有（n -2）個是唯一積
??????????????? If SUMtoPRODUCT_N_2(SUM) < 2 Then GoTo NextItem
??????????????? '乙的積產(chǎn)生的和中有且只有一個滿足1、不是唯一和 2、和產(chǎn)生的積中最多有（n -2）個是唯一積
??????????????? '并且其余的和均滿足 1、不是唯一和 2、有n－1個唯一積
??????????????? If PROCUCTtoSUM(PRODUCT) Then
??????????????????? MsgBox(m.ToString() & "? " & n.ToString())
??????????????? End If
NextItem:?? Next
??????? Next
??? End Sub
??? Private Sub GetSum1()
??????? '產(chǎn)生唯一和并保存在數(shù)組中
??????? ReDim Sum1(0)(1)
??????? Sum1(0)(0) = 1
??????? Sum1(0)(1) = 1
??????? ReDim Sum1(1)(1)
??????? Sum1(1)(0) = 1
??????? Sum1(1)(1) = 2
??????? ReDim Sum1(2)(1)
??????? Sum1(2)(0) = NUM - 1
??????? Sum1(2)(1) = NUM
??????? ReDim Sum1(3)(1)
??????? Sum1(3)(0) = NUM
??????? Sum1(3)(1) = NUM
??? End Sub
??? Private Function SumOnly(ByVal N1 As Int32, ByVal N2 As Int32) As Boolean
??????? '判斷是否為唯一和
??????? Dim i As Int32
??????? For i = 0 To 3
??????????? If N1 = Sum1(i)(0) AndAlso N2 = Sum1(i)(1) Then Return True
??????? Next
??????? Return False
??? End Function
??? Private Sub GetProduct1()
??????? '產(chǎn)生唯一積并保存在數(shù)組中
??????? Dim tmp(NUM * NUM)() As Int32
??????? For m = 1 To NUM '????????????????
??????????? For n = m To NUM? '??????????????
??????????????? Dim meme() As Int32 = tmp(m * n)
??????????????? If meme Is Nothing Then
??????????????????? ReDim meme(2)
??????????????? Else
??????????????????? ReDim Preserve meme(meme.Length + 1)
??????????????? End If
??????????????? meme(meme.Length - 1) = m
??????????????? meme(meme.Length - 2) = n
??????????????? meme(0) += 1
??????????????? tmp(m * n) = meme
??????????????? meme = Nothing
??????????? Next
??????? Next
??????? For i = 1 To NUM * NUM
??????????? If Not tmp(i) Is Nothing AndAlso tmp(i)(0) = 1 Then
??????????????? For m = 1 To tmp(i).GetUpperBound(0) Step 2
??????????????????? If Product1 Is Nothing Then
??????????????????????? ReDim Product1(0)
??????????????????????? ReDim Product1(0)(1)
??????????????????? Else
??????????????????????? ReDim Preserve Product1(Product1.Length)
??????????????????????? ReDim Product1(Product1.Length - 1)(1)
??????????????????? End If
??????????????????? Product1(Product1.Length - 1)(0) = tmp(i)(m)
??????????????????? Product1(Product1.Length - 1)(1) = tmp(i)(m + 1)
??????????????? Next
??????????? End If
??????? Next
??? End Sub
??? Private Function ProductOnly(ByVal N1 As Int32, ByVal N2 As Int32) As Boolean
??????? '判斷是否為唯一積
??????? Dim i As Int32
??????? For i = 0 To Product1.GetUpperBound(0)
??????????? If N1 = Product1(i)(1) AndAlso N2 = Product1(i)(0) Then Return True
??????????? If N1 = Product1(i)(0) AndAlso N2 = Product1(i)(1) Then Return True
??????? Next
??????? Return False
??? End Function
??? Private Function SUMtoPRODUCT_N_2(ByVal SUM As Int32) As Int32
??????? '甲的和產(chǎn)生的積中最多有（n -2）個是唯一積
??????? Dim n As Int32 = CInt(SUM / 2 - 0.2)
??????? Dim i, m As Int32
??????? For i = 1 To n
??????????? If ProductOnly(i, SUM - i) Then m += 1
??????? Next
??????? Return n - m
??? End Function
??? Private Function PROCUCTtoSUM(ByVal PRODUCT As Int32) As Boolean
??????? '乙的積產(chǎn)生的和中有且只有一個滿足1、不是唯一和 2、和產(chǎn)生的積中最多有（n -2）個是唯一積
??????? '并且其余的和均滿足 1、不是唯一和 2、有n－1個唯一積
??????? Dim tmp()(), i, m, n As Int32
??????? '1、分解積看能產(chǎn)生多少個和
??????? For i = 1 To CInt(Math.Sqrt(PRODUCT) - 0.4)
??????????? If PRODUCT Mod i = 0 Then
??????????????? If tmp Is Nothing Then
??????????????????? ReDim tmp(0)
??????????????????? ReDim tmp(0)(2)
??????????????? Else
??????????????????? ReDim Preserve tmp(tmp.Length)
??????????????????? ReDim Preserve tmp(tmp.Length - 1)(2)
??????????????? End If
??????????????? tmp(tmp.Length - 1)(2) = PRODUCT / i
??????????????? tmp(tmp.Length - 1)(1) = i
??????????????? If Not SumOnly(tmp(tmp.Length - 1)(1), tmp(tmp.Length - 1)(2)) And SUMtoPRODUCT_N_2(i + PRODUCT / i) >= 2 Then
??????????????????? '和不為唯一和，且和產(chǎn)生的積中支多有n－2個是唯一積
??????????????????? tmp(tmp.Length - 1)(0) = 1
??????????????? End If
??????????????? If SumOnly(tmp(tmp.Length - 1)(1), tmp(tmp.Length - 1)(2)) Then
??????????????????? '唯一和
??????????????????? tmp(tmp.Length - 1)(0) = 3
??????????????? End If
??????????????? If Not SumOnly(tmp(tmp.Length - 1)(1), tmp(tmp.Length - 1)(2)) And SUMtoPRODUCT_N_2(i + PRODUCT / i) = 1 Then
??????????????????? '不是唯一和，但是有n－1個唯一積
??????????????????? tmp(tmp.Length - 1)(0) = 2
??????????????? End If
??????????? End If
??????? Next
??????? Dim count As Int32 = 0
??????? For i = 0 To tmp.Length - 1
??????????? If tmp(i)(0) = 0 Then Return False
??????????? If tmp(i)(0) = 1 Then count += 1
??????? Next
??????? If count <> 1 Then Return False
??????? Return True
??? End Function
轉載于:https://www.cnblogs.com/cuihongyu3503319/archive/2006/11/25/571851.html
與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的一道微软公司的面试题目的算法实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
