チップテスト-動的計画アルゴリズム

n枚のチップがあり、良いチップは悪いチップより少なくとも1枚多いことが知られている.今、テストを通じて中から1枚の良いチップを探し出す必要があります.テスト方法は以下の通りです.2枚のチップをテスト台に置いて、2枚のチップは互いにテストして、テスト結果(つまり良いか悪いか)を報告します.その中で、良いチップの報告は正しいが、悪いチップの報告は信頼できない.上記の背景の下で下記の問題を解決してください.
良いチップが少なくとも悪いチップより1枚多いという条件から、チップ数が3枚より大きい場合には、チップ相互検出の結果が1つの良い1つまたは2つの悪い(少なくとも1つの悪いチップが必要である)であるチップセットを破棄することによって、検出結果が2つの良いチップのみを残してランダムに1枚を破棄し、チップ数のパリティに基づいて、奇数のチップの残りの1枚の未整合チップを、前のマッチングが完了し、廃棄されたチップと逐一マッチングし、チップの数を縮小し、良いチップが少なくとも悪いチップの数より1枚多いことを確保する条件を実現する.チップの数が3枚しか残っていない場合、その条件によって2つの良いものと悪いもの、または3つの良いものしかない場合、簡単な判断で良いチップを見つけることができます.//注記元の最適化されていないアルゴリズム

import java.util.Scanner;


class Chip{// 
	boolean quality;// 
	int position;// 
	public Chip(boolean quality,int position){
		this.quality = quality;
		this.position = position;
	}


	public static void init(Chip chips[],int inits[]){
		for(int i=0;i3){
			int index = 0;
			boolean flag = false;
//			if(n%2!=0){// 
//				int good = 0;
//				for(int i=0;in/2){// 
//					flag = true;// 
//				}
//			}
			for(int i=0;i