程序竞赛中的交互问题

交互问题是指我们的解决方案或代码与裁判实时互动的问题。当我们为交互式问题开发解决方案时,提供给我们解决方案的输入数据可能不是预先确定的,而是专门为该问题而构建的。该解决方案与裁判进行一系列数据交换,并且在对话结束时,裁判将决定我们的解决方案是否正确。

猜数字(一个交互式问题)

在这个问题中,用户必须在与裁判沟通期间猜测数字。为用户提供上限和下限,他/她可以询问裁判数字是否为要猜测的数字。如果数字小于要猜测的数字,则裁判以-1答复,如果数字大于要猜测的数字,则裁判以1答复,或者如果数字等于要猜测的数字,则裁判以0答复。

方法1:线性猜测

用户可以查询裁判在下限和上限之间的所有数字以找到解决方案。

import java.util.*; 
class GFG { 
    public static void main(String[] args) 
    { 
        Scanner sc1 = new Scanner(System.in); 
        int lower_bound = 2; 
        int upper_bound = 10; 
  
        // Number to be guessed is 6 
  
        // Iterating from lower_bound to upper_bound 
        for (int i = lower_bound; i <= upper_bound; i++) { 
            System.out.println(i); 
  
            // Input the response from the judge 
            int response = sc1.nextInt(); 
  
            if (response == 0) { 
                System.out.println("Number guessed is :" + i); 
                break; 
            } 
        } 
    } 
} 

时间复杂度:O(n)

方法2:应用二进制搜索

我们还可以交互式地应用二进制搜索来找到解决方案。与先前的方法相比,该解决方案是有效的。

import java.util.*; 
class GFG { 
    public static void main(String[] args) 
    { 
        Scanner sc1 = new Scanner(System.in); 
        int lower_bound = 2; 
        int upper_bound = 10; 
  
        // Number to be guessed is 9 
  
        // Applying Binary Search interactively 
        while (lower_bound <= upper_bound) { 
            int mid = (lower_bound + upper_bound) / 2; 
  
            // Print the guessed number 
            System.out.println(mid); 
  
            // Input the response from the judge 
            int response = sc1.nextInt(); 
  
            if (response == -1) { 
                lower_bound = mid + 1; 
            } 
            else if (response == 1) { 
                upper_bound = mid - 1; 
            } 
            else if (response == 0) { 
                System.out.println("Number guessed is :" + mid); 
                break; 
            } 
        } 
    } 
} 

时间复杂度:O(logn)
算法范例:分而治之(Divide and Conquer)

六一编程网

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Next Post

如何在Mac上安装Python

周二 3月 3 , 2020
您的Mac系统可能已经安装了Python。根据您使用Python的方式,您可能需要在某个时候更新安装 […]