練習Day-14


目次

  • チップテスト
  • Sineの舞(BASIC-21)
  • 先順配列
  • を求める
  • FBIツリー
  • 一元三次方程式解

  • チップテスト


    タイトル説明はn(2≦n≦20)ブロックチップがあり、良いチップと悪いチップがあり、良いチップが悪いチップより多いことが知られている.各チップは他のチップをテストするために使用できます.他のチップをチップでテストすると、テストされたチップが良いか悪いかを正確に与えることができます.一方、悪いチップで他のチップをテストすると、良いか悪いかのテスト結果がランダムに与えられます(すなわち、この結果は被テストチップの実際の良し悪しとは関係ありません).すべてのチップのテスト結果を示し、どのチップが良いチップなのかを尋ねます.
    入力データの第1の動作は、チップ個数を表す整数nである.2行目からn+1行目n*nのテーブルで、1行n個のデータが表示されます.表中の各データは0または1であり、このn行のi行目j列目(1≦i,j≦n)のデータは、iブロック目チップでjブロック目チップをテストしたときに得られたテスト結果を示し、1は良い、0は悪い、i=jの場合は一律に1(このチップが自分に対するテスト結果を示さない.コアシートは自分に対してテストできない)である.
    出力は小さい順にすべての良いチップの番号を出力します
    サンプル入力3 1 0 1 0 1 0 1 0 1 0 1 0 1 1
    サンプル出力1 3
    題目解析は現在のチップが良いと仮定し、良いチップで現在のチップをテストした結果は良いが、悪いチップで現在のチップをテストした結果は良いかもしれないし、悪いかもしれない.また、良いチップの数は必ず悪いチップの数(x>n/2)より大きいため、現在のチップが本当に良い場合は、他のチップを含めて現在のチップをテストし、結果の正しい数(現在のチップが良いことを測定する)は必ずn/2より大きい.
    import java.util.Scanner;
    
    // 
    
    public class Main {
         
    	public static void main(String[]args) {
         
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();
    		int num[][]=new int[n][n];
    		for(int i=0;i<n;i++) {
         
    			for(int j=0;j<n;j++) {
         
    				num[i][j]=scan.nextInt();
    			}
    		}
    		scan.close();
    		
    		// 
    		for(int i=0;i<n;i++) {
         
    			int count=0;// 
    			for(int j=0;j<n;j++) {
         
    				if(num[j][i]==1) {
         
    					count++;
    				}
    			}
    			if(count>n/2) {
         
    				System.out.print(i+1+" ");
    			}
    		}
    	}
    }
    
    

    Sineの舞(BASIC-21)


    最近、FJは彼の乳牛たちのために数学分析の授業を開設しました.FJはこの授業をマスターするには、良い三角関数の基本功が必要だと知っています.だから彼は乳牛たちと「Sineのダンス」のゲームをして、楽しみに教えて、乳牛たちの計算能力を高めるつもりです.An=sin(1–sin(2+sin(3–sin(4+...sin(n)…)Sn=(…(A 1+n)A 2+n-1)A 3+…+2)An+1 FJを乳牛たちにSnの値を計算させたい場合は、FJがSnの完全な式を印刷して、乳牛たちが問題を起こすのを便利にしてください.
    入力数は1つのみ:N<201.
    出力は、対応する式Snを出力し、1つの改行で終了してください.出力に余分なスペースや改行、戻り文字を含めてはいけません.
    サンプル入力3
    サンプル出力((sin(1)+3)sin(1-sin(2))+2)sin(1-sin(2+sin(3)))))+1
    import java.util.Scanner;
    //sine 
    //An=sin(1–sin(2+sin(3–sin(4+...sin(n))...)
    //Sn=(...(A1+n)A2+n-1)A3+...+2)An+1
    
    public class Main {
         
    	public static void main(String[]args) {
         
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();
    		scan.close();
    		StringBuffer str=S(n,n);
    		System.out.println(str);
    	}
    
    	private static StringBuffer S(int n,int m) {
         
    		StringBuffer str=new StringBuffer();
    		if(n==1)
    			str.append(AA(1)).append("+"+(m));
    		else
    			str.append("(").append(S(n-1,m)).append(")").append(AA(n)).append("+"+(m-n+1));
    		return str;
    	}
    
    	private static StringBuffer A(int n) {
         
    		StringBuffer str=new StringBuffer();
    		if(n==1)
    			str.append("sin(1");
    		else
    			str.append(A(n-1)).append(n%2==1?"+":"-").append("sin("+n);
    		return str;
    	}
    	
    	private static StringBuffer AA(int n) {
         
    		StringBuffer str=A(n);
    		while(n>0) {
         
    			str.append(")");
    			n--;
    		}
    		return str;
    	}
    
    }
    
    

    序列を求める


    タイトルの説明は1本の二叉木の中序と後序の配列を与える.その先順配列を求める.(約定木のノードは異なる大文字で表され、長さ<=8).
    2つの行を入力します.各行に1つの文字列で、それぞれ中順と後順の配列を表します.
    求めたシーケンス配列を表す文字列を出力
    サンプル入力BADC BDCA
    サンプル出力ABCD
    题目解析先序遍歴:根左右中序遍歴:左根右后序遍歴:左右根先按后序遍歴结果,文字列の最后の1位は木の根ノードで,それから顺次左サブツリー,右サブツリーを遍歴する
    import java.util.Scanner;
    
    // 
    public class Main {
         
    	public static void main(String[]args) {
         
    		Scanner scan=new Scanner(System.in);
    		String in=scan.next();// 
    		String post=scan.next();// 
    		scan.close();
    		
    		func(in,post);
    	}
    
    	private static void func(String in, String post) {
         
    		char root=post.charAt(post.length()-1);// 
    		System.out.print(root);
    		int index=in.indexOf(root);// 
    		if(index>0) {
         
    			String str1=in.substring(0, index);
    			String str2=post.substring(0,index);
    			func(str1,str2);
    		}
    		if(index<post.length()-1) {
         
    			String str3=in.substring(index+1);
    			String str4=post.substring(index, post.length()-1);
    			func(str3,str4);
    		}
    	}
    	
    
    }
    
    

    FBIツリー


    タイトル記述では、「0」と「1」からなる文字列を3種類に分けることができます.全「0」列をB列、全「1」列をI列、「0」と「1」を含む列をF列と呼びます.FBIツリーは二叉木で、そのノードタイプにはFノード、Bノード、Iノードの3種類も含まれています.長さ2 Nの「01」列SからFBIツリーTを構築することができ、再帰的な構造方法は以下の通りである:1)TのルートノードはRであり、そのタイプはシリアルSのタイプと同じである.2)シリアルSの長さが1より大きい場合、シリアルSを中間から分離し、等長の左右のサブシリアルS 1とS 2に分ける.左サブ列S 1によってRの左サブツリーT 1が構築され、右サブ列S 2によってRの右サブツリーT 2が構築される.長さ2 Nの「01」列を指定し、上記の構造方法でFBIツリーを構築し、その後順ループシーケンスを出力します.
    データ規模と約定はすべてのデータに対してN<=10である.注意:[1]二叉木:二叉木は、ノードの有限な集合であり、この集合は空の集合であるか、または1つのルートノードと2つの交差しない二叉木から構成されています.この2本の交差しない二叉木をそれぞれこの根の結点の左の木と右の木と呼ぶ.[2]後順遍歴:後順遍歴は深さ優先二叉木を遍歴する方法であり、その再帰定義は:前後順に左サブツリーを遍歴し、後順に右サブツリーを遍歴し、最後にルートにアクセスすることである.
    入力1行目は整数N(0<=N<=10)で、2行目は長さ2 Nの「01」列です.
    出力には、FBIツリーのシーケンスループシーケンスである1つの文字列のみが含まれる行が含まれます.
    サンプル入力3 10001011
    サンプル出力IBFBBBFIBFIIFF
    テーマ解析はシリアルSを2つの部分に分け、中点を境に0~s.length/2とs.length/2~s.lengthの2つの部分(左右のサブツリーの2つの部分に分けられる)に分け、この2つの部分はそれぞれ再帰処理を行う.列長が1のみの場合(すなわち、葉ノードが1つしか残っていない場合)、文字が1または0の場合、IまたはBが返されると判断する.次に、2つの部分で返される文字(左右のサブツリーに含まれる文字)を比較し、同じであれば、1または0が返されることを示し、最後にIまたはBが直接返される.異なる場合、返される0と1が含まれていることが証明され、最後にFが返される.
    import java.util.Arrays;
    import java.util.Scanner;
    
    //FBI 
    public class Main {
         
    	public static void main(String[]args) {
         
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();// 2n
    		String s=scan.next();
    		scan.close();
    		
    		char ch[]=s.toCharArray();
    		func(ch);
    		
    	}
    
    	private static String func(char ch[]) {
         
    		if(ch.length==1) {
         
    			if(ch[0]=='1') {
         
    				System.out.print("I");
    				return "I";
    			}
    			else if(ch[0]=='0') {
         
    				System.out.print("B");
    				return "B";
    			}
    		}
    			char ch1[]=Arrays.copyOfRange(ch, 0, ch.length/2);
    			char ch2[]=Arrays.copyOfRange(ch, ch.length/2, ch.length);
    			String str1=func(ch1);
    			String str2=func(ch2);
    			if(str1==str2) {
         
    				System.out.print(str1);
    				return str1;
    			}
    				
    			else {
         
    				System.out.print("F");
    				return "F";
    			}
    		
    	}
    
    }
    
    

    一元三次方程式の解


    テーマ記述には,ax 3+bx 2+cx+d=0のような一元三次方程式がある.この方程式の各係数(a,b,c,dはいずれも実数)を与え、この方程式には3つの異なる実根(根の範囲は-100から100の間)が存在し、根と根の差の絶対値>=1が規定されている.3つの実根を要求する.
    データ規模と約束|a|,|b|,|c|,|d|<=20
    実数を4つ入力:a,b,c,d
    出力は、3つの実ルート(ルートとルートの間にスペースが残っている)を小から大の順に同じ行に出力し、小数点以下2桁まで正確に出力します.
    サンプル入力1-5-4 20
    サンプル出力-2.00 2.00 5.00
    import java.util.Scanner;
    
    // 
    public class Main {
         
    	public static void main(String[]args) {
         
    		Scanner scan=new Scanner(System.in);
    		double a=scan.nextDouble();
    		double b=scan.nextDouble();
    		double c=scan.nextDouble();
    		double d=scan.nextDouble();
    		scan.close();
    		for(double i=-100;i<=100;i+=0.01) {
         
    			if(Math.abs(a*i*i*i+b*i*i+c*i+d)<=0.0000001)
    				System.out.printf("%.2f ", i);
    		}
    	}
    
    }