分治代码模板
2020年7月31日 更新
开启更多功能,提升办公效能
# Python
def divide_conquer(problem, param1, param2, ...): 
# recursion terminator 
if problem is None: 
print_result 
return 

# prepare data 
data = prepare_data(problem) 
subproblems = split_problem(problem, data) 

# conquer subproblems 
subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
subresult3 = self.divide_conquer(subproblems[2], p1, ...) 

# process and generate the final result 
result = process_result(subresult1, subresult2, subresult3, …)
# revert the current level states


C/C++
int divide_conquer(Problem *problem, int params) {
  // recursion terminator
  if (problem == nullptr) {
    process_result
    return return_result;
  } 

  // process current problem
  subproblems = split_problem(problem, data)
  subresult1 = divide_conquer(subproblem[0], p1)
  subresult2 = divide_conquer(subproblem[1], p1)
  subresult3 = divide_conquer(subproblem[2], p1)
  ...

  // merge
  result = process_result(subresult1, subresult2, subresult3)
  // revert the current level status
 
  return 0;
}


//Javascript
const divide_conquer = (problem, params) => {

  // recursion terminator

  if (problem == null) {

    process_result

    return

  } 

  // process current problem

  subproblems = split_problem(problem, data)

  subresult1 = divide_conquer(subproblem[0], p1)

  subresult2 = divide_conquer(subproblem[1], p1)

  subresult3 = divide_conquer(subproblem[2], p1)

  ...

  // merge

  result = process_result(subresult1, subresult2, subresult3)

  // revert the current level status

}



Java

private static int divide_conquer(Problem problem, ) {
if (problem == NULL) {
int res = process_last_result();
return res;
}

subProblems = split_problem(problem)
res0 = divide_conquer(subProblems[0])
res1 = divide_conquer(subProblems[1])
result = process_result(res0, res1);
return result;
}