欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

csp试题1:线性分类器

程序员文章站 2022-07-10 19:06:44
csp试题1:线性分类器题目题目题目描述考虑一个简单的二分类问题——将二维平面上的点分为 A 和 B 类。训练数据包含 n 个点,其中第 i 个点(1 <= i <= n)可以表示为一个三元组(xi, yi, typei),即该点的横坐标,纵坐标,和类别。在二维平面上,任意...

csp试题1:线性分类器

题目

题目描述
      考虑一个简单的二分类问题——将二维平面上的点分为 AB 类。
      训练数据包含 n 个点,其中第 i 个点(1 <= i <= n)可以表示为一个三元组(xi, yi, typei),即该点的横坐标,纵坐标,和类别。
      在二维平面上,任意一条直线可以表示为Θ0 + Θ1x + Θ2y = 0 的形式,即由Θ0、Θ1、Θ2三个参数确定该直线,且满足Θ1、Θ2不同时为0。
      基于这 n 个已知类别的点,我们想要在平面上找到一条直线作为一个线性分类器。具体来说,这条线要把训练数据中的 A、B 两类点完美分隔开来,即一侧只有 A 类点、另一侧只有 B 类点。这样,对于任意一个的位置类别的点,我们就可以根据它是位于直线的那一侧来预测它的类别了。
      在本题中我们仅需要处理 m 个如下查询:给定一条直线,判断它是否能将训练数据中的 A、B两类点完美分开。
输入格式
      从标准输入读入数据。
      输入共 n+m+1行。
      第一行包含用空格分隔的两个正整数 n 和 m,分别表示 点 和 查询 的个数。
      第二行到第 n+1 行依次输入 n 个点的信息。第 i+1 行(1<=i<=n)包含用空格分隔的三项 xi, yi 和 typei,分别表示第 i 个点的横、纵坐标和类别,其中坐标为整数、类别为一个大写英文字母 A 或 B。
      第 n+2 行到第 n+m+1行依次输入 m 个查询。第 j+n+1 行(1<=j<=m)包含用空格分割的三个整数Θ0、Θ1 和 Θ2,表示第 j 个查询中给定直线的三个参数。
输出格式
      输出到标准输出。
      输出共 m 行,每行输出一个字符串。
      第 j 行(1<=j<=m)输出的字符串对应第 j 个查询的结果:如果给定直线可以完美分割 A、B 两点,则输出 Yes;否则输出No。
样例1
输入:

9 3
1 1 A
1 0 A
1 -1 A
2 2 B
2 3 B
0 1 A
3 1 B
1 3 B
2 0 A
0 2 -3
-3 0 2
-3 1 1

输出:

No
No
Yes

解释:
csp试题1:线性分类器
子任务

  • 输入数据保证不存在恰好落在给定直线上的点;
  • 0<n<=103、0<m<=20,且 A、B 两类点的数量均不为0;
  • 所有点的坐标和给定直线的三个参数均为整数,且绝对值<=106
  • 任意两个点的坐标不完全相同。
    csp试题1:线性分类器

分析

  1. 如何使用直线去分类:通过三个 Θ 值我们得到了一个直线等式,将点的x、y坐标带入直线算式中,得出的结果由三种:大于0、小于0、等于0。等于0的点不考虑,通过结果大于0还是小于0就将点分成了两类。
  2. 当一条直线可以将数据完美二分类时,标签为 A 的点可能会是大于0的那一类,也可能是小于0的哪一类。

代码

import java.util.Scanner;

/**
 * csp测试
 * 题目:202006-1 线性分类器
 * @author dxt
 *
 */
public class Main {
	public static void main(String[] args){
		//1.1  接收数据 n和m
		int n, m;
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		//System.out.println(n);
		
		//1.2 接收点的坐标数据 和 对应分类
		int[][] datas = new int[n][2];
		char[] types = new char[n];
		for(int i=0; i<n; i++){
			datas[i][0] = scan.nextInt();	//横坐标
			datas[i][1] = scan.nextInt();	//纵坐标
			types[i] = scan.next().charAt(0);	//types
		}
		//1.3 创建theta[],保存每次直线的参数
		int[] theta = new int[3];
		
		//1.4 创建outcome[], 保存分类的结果
		boolean[] outcome = new boolean[m];
		
		//2. 不断接收参数,然后计算 --> 判断 --> 分类 --> 设置结果
		boolean AisUp = true;	//标签为A的点通过计算结果是否大于0
		for(int i=0; i<m; i++){
			//2.1 接收这次分类的直线数据
			for(int j=0; j<3; j++){
				theta[j] = scan.nextInt();
			}
			
			//2.2 使用这条直线对n个点进行分类
			//2.2.1  先对第一个点进行计算,判断A、B标签应该在直线哪一侧
			int result = theta[0] + (theta[1]*datas[0][0]) + (theta[2]*datas[0][1]);
			//2.2.2 依据 结果 和 type 对 A 、 B 进行分侧
			if(types[0] == 'A'){
				if(result > 0){		
					AisUp = true;	//A标签的点结果大于0
				}else{
					AisUp = false;	//A标签的点结果小于0
				}
			}else if(types[0] == 'B'){
				if(result > 0){
					AisUp = false;	//B标签的点结果大于0
				}else{
					AisUp = true;	//B标签的点结果小于0
				}
			}
			//2.2.3 从第二个点开始处理
			for(int k=1; k<n; k++){
				//2.2.3.1 将点的坐标代入直线方程,计算结果
				result = theta[0] + (theta[1]*datas[k][0]) + (theta[2]*datas[k][1]);
				//2.2.3.2 判断是否分类正确
				if(AisUp){	//A标签的数据>0
					if((types[k]=='A') && (result > 0)){
						//则分类正确
						outcome[i] = true;	//设置为true
					}else if((types[k]=='A') && (result < 0)){
						//分类错误
						outcome[i] = false;	//设置为false
						break;	//已经分类错误了,不用再去计算剩余数据
					}else if((types[k]=='B') && (result > 0)){
						//分类错误
						outcome[i] = false;	
						break;	
					}else if((types[k]=='B') && (result < 0)){
						//分类正确
						outcome[i] = true;	
					}
				}else{	//A标签的数据<0
					if((types[k]=='A') && (result > 0)){
						//则分类错误
						outcome[i] = false;	//设置为false
						break;	//已经分类错误了,不用再去计算剩余数据
					}else if((types[k]=='A') && (result < 0)){
						//分类正确
						outcome[i] = true;	//设置为true
					}else if((types[k]=='B') && (result > 0)){
						//分类正确
						outcome[i] = true;	
					}else if((types[k]=='B') && (result < 0)){
						//分类错误
						outcome[i] = false;
						break;
					}
				}
			}
		}
		
		//3. 输出结果
		for(int i=0; i<m; i++){
			if(outcome[i]){
				System.out.println("Yes");
			}else{
				System.out.println("No");
			}
		}
	}
}

总结

  1. Scanner无法直接接收字符数据。

本文地址:https://blog.csdn.net/qq_37665301/article/details/107475061