0
現在、プログラムにはN個の数字とゴールターゲットがあります。ゴールに到達するために数字の間に「+」または「*」のいずれかを挿入します。目標に達すると、正しい操作が印刷されます。 しかし、それが答えを見つけ出す方法はブルートフォースによるものであり、これはN個の数字の大きなセットでは不十分です。私の現在のコードは以下の通りです：操作挿入プログラムの最適化アルゴリズム
public class Arithmetic4{
private static ArrayList<String> input = new ArrayList<String>();
private static ArrayList<String> second_line = new ArrayList<String>();
private static ArrayList<Integer> numbers = new ArrayList<Integer>();
private static ArrayList<String> operations = new ArrayList<String>();
private static ArrayList<Integer> temp_array = new ArrayList<Integer>();
public static void main(String [] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()){
readInput(sc);
}
}
public static void readInput(Scanner sc){
String line = sc.nextLine();
input.add(line);
line = sc.nextLine();
second_line.add(line);
dealInput();
}
public static void dealInput(){
String numberS = input.get(0);
String[] stringNumbers = numberS.split("\\s+");
for(int i = 0; i < stringNumbers.length; i++){
String numberAsString = stringNumbers[i];
numbers.add(Integer.parseInt(numberAsString));
}
String orderString = second_line.get(0);
String[] stringWhatWay = orderString.split("\\s+");
int target = Integer.parseInt(stringWhatWay[0]);
char whatway = stringWhatWay[1].charAt(0);
long startTime = System.currentTimeMillis();
whatEquation(numbers, target, whatway);
long elapsedTime = System.currentTimeMillis() - startTime;
long elapsedMSeconds = elapsedTime/1;
System.out.println(elapsedMSeconds);
numbers.clear();
input.clear();
second_line.clear();
}
public static void whatEquation(ArrayList<Integer> numbers, int target, char whatway){
if(whatway != 'L' && whatway != 'N'){
System.out.println("Not an option");
}
if(whatway == 'N'){
ArrayList<Integer> tempo_array = new ArrayList<Integer>(numbers);
int count = 0;
for (int y: numbers) {
count++;
}
count--;
int q = count;
calculateN(numbers, target, tempo_array, q);
}
if (whatway == 'L'){
if(numbers.size() == 1){
System.out.println("L " + numbers.get(0));
}
ArrayList<Integer> temp_array = new ArrayList<Integer>(numbers);
calculateL(numbers, target, temp_array);
}
}
public static void calculateN(ArrayList<Integer> numbers, int target, ArrayList<Integer> tempo_numbers, int q){
int sum = 0;
int value_inc = 0;
int value_add;
boolean firstRun = true;
ArrayList<Character> ops = new ArrayList<Character>();
ops.add('+');
ops.add('*');
for(int i = 0; i < Math.pow(2, q); i++){
String bin = Integer.toBinaryString(i);
while(bin.length() < q)
bin = "0" + bin;
char[] chars = bin.toCharArray();
List<Character> oList = new ArrayList<Character>();
for(char c: chars){
oList.add(c);
}
ArrayList<Character> op_array = new ArrayList<Character>();
ArrayList<Character> temp_op_array = new ArrayList<Character>();
for (int j = 0; j < oList.size(); j++) {
if (oList.get(j) == '0') {
op_array.add(j, ops.get(0));
temp_op_array.add(j, ops.get(0));
} else if (oList.get(j) == '1') {
op_array.add(j, ops.get(1));
temp_op_array.add(j, ops.get(1));
}
}
sum = 0;
for(int p = 0; p < op_array.size(); p++){
if(op_array.get(p) == '*'){
int multiSum = numbers.get(p) * numbers.get(p+1);
numbers.remove(p);
numbers.remove(p);
numbers.add(p, multiSum);
op_array.remove(p);
p -= 1;
}
}
for(Integer n: numbers){
sum += n;
}
if(sum != target){
numbers.clear();
for (int t = 0; t < tempo_numbers.size(); t++) {
numbers.add(t, tempo_numbers.get(t));
}
}
if (sum == target){
int count_print_symbol = 0;
System.out.print("N ");
for(int g = 0; g < tempo_numbers.size(); g++){
System.out.print(tempo_numbers.get(g) + " ");
if(count_print_symbol == q){
break;
}
System.out.print(temp_op_array.get(count_print_symbol) + " ");
count_print_symbol++;
}
System.out.print("\n");
return;
}
}
System.out.println("N is Impossible");
}
public static void calculateL(ArrayList<Integer> numbers, int target, ArrayList<Integer> temp_array){
int op_count = 0;
int sum = 0;
int n = (numbers.size() -1);
boolean firstRun = true;
for (int i = 0; i < Math.pow(2, n); i++) {
String bin = Integer.toBinaryString(i);
while (bin.length() < n)
bin = "0" + bin;
char[] chars = bin.toCharArray();
char[] charArray = new char[n];
for (int j = 0; j < chars.length; j++) {
charArray[j] = chars[j] == '0' ? '+' : '*';
}
//System.out.println(charArray);
for(char c : charArray){
op_count++;
if(firstRun == true){
sum = numbers.get(0);
numbers.remove(0);
// System.out.println(sum);
}
if (!numbers.isEmpty()){
if (c == '+') {
sum += numbers.get(0);
} else if (c == '*') {
sum *= numbers.get(0);
}
numbers.remove(0);
}
firstRun = false;
//System.out.println(sum);
if(sum == target && op_count == n){
int count_print_op = 0;
System.out.print("L ");
for(int r = 0; r < temp_array.size(); r++){
System.out.print(temp_array.get(r) + " ");
if(count_print_op == n){
break;
}
System.out.print(charArray[count_print_op] + " ");
count_print_op++;
}
System.out.print("\n");
return;
}
if(op_count == n && sum != target){
firstRun = true;
sum = 0;
op_count = 0;
for(int e = 0; e < temp_array.size(); e++){
numbers.add(e, temp_array.get(e));
}
}
}
}
System.out.println("L is impossible");
}
}
同様の結論に到達する方法はありますか？
ここにはたくさんのコードがあります。あなたの質問を述べたい部分を分離してみてください。 –
私は実際にあなたのコードを実行して勉強している人がいなければ、それが何をしているのかを実際に理解することはできないかもしれません。ここで達成しようとしていることについての説明を含めるように質問を更新できますか？ –