程序的输出为( )_360集团笔试题

#include<iostream>
using namespace std;

int n = 300;
int solve(int x) {
    return x * (n - x);
}
int main() {
    int l = 1, r = n;
    int mid1, mid2;
    int t = 50;
    while (t--) {
        mid1 = l + r >> 1;
        mid2 = mid1 + r >> 1;
        if (solve(mid1) > solve(mid2)) {
            r = mid2;
        } else {
            l = mid1;
        }
    }
    cout << l << endl;
    return 0;
}

程序的输出为（）

201906261056657

t=49: r=mid2: 225 = 225 l=mid1: 1 = 150
t=48: r=mid2: 225 = 169 l=mid1: 113 = 113
t=47: r=mid2: 197 = 197 l=mid1: 113 = 169
t=46: r=mid2: 176 = 176 l=mid1: 113 = 155
t=45: r=mid2: 160 = 160 l=mid1: 113 = 144
t=44: r=mid2: 160 = 148 l=mid1: 136 = 136
t=43: r=mid2: 154 = 154 l=mid1: 136 = 148
t=42: r=mid2: 154 = 149 l=mid1: 145 = 145
t=41: r=mid2: 154 = 151 l=mid1: 149 = 149
t=40: r=mid2: 152 = 152 l=mid1: 149 = 151
t=39: r=mid2: 151 = 151 l=mid1: 149 = 150
t=38: r=mid2: 151 = 150 l=mid1: 150 = 150
t=37: r=mid2: 151 = 150 l=mid1: 150 = 150
t=36: r=mid2: 151 = 150 l=mid1: 150 = 150
t=35: r=mid2: 151 = 150 l=mid1: 150 = 150
t=34: r=mid2: 151 = 150 l=mid1: 150 = 150
t=33: r=mid2: 151 = 150 l=mid1: 150 = 150
t=32: r=mid2: 151 = 150 l=mid1: 150 = 150
t=31: r=mid2: 151 = 150 l=mid1: 150 = 150
t=30: r=mid2: 151 = 150 l=mid1: 150 = 150
t=29: r=mid2: 151 = 150 l=mid1: 150 = 150
t=28: r=mid2: 151 = 150 l=mid1: 150 = 150
t=27: r=mid2: 151 = 150 l=mid1: 150 = 150
t=26: r=mid2: 151 = 150 l=mid1: 150 = 150
t=25: r=mid2: 151 = 150 l=mid1: 150 = 150
t=24: r=mid2: 151 = 150 l=mid1: 150 = 150
t=23: r=mid2: 151 = 150 l=mid1: 150 = 150
t=22: r=mid2: 151 = 150 l=mid1: 150 = 150
t=21: r=mid2: 151 = 150 l=mid1: 150 = 150
t=20: r=mid2: 151 = 150 l=mid1: 150 = 150
t=19: r=mid2: 151 = 150 l=mid1: 150 = 150
t=18: r=mid2: 151 = 150 l=mid1: 150 = 150
t=17: r=mid2: 151 = 150 l=mid1: 150 = 150
t=16: r=mid2: 151 = 150 l=mid1: 150 = 150
t=15: r=mid2: 151 = 150 l=mid1: 150 = 150
t=14: r=mid2: 151 = 150 l=mid1: 150 = 150
t=13: r=mid2: 151 = 150 l=mid1: 150 = 150
t=12: r=mid2: 151 = 150 l=mid1: 150 = 150
t=11: r=mid2: 151 = 150 l=mid1: 150 = 150
t=10: r=mid2: 151 = 150 l=mid1: 150 = 150
t=9: r=mid2: 151 = 150 l=mid1: 150 = 150
t=8: r=mid2: 151 = 150 l=mid1: 150 = 150
t=7: r=mid2: 151 = 150 l=mid1: 150 = 150
t=6: r=mid2: 151 = 150 l=mid1: 150 = 150
t=5: r=mid2: 151 = 150 l=mid1: 150 = 150
t=4: r=mid2: 151 = 150 l=mid1: 150 = 150
t=3: r=mid2: 151 = 150 l=mid1: 150 = 150
t=2: r=mid2: 151 = 150 l=mid1: 150 = 150
t=1: r=mid2: 151 = 150 l=mid1: 150 = 150
t=0: r=mid2: 151 = 150 l=mid1: 150 = 150

发表于 2019-11-02 10:33:13 回复(5)

蜗牛Gray

+运算符的优先级高于位移运算符

l和r逐渐向函数的最大值（150）靠近

发表于 2020-03-20 23:55:29 回复(0)

牛客42755756号

#include<bits/stdc++.h>

using namespace std;

int n = 300;

int solve(int x){

return x * (n - x);//对此函数求导，发现最大值在150处，先增后减

}

int main(){

int l = 1, r = n;

int mid1, mid2;

int t = 50;

while(t--){

mid1 = l + r >> 1;//L和R中的中值点，向右移位一位可视为除以2

mid2 = mid1 + r >> 1;//在mid1和R中的中值点

if(solve(mid1) > solve(mid2))//缩小范围，改变较小值一端的范围（L和R），确保较大值在范围内

{

r = mid2;

}

else{

l = mid1;

}

cout<< l <<endl;//经过50次循环，范围不断靠近最大值，已知最大值在150处，范围移动了50次，每一次移动范围减半，不断靠近150

return 0;

}

发表于 2020-06-07 15:02:14 回复(0)

THE_LIN

有没有期待这个题出一个合理的解析的童鞋！来，把我顶上去，蟹蟹！

发表于 2020-05-28 23:07:33 回复(2)

蔡徐坤的篮球

像是二分查找直接蒙150

发表于 2020-04-01 15:34:40 回复(0)

风月旧年

我tm哪个是l哪个是1都看不出来

发表于 2019-12-11 13:45:30 回复(0)

珊瑚树就是豆角啊

1.常识猜测法

小学的时候有没有背过“两数的和一定，差越小积越大”，所以150乘150最大。那么要搞清楚这个函数最后留下了什么，把1到300看成数轴上面的点，那么mid1是二等分点，mid2是四等分点，且mid2 > mid1,然后对乘积做了比较，那个小，则砍掉数轴上该点向外的部分，那么最大的那个数肯定不会砍掉，所以无线循环的情况下肯定会留下150*150，答案中也有150，所以选150.

2.正解

请先看下第一种解发，其实当第一种解发完成之后，问题已经解决了大半，唯一的问题是，迭代多少次，就能得到最大值，其实每次砍掉的都是离150远的那部分，最开始数据范围是1到300，砍一刀1到225，再砍一刀，113到225，答案只能选C。有兴趣的同学可以继续砍下去。。。。

发表于 2022-01-29 18:07:29 回复(0)

幻翳

学过最优化应该会明白，这类似于最优化问题中的黄金分割法

发表于 2021-10-26 12:46:53 回复(0)

凌星晓

这个题其实可以从直觉的方面来看。

n一直不变，x * (n - x) 的极大值显然是在x=150取到。

而下面的循环其实是类似于二分查找去寻找solve更大，也就是和150更接近的值，迭代50次。

选择题嘛，看看没有151,149等可能没有完全收敛的疑似选项，差不多就可以150了。

发表于 2020-02-02 20:24:17 回复(0)

牛客903822405号

l + r >> 1 即（l + r）>> 1

发表于 2021-08-25 19:23:38 回复(0)

201902150110213

<p>log2为底数300的值大于八小于九，而t为50，一次循环就往300的中值逼近一次，所以l的值应该早就到150了</p>

发表于 2020-08-14 23:23:43 回复(0)

阿wsl

mid1 = (l + r) / 2

mid2 = (mid1 + r) / 2

将l-r的空间分成了三个部分

solve函数在参数为150时是一个临界点

所有可以轻松推测出答案是150

发表于 2020-07-26 11:38:39 回复(0)

这题一时没反应过来

>>1是移位操作。。。。

发表于 2020-03-09 20:05:33 回复(0)

喵喵喵干啥呢？

答案应该是1

发表于 2020-01-08 23:21:36 回复(3)

小zeka酱

解题步骤为：

(1) solve函数等价于数学层面的 y = -x² + 300x 函数，对函数求导可得 y' = -2x + 300，令y' = 0时，可以得到该函数的极值点，即x = 150，此时的y为最大值。

(2) main函数中有mid1 = l + r >> 1等价于 mid1 = (l + r) / 2，所以首次循环中mid1和mid2分别代表的实际含义其实是总区间[1, 300]的中点和右半区间[150, 300]的中点，依此类推循环查找令slove函数得到最大值的x点位置。

发表于 2025-04-22 09:09:20 回复(0)

超脱的肖恩在思考

mark

发表于 2024-12-04 23:13:35 回复(0)

Tudorlin

首先得知道右移以为相当于/2，然后先不看slove干了啥，直接看l+r>>1,显然这是求了lr两个数的中点，那么lr是什么呢,一个是1，一个是300，仔细一看这不是范围嘛，先记住；mid1 + r >> 1;又做了什么呢？仔细一看，刚刚的中点加上右边界再右移1，也就是另一个区间的中点。然后看if干了啥：调用了slove函数计算了两个值来比较谁大，如果是用一开始的中点算出值大，就修改右边界；反之就修改左边界，最后将修改完的边界用于下次的循环，现在完全看懂这个循环在干些啥了：求slove函数里面表达式在(l,r)范围中取得最大值的解。翻译一下就是当x∈（1,300）时，x*(300-x)取得最大值时x的取值，开口向下，b/-2a正好在区间里面，即150

发表于 2023-12-27 12:45:27 回复(0)

lei109

2022年了有人知道是为什么这样吗，我看着二分法蒙对了。。。

发表于 2022-08-31 16:48:36 回复(2)

EteRni_ty

最优化问题求极值

发表于 2022-02-07 23:03:36 回复(0)

朱修远

这里我认为的主要考察的点是运算顺序,因为我就错在这个上面.移位运算比加减运算的优先级要低一点.

发表于 2021-10-18 18:45:23 回复(0)

程序的输出为( )

问题信息

热门推荐

相关试题