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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
/ [+ z0 Y# i% c- \# g4 x' G

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

角凳

好像不是很有意义...

trytoday

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

bingcheers

回复 trytoday 的帖子
  i1 v( ]( w) n4 [& s$ D

    牛牛，    牛牛，    牛牛

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
! G; G3 s7 H- [* _+ j; R7 t
另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：

2 }  ^0 |+ p4 x/ {) Y  W
C#code:
                private void button1_Click(object sender, EventArgs e)
                {
0 H' C! w4 e1 O  ^3 W) y            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
* B# s& S' c! c2 ]5 J  }. m            //          就可以使所有车辆连续停放
            
            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);
/ l% l  w" _3 e5 s. ]  ^. `
/ k/ Y5 @* L+ P) a1 b            //500次随机模拟的最接近数字，对比公式计算
  I0 v6 j2 Z0 R% A            int maxValue = 0;
            for (int i = 0; i < 500; i++)
; f9 A$ w, l) g9 n# H' F3 b2 \            {
                int value = randResult(x, n);
9 v3 p1 w# ^* R% z3 l4 x3 J3 c                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
+ M8 T# p. V1 D. _; f( }            }
# j' \5 X8 e/ `            textBox3.Text = maxValue.ToString();

            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
; s  R$ Q/ S% y7 h  h: A            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
# W* w4 D  s. H# a% i                }
8 j! W/ B  {; G6 G
0 |1 ~5 F# t; |6 g        private int randResult(int max, int n)
        {
            if(max <= n) return 0; //error
: Q/ }( e! z; \+ P$ S9 g            if (n < 3) return 0; //error
            if (max < 3) return 0; //error

4 C9 p) d2 h- @0 R; t* j            int[] lib = new int[max + 1];
            //随机产生数字来填充
            lib[1] = 1; lib[max] = 1;
            int count = n - 2;
: b& J* i# X. Z, O. z( y            Random rand = new Random();
            while (count > 0)
, g% m% E8 T- |/ }  T& w1 Z. R            {
                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
                {
                    lib[rnd] = 1;
                    count--;
                }
$ S& y- i3 V9 Z/ t8 a* q7 X. Y            }
            //循环检查最密集区域，也就是需要移动最少的区域
/ Y. M! a  k. e$ ~            int min_space = n;
            for (int i = 1; i <= max - n + 1; i++)
; W6 O4 ?) ?" u. |9 b- Y. q            {
$ v! @# g+ v0 ~2 l5 `: q7 P                int space = space_count(lib, i, n);
; M% f7 [" U1 B' u1 D6 N% q                if (min_space > space) min_space = space;
            }
            return min_space;
& Z# J$ J( g1 l) _7 ?$ m        }

        private int space_count(int[] lib, int start, int n)
/ n0 G; P+ K$ x4 X4 F# [        {   //检查数组start后面n项数据里面有多少个1
            int count = 0;
            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
            return count;
        }
7 k( ^- N, h. V6 R

yupo_smart

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

linmatsas

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