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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
' F; r$ R* a( Q% i* M( {1 Y+ e- q
& i: F7 c$ A3 r, |5 q* Y
! G: Y5 C6 ^: {  y+ f9 R比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
" k$ O3 F4 _$ I$ O
例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

linmatsas

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

yupo_smart

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

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
0 f4 A- k+ {. ]% q* W, z8 l
8 b% H5 W' x- D) k: \0 R另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
2 J3 P8 C. J+ f$ l1 @$ o我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：

) v1 [5 S6 W/ e0 W0 P& X/ X' C& }1 O
5 D6 T- E5 @- t9 ^$ W1 |( {% xC#code:
                private void button1_Click(object sender, EventArgs e)
( o9 g+ _, t/ k; G' V$ a                {
            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
            //          就可以使所有车辆连续停放
            
            int n = int.Parse(textBox1.Text);
7 k8 y0 f, b; [% e4 X9 G            int x = int.Parse(textBox2.Text);

' j& h( A% Y% n8 v0 A- u            //500次随机模拟的最接近数字，对比公式计算
9 O6 t$ Z8 Z7 D8 L/ W( g            int maxValue = 0;
( }5 y" ?7 k( l            for (int i = 0; i < 500; i++)
            {
                int value = randResult(x, n);
                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
9 M. Z2 |! O; [+ a& w' U/ j                lbMsg.Refresh();
            }
4 a( I* k7 W& N            textBox3.Text = maxValue.ToString();

            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
2 o5 |% i+ y- a( x            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
                }

* j  o" l5 W/ E! P# Y; r        private int randResult(int max, int n)
  q4 N  P1 r- ^        {
# h9 o4 @3 u! Z7 u% }            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
5 F) ^  y8 M) S6 |            if (max < 3) return 0; //error

; x8 J! R; E# H2 @1 Y: Q, e            int[] lib = new int[max + 1];
            //随机产生数字来填充
8 \( s& s2 Q0 d/ ~9 N) z3 v6 D6 u            lib[1] = 1; lib[max] = 1;
" n' G; P1 y3 D3 C            int count = n - 2;
            Random rand = new Random();
6 o1 G0 l" ^( ^3 I- {            while (count > 0)
            {
                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
                {
1 o( v9 e" Q) O; S. ~0 {+ [% V                    lib[rnd] = 1;
                    count--;
6 |* D2 l( I% W0 C! _                }
            }
            //循环检查最密集区域，也就是需要移动最少的区域
  {+ o9 U+ r( y. b  [            int min_space = n;
            for (int i = 1; i <= max - n + 1; i++)
5 y) y) a+ C7 D            {
                int space = space_count(lib, i, n);
' o& u7 k' b2 N+ B+ Y                if (min_space > space) min_space = space;
6 t+ F. ^$ C: U            }
) w+ S, B& |8 c2 t            return min_space;
4 O) H) ^. g: j        }

: a7 T4 ~3 r! Z2 }- D  z/ n        private int space_count(int[] lib, int start, int n)
0 u* {) ^8 M# z! h; p* e) x$ m7 [        {   //检查数组start后面n项数据里面有多少个1
( }% c( C4 W: n, S6 ~            int count = 0;
3 S+ G5 w* m, F4 c: ^# x" s            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
) u6 ^! _9 t: y0 B, z- v            return count;
8 _. j" j9 F# A. w9 h$ ~: S        }
- b4 W# O$ ?; q% K3 v

bingcheers

回复 trytoday 的帖子
% ^7 d( O+ B7 y7 Q
/ N* R0 N: r! z9 f; [5 K
    牛牛，    牛牛，    牛牛

trytoday

问题已经被另一位高人解决，请参阅：
5 i/ ?. {' J% u* zhttp://topic.csdn.net/u/20100626 ... d-0495bbbb15fc.html

角凳

好像不是很有意义...