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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
* W+ J4 Y! o, n5 X

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

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

linmatsas

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

yupo_smart

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

trytoday

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

, \. x8 w' s( h! B
C#code:
% C) o3 J' c* }$ A/ ^8 e$ @7 d9 q                private void button1_Click(object sender, EventArgs e)
                {
            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
6 {  I3 D3 V- d& @9 z7 b0 |9 O            //          就可以使所有车辆连续停放
            
            int n = int.Parse(textBox1.Text);
9 B5 r# E! u+ Q/ M# r# J0 _& B5 B            int x = int.Parse(textBox2.Text);
! G& {$ h: W( Y, A7 {
            //500次随机模拟的最接近数字，对比公式计算
+ m1 P2 Y) \1 a! y# m$ X9 }            int maxValue = 0;
            for (int i = 0; i < 500; i++)
, t6 W5 z1 @' _            {
                int value = randResult(x, n);
5 E2 L8 _2 D% C9 `# \                if (maxValue < value) maxValue = value;
$ B) @% J" e4 A- Y$ C! f0 ?                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
            }
! D- k& U- e5 r            textBox3.Text = maxValue.ToString();
' [; |7 M* d+ t3 O" ~
            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
            double newValue = (double)n - ((n*n)/(double)x);
4 ?3 Z1 f, J5 x) R# p. d            textBox4.Text = newValue.ToString();
  M4 ]9 p7 u  |* l* S+ W                }
" x& r. T5 L- o3 N
2 D4 N% U" X$ j        private int randResult(int max, int n)
. V: ^2 T( z: r0 t7 c/ ?2 n        {
3 Y8 z1 A, Q" M' l6 K- z            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
            if (max < 3) return 0; //error
) r) d* H, m6 ?. R9 y* I
            int[] lib = new int[max + 1];
9 ]1 h# m+ f9 \" |" o' f            //随机产生数字来填充
            lib[1] = 1; lib[max] = 1;
            int count = n - 2;
            Random rand = new Random();
            while (count > 0)
" C$ ?. t2 d2 m0 P' [7 l6 p2 D9 o6 s# Q            {
5 r. f* b' a% r% Q                int rnd = rand.Next(1, max);
& K3 P: V( Q3 n1 I                if (lib[rnd] == 0)
6 c+ l+ c9 o4 [& U6 ^# y                {
4 o, I- u: ~# [& |; p                    lib[rnd] = 1;
                    count--;
$ M, Y& I# O; n8 r/ b6 [+ |5 g                }
2 G) d5 c' M- ^3 h  t7 x            }
            //循环检查最密集区域，也就是需要移动最少的区域
# U6 E7 q, e8 D4 t4 P4 C1 ?            int min_space = n;
            for (int i = 1; i <= max - n + 1; i++)
            {
+ j: m& O$ i5 c" h8 ^                int space = space_count(lib, i, n);
: P- x! h4 d; W/ I' R                if (min_space > space) min_space = space;
            }
            return min_space;
" n/ d6 H6 [, {* q, f1 n$ E* Z% T$ u        }

        private int space_count(int[] lib, int start, int n)
        {   //检查数组start后面n项数据里面有多少个1
            int count = 0;
            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
/ E  k9 W, V; Y7 f8 U* }9 W4 w; L            return count;
- W4 [0 [& [5 j& C' k        }
9 j' Z' w5 O5 A( @% ~# B

bingcheers

回复 trytoday 的帖子

8 r+ T9 _6 w, j0 T0 P% \' k
( D9 j7 v3 z1 H/ V    牛牛，    牛牛，    牛牛

trytoday

问题已经被另一位高人解决，请参阅：
0 S+ k! V  h9 P6 V# e' Y0 _/ whttp://topic.csdn.net/u/20100626 ... d-0495bbbb15fc.html

角凳

好像不是很有意义...