CS计算机代考程序代写 algorithm /*

/*
* The given code is provided to assist you to complete the required tasks. But the
* given code is often incomplete. You have to read and understand the given code
* carefully, before you can apply the code properly.
*/

/*
* Please review Lecture 5 Algorithms Part I, slide 49 to complete this task.
* */

public class MultiplicationAlgorithm {

/**
* Using divide-and-conquer to implement the Karatsuba multiplication to compute the product x times y.
* x and y are two n-digit input numbers.

*/
public static long KMultiply(long x, long y){
// TODO: Complete this method
tracker.calltracking(x,y); //Do not modify this method. Otherwise, you will be penalized for violation.
// START YOUR CODE
String num1 = String.valueOf(x);
String num2 = String.valueOf(y);
if(num1.length() < 10 || num2.length() < 10) return Long.parseLong(num1) * Long.parseLong(num2); // 计算拆分长度 int size1 = num1.length(); int size2 = num2.length(); int halfN = Math.max(size1, size2) / 2; /* 拆分为a, b, c, d */ String a = num1.substring(0, size1 - halfN); String b = num1.substring(size1 - halfN); String c = num2.substring(0, size2 - halfN); String d = num2.substring(size2 - halfN); // 计算z2, z0, z1, 此处的乘法使用递归 long z2 = KMultiply(Long.parseLong(a), Long.parseLong(c)); long z0 = KMultiply(Long.parseLong(b), Long.parseLong(d)); long z1 = KMultiply((Long.parseLong(a) + Long.parseLong(b)), (Long.parseLong(c) + Long.parseLong(d))) - z0 - z2; return (long)(z2 * Math.pow(10, (2*halfN)) + z1 * Math.pow(10, halfN) + z0); // END YOUR CODE } }