查看: 4980|回复: 6

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

[复制链接]

字体大小: 正常放大

trytoday

1 主题	2 听众	14 积分

升级 9.47%

该用户从未签到

电梯直达

1^#

发表于 2010-6-27 15:46 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

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

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

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

linmatsas

53 主题	13 听众	3592 积分

逍遥游

TA的每日心情

	奋斗 2014-12-2 09:53

签到天数: 54 天

[LV.5]常住居民I

自我介绍: 额。。。。世界上最讨厌的事情就是自我介绍。。。

群组: Matlab讨论组

群组: 数学建模

群组: 小草的客厅

群组: 2012数学一考研交流

群组: C 语言讨论组

2^#

发表于 2010-6-27 16:24 |只看该作者 |招呼Ta 关注Ta |邮箱已经成功绑定

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

我也说一句

发表

使用道具举报

yupo_smart

6 主题	5 听众	525 积分

升级 75%

TA的每日心情

	奋斗 2016-5-23 20:51

签到天数: 9 天

[LV.3]偶尔看看II

群组: 数学建模

群组: Matlab讨论组

群组: Linux推广

群组: 09年国际数学建模群—鹰之队

群组: 半**流

3^#

发表于 2010-6-27 19:25 |只看该作者 |招呼Ta 关注Ta |邮箱已经成功绑定

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

我也说一句

发表

使用道具举报

trytoday

1 主题	2 听众	14 积分

升级 9.47%

该用户从未签到

4^#

发表于 2010-6-27 21:49 |只看该作者 |招呼Ta 关注Ta

已经能够确定的是：如果 x > (n * (n-1) + 1)，表示密度太‘稀’了，这种情况下必然是移动 n - 1次，也就是说保留一个以外都得移动。

另外发现一个简化公式 n - (n*n/x)。用这个公式计算的结果在一些情况有少量误差。
我也没有标准答案来判断误差，只是用随机模拟的方式，对指定的 n x 随机几百次试验确定最有可能的值，以下是代码，效率一般，但n在1000以上几百次模拟也能在几秒内搞定：

C#code:
private void button1_Click(object sender, EventArgs e)
{
         //新的描述：编号 1 -- X 的停车位，随机停放 n 辆车，无论当前车辆怎样的位置，最少让多少辆车重新停放
         //       就可以使所有车辆连续停放

         int n = int.Parse(textBox1.Text);
         int x = int.Parse(textBox2.Text);

         //500次随机模拟的最接近数字，对比公式计算
         int maxValue = 0;
         for (int i = 0; i < 500; i++)
         {
            int value = randResult(x, n);
            if (maxValue < value) maxValue = value;
            lbMsg.Text = i.ToString();
            lbMsg.Refresh();
         }
         textBox3.Text = maxValue.ToString();

         //这是公式计算的结果，据观察大部分正确，少数误差也不超过 3  ：）
         double newValue = (double)n - ((n*n)/(double)x);
         textBox4.Text = newValue.ToString();
}

      private int randResult(int max, int n)
      {
         if(max <= n) return 0; //error
         if (n < 3) return 0; //error
         if (max < 3) return 0; //error

         int[] lib = new int[max + 1];
         //随机产生数字来填充
         lib[1] = 1; lib[max] = 1;
         int count = n - 2;
         Random rand = new Random();
         while (count > 0)
         {
            int rnd = rand.Next(1, max);
            if (lib[rnd] == 0)
            {
                  lib[rnd] = 1;
                  count--;
            }
         }
         //循环检查最密集区域，也就是需要移动最少的区域
         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;
         }
         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;
      }