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

trytoday

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


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

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

角凳

好像不是很有意义...

trytoday

问题已经被另一位高人解决，请参阅：
. R9 W; l) T+ s9 Rhttp://topic.csdn.net/u/20100626 ... d-0495bbbb15fc.html

bingcheers

回复 trytoday 的帖子


5 ~/ _  B6 R5 W1 q    牛牛，    牛牛，    牛牛

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
! K9 Q% ]% n4 Z& w6 z$ L
4 L# g# r9 I1 w. Z另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
# D" G+ G+ S$ k% ~我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：


7 U2 o( N/ s# _, l" o2 vC#code:
, R0 U1 \% w% t9 g! V% ]8 C                private void button1_Click(object sender, EventArgs e)
                {
! e0 X( o0 M3 ?' m2 A! {" p            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
2 v; A8 H. ^' w6 L0 g; `            //          就可以使所有车辆连续停放
            
2 }9 Q7 P" d/ |            int n = int.Parse(textBox1.Text);
$ I; m8 p, b  a# y            int x = int.Parse(textBox2.Text);

            //500次随机模拟的最接近数字，对比公式计算
            int maxValue = 0;
            for (int i = 0; i < 500; i++)
& Q" R: k" @+ Y# |$ x) c4 P' }            {
                int value = randResult(x, n);
6 c/ ~  D$ I4 M                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
+ z- k! x5 T' e5 T            }
            textBox3.Text = maxValue.ToString();
/ i+ N( A7 }$ W8 A- P) V1 |
* t- E( Q3 D) k: i            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
: s* R* M) Q- u+ U            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
/ c2 T. \$ R, D4 i2 a0 R; X' ~                }

        private int randResult(int max, int n)
        {
! I0 B, \* Q; W2 S% f0 a( Q            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
            if (max < 3) return 0; //error
0 l4 z6 m% f& `$ l$ s4 s
6 E- Y. L! Q; u0 n            int[] lib = new int[max + 1];
            //随机产生数字来填充
4 V& L8 j2 ^' \. ~% m5 d6 ?$ b            lib[1] = 1; lib[max] = 1;
            int count = n - 2;
            Random rand = new Random();
            while (count > 0)
            {
                int rnd = rand.Next(1, max);
0 K3 k+ x9 v4 S* N                if (lib[rnd] == 0)
0 V# V. U, J* R2 r7 g0 G- Q                {
                    lib[rnd] = 1;
1 ?; }$ H* L7 ~2 D( M( ?1 j                    count--;
                }
            }
            //循环检查最密集区域，也就是需要移动最少的区域
4 l- n( B3 ?8 `9 v, Z9 z7 A            int min_space = n;
' r* Q; ]$ N' j' X2 a& @) g            for (int i = 1; i <= max - n + 1; i++)
: S+ Z( P( n$ q3 X8 L) e% D0 L            {
3 l& ?, \/ [; V  U% Y# }                int space = space_count(lib, i, n);
                if (min_space > space) min_space = space;
$ [* H6 W) S  t7 A; B& E# S            }
            return min_space;
        }

        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++;
            return count;
1 ~9 {( P7 g8 r: o        }

yupo_smart

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

linmatsas

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