(1)设计大数单位
我觉得用科学记数法就好~
(2)设计比冒泡排序O(n^2)好的排序算法, 支持任意对象
假设: 内存无限大, Integer能存无限大的数
首先我们需要有一个函数Integer f(Object x), 该函数接受任意实现了比大小的接口的对象, 它返回一个整数(对于不同的x有不同的函数值), 若x1>x2则f(x1)>f(x2)。
如: 对于x是任意数字对象则可以有f(x)=x。
然后我们只需要两个大数组记为Integer[] C和Object[] O。
对于每个输入的x, 执行O[f(x)]=x;/*这是便于以后用f(x)来反查x*/ C[f(x)]++;/*计数器*/ max_v=f(x)>max_v?f(x):max_v; min_v=f(x)<min_v?f(x):min_v; /*这两个是用来记录下一步要扫描的范围*/
然后需要类似于vector的东西记为vector<Object> V。
然后只要扫描一遍C[i=min_v->max_v],
for j=1->C[i] : V.push_back(O[i]);
V中内容即为所求。
据说是O(n)的算法!
(只是为了写作业~)
一次讲座的作业这么难?
好。。。厉害的样子,完全没懂
orz 反正是作业 胡写即可!