- 在线时间
- 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次,也就是说保留一个以外都得移动。# X3 c* J8 T: l. V
% M+ U$ e, a8 X+ [: W+ Q
另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。4 u/ _( l6 b4 _; ^- s0 ?' S
我也没有标准答案来判断误差,只是用随机模拟的方式,对指定的 n x 随机几百次试验确定最有可能的值,以下是代码,效率一般,但n在1000以上几百次模拟也能在几秒内搞定:. R) S, X4 |+ u/ T1 C2 n
4 u$ g0 Q# z- Y& c+ b6 q! Z) `* D
2 `' o8 a! d5 T, b5 p9 UC#code:7 z! c& @& B T4 `- q9 {9 W
private void button1_Click(object sender, EventArgs e)
& y" J% R; m O+ S {
! F3 V/ @ e2 |4 I0 b //新的描述:编号 1 -- X 的停车位,随机停放 n 辆车,无论当前车辆怎样的位置,最少让多少辆车重新停放
9 X" }4 K; V) h ~% c" q! ^ // 就可以使所有车辆连续停放
- e' O! k# y1 r- W6 C
" `. M6 w- {, ~ int n = int.Parse(textBox1.Text);- s C* L9 {( w3 A6 M
int x = int.Parse(textBox2.Text);9 f: M; O, ]7 _: F
8 h/ z+ [& j$ h: ?
//500次随机模拟的最接近数字,对比公式计算1 w. x1 L! j5 A
int maxValue = 0;3 U2 F( |% P/ g' v0 S" q) w; s0 r0 p
for (int i = 0; i < 500; i++)* `) K( u. O+ P: u& ~) L* I& j
{8 I$ h9 L& W, y0 I
int value = randResult(x, n);
) k- B$ F! B* i% x! g/ b if (maxValue < value) maxValue = value;& S Y7 q: ?; k
lbMsg.Text = i.ToString();
9 p& i c/ B1 ~+ q lbMsg.Refresh();0 W9 R% I0 R& V" Z
}3 k% M4 _# h7 v5 l+ L
textBox3.Text = maxValue.ToString();0 a; e6 v- F2 I* I7 w
6 m1 v( p" D: {3 |4 Q
//这是公式计算的结果,据观察大部分正确,少数误差也不超过 3 :)
" F5 Q% K# N* u. ?7 F double newValue = (double)n - ((n*n)/(double)x);3 T* Q' X: j1 ^4 i& d/ @4 o
textBox4.Text = newValue.ToString();
9 `/ T, g7 G# Y+ X" S }
# h, D& i/ F: G* F$ Z! U
$ D9 A5 V0 ]& h j4 D$ e! I private int randResult(int max, int n)+ n* u2 y" k" p+ F. j
{) O! C6 ^# r3 ]5 r
if(max <= n) return 0; //error
) Z" g( x6 A% c' q if (n < 3) return 0; //error, N- O* |$ C2 X$ _
if (max < 3) return 0; //error
+ g* D7 X% W4 Q8 A3 M) b9 s a: _1 J0 v X# e! c/ o8 c, t
int[] lib = new int[max + 1]; \2 A' @! m4 F4 }
//随机产生数字来填充
9 T4 |- g7 v( L5 g" u7 a lib[1] = 1; lib[max] = 1;
# N' T- f( F0 |, N int count = n - 2;
2 P' W4 u) V2 P$ p Random rand = new Random();* U; P" q O" [$ r8 {4 |
while (count > 0)$ B9 d/ {. ]; ?# k4 o% V m# u9 y# Y
{
% W3 N# x8 ]+ L int rnd = rand.Next(1, max);& K9 j& S" }! `0 D' X; v
if (lib[rnd] == 0)! u) n9 [5 S4 a# f1 i, ?
{ \- @+ T4 e O2 n8 ^% h/ V/ p
lib[rnd] = 1;
. S: Q. Y& t' P' n) I, ~9 ^% C count--;8 A- x" N. F" ]# ?
}
! ^4 u' X+ q& ]1 V' }# ?2 G6 F: S }- {9 J! n/ |# A0 M! \
//循环检查最密集区域,也就是需要移动最少的区域6 M3 w% X* c+ e+ e1 h2 H6 a; Q! ^
int min_space = n;
. e# z# J$ l5 R0 h& Z k9 e2 Y for (int i = 1; i <= max - n + 1; i++)/ L4 E5 N& I4 @1 d3 x2 f
{
~0 p4 [2 r: L, q int space = space_count(lib, i, n);7 i& C8 I: n* T, `* A6 ]
if (min_space > space) min_space = space;# {2 w7 w* x$ o! _
}9 a( K9 L$ _: ~6 C, _- N' J
return min_space;5 C/ W/ d; h# E$ J
}, h: r$ Q* L, f( s: z
$ I- a, m! N# p; [
private int space_count(int[] lib, int start, int n)4 n, c2 V L* D/ X
{ //检查数组start后面n项数据里面有多少个1 [& ~; z1 a( ~2 v+ _
int count = 0;
, {9 c, O* J% | ~9 t8 @/ W/ t8 i/ \ for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;. ^) c$ u+ L3 v- y# `
return count;8 z) P9 R4 j( D( |6 Z) W" r
}
- v7 h( e; P% c$ B% ^8 R, t) T |
|