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

trytoday

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


比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
2 p0 d4 x2 r! ^4 V
* V9 D4 c$ Y9 ~! G0 s2 I+ _例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

linmatsas

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

yupo_smart

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

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
8 _% D% H% l8 K/ w2 y0 @' u
8 `, Z& R' ^  ~. Z另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：
# K3 C2 h, b" n8 R. ^

C#code:
                private void button1_Click(object sender, EventArgs e)
                {
& c# I2 |0 x/ ^            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
            //          就可以使所有车辆连续停放
            
% V1 N) F! Z" `            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);
- J  H, x2 A  V( g- h9 ~7 @8 A* L+ F
/ s" C3 t/ S: Y            //500次随机模拟的最接近数字，对比公式计算
9 ]. o7 c( P7 d            int maxValue = 0;
2 \! \! [2 I- \" _            for (int i = 0; i < 500; i++)
            {
                int value = randResult(x, n);
                if (maxValue < value) maxValue = value;
  l8 ?4 f0 I* ]' y                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
            }
+ B+ ?7 l9 @' K5 {2 m            textBox3.Text = maxValue.ToString();
( K4 t3 o0 n- y: s7 b
  L- E' m+ P) p' ~$ `) b# n$ R            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
) y" M; d$ K/ F+ z" r' A            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
5 I2 Z9 G! p: d                }

& B0 m  |; C9 P0 V0 l2 p6 t) s) x        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];
- Q) e  c6 Z! K! o. l            //随机产生数字来填充
            lib[1] = 1; lib[max] = 1;
            int count = n - 2;
3 D% T. e9 @1 W$ e9 ~, b/ Z9 L            Random rand = new Random();
( B. W; c( R# S2 ^8 G8 n$ j: Z, M9 \            while (count > 0)
7 b! s4 Q7 Z1 |2 H+ T( O- d' y9 ]            {
                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
                {
                    lib[rnd] = 1;
                    count--;
% R0 p0 V) d5 j6 L1 z; w& {                }
            }
            //循环检查最密集区域，也就是需要移动最少的区域
            int min_space = n;
5 ~) @4 s0 m) g+ A            for (int i = 1; i <= max - n + 1; i++)
            {
4 ]5 d( {* e4 T                int space = space_count(lib, i, n);
) b+ P3 Q% m( i                if (min_space > space) min_space = space;
            }
  S3 Q7 }0 Q5 G8 D+ n/ u            return min_space;
        }
8 w7 V3 Y) ~: U/ E2 d- V7 [2 w
5 K+ r+ H" H, E6 M7 K* c        private int space_count(int[] lib, int start, int n)
        {   //检查数组start后面n项数据里面有多少个1
" N  I. r$ e3 Z* n) t: \            int count = 0;
+ i) Q. o3 k8 l& G" L9 _* G  u            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
! N2 }% t# {1 C6 V/ N  @            return count;
        }

bingcheers

回复 trytoday 的帖子


    牛牛，    牛牛，    牛牛

trytoday

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

角凳

好像不是很有意义...