名家讲坛作业

(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)的算法!

(只是为了写作业~)

发表评论?

4 条评论。

  1. 一次讲座的作业这么难? :twisted:

  2. 好。。。厉害的样子,完全没懂

发表评论

注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

Trackbacks and Pingbacks:

本文链接:https://twd2.me/archives/3830QrCode