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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
8 v' U  V$ i( Q1 R

2 D8 K( r: q% b  h比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。

例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

linmatsas

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

yupo_smart

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

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
2 z4 v* X2 w  y+ A/ g
8 H! }: l) z0 q. k6 B另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：
6 ]! W2 d( N7 z& N) ]& A
/ @% A9 Q% d  |+ B9 d( }
3 ?4 y( O* F; F+ U, nC#code:
                private void button1_Click(object sender, EventArgs e)
                {
            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
            //          就可以使所有车辆连续停放
4 p0 P2 ]0 |! i$ Z. \            
            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);

            //500次随机模拟的最接近数字，对比公式计算
            int maxValue = 0;
            for (int i = 0; i < 500; i++)
4 \! B: a9 b* }- D) a            {
( z% e1 V/ S4 ?8 A                int value = randResult(x, n);
                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
% {- ]5 I% {, _- x            }
0 D  v* `5 _9 z* @/ r/ T            textBox3.Text = maxValue.ToString();
; L# T8 f8 C3 b* T' J
            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
  ]( G( }2 [2 h8 w            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
: p/ S. P& I% q                }

        private int randResult(int max, int n)
        {
* H' {5 S, I" F! w            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
% g! D  Y! B2 m1 Q            if (max < 3) return 0; //error

            int[] lib = new int[max + 1];
            //随机产生数字来填充
$ H7 z2 Z9 C9 k/ S" v            lib[1] = 1; lib[max] = 1;
  t# ~6 K4 w& T: m4 x            int count = n - 2;
2 u, Q- W8 F& T/ [$ R; I            Random rand = new Random();
            while (count > 0)
1 _- V- M, \9 G) [            {
" }1 s5 y( P/ W8 |                int rnd = rand.Next(1, max);
8 b1 k/ ~& Q# a7 f! `5 G" i                if (lib[rnd] == 0)
                {
                    lib[rnd] = 1;
                    count--;
                }
) C- m0 e# a* D' S+ m/ W* H            }
6 p8 |9 R. s# f6 w, O5 c& L! @* T            //循环检查最密集区域，也就是需要移动最少的区域
" K7 w: ?6 o; j, j/ z* }6 p            int min_space = n;
9 |# }) P0 h8 m3 L            for (int i = 1; i <= max - n + 1; i++)
            {
) I. q- P8 r& N# c6 T8 c                int space = space_count(lib, i, n);
& t  q/ R( {! I3 q                if (min_space > space) min_space = space;
            }
' Y  U/ N0 Y4 |( n7 b8 m            return min_space;
        }
9 R3 S6 i+ f9 q$ {1 ]
( g0 l- z0 v8 [        private int space_count(int[] lib, int start, int n)
        {   //检查数组start后面n项数据里面有多少个1
: J. g* g$ l" ?2 s6 t            int count = 0;
            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
            return count;
        }

bingcheers

回复 trytoday 的帖子

4 V/ g4 m1 }/ X7 h- g' h
    牛牛，    牛牛，    牛牛

trytoday

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

角凳

好像不是很有意义...