文学城论坛
+A-

回复:IBM 11月:猜因子(2.5星)

AceOnRiver 2009-11-03 07:06:27 ( reads)

1. 5
the worst case: asking the whether the number can be divided by 2,3,5,7 or 11.

2. 53/23
if the minimum divisor is 2, need to ask only 1 question, we have [162/2]=81 such numbers;
if the minimum divisor is 3, minimum 2 questions, we have [162/2]-[162/6]=27 such numbers;
similarly, for minimum divisor of 5, 11 numbers and 3 questions; for minimum divisor of 7, 7 numbers and 4 questions; for minimum divisor of 11, 3 numbers and 5 questions; for prime numbers greater than 11, 32 numbers and 5 questions.
so the expected value is (81*2+27*2+11*3+7*4+3*5+32*5)/161 = 371/161 = 53/23

跟帖(1)

AceOnRiver

2009-11-03 12:11:20

Correction