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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
, N3 V, I! p' X  f+ o: d

比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
) S3 c0 m1 k" b" K+ v# ~& K
+ D1 D& k8 @( |8 Y' a# F' z6 X. D例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

角凳

好像不是很有意义...

trytoday

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

bingcheers

回复 trytoday 的帖子
$ o- }8 i' V; c% C1 K6 B

    牛牛，    牛牛，    牛牛

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
' h9 G$ i" x/ x& H. \; N' X
- H$ n9 T" q/ K! F$ `另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
6 c, M* H  \! `5 g$ q. Q我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：


C#code:
                private void button1_Click(object sender, EventArgs e)
# x  ^: C) E) t+ E- h                {
. s) M) ^/ U9 m2 t; K9 Z4 t$ p. z            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
            //          就可以使所有车辆连续停放
) K$ N' R( ?" ?: j            
. Q: A4 W9 q( d            int n = int.Parse(textBox1.Text);
4 @6 ]9 G" y5 U! p# G7 j            int x = int.Parse(textBox2.Text);
! Z5 b5 A. l3 E5 P, O$ ^# R
: O9 d$ \7 g0 ^" {            //500次随机模拟的最接近数字，对比公式计算
$ g# Y/ T( v9 F8 i- e* w7 w            int maxValue = 0;
            for (int i = 0; i < 500; i++)
            {
; g6 x+ D% \1 k                int value = randResult(x, n);
                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
3 }) P( O7 i+ @' ~8 Y. ]                lbMsg.Refresh();
1 I+ d' Y  ~5 g! R            }
( |# ^( {0 ^; T1 w9 R1 O            textBox3.Text = maxValue.ToString();

            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
8 A" B+ K: x# Q" ?+ A1 ]            double newValue = (double)n - ((n*n)/(double)x);
" w4 N% w' k6 u; i- c, W            textBox4.Text = newValue.ToString();
                }
) X  t$ H0 g( Y1 Q
1 i4 z3 p$ z% ]" }5 t: f7 `+ ^        private int randResult(int max, int n)
' E" M$ k- z+ i9 q( z        {
; V3 k7 @, {% B) @            if(max <= n) return 0; //error
            if (n < 3) return 0; //error
+ A  Z& v5 l; ^/ Y            if (max < 3) return 0; //error
! c6 [$ O3 D( t. V" ?1 s$ v
            int[] lib = new int[max + 1];
            //随机产生数字来填充
: S  B* v( X  H6 {. P2 w. N            lib[1] = 1; lib[max] = 1;
; S  I2 g+ n9 S. ~; W            int count = n - 2;
7 K+ S, M  V( @% s: X8 P/ F            Random rand = new Random();
3 x" n5 T' F/ z$ x            while (count > 0)
            {
- c, V* o7 k5 X- e/ i6 \2 }: C$ [' o                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
                {
                    lib[rnd] = 1;
                    count--;
8 Z# a( a" ~( [+ L* x( o( J                }
5 b5 w# |2 c2 O; T8 j, M1 G: e            }
. G% t$ M9 l1 j! S; r! e            //循环检查最密集区域，也就是需要移动最少的区域
            int min_space = n;
: t2 m" @. V& o+ }, `            for (int i = 1; i <= max - n + 1; i++)
# p, ?5 h2 s7 v, c& Z            {
) X% N1 r  f" P$ g                int space = space_count(lib, i, n);
6 D2 @8 z7 H! g: }4 p" ?                if (min_space > space) min_space = space;
            }
1 W- p; w/ `# h' ?            return min_space;
        }

& _7 L& w, W+ Y! B" b$ U; R. o  E: o        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++;
3 l5 F& P/ C/ }0 |            return count;
& r! N5 n+ m. R, ]  M        }

yupo_smart

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

linmatsas

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