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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
) C( i# G, ^2 H/ ^* f; d7 E

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

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

linmatsas

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

yupo_smart

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

trytoday

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


C#code:
$ A4 v* f! i, r5 n6 M. f1 `1 v                private void button1_Click(object sender, EventArgs e)
                {
% {* W, K( y& y) B4 M2 U            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
            //          就可以使所有车辆连续停放
            
            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);
0 ^7 g  T- W5 h* p4 y
! r( A$ I; b  c$ e% A  A$ a            //500次随机模拟的最接近数字，对比公式计算
5 h% ?( M% o5 A3 J  k  i2 x/ O            int maxValue = 0;
3 t! X5 o% E2 G$ u3 L- Q2 Q4 |            for (int i = 0; i < 500; i++)
            {
: x! u6 Y" I* f  W& ?$ f                int value = randResult(x, n);
                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
            }
            textBox3.Text = maxValue.ToString();

$ F' K& ]; p' o) n: d            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
6 q5 L2 o8 j6 a" J0 w& p8 i( {& h/ D            double newValue = (double)n - ((n*n)/(double)x);
+ n& W2 P$ V: e! z, W( a4 O! I            textBox4.Text = newValue.ToString();
                }
7 r1 s8 M1 u0 O+ m# W$ b5 n
7 p$ ^) H% M0 [        private int randResult(int max, int n)
0 b0 ?8 i$ M- S  [        {
            if(max <= n) return 0; //error
4 ^- `( G+ ?& j+ `            if (n < 3) return 0; //error
            if (max < 3) return 0; //error
4 {6 x, ^+ Y4 L! j+ Z: H7 d
            int[] lib = new int[max + 1];
            //随机产生数字来填充
            lib[1] = 1; lib[max] = 1;
; t2 W! T; z5 p% }            int count = n - 2;
            Random rand = new Random();
" S, u- K! V' B# Y. r            while (count > 0)
5 b% l# y$ U/ |& {5 ^. X# H& o3 K            {
                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
% V! H% O4 T$ G2 Z* H                {
                    lib[rnd] = 1;
; f. T  R+ }3 m8 s                    count--;
                }
9 P& s1 }+ a% s: ~" @            }
            //循环检查最密集区域，也就是需要移动最少的区域
            int min_space = n;
            for (int i = 1; i <= max - n + 1; i++)
            {
                int space = space_count(lib, i, n);
                if (min_space > space) min_space = space;
" y& ]: A! O1 N6 d5 A% u            }
+ ~) f3 G" b! U4 D- T            return min_space;
        }
2 V& y4 J: W  [, v) c; H
. X8 B+ R: \1 Q( r( S( n! {        private int space_count(int[] lib, int start, int n)
& K6 x$ Z- D% Z* \! J2 k5 @' Q! k        {   //检查数组start后面n项数据里面有多少个1
            int count = 0;
            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
) p% s8 R9 I1 |$ W+ M/ E6 J) d            return count;
        }
" V- M3 f$ U1 Y6 O& }

bingcheers

回复 trytoday 的帖子

7 ?; z! A$ C+ q% v7 t8 {
    牛牛，    牛牛，    牛牛

trytoday

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

角凳

好像不是很有意义...