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

trytoday

看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类
* d; g  u- e: n& r) l/ U+ O9 F
1 k4 y1 a" \. F
  Q" p3 b  |, l4 u+ l比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
4 m4 H- O% |/ y8 R- u, M* ~
2 H9 ^+ T8 Q" B例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。

linmatsas

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

yupo_smart

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

trytoday

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。
' Y- p. {0 v8 g: Y) u; B- W9 w: x0 {
3 M  u; d% a0 q& V1 ~) J另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
1 P  y- q9 k. g5 g9 i, I% o我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：


. v3 U1 m7 V* V+ YC#code:
% M$ C2 v4 P* S' }& w( I                private void button1_Click(object sender, EventArgs e)
1 I) H/ f& v) f* G                {
            //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
" q  ?) e0 i0 V+ q            //          就可以使所有车辆连续停放
            
9 l# d. P* t: a            int n = int.Parse(textBox1.Text);
            int x = int.Parse(textBox2.Text);
8 W; x0 s0 M" ]3 Q8 N
            //500次随机模拟的最接近数字，对比公式计算
6 R: U" S5 J1 p) b8 M6 a            int maxValue = 0;
  X9 t9 u. l" o% m            for (int i = 0; i < 500; i++)
* c8 q& h7 E3 o1 a( ]            {
% |: v! V2 f; o$ P* I8 y                int value = randResult(x, n);
) b* b! G1 I+ E# Z! Z# C                if (maxValue < value) maxValue = value;
                lbMsg.Text = i.ToString();
                lbMsg.Refresh();
            }
! X# c  Y: k9 T& L) T5 j            textBox3.Text = maxValue.ToString();

4 V9 W% n; r" ?4 P            //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
% I. {: C: p3 D( ~; m            double newValue = (double)n - ((n*n)/(double)x);
            textBox4.Text = newValue.ToString();
) [; i" }& J- ^- O+ e& o0 q( |                }

4 a" S/ U3 a7 h% B        private int randResult(int max, int n)
        {
5 l6 \, K$ _+ L, k, a8 }* O+ x  T            if(max <= n) return 0; //error
8 T+ v, a- e, d' ^6 r) t" v            if (n < 3) return 0; //error
            if (max < 3) return 0; //error
0 \6 _1 ~/ `" `; p' C, j
4 P/ I/ L5 B8 e* h: Q; Q6 @5 U# y            int[] lib = new int[max + 1];
4 F4 N$ g* ^0 b( E; C/ [& U) s0 z            //随机产生数字来填充
9 f- k* F" f8 A6 y$ N9 V: }$ L            lib[1] = 1; lib[max] = 1;
) p/ C$ U! I1 z* {0 A) Z: ]" u            int count = n - 2;
            Random rand = new Random();
            while (count > 0)
" g' }' @5 M. p" s0 Z5 K            {
+ c8 T7 \) s# l                int rnd = rand.Next(1, max);
                if (lib[rnd] == 0)
4 B* u$ {) Z$ b. J9 m5 L                {
- H+ O( ^* [& \' f                    lib[rnd] = 1;
                    count--;
                }
0 q: t0 N! r; _6 H: l. ?. D            }
  W. X$ X" S. m" H            //循环检查最密集区域，也就是需要移动最少的区域
; Q/ U4 H: {1 C5 M8 K            int min_space = n;
2 I6 u! e8 U8 ^4 Q, B3 v            for (int i = 1; i <= max - n + 1; i++)
            {
: c1 f9 a+ ~  B8 n8 f$ G- V                int space = space_count(lib, i, n);
  |# Z8 T$ s& H+ B' J' Y                if (min_space > space) min_space = space;
' [5 Z2 g0 v  O" f2 ^1 k            }
0 M' Q+ {+ S/ t: }# u' f3 P  ^8 D            return min_space;
        }

        private int space_count(int[] lib, int start, int n)
3 y, p6 F1 L4 P+ M: W8 b3 l$ H- d        {   //检查数组start后面n项数据里面有多少个1
            int count = 0;
, Z* u' R/ P# D            for (int i = start; i < start + n; i++) if (lib[i] == 0) count++;
# K- `9 {* J- l            return count;
8 r5 @$ L5 U, J7 i# b        }
5 e* ^9 V' }6 N- j9 v3 }) T

bingcheers

回复 trytoday 的帖子

9 y' n: I2 S* l: B" m% I% q4 z
0 j$ _0 }7 `% g9 B    牛牛，    牛牛，    牛牛

trytoday

问题已经被另一位高人解决，请参阅：
" ?6 N9 j3 V( O" j" Z6 ^http://topic.csdn.net/u/20100626 ... d-0495bbbb15fc.html

角凳

好像不是很有意义...