看着车牌忽然想到一个题目,几次变化使之连续

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
# y  N6 V7 W9 m# f4 o  N# S. e2 w4 m7 s
2 B+ R  I. n! F$ D0 Q
/ b  \% ]1 j: G( E比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
3 u% p* M4 b; B# q. |
1 x) N: D1 b" C9 m0 U4 R0 E例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

linmatsas

是最少需要几次变化吧…………

yupo_smart

想法很好，可以好好考虑一下。

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
# L) D+ K- h: W$ K1 Y
另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
+ z& t0 U( K0 q/ i我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：

( J# n! D5 L+ z/ o
( Q( K3 m, v% P0 N, F+ ~1 [C#code:
6 S# {: ]( U8 w& j8 ?  s                private void button1_Click(object sender, EventArgs e)
                {
: d! Y  V! Z, d; B            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
% a5 i3 C! E0 d5 ~7 u' x            //          就可以使所有车辆连续停放
: I1 F* M; Q$ C* g$ u) W; U& x            
            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);

            //500次随机模拟的最接近数字，对比公式计算
            int maxValue = 0;
            for (int i = 0; i < 500; i++)
. ~) \2 b( L+ E1 P            {
2 h5 ^# p. Z1 Z2 Y+ `- R                int value = randResult(x, n);
" F: m8 x) D- z- j                if (maxValue < value) maxValue = value;
; s( w. c3 J1 I                lbMsg.Text = i.ToString();
, V. b& Z4 P8 Y* q  X6 s                lbMsg.Refresh();
6 k% H8 C  o! X7 I            }
0 A" S9 m6 M2 `+ `! i1 z            textBox3.Text = maxValue.ToString();
: E' ]. Q' H9 Y; g
& M" h& d; l. N% L+ L/ B7 m$ _            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
7 ^, Y6 S$ M2 ~) l5 _+ U            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
  _$ e' p2 ^$ X+ G8 v7 y* L' d$ O                }
  z( N6 b7 K2 z6 M
        private int randResult(int max, int n)
7 I/ o- n7 h" X4 }5 s        {
$ {/ U, D; a8 l  ]/ l" K            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
            if (max < 3) return 0; //error

7 E( q7 k4 e/ N( W6 F1 Z            int[] lib = new int[max + 1];
            //随机产生数字来填充
            lib[1] = 1; lib[max] = 1;
6 s( K  c0 D& F0 S( l5 b            int count = n - 2;
6 @# i5 V) K0 P% @" z            Random rand = new Random();
1 s3 y! g6 b! g/ z            while (count > 0)
; R4 j# Y4 ]& y6 ^2 P3 K% D% C            {
                int rnd = rand.Next(1, max);
; j3 E/ A; }/ v8 ]( `0 l4 k                if (lib[rnd] == 0)
0 J0 u' h2 ?, h, J0 c                {
                    lib[rnd] = 1;
/ R& D3 s4 a4 J6 f- y' l& L' K: S$ y                    count--;
                }
            }
( x4 t' t4 ~2 F: U            //循环检查最密集区域，也就是需要移动最少的区域
) S& {  u$ H8 {5 }$ F8 t            int min_space = n;
( l3 X/ u/ i& q9 k9 i7 i/ A            for (int i = 1; i <= max - n + 1; i++)
/ N4 |2 E% b7 H8 I            {
                int space = space_count(lib, i, n);
# K! R& K' T8 z2 }6 X" D                if (min_space > space) min_space = space;
            }
$ G. _) j) n' O# j7 p. G            return min_space;
        }
5 s- Y( c3 K& u" v6 i
* R6 x1 z# g7 R7 |        private int space_count(int[] lib, int start, int n)
        {   //检查数组start后面n项数据里面有多少个1
            int count = 0;
            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
# |+ ]9 D4 L0 \3 m* d            return count;
        }
1 L% ~& t* [! ^" _7 I" u

bingcheers

回复 trytoday 的帖子
) m, A* E9 G* l. y( a: I% Y
) s0 }; S8 J% W" M. C. r+ ?7 M
    牛牛，    牛牛，    牛牛

trytoday

问题已经被另一位高人解决，请参阅：
8 a2 t6 E2 ?6 }. l1 f, h# xhttp://topic.csdn.net/u/20100626 ... d-0495bbbb15fc.html

角凳

好像不是很有意义...