看着车牌忽然想到一个题目,几次变化使之连续
看着车牌忽然想到一个题目，细一想还挺难，不知道是否属于数论分类比如车牌398276，需要两次变化：把2变成4,3变成5，就成为完全连续的数字了。推广开来，一共有n个不重复的整数，最大不超过max，问需要最多几次变化可以使之全部连续。
例如上面车牌：n=6个不重复整数，最大不超过max=10，需要最多3次变化使之全部连续。 是最少需要几次变化吧………… 想法很好，可以好好考虑一下。 已经能够确定的是：如果 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;
//随机产生数字来填充
lib = 1; lib = 1;
int count = n - 2;
Random rand = new Random();
while (count > 0)
{
int rnd = rand.Next(1, max);
if (lib == 0)
{
lib = 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 == 0) count++;
return count;
}
回复 trytoday 的帖子
牛牛， 牛牛， 牛牛 问题已经被另一位高人解决，请参阅：
http://topic.csdn.net/u/20100626/17/5f9a6239-eab1-440b-9bcd-0495bbbb15fc.html 好像不是很有意义...
页:
[1]