PTA：猜数字-交互版-Toy模板网

这篇具有很好参考价值的文章主要介绍了PTA：猜数字-交互版。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

你需要编写一个“猜数字”的程序。跟你做过的大部分题目不一样，你需要通过不断地询问另外一个程序（以下称之为“交互程序”）来猜到最终的数字。

在你的程序刚运行时，交互程序会通过标准输入给你提供一个数字 N，表示你需要猜的数字在 1 到 N 范围里。

接下来你可以开始发起你的询问。你可以直接通过输出到标准输出来询问；每次询问为一个数字，表示你猜测的结果。每次询问后，你需要刷新输出流，否则可能会有输出内容停留在缓冲区不被输出。例如 C++ 你可以使用 fflush(stdout)，Java 你可以使用 System.out.flush() ，Pascal 你可以使用 flush(output) ，Python 则可以使用 stdout.flush()。

交互程序会根据你的询问返回你的猜测与正确答案的比较情况。具体而言：

如果正确答案小于你的猜测，则会返回 <；
如果正确答案大于等于你的猜测，则会返回 >=

一旦你确定你找到了正确的答案，则输出 ! x（x 是你猜测的数字，注意与感叹号用空格隔开），并立刻结束你的程序（否则判题系统可能不能返回正确的判题结果）。

最后，总的询问次数不能大于等于 25 次。

请你尝试猜对正确的数字吧！

输入样例:

20
>=
<
>=
<
>=
<

输出样例:

样例程序

以下程序用于你理解如何与交互程序进行交互，并不是正确的程序。

#include <cstdio>

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", n / 2);
    fflush(stdout);
    char ans[10];
    scanf("%s", ans);
    if(ans[0] == '>') {
        printf("! %d\n", n / 2 + 1);
        fflush(stdout);
    } else {
        printf("! %d\n", n / 2 - 1);
        fflush(stdout);
    }
}

解题思路：

对面的程序首先确定了确定了一个值（程序心里想着。。。），然后告诉了我们一个最大数，确定值就在这之间，然后我们开始猜，对面程序会根据我们猜的数不断告诉我们是大于等于或者小了，最后我们能够确定就是这个数的时候，输出！+数。

但是这个过程，不管是对面的程序还是自己，都是我们自己写出来的。。。所以有点难以理解，不过慢慢想想就懂了。（假设自己分身？？？对面程序是分身，他心里想了一个数，本体来猜）

代码本身使用了类似于折半查找的思想，每次输入更新mid，min和max的值，不太难就没写注释，建议先跟着代码过程手写一波每一步的结果，一目了然。

AC代码如下：

#include <stdio.h>
int main()
{
    int mid,max,min=0;
    scanf("%d", &max);
    mid=(max+min)/2;
    printf("%d\n",mid);
    fflush(stdout);
    char ans[2];
    for(int i=0; i<25; i++)
    {
        scanf("%s", ans);
        if(ans[0] == '>'){
            min = mid;
            mid=(max+min)/2;
            if(mid == min){
                printf("! %d\n",mid);
                break;
            }
            else{
                printf("%d\n", mid);
            }

            fflush(stdout);
        }
        else{
            max = mid;
            mid=(max+min)/2;
            if(mid == max){
                printf("! %d\n",mid);
                break;
            }
            else{
                printf("%d\n", mid);
            }
            fflush(stdout);
        }
    }
    return 0;
}

测试：两个测试，一个12，一个18，为什么输入>是正确结果，而输入>=就错误了？蒙了，希望大佬评论解释一下，谢。

猜数字-交互版,算法