- 在线时间
- 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次,也就是说保留一个以外都得移动。- |6 [( l0 e2 l% }
$ k4 _" ` t2 J
另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
! c4 B# V( k8 E7 B我也没有标准答案来判断误差,只是用随机模拟的方式,对指定的 n x 随机几百次试验确定最有可能的值,以下是代码,效率一般,但n在1000以上几百次模拟也能在几秒内搞定:
/ f& ~+ R. l: q: ]+ g6 n2 b
$ k |* B" h" z; b# O" @4 z8 j' z* T {& W6 P. A5 t8 c! I
C#code:
@% S L5 G, T: N3 Z# i" q [0 Y: G private void button1_Click(object sender, EventArgs e)$ T5 h+ E g' a& f* \) b- n1 R
{
1 L+ p ~: W( P% ? //新的描述:编号 1 -- X 的停车位,随机停放 n 辆车,无论当前车辆怎样的位置,最少让多少辆车重新停放' J1 u# P) A2 n* ?2 R
// 就可以使所有车辆连续停放7 r6 W! y3 O; Z5 _9 m) R7 F
1 @, [8 k. w$ o$ s3 l! f3 w, S int n = int.Parse(textBox1.Text);& e; a6 i$ |+ i6 _* z& H) K
int x = int.Parse(textBox2.Text);
7 y# }1 C) p& r4 N
5 o* X9 m" B7 e3 s( k% D( q+ I //500次随机模拟的最接近数字,对比公式计算
# a3 U* w. B$ g, e# @3 O f; |8 [ int maxValue = 0;- P3 G8 m1 B/ G, p. B
for (int i = 0; i < 500; i++)
$ F" L3 r$ N* x. x {
+ a `- ]5 v/ ], R8 i int value = randResult(x, n);/ h% P& Z7 d2 X0 M
if (maxValue < value) maxValue = value;6 A" O: {: k" y0 t
lbMsg.Text = i.ToString();* u' o" r5 [5 f6 ~- q# y; l
lbMsg.Refresh();9 l1 p4 x# _3 X7 |4 W& y2 C5 n
}! e" V7 x6 E* B; H+ N% A/ T4 g( h' Z
textBox3.Text = maxValue.ToString();
6 D: w4 z/ w2 ~3 `" v/ k- i! Q
" j; H" r# I2 |7 k& L //这是公式计算的结果,据观察大部分正确,少数误差也不超过 3 :)
2 y" ]0 g+ I6 ~1 e8 Y* H4 C double newValue = (double)n - ((n*n)/(double)x);
\. R4 I, W N6 S% n3 A7 v textBox4.Text = newValue.ToString();! P- v% H5 S' H y. _4 ~
}
) I% V# R9 ^; p* c* Q4 l ]" B/ o$ |
( w, v4 j* S! ]8 d private int randResult(int max, int n)! \* _1 I; y: \6 m2 W: C
{
3 o2 x: Y' i$ {+ A& ^ if(max <= n) return 0; //error
' o$ w2 k6 y9 y" P7 z if (n < 3) return 0; //error p% H6 a- w+ g5 Z k w! _# x
if (max < 3) return 0; //error
9 H- \ W* f$ Z1 N3 ^( W. j
9 `' I" z' v6 _" @' Z) E3 J int[] lib = new int[max + 1];' W: {, B8 R. c# T' }! w. R
//随机产生数字来填充1 D/ {9 H, G, H; c4 V- \+ p
lib[1] = 1; lib[max] = 1;; J) \! B. B# i: b8 h# i
int count = n - 2;' j1 |% K7 Y/ o" o/ F
Random rand = new Random();0 Y$ H$ {8 B0 _# a# B) N6 p* _
while (count > 0)! q& i* U& F6 `0 o4 Q
{4 w, O# i" c$ i. x, `) @# W
int rnd = rand.Next(1, max);
" I9 v& A P3 O. }4 k, d if (lib[rnd] == 0)
5 p; u$ v( s( b {& n% c' G( Q2 C0 W
lib[rnd] = 1;
. T) ^, n7 q2 O0 I4 ^1 l% k) m count--;
E" n$ w% }5 K# Y! h, x: C } T7 `0 ]. M. n% h }
}
2 n5 k' E# u$ u2 U* p //循环检查最密集区域,也就是需要移动最少的区域9 C% p4 M" x# ~" m4 s' f6 T
int min_space = n;
* s' v( h0 D# e7 n for (int i = 1; i <= max - n + 1; i++): M5 V3 [& r4 n5 ~
{
) y& K. Q, w& H U- ^+ ~" [ int space = space_count(lib, i, n);
7 t# B$ E) V s+ O( x j5 v& B+ Y if (min_space > space) min_space = space;7 u0 L7 N& a/ L
}# L) q/ h4 _3 `, w" e
return min_space;
+ |" q1 r* E% T8 O+ d }
6 q2 {2 d' j+ A( X: o+ W
" ?; Q# U2 R1 G; W/ @1 q4 h private int space_count(int[] lib, int start, int n)
2 q# q. c+ P! j8 v; h6 v { //检查数组start后面n项数据里面有多少个16 K$ a3 H; `$ s) B5 y& Z+ G
int count = 0;
1 u/ j; \# S& E L) M- G; b0 D for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
6 Z! N: a3 Y$ V# {0 \ d return count;
1 u( K0 z% z/ h }
# C% {; x" X# D# t2 v' G |
|