几个算法问题求解
1.在盒子里有个奖品,奖品的数字是一个1到N之间的正整数。为了赢得奖品,你不得不猜它的值。你的目标就是竟可能晓得猜中它。你开始有一堆纸片。每个纸片允许你猜的高一次。如果你猜高了而且你没卡片了,那就输了。 所以,例如,你刚开始没有卡片,你可以简单赢得奖品从1,2,3。。。这个序列猜N次。 现在假设你刚开始有1张卡片,描述一下一个猜O(N^(1/2))次的策略
2.用(哈希)Carter-Wegman trick证明1463528785364712 MOD 99999999的值。不能用计算器和长除法。
3.假设你有N个有理数t1,t2,t3,…..tn, 它的分子分母全部在1到N之间, 你可以假设所有有理数的值最小是1.展现如何将这些书排序成线性时间。 假设任何在分子分母上的操作(加减乘除取余)是常数时间。 提示:线性时间排序一般由基数排序完成。假设Ri-Rj>0. Ri-Rj最小值是多少?