C++炮台实验

2021-02-13 22:20

阅读：429

标签：cstring fine 循环失败例子 double mes ref on()

炮台实验

蒜头君在玩一个战争模拟游戏，他有高度为 1,2,3,... ,n的炮台各一个，他需要把这 n个炮台从左往右排成一行，并且炮口都朝向右边。

在这个游戏中，所有炮台发射的炮弹会摧毁前方所有高度比自己低的炮台。每当蒜头君把 n个炮台排成一行后，可能会有一些炮台被摧毁。举个例子：当前有 5 个炮台，从左到右高度分别为 2,1,3,5,4往右发射炮弹后，高度为 4 的炮台被高度为 5 的摧毁，高度为 1 的炮台被高度为 2 的炮台摧毁，最后只会剩下 2,3,5 这三个炮台。

现在蒜头君想知道，如果随机地摆放这 n个炮台，最后剩下炮台个数的期望是多少？比如 n=时，有两种摆放方式，高度序列分别为 1,2和 2,1，前者最后剩下 22 个炮台，后者最后剩下一个炮台，因此期望为 (2+1)\2=1.5000。

请你求出 n=201时剩下炮台个数的期望，保留四位小数。

样例输入复制

无

样例输出复制

无

题目来源

2019 蓝桥杯省赛 A 组模拟赛（一）

思路一（运行时间过长，失败）：

创建一个数组arr[2019]之后分别赋值为1,2,3.....2019。随后用next_permutation()函数把所有的排列情况都输入一遍，之后用循环把后面小于前面的数都去掉变可以了。

代码如下：

#include 
#include 
#includestring>
#include
#includeusing namespace std;
#define N 9
int main()
{
    int arr[2019];
    for (int i = 0;i i)
    {
        arr[i] = i+1;
    }
    double num1 = 0, num2 = 0;
    do {
        bool b[2019] = { 0 };
        num2++;
        for (int i = 0;i i)
        {
            for (int j = i + 1;j j)
            {
                if (arr[i] > arr[j]) b[j] = 1;
            }
        }
        for (int i = 0;i i)
        {
            if (!b[i]) num1++;
        }
    } while (next_permutation(arr, arr + N));
    printf("%.4f", num1/num2 );
    return 0;
}

运行发现之后，想法很好，但是由于循环次数很大，编译器需要大量时间，也就能算n=20左右的情况，这离2019还差很多，所以这个思路就得换了，于是产生了第二个思路。

思路二：

因为题中是求期望值，比如2019这个数，无论怎么排列2019这个数都是存在的，所以2019这个数期望值是1；2018这个数只有2019在他前面时候才能消灭它，所以2018这个数的期望值就是1/2;同理，n=2019时，只用一个循环1/i就可以解决了。

代码如下：

#include
#includeusing namespace std;
int main()
{
    double num = 0;
    int n = 2019;
    for (int i = 1; i ) {
        num += 1.0 / i;
    }
    printf("%.4f\n", num);
    return 0;
 }

C++炮台实验

标签：cstring fine 循环失败例子 double mes ref on()

原文地址：https://www.cnblogs.com/liushipeng648/p/12725100.html

上一篇：Java并发组件二之CyclicBarriar

下一篇：数据结构和算法(Golang实现)(19)排序算法-冒泡排序

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：C++炮台实验
文章链接：http://soscw.com/essay/55002.html

亲，登录后才可以留言！

C++炮台实验

炮台实验

样例输入复制

样例输出复制

题目来源

评论

热门文章

推荐文章

最新文章

置顶文章