- 在线时间
- 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次,也就是说保留一个以外都得移动。
8 _% D% H% l8 K/ w2 y0 @' u
8 `, Z& R' ^ ~. Z另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。( j8 m# p* V% k
我也没有标准答案来判断误差,只是用随机模拟的方式,对指定的 n x 随机几百次试验确定最有可能的值,以下是代码,效率一般,但n在1000以上几百次模拟也能在几秒内搞定:
# K3 C2 h, b" n8 R. ^7 i, @7 F( ?1 W0 v% _1 l7 p
5 Y2 T! }8 \5 e# ^
C#code:# [% @; ~+ k5 q# P8 T
private void button1_Click(object sender, EventArgs e). ]& Q" o7 E, ^. _+ S+ C0 F9 }
{
& c# I2 |0 x/ ^ //新的描述:编号 1 -- X 的停车位,随机停放 n 辆车,无论当前车辆怎样的位置,最少让多少辆车重新停放9 j5 V" y' d4 [& X6 N7 a) l
// 就可以使所有车辆连续停放4 ], g5 o0 A/ e$ r! O: E
% V1 N) F! Z" ` int n = int.Parse(textBox1.Text);2 m% n+ N0 s" ?: r2 I9 a: \% j
int x = int.Parse(textBox2.Text);
- J H, x2 A V( g- h9 ~7 @8 A* L+ F
/ s" C3 t/ S: Y //500次随机模拟的最接近数字,对比公式计算
9 ]. o7 c( P7 d int maxValue = 0;
2 \! \! [2 I- \" _ for (int i = 0; i < 500; i++)! Q" R9 \/ b2 I, N/ r6 k
{) x ~* b: ~6 U) w s- a
int value = randResult(x, n);. a3 Y# T. e5 W9 m+ r, E# f
if (maxValue < value) maxValue = value;
l8 ?4 f0 I* ]' y lbMsg.Text = i.ToString();( f$ {6 X0 n3 x. U: j3 B! B0 X
lbMsg.Refresh();9 ^ p, b |) M( S
}
+ B+ ?7 l9 @' K5 {2 m textBox3.Text = maxValue.ToString();
( K4 t3 o0 n- y: s7 b
L- E' m+ P) p' ~$ `) b# n$ R //这是公式计算的结果,据观察大部分正确,少数误差也不超过 3 :)
) y" M; d$ K/ F+ z" r' A double newValue = (double)n - ((n*n)/(double)x);6 F- F7 O4 {6 _: E+ x
textBox4.Text = newValue.ToString();
5 I2 Z9 G! p: d }0 X# ?6 s2 g: H, t/ M. r Q
& B0 m |; C9 P0 V0 l2 p6 t) s) x private int randResult(int max, int n)* u0 c4 r8 ~) D! }2 w; T* y: Q
{4 x5 n1 K5 X- R! W! q
if(max <= n) return 0; //error" H) A" g5 R2 P- J% E
if (n < 3) return 0; //error7 K7 T' `. k' H- K$ @
if (max < 3) return 0; //error1 P) W1 b$ d3 k
- L7 H* z( U$ j Y* ?$ b; P& B
int[] lib = new int[max + 1];
- Q) e c6 Z! K! o. l //随机产生数字来填充0 W5 U$ q8 w4 }
lib[1] = 1; lib[max] = 1;, S) [* v, a% t, c
int count = n - 2;
3 D% T. e9 @1 W$ e9 ~, b/ Z9 L Random rand = new Random();
( B. W; c( R# S2 ^8 G8 n$ j: Z, M9 \ while (count > 0)
7 b! s4 Q7 Z1 |2 H+ T( O- d' y9 ] {3 a# y* A& W/ M; t7 ~9 ]$ y
int rnd = rand.Next(1, max);# Y9 F/ U: A& s1 D# E
if (lib[rnd] == 0)" }& `/ [+ G/ B" V2 A8 H
{) x/ [1 M7 P" ]# Z G
lib[rnd] = 1;6 \% ?9 ?4 i2 N; w) W
count--;
% R0 p0 V) d5 j6 L1 z; w& { }" n8 U2 i% I) R3 s# {+ N$ p. O
}/ X6 ^# {8 m6 \( n' J8 t, }. y% Y
//循环检查最密集区域,也就是需要移动最少的区域# c3 S7 v+ r4 l6 E; F; f. N
int min_space = n;
5 ~) @4 s0 m) g+ A for (int i = 1; i <= max - n + 1; i++)8 R( v7 i2 w9 G" j
{
4 ]5 d( {* e4 T int space = space_count(lib, i, n);
) b+ P3 Q% m( i if (min_space > space) min_space = space;! b5 d- h% \+ B& W8 d
}
S3 Q7 }0 Q5 G8 D+ n/ u return min_space;/ w+ p: Q9 d: ?. \! R; }7 K: B
}
8 w7 V3 Y) ~: U/ E2 d- V7 [2 w
5 K+ r+ H" H, E6 M7 K* c private int space_count(int[] lib, int start, int n), g$ I5 R' J6 `" H# g c
{ //检查数组start后面n项数据里面有多少个1
" N I. r$ e3 Z* n) t: \ int count = 0;
+ i) Q. o3 k8 l& G" L9 _* G u for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
! N2 }% t# {1 C6 V/ N @ return count;! F4 X" S7 {) F( Z" ]# |0 n' v
}! Z; u! D3 d: \6 Y2 |
|
|