java.io包和杯子测楼

1 java.io

字符流:Reader

字节流:InputStream

2 杯子测楼

一种杯子,若在第N层被摔破,则在任何比N高的楼层均会破,若在第M层不破,则在任何比M低的楼层均不会破,给你两个这样的杯子,让你在100层高的楼层中测试,要求用最少的测试次数找出恰巧会使杯子破碎的楼层。

分析:

1 如果只有一个杯子,则需要从第1层往上,逐层测试。

2 现在多了一个杯子,就可以用这个杯子确定临界楼层的大致区间,然后第一个杯子用分析1的方式继续。需要测试的次数约为100^(1/2)=10

解答:

1 将100层分K个连续的楼层,每个楼层区间的楼层数为F层,这样,问题就变成了用第一个杯子确定楼层区间,用第二个杯子确定临界楼层的问题。

2 从第一个楼层区间开始测起,所以第Ki个楼层区间的测试次数比第Ki-1个楼层区间多一次。

3 测K次最多能测出临界楼层的最高楼层数为:S=K+(K-1)+……+1=(K^2-K)/2

4 对于本题S>100,解得K=14

扩展:

1 如果有3个杯子,K次能测出临界楼层的最高楼层数为:S=S2(K)+S2(K-1)+……+3=(K^3-K)/6

原文地址:https://www.cnblogs.com/yanyichao/p/3910213.html