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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类


比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
* B* g0 L+ \  Q
! b& }) n% e; `% ~3 P  c' T8 O例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

linmatsas

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

yupo_smart

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

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
6 ]  q( s0 C4 B: P
另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：
, e* [3 r! k1 P* _
! T3 e: m6 f7 N2 i9 x  }
C#code:
                private void button1_Click(object sender, EventArgs e)
2 ]! T5 d' n7 e! o# v2 {" ?                {
3 C& t) J8 K# G% s            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
            //          就可以使所有车辆连续停放
7 W% G/ E& }# j% O, j+ ?            
* S* r) S/ p: V$ l8 T& [+ s) C            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);
6 V- V$ p( ]9 I& R8 Q8 c  ^; p# }; ]
            //500次随机模拟的最接近数字，对比公式计算
0 G3 F9 _$ t8 e; b: f0 K6 W9 a2 c9 M            int maxValue = 0;
4 c7 V+ m8 X# D3 s9 [            for (int i = 0; i < 500; i++)
            {
7 _. m2 p  t3 R( X9 {' N                int value = randResult(x, n);
                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
! Y( K; M+ f6 Z                lbMsg.Refresh();
6 Z* n8 ?# d3 U6 X# |5 H- E            }
            textBox3.Text = maxValue.ToString();

            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
! U+ A* e+ [, L3 r; [            double newValue = (double)n - ((n*n)/(double)x);
3 @4 E5 R/ ?. a6 P7 q            textBox4.Text = newValue.ToString();
$ V; E( c' T6 [0 _1 F3 t                }

7 e( C) F; L5 ~4 d! b6 e4 T        private int randResult(int max, int n)
        {
            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
            if (max < 3) return 0; //error

            int[] lib = new int[max + 1];
            //随机产生数字来填充
1 Y- F$ u7 a/ |2 W, S7 X9 ]6 [            lib[1] = 1; lib[max] = 1;
            int count = n - 2;
! H2 i5 a4 z' s, m            Random rand = new Random();
            while (count > 0)
            {
                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
                {
  g: R6 i6 A- ]+ C4 o+ q( ~                    lib[rnd] = 1;
9 j' S( n1 I. _3 x! w% w                    count--;
                }
            }
1 o- X8 M! m3 q  v* I3 h            //循环检查最密集区域，也就是需要移动最少的区域
            int min_space = n;
5 [) h0 e" A( h7 G, s* v! t/ C            for (int i = 1; i <= max - n + 1; i++)
# Q; G* r1 Q- j+ W            {
& \$ u4 G1 ]2 g8 c                int space = space_count(lib, i, n);
2 C- z' h+ M  u# t1 w                if (min_space > space) min_space = space;
/ V  Y$ X* B( f" [  J# Z, a            }
4 e0 i0 e. U) \2 M# \# v7 ^' f            return min_space;
$ [$ H9 T6 ~' X) c. Q6 N        }
3 c8 K: N3 F! @& @+ |6 Z4 K' U, a6 H
+ [/ x* c  {% l$ Z        private int space_count(int[] lib, int start, int n)
        {   //检查数组start后面n项数据里面有多少个1
4 s" z# E4 s+ i5 E/ D            int count = 0;
            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
            return count;
        }

bingcheers

回复 trytoday 的帖子

7 d. i% q' C. }; K5 }: F
/ K7 j8 j# ?3 G4 x) Z2 H, a1 F4 x    牛牛，    牛牛，    牛牛

trytoday

问题已经被另一位高人解决，请参阅：
http://topic.csdn.net/u/20100626 ... d-0495bbbb15fc.html

角凳

好像不是很有意义...