|
题6
# M6 H' C" S! ?建设节约型社会要求在社会生产、建设、流通、消费的各个领域,在经济和社会发展的各个方面,切实保护和合理利用各种资源,提高资源利用效率,以尽可能少的资源消耗获得最大的经济效益和社会效益。近年来,能源紧缺问题日益突出。尽管单台计算机功率不大,但总的数量增长十分迅速。据统计,1998 年在美国计算机消耗了13%的电力供应。CPU 节能的另一个动因来自笔记本电脑、智能手机等靠电池供电的电子设备上。为了延长电池使用时间,必须尽可能地减少能量消耗。 ) l$ n8 Q% c# Q3 N5 y# ^
一般说来,单位时间CPU 能耗与CPU 在该时刻的工作率有关,工作率越大,能耗越高。而工作率又影响设备的性能,决定程序的反应时间和完成工作所需的时间。当然不同情况下,侧重有所不同。以下是两类常见的问题。 " ^, `8 D6 `- S0 V' q! X L* Y
问题一:现有一批任务,每个任务有其到达时刻和截止时刻,任务必须在两者之间完成,但允许在多个不连续的时间区间内运行,CPU 在同一时刻也可执行多个任务。要求这些任务都可按时完成,并且耗用的能量最小。 ' P* J9 z* w# b8 \/ H, y
问题二:假设任务只有到达时刻,没有截止时刻,完成这些任务所消耗的能 2 D7 g/ s2 c' B+ }/ x
量有一个上限。要求在耗用能量不超过上限的条件下,使这些任务的流程时间之和尽可能小,这里某个任务的流程时间是指其完成时刻与到达时刻之差。 , j( g; G/ d; h/ Z# A3 y2 S
对以上两个问题,试作出合理的假设,建立模型,设计算法以给出CPU 如何处理一批任务的方案,并分析你的算法的性能。
+ U ^, M' g3 Q; N" [8 f下面给出一组简单数据用于问题一的测试,你的算法应能处理更复杂的情况。假设CPU 每秒最多可完成1000 万个单位的运算,到达时刻与截止时刻单位均为秒。 7 n) r' l: | c- U- O/ X7 |/ V u/ F
_& m3 J( F, q. @" [
任务序号 $ K0 q( e' u+ H% K% ~; H
| 1
2 c7 \% S9 l9 y# l | 2 ; d% _% k# H. a/ s) Q0 x" c
| 3 " b4 t& k6 _5 k) K! _0 w. v' P
| 4
1 Q4 B4 q P1 }: c) c/ X, I# E | 5
5 O8 {% G- V9 H: v7 C* H | 6 . `& | T( P2 k; Q+ f% R
| 7
. d$ g0 \: _/ L3 k | 8 7 m2 x& w+ H/ m3 |: p4 A9 n
| 9
5 I1 P G9 P: x4 s, a | 10
+ h! v! \1 l5 r2 M+ J' b% g& ? | 11
, Q$ L. E g3 Z. o | 到达时刻 6 d0 C4 m. k. _, s
| 0
" ?' X4 b4 Q) K4 { | 1
. v, @, B- P- c | 1
: d0 `8 `+ |# e0 G0 ~ | 2
+ ]+ K* ?5 @. {3 e: \$ l& ^1 z% @ | 4 $ Z4 z: X& W2 v9 t' @" D6 a
| 5 8 [. s+ L- I, x3 r) C6 `4 y
| 8
6 i E K% d6 [- f2 p" J# } | 7
, ^, Z$ K- `' ]2 X" A" [ | 7
; s8 }. S/ m8 R# x8 F | 8 # s; g' b j$ ~' n
| 5
" o4 x1 C& `/ _$ Y | 截止时刻
6 Z/ R0 {- A" M+ M Q( z5 F | 2
- ^# I1 I; ?9 |- f | 2
$ O: Z4 f; r) y. w% V0 h | 3 . p& x3 D; j# i9 o) I f
| 5
! q- J K% X1 t0 {9 i. T6 Y | 8
8 _1 K- }$ n. A" g; R, T | 7 ) L+ F+ ?) `5 b3 C' o: [
| 9 , w# t& y5 ?: I' m# ~9 G1 ]9 i
| 8 $ M" s1 D6 ^; y1 ?) J
| 9
9 |. R ?# l+ D | 10
4 ]$ I5 b3 Q% x# B/ ? | 10 * ~( U. n8 x4 ?* }3 K/ x( T
| 所需运算单位数(百万) 3 E' E; f: f8 u3 I _. A. B: t
| 3 $ e4 l( f; h8 h1 b
| 6
0 h7 v6 V4 g' ^# D8 Q* J5 d# A% R | 9 - i( s' N1 Z9 R \( I. |% v
| 6 ! ]( V7 F& j# v4 J9 q& }$ y
| 12 4 u5 {: g) q- W
| 6
% B, j$ a/ _0 Y% y e8 y/ I" g | 3
4 y8 F+ v' y" E! j1 l/ i- J | 9 8 x4 X# }' b6 Y
| 6 - S4 o- G; ?, E2 s6 g( o
| 3
3 J; v: M$ O# \1 ` | 3 : F% A. v! j2 K0 n" a3 J
|
( h; k7 V6 j* Y( t
6 F# v8 o; _( \9 ^有知道答案的吗?或者给我一点思路 急求!后天就要交了~ 相关文献也可以,谢谢了 |