- 在线时间
- 2 小时
- 最后登录
- 2017-8-7
- 注册时间
- 2010-6-27
- 听众数
- 2
- 收听数
- 0
- 能力
- 0 分
- 体力
- 40 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 14
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 3
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   9.47% 该用户从未签到
|
已经能够确定的是:如果 x > (n * (n-1) + 1),表示密度太‘稀’了,这种情况下必然是移动 n - 1次,也就是说保留一个以外都得移动。
' h9 G$ i" x/ x& H. \; N' X
- H$ n9 T" q/ K! F$ `另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
6 c, M* H \! `5 g$ q. Q我也没有标准答案来判断误差,只是用随机模拟的方式,对指定的 n x 随机几百次试验确定最有可能的值,以下是代码,效率一般,但n在1000以上几百次模拟也能在几秒内搞定:/ j% m7 P \; E* e, v* q
; H1 ?( j+ R U t0 S) m
1 w; N m- u0 F) b3 y
C#code:% E- b$ {% Y) N0 Z; l& S
private void button1_Click(object sender, EventArgs e)
# x ^: C) E) t+ E- h {
. s) M) ^/ U9 m2 t; K9 Z4 t$ p. z //新的描述:编号 1 -- X 的停车位,随机停放 n 辆车,无论当前车辆怎样的位置,最少让多少辆车重新停放2 E U0 u7 J9 P9 w8 S
// 就可以使所有车辆连续停放
) K$ N' R( ?" ?: j
. Q: A4 W9 q( d int n = int.Parse(textBox1.Text);
4 @6 ]9 G" y5 U! p# G7 j int x = int.Parse(textBox2.Text);
! Z5 b5 A. l3 E5 P, O$ ^# R
: O9 d$ \7 g0 ^" { //500次随机模拟的最接近数字,对比公式计算
$ g# Y/ T( v9 F8 i- e* w7 w int maxValue = 0;9 | t ^$ d: t* b2 t/ d/ H1 b
for (int i = 0; i < 500; i++) ]- C1 _" x# O L8 y4 t' a) J
{
; g6 x+ D% \1 k int value = randResult(x, n);# M# i |" ?6 t2 n" L, s" v8 H
if (maxValue < value) maxValue = value;) h/ q [$ I5 l: W+ k
lbMsg.Text = i.ToString();
3 }) P( O7 i+ @' ~8 Y. ] lbMsg.Refresh();
1 I+ d' Y ~5 g! R }
( |# ^( {0 ^; T1 w9 R1 O textBox3.Text = maxValue.ToString();* I6 f' z) Y% z8 i6 B8 q$ u: r, z# U2 R
- X ]9 y' b8 c( e0 X' K' k
//这是公式计算的结果,据观察大部分正确,少数误差也不超过 3 :)
8 A" B+ K: x# Q" ?+ A1 ] double newValue = (double)n - ((n*n)/(double)x);
" w4 N% w' k6 u; i- c, W textBox4.Text = newValue.ToString();' {5 D6 W6 i( A1 }/ C6 b/ G& s$ R
}
) X t$ H0 g( Y1 Q
1 i4 z3 p$ z% ]" }5 t: f7 `+ ^ private int randResult(int max, int n)
' E" M$ k- z+ i9 q( z {
; V3 k7 @, {% B) @ if(max <= n) return 0; //error- S" I4 X( [! t7 T0 W# a; n6 Y
if (n < 3) return 0; //error
+ A Z& v5 l; ^/ Y if (max < 3) return 0; //error
! c6 [$ O3 D( t. V" ?1 s$ v" ^( V- ` _7 j+ _" g2 Q
int[] lib = new int[max + 1];: M n0 c$ N) Y& ]
//随机产生数字来填充
: S B* v( X H6 {. P2 w. N lib[1] = 1; lib[max] = 1;
; S I2 g+ n9 S. ~; W int count = n - 2;
7 K+ S, M V( @% s: X8 P/ F Random rand = new Random();
3 x" n5 T' F/ z$ x while (count > 0)8 @1 j( q- P4 ?0 c
{
- c, V* o7 k5 X- e/ i6 \2 }: C$ [' o int rnd = rand.Next(1, max);5 J' R# q- g3 U; O3 P- [5 t
if (lib[rnd] == 0). ?6 V# x, K: |% q* m: U- u" W
{4 Z6 O3 r4 V( _
lib[rnd] = 1;3 V! Y6 i. t$ t% D6 n. ^1 g. f
count--;
8 Z# a( a" ~( [+ L* x( o( J }
5 b5 w# |2 c2 O; T8 j, M1 G: e }
. G% t$ M9 l1 j! S; r! e //循环检查最密集区域,也就是需要移动最少的区域5 ^. @: ^7 U) }. N
int min_space = n;
: t2 m" @. V& o+ }, ` for (int i = 1; i <= max - n + 1; i++)
# p, ?5 h2 s7 v, c& Z {
) X% N1 r f" P$ g int space = space_count(lib, i, n);
6 D2 @8 z7 H! g: }4 p" ? if (min_space > space) min_space = space;6 B8 b" ]7 h3 @! S) d% x0 t& n
}
1 W- p; w/ `# h' ? return min_space;# ~# p9 p7 I# r3 U) K
}1 V3 n/ G1 I! A6 E
& _7 L& w, W+ Y! B" b$ U; R. o E: o private int space_count(int[] lib, int start, int n)# Q; `% G, S+ ?: m8 p" S$ ~
{ //检查数组start后面n项数据里面有多少个17 @+ l! c% ?- n6 I1 t
int count = 0;# p [ a- l0 V6 W6 p: [0 O
for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
3 l5 F& P/ C/ }0 | return count;
& r! N5 n+ m. R, ] M }+ {2 H9 B6 [6 v' A4 y7 P7 n
|
|