计算机科学论坛--[原创]求解几道题目

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

1、有300层高楼与2个玻璃杯，玻璃杯从x层掉落摔到地面刚好摔碎(x层以下是摔不
碎的)，请问至少需要多少次摔杯子试验就一定能够找到x层是第几层？

2、5000个数中找出3个数，使它们和的绝对值最小，求算法与时间复杂度。
该问题主要解决数学组合求解问题。即从5000个数找出3个数，然后分别比较它们和的绝对值大小。

3、在2×n的一个长方形方格中(高：2,宽：n),用一个1× 2的骨牌铺满方格(高：1,宽：2 / 高：2,宽：1),输入n ,输出铺放方案的总数.

例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：
|----|----|----|
| | | |
| 1 | 3 | 5 |
|----|----|----|
| | | |
| 2 | 4 | 6 |
|----|----|----|

A方格:高：1,宽：2
B方格:高：2宽：1
方案1：(1,2)放入B、 (3,4)放入B、 (5,6)放入B
方案2: (1,2)放入B、 (3,5)放入A、 (4,6)放入A
方案3：(1,3)放入A、 (2,4)放入A、 (5,6)放入B

4、从1-N这N个数中任意取3个数使这三个数之和为Sum，其中N<Sum<3N，求共有多少种组合方式，请给出算法与时间复杂度。（注：1+2=3与2+1=3只能算一种组合方式）

5、一个字符串，长度为200，字符串的每个位置上只能出现A T G C四个字符中的一个，每个位置上的四种字符出现的概率不同，要求计算出生成概率最大的前50个字符串，请给出算法与时间复杂度。
例如长度为6的相关概率数据：
位置 1 2 3 4 5 6
A 0.2 0.3 0.1 0.55 0.25 0.3
T 0.3 0.5 0.6 0.25 0.25 0.1
G 0.1 0.05 0.2 0.2 0.25 0.4
C 0.4 0.15 0.1 0 0.25 0.2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

1、有编号为1-N的N个房间，从左到右，每个房间分别有一台机器(重量各不相等)，现在要求把这些机器按照重量重新分配房间，重量从左到右依次递增。移动机器只能做交换操作，但交换机器要花费一定的费用，费用的大小就是交换机器重量的和。问怎样移动机器才能使排序的费用最小。

2 假定有这样一个游戏，规则定义如下:
游戏的基本元素是25个字母。游戏开始，玩家会获得一定目的字母，可能有重复的字母。比如两个A,一个B。
玩家把这些字母排成一行，两个字母相邻会有一定分值，本次游戏的得分为所有相邻字母的分值的和。
比如假定a-a 100 a-b 101。一次游戏的字母为两个A,一个B,则排成a-b-a得到最大的分数为202。
给定了字母之间的分值计算游戏能取得的最大分值，一次输入的字母数量不超过20。

3 有一副特别扑克牌,有26*3张,每张扑克牌的点数为A-Z，扑克牌没有花色,相同点数的有3张。随机从扑克牌里抽30张出来，去掉里面的成对的点数相同的牌(比如抽6张牌得到A,A,A,B,B,C成对去掉点数相的牌后得到A,C)，最后剩下5张牌的概率为多少?最后剩下6张牌的概率为多少?

4、定义一种数列，它的定义如下
s(x) = 0 (x<0)
s(x) = 1 (0<=x<1)
s(x) = s(x-1) + s(x-3.14) (x>=1)

现在需要计算出s(x) (x为浮点数)

1)、求s(x) MOD 1000000007的值，x < 1000
2)、求s(x) MOD 107的值，x < 2^31
3)、求s(x) MOD 1000000007的值，x < 2^31
请分别给出以上几问的算法与时间复杂度

5、5个不同的自然数N1 N2 N3 N4 N5，其中N1 < N2 < N3 < N4 < N5，并且满足 N1^2 + N2^2 + N3^2 + N4^2 + N5^2 = N1 * N2 * N3 * N4 * N5

1）、求符合条件的1组N1,N2,N3,N4,N5
2）、求符合条件的100组N1,N2,N3,N4,N5
3）、求N5 < 100000的解的数

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用evenyee在2010-11-29 11:00:00的发言：
1、有300层高楼与2个玻璃杯，玻璃杯从x层掉落摔到地面刚好摔碎(x层以下是摔不
碎的)，请问至少需要多少次摔杯子试验就一定能够找到x层是第几层？

这题真有意思，琢磨了下未找出解决方法，但是有一些想法，说出来与大家一起讨论讨论。
本题可抽象为一个查找问题，而且待查序列是有序的。为了讨论方便，先设定几个符号及对题目一些不清楚的条件进行说明：
N：楼层数。（本题中：N=300）
BN：玻璃杯数。（本体中：BN=2）
x：1<=x<=300。
对有序序列的查找最先想到的是二分查找，但是本题与典型的二分查找有个区别是BN。
若BN>=logN，（注：因为茶杯会碎，如果茶杯数量大于或等于二分查找的比较次数），则直接可以用典型的二分查找，但是本题中BN<logN，所以典型的二分查找不适用。

通过以上分析，有以下想法：
（1）i←1 to N，Li表示第i层楼
（2）将茶杯1从Li摔下，若未摔碎，则i←i*2，继续（2）；否则跳（3）。
（3）若i == 1，则x←i；否则，j←i/2，跳（4）。
（4）j ++，将茶杯2从Lj摔下，若未摔碎，则继续（4），否则x←j-1。

这样一定能找到x，但是是否是最小我不置可否——至少比从一楼递增一层往上试验的次数少。。。
另外，针对上述算法中的（2）可以考虑改进“i←i*2”中的步长2，调节这个步长到一个合适值也许会得到更好的效果。。

以上是我的一点拙见，欢迎大家一起讨论~


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	58.594ms