前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >分治法的经典问题——大整数相乘

分治法的经典问题——大整数相乘

作者头像
墨文
发布于 2020-02-28 12:38:04
2.6K0
发布于 2020-02-28 12:38:04
举报
文章被收录于专栏：m0w3nm0w3n

分治法的经典问题——大整数相乘

分治法的原理

       分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。即一种分目标完成程序算法，简单问题可用二分法完成。（来自度娘的搬运工）

       简单的说，分治就是分而治之，把一个问题拆分成几个小问题，最后再汇总解决的办法。

有两点需要记住：

（1） 分治法基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。

（2）递归的解这些子问题，然后将各子问题的解合并得到原问题的解。

分治法的重点是分析问题是否可以划分为规模较小的子问题，难点是如何划分以及划分之后如何将各个子问题的解合并成最终的解。这一般需要用到数学知识或者其他理论。

下面我们用图来说明：

通过大整数相乘问题来了解分治法（理想状态下）

       这里我们假设有两个大整数X、Y，分别设X=1234、Y=5678。现在要求X*Y的乘积，小学的算法就是把X与Y中的每一项去乘，但是这样的乘法所需的时间复杂度为，效率比较低下。那我们可以采用分治的算法，将X、Y分别拆分为A与B、C与D，如下图:

注：我们这里取的大整数X、Y是在理想状态下，即X与Y的位数一致，且

。

算法分析

  1. 首先将X和Y分成A，B，C，D
  2. 此时将X和Y的乘积转化为（1）式，把问题转化为求解因式分解的值

在（1）式中，我们一共需要进行4次n/2的乘法（AC2次，AD、BC各一次）和3次加法，因而该算法的时间复杂度为：

通过master定理可以求得

，跟小学算法的时间复杂度没有区别。

但是我们再来看看，我们是否可以用加法来换取乘法？因为多一个加法操作，也是常数项，对时间复杂度没有影响，如果减少一个乘法则不同。

（1）式化为：

 （2）

现在的时间复杂度为：

，通过master定理求得，

。

理想状态下代码实现（部分）：

c#:

代码语言：javascript
复制
static void Main(string[] args)
        {
            //SameNumber();
            //UnSameNumber();
            UnSameNumber2();
        }

        static int SIGN(long A)
        {
            return A > 0 ? 1 : -1;
        }

        #region 两整数位数相同
        private static void SameNumber()
        {
            Console.Write("请输入两个大整数：\nX=");
            long X = Convert.ToInt64(Console.ReadLine());
            Console.Write("Y=");
            long Y = Convert.ToInt64(Console.ReadLine());
            Console.Write("请输入两个大整数的长度：n=");
            int n = Convert.ToInt32(Console.ReadLine());

            long sum = CalculateSame(X, Y, n);

            Console.WriteLine("普通乘法 X*Y={0}*{1}={2}\n", X, Y, X * Y);
            Console.WriteLine("分治乘法 X*Y={0}*{1}={2}\n", X, Y, sum);
        }

        static long CalculateSame(long X, long Y, int n)
        {
            int sign = SIGN(X) * SIGN(Y);

            X = Math.Abs(X);
            Y = Math.Abs(Y);
            if (X == 0 || Y == 0)
                return 0;
            else if (n == 1)
                return sign * X * Y;
            else
            {
                long A = (long)(X / Math.Pow(10, n / 2));
                long B = (long)(X % Math.Pow(10, n / 2));
                long C = (long)(Y / Math.Pow(10, n / 2));
                long D = (long)(Y % Math.Pow(10, n / 2));

                long AC = CalculateSame(A, C, n / 2);
                long BD = CalculateSame(B, D, n / 2);
                long ABCD = CalculateSame((A - B), (D - C), n / 2) + AC + BD;

                //Console.WriteLine("A={0} B={1} C={2} D={3}\n", A, B, C, D);

                return (long)(sign * (AC * Math.Pow(10, n) + ABCD * Math.Pow(10, n / 2) + BD));
            }
        }
        #endregion

大整数相乘算法非理想状态下

       这里我们还是假设有两个大整数X、Y，分别设X=123、Y=45678。现在要求X*Y的乘积，乘法所需的时间复杂度为。我们采用分治的算法，将X、Y分别拆分为A与B、C与D，如下图:

   （3）

在（3）式中，我们一共需要进行2次xn0的乘法（AC、AD各一次）、2次yn0的乘法（AC、BC各一次）和3次加法，因而该算法的时间复杂度为：

现在我们用加法来换取乘法并计算其时间复杂度。

（3）式化为：

（4）

现在的时间复杂度为：

由于

，所以（4）式的时间复杂度小于（3）式的时间复杂度。

非理想状态下代码实现（部分）：

c#:

代码语言：javascript
复制
 #region 两整数位数不相同
        private static void UnSameNumber2()
        {
            Console.Write("请输入两个大整数：\nX=");
            long X = Convert.ToInt64(Console.ReadLine());
            Console.Write("Y=");
            long Y = Convert.ToInt64(Console.ReadLine());
            Console.Write("请输入X的长度：xn=");
            int xn = Convert.ToInt32(Console.ReadLine());
            Console.Write("请输入Y的长度：yn=");
            int yn = Convert.ToInt32(Console.ReadLine());

            long sum = CalculateUnSame2(X, Y, xn, yn);

            Console.WriteLine("\n普通乘法 X*Y={0}*{1}={2}", X, Y, X * Y);
            Console.WriteLine("分治乘法 X*Y={0}*{1}={2}\n", X, Y, sum);
        }

        static long CalculateUnSame2(long X, long Y, int xn, int yn)
        {
            if (X == 0 || Y == 0)
                return 0;
            else if ((xn == 1 && yn == 1) || xn == 1 || yn == 1)
                return X * Y;
            else
            {
                int xn0 = xn / 2, yn0 = yn / 2;
                int xn1 = xn - xn0, yn1 = yn - yn0;

                long A = (long)(X / Math.Pow(10, xn0));
                long B = (long)(X % Math.Pow(10, xn0));
                long C = (long)(Y / Math.Pow(10, yn0));
                long D = (long)(Y % Math.Pow(10, yn0));

                //Console.WriteLine("A={0}*10^{1} B={2}*10^{3} C={4}*10^{5} D={6}*10^{7}\n", A, xn1, B, xn0, C, yn1, D, yn0);

                long AC = CalculateUnSame2(A, C, xn1, yn1);
                long BD = CalculateUnSame2(B, D, xn0, yn0);
                long ABCD = CalculateUnSame2((long)(A * Math.Pow(10, xn0) - B), (long)(D - C * Math.Pow(10, yn0)), xn1, yn1);

                return (long)(2 * AC * Math.Pow(10, (xn0 + yn0)) + ABCD + 2 * BD);
            }
        }
        #endregion

理想状态下与非理想状态下代码实现（完整）：

c语言：

代码语言：javascript
复制
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

void SameNumber();
void UnSameNumber();
int SIGN(long A);
long CalculateSame(long X, long Y, int n);
long CalculateUnSame(long X, long Y, int xn, int yn);

int main()
{
	SameNumber();
	UnSameNumber();
	return (0);
}

int SIGN(long A)
{
	return A > 0 ? 1 : -1;
}

void SameNumber()
{
	long X=0,Y = 0;
	int n=0;
	printf("理想状态下用法！");
	printf("请输入两个大整数：\nX=");
	scanf("%d",&X);
	printf("Y=");
	scanf("%d",&Y);
	printf("请输入两个大整数的长度：n=");
	scanf("%d",&n);

	long sum = CalculateSame(X, Y, n);

	printf("普通乘法 X*Y=%d*%d=%d\n",X,Y,X*Y);
	printf("分治乘法 X*Y=%d*%d=%d\n",X,Y,sum);
}

long CalculateSame(long X, long Y, int n)
{
	int sign = SIGN(X) * SIGN(Y);

	X = labs(X);
	Y = labs(Y);
	if (X == 0 || Y == 0)
		return 0;
	else if (n == 1)
		return sign * X * Y;
	else
	{
		long A = (long)(X / pow(10, n / 2));
		long B = (X % (long)pow(10, n / 2));
		long C = (long)(Y / pow(10, n / 2));
		long D = (Y % (long)pow(10, n / 2));

		long AC = CalculateSame(A, C, n / 2);
		long BD = CalculateSame(B, D, n / 2);
		long ABCD = CalculateSame((A - B), (D - C), n / 2) + AC + BD;
		
		//cout<<"A="<<A<<" B="<<B<<" C="<<C<<" D="<<D<<endl;

		return (long)(sign * (AC * pow(10, n) + ABCD * pow(10, n / 2) + BD));
	}
}

void UnSameNumber()
{
	long X=0,Y = 0;
	int xn=0,yn=0;
	printf("非理想状态下用法！");
	printf("请输入两个大整数：\nX=");
	scanf("%d",&X);
	printf("Y=");
	scanf("%d",&Y);
	printf("请输入X的长度：xn=");
	scanf("%d",&xn);
	printf("请输入Y的长度：xn=");
	scanf("%d",&yn);

	long sum = CalculateUnSame(X, Y, xn,yn);

	printf("普通乘法 X*Y=%d*%d=%d\n",X,Y,X*Y);
	printf("分治乘法 X*Y=%d*%d=%d\n",X,Y,sum);
}

long CalculateUnSame(long X, long Y, int xn, int yn)
{
	if (X == 0 || Y == 0)
		return 0;
	else if ((xn == 1 && yn == 1) || xn == 1 || yn == 1)
		return X * Y;
	else
	{
		int xn0 = xn / 2, yn0 = yn / 2;
		int xn1 = xn - xn0, yn1 = yn - yn0;

		long A = (long)(X / pow(10, xn0));
		long B = (long)(X % (long)pow(10, xn0));
		long C = (long)(Y / pow(10, yn0));
		long D = (long)(Y % (long)pow(10, yn0));

		long AC = CalculateUnSame(A, C, xn1, yn1);
		long BD = CalculateUnSame(B, D, xn0, yn0);
		long ABCD = CalculateUnSame((long)(A * pow(10, xn0) - B), (long)(D - C * pow(10, yn0)), xn1, yn1);

		return (long)(2 * AC * pow(10, (xn0 + yn0)) + ABCD + 2 * BD);
	}
}

c++语言：

代码语言：javascript
复制
#include <iostream>
#include <string> 
#include <math.h>
int count=0;
using namespace std;
void SameNumber();
void UnSameNumber();
int SIGN(long A);
long CalculateSame(long X, long Y, int n);
long CalculateUnSame(long X, long Y, int xn, int yn);

int main()
{
	SameNumber();
	UnSameNumber();
	return (0);
}

int SIGN(long A)
{
	return A > 0 ? 1 : -1;
}

void SameNumber()
{
	cout<<"理想状态用法！"<<endl;;
	cout<<"请输入两个大整数：\nX=";
	long X = 0;
	cin>>X;
	cout<<"Y=";
	long Y = 0;
	cin>>Y;
	cout<<"请输入两个大整数的长度：n=";
	int n = 0;
	cin>>n;

	long sum = CalculateSame(X, Y, n);

	cout<<"普通乘法 X*Y="<<X<<"*"<<Y<<"="<<X * Y<<endl;
	cout<<"分治乘法 X*Y="<<X<<"*"<<Y<<"="<<sum<<endl;
}

long CalculateSame(long X, long Y, int n)
{
	int sign = SIGN(X) * SIGN(Y);

	X = abs(X);
	Y = abs(Y);
	if (X == 0 || Y == 0)
		return 0;
	else if (n == 1)
		return sign * X * Y;
	else
	{
		long A = (long)(X / pow(10, n / 2));
		long B = (X % (long)pow(10, n / 2));
		long C = (long)(Y / pow(10, n / 2));
		long D = (Y % (long)pow(10, n / 2));

		long AC = CalculateSame(A, C, n / 2);
		long BD = CalculateSame(B, D, n / 2);
		long ABCD = CalculateSame((A - B), (D - C), n / 2) + AC + BD;
		
		cout<<"A="<<A<<" B="<<B<<" C="<<C<<" D="<<D<<endl;

		return (long)(sign * (AC * pow(10, n) + ABCD * pow(10, n / 2) + BD));
	}
}

void UnSameNumber()
{
	cout<<"\n非理想状态用法！"<<endl;;
	cout<<"请输入两个大整数：\nX=";
	long X = 0;
	cin>>X;
	cout<<"Y=";
	long Y = 0;
	cin>>Y;
	cout<<"请输入两个大整数的长度：xn=";
	int xn = 0;
	cin>>xn;
	cout<<"请输入两个大整数的长度：yn=";
	int yn = 0;
	cin>>yn;

	long sum = CalculateUnSame(X, Y, xn,yn);

	cout<<"普通乘法 X*Y="<<X<<"*"<<Y<<"="<<X * Y<<endl;
	cout<<"分治乘法 X*Y="<<X<<"*"<<Y<<"="<<sum<<endl;
}

long CalculateUnSame(long X, long Y, int xn, int yn)
{
	if (X == 0 || Y == 0)
		return 0;
	else if ((xn == 1 && yn == 1) || xn == 1 || yn == 1)
		return X * Y;
	else
	{
		int xn0 = xn / 2, yn0 = yn / 2;
		int xn1 = xn - xn0, yn1 = yn - yn0;

		long A = (long)(X / pow(10, xn0));
		long B = (long)(X % (long)pow(10, xn0));
		long C = (long)(Y / pow(10, yn0));
		long D = (long)(Y % (long)pow(10, yn0));

		long AC = CalculateUnSame(A, C, xn1, yn1);
		long BD = CalculateUnSame(B, D, xn0, yn0);
		long ABCD = CalculateUnSame((long)(A * pow(10, xn0) - B), (long)(D - C * pow(10, yn0)), xn1, yn1);

		return (long)(2 * AC * pow(10, (xn0 + yn0)) + ABCD + 2 * BD);
	}
}

c#语言：

代码语言：javascript
复制
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace BigInteger
{
	class Program
	{
		static void Main(string[] args)
		{
          	SameNumber();
			UnSameNumber();
		}

		static int SIGN(long A)
		{
			return A > 0 ? 1 : -1;
		}

		#region 两整数位数相同
		private static void SameNumber()
		{
			Console.Write("请输入两个大整数：\nX=");
			long X = Convert.ToInt64(Console.ReadLine());
			Console.Write("Y=");
			long Y = Convert.ToInt64(Console.ReadLine());
			Console.Write("请输入两个大整数的长度：n=");
			int n = Convert.ToInt32(Console.ReadLine());

			long sum = CalculateSame(X, Y, n);

			Console.WriteLine("普通乘法 X*Y={0}*{1}={2}\n", X, Y, X * Y);
			Console.WriteLine("分治乘法 X*Y={0}*{1}={2}\n", X, Y, sum);
		}

		static long CalculateSame(long X, long Y, int n)
		{
			int sign = SIGN(X) * SIGN(Y);

			X = Math.Abs(X);
			Y = Math.Abs(Y);
			if (X == 0 || Y == 0)
				return 0;
			else if (n == 1)
				return sign * X * Y;
			else
			{
				long A = (long)(X / Math.Pow(10, n / 2));
				long B = (long)(X % Math.Pow(10, n / 2));
				long C = (long)(Y / Math.Pow(10, n / 2));
				long D = (long)(Y % Math.Pow(10, n / 2));

				long AC = CalculateSame(A, C, n / 2);
				long BD = CalculateSame(B, D, n / 2);
				long ABCD = CalculateSame((A - B), (D - C), n / 2) + AC + BD;

				return (long)(sign * (AC * Math.Pow(10, n) + ABCD * Math.Pow(10, n / 2) + BD));
			}
		}
		#endregion

		#region 两整数位数不相同
		private static void UnSameNumber()
		{
			Console.Write("请输入两个大整数：\nX=");
			long X = Convert.ToInt64(Console.ReadLine());
			Console.Write("Y=");
			long Y = Convert.ToInt64(Console.ReadLine());
			Console.Write("请输入X的长度：xn=");
			int xn = Convert.ToInt32(Console.ReadLine());
			Console.Write("请输入Y的长度：yn=");
			int yn = Convert.ToInt32(Console.ReadLine());

			long sum = CalculateUnSame(X, Y, xn, yn);

			Console.WriteLine("\n普通乘法 X*Y={0}*{1}={2}", X, Y, X * Y);
			Console.WriteLine("分治乘法 X*Y={0}*{1}={2}\n", X, Y, sum);
		}

		static long CalculateUnSame(long X, long Y, int xn, int yn)
		{
			if (X == 0 || Y == 0)
				return 0;
			else if ((xn == 1 && yn == 1) || xn == 1 || yn == 1)
				return X * Y;
			else
			{
				int xn0 = xn / 2, yn0 = yn / 2;
				int xn1 = xn - xn0, yn1 = yn - yn0;

				long A = (long)(X / Math.Pow(10, xn0));
				long B = (long)(X % Math.Pow(10, xn0));
				long C = (long)(Y / Math.Pow(10, yn0));
				long D = (long)(Y % Math.Pow(10, yn0));

				long AC = CalculateUnSame(A, C, xn1, yn1);
				long BD = CalculateUnSame(B, D, xn0, yn0);
				long ABCD = CalculateUnSame((long)(A * Math.Pow(10, xn0) - B), (long)(D - C * Math.Pow(10, yn0)), xn1, yn1);

				return (long)(2 * AC * Math.Pow(10, (xn0 + yn0)) + ABCD + 2 * BD);
			}
		}
		#endregion
    }
}

Java语言：

代码语言：javascript
复制
import java.util.ArrayList; 
import java.util.Date; 
import java.util.List;
import java.io.*;
import java.util.Scanner;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

public class Program
{
	public static Scanner sc = new Scanner(System.in);
	public static int count=0;
	public static void main(String[] args)
	{
		SameNumber();
		UnSameNumber();
	}

	public static int SIGN(long A)
	{
		return A > 0 ? 1 : -1;
	}

	//两整数位数相同
	private static void SameNumber()
	{
		System.out.print("请输入两个大整数：\nX=");
		long X = sc.nextLong();
		System.out.print("Y=");
		long Y = sc.nextLong();
		System.out.print("请输入两个大整数的长度：n=");
		int n = sc.nextInt();

		long sum = CalculateSame(X, Y, n);

		System.out.println("普通乘法 X*Y="+X+"*"+Y+"="+X*Y+"\n");
		System.out.println("分治乘法 X*Y="+X+"*"+Y+"="+sum+"\n");
	}

	public static long CalculateSame(long X, long Y, int n)
	{
		int sign = SIGN(X) * SIGN(Y);

		X = Math.abs(X);
		Y = Math.abs(Y);
		if (X == 0 || Y == 0)
			return 0;
		else if (n == 1)
			return sign * X * Y;
		else
		{
			long A = (long)(X / Math.pow(10, n / 2));
			long B = (long)(X % Math.pow(10, n / 2));
			long C = (long)(Y / Math.pow(10, n / 2));
			long D = (long)(Y % Math.pow(10, n / 2));

			long AC = CalculateSame(A, C, n / 2);
			long BD = CalculateSame(B, D, n / 2);
			long ABCD = CalculateSame((A - B), (D - C), n / 2) + AC + BD;

			return (long)(sign * (AC * Math.pow(10, n) + ABCD * Math.pow(10, n / 2) + BD));
		}
	}

//两整数位数不同
	private static void UnSameNumber()
	{
		System.out.print("请输入两个大整数：\nX=");
		long X = sc.nextLong();
		System.out.print("Y=");
		long Y = sc.nextLong();
		System.out.print("请输入X的长度：xn=");
		int xn = sc.nextInt();
		System.out.print("请输入Y的长度：yn=");
		int yn = sc.nextInt();

		long sum = CalculateUnSame(X, Y, xn, yn);

		System.out.println("普通乘法 X*Y="+X+"*"+Y+"="+X*Y+"\n");
		System.out.println("分治乘法 X*Y="+X+"*"+Y+"="+sum+"\n");
	}

	public static long CalculateUnSame(long X, long Y, int xn, int yn)
	{
		if (X == 0 || Y == 0)
			return 0;
		else if ((xn == 1 && yn == 1) || xn == 1 || yn == 1)
			return X * Y;
		else
		{
			int xn0 = xn / 2, yn0 = yn / 2;
			int xn1 = xn - xn0, yn1 = yn - yn0;

			long A = (long)(X / Math.pow(10, xn0));
			long B = (long)(X % Math.pow(10, xn0));
			long C = (long)(Y / Math.pow(10, yn0));
			long D = (long)(Y % Math.pow(10, yn0));

			long AC = CalculateUnSame(A, C, xn1, yn1);
			long BD = CalculateUnSame(B, D, xn0, yn0);
			long ABCD = CalculateUnSame((long)(A * Math.pow(10, xn0) - B), (long)(D - C * Math.pow(10, yn0)), xn1, yn1);

			return (long)(2 * AC * Math.pow(10, (xn0 + yn0)) + ABCD + 2 * BD);
		}
	}
}

JavaScript语言：

代码语言：javascript
复制
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<script>
function SIGN(A)
{
	return A > 0 ? 1 : -1;
}

function SameNumber()
{
	var str = "";
	var X = document.getElementById('SX').value;
	var Y = document.getElementById('SY').value;
	var n = document.getElementById('Sn').value;

	var sum = CalculateSame(X, Y, n);

	str += "普通乘法 X*Y="+X+"*"+Y+"="+X * Y+"<br/>";
	str += "分治乘法 X*Y="+X+"*"+Y+"="+sum;
	document.getElementById('oldcontent').innerHTML = str;
}

function CalculateSame(X, Y, n)
{
	var sign = SIGN(X) * SIGN(Y);

	X = Math.abs(X);
	Y = Math.abs(Y);
	if (X == 0 || Y == 0)
		return 0;
	else if (n == 1)
		return sign * X * Y;
	else
	{
		var A = parseInt(X / Math.pow(10, n / 2));
		var B = parseInt(X % Math.pow(10, n / 2));
		var C = parseInt(Y / Math.pow(10, n / 2));
		var D = parseInt(Y % Math.pow(10, n / 2));

		var AC = CalculateSame(A, C, n / 2);
		var BD = CalculateSame(B, D, n / 2);
		var ABCD = CalculateSame((A - B), (D - C), n / 2) + AC + BD;

		return (sign * (AC * Math.pow(10, n) + ABCD * Math.pow(10, n / 2) + BD));
	}
}

function UnSameNumber()
{
	var str = "";
	var X = document.getElementById('KX').value;
	var Y = document.getElementById('KY').value;
	var xn = document.getElementById('xn').value;
	var yn = document.getElementById('yn').value;

	var sum = CalculateUnSame(X, Y, xn, yn);

	str += "普通乘法 X*Y="+X+"*"+Y+"="+X * Y+"<br/>";
	str += "分治乘法 X*Y="+X+"*"+Y+"="+sum;
	document.getElementById('newcontent').innerHTML = str;

}

function CalculateUnSame(X,Y,xn,yn)
{
	if (X == 0 || Y == 0)
		return 0;
	else if ((xn == 1 && yn == 1) || xn == 1 || yn == 1)
		return X * Y;
	else
	{
		var xn0 = parseInt(xn / 2), yn0 = parseInt(yn / 2);
		var xn1 = xn - xn0, yn1 = yn - yn0;

		var A = parseInt(X / Math.pow(10, xn0));
		var B = parseInt(X % Math.pow(10, xn0));
		var C = parseInt(Y / Math.pow(10, yn0));
		var D = parseInt(Y % Math.pow(10, yn0));

		var AC = CalculateUnSame(A, C, xn1, yn1);
		var BD = CalculateUnSame(B, D, xn0, yn0);
		var ABCD = CalculateUnSame((A * Math.pow(10, xn0) - B), (D - C * Math.pow(10, yn0)), xn1, yn1);

		return (2 * AC * Math.pow(10, (xn0 + yn0)) + ABCD + 2 * BD);
	}
}
</script>
<body>
<div>请输入两个大整数：X=<input id="SX"/> Y=<input id="SY"/> 请输入两个大整数的长度：n=<input id="Sn"/>
<input type="button" onclick="SameNumber()" value="计算"/></div>
<div id="oldcontent"></div>
<div>请输入两个大整数：X=<input id="KX"/> Y=<input id="KY"/> 请输入X的长度：xn=<input id="xn"/>请输入Y的长度：yn=<input id="yn"/>
<input type="button" onclick="UnSameNumber()" value="计算"/></div>
<div id="newcontent"></div>
</body>
</html>

PHP语言：

代码语言：javascript
复制
<?php
error_reporting(E_ALL ^ E_NOTICE);
SameNumber();
UnSameNumber();

function SameNumber()
{
	fwrite(STDOUT, "理想状态算法！\n请输入两个大整数：\nX=");
	$X = trim(fgets(STDIN));
	fwrite(STDOUT, "Y=");
	$Y = trim(fgets(STDIN));
	fwrite(STDOUT, "请输入两个大整数的长度：n=");
	$n = trim(fgets(STDIN));

	$sum = CalculateSame($X, $Y, $n);

	echo "普通乘法 X*Y=".$X."*".$Y."=".$X*$Y."\n";
	echo "分治乘法 X*Y=".$X."*".$Y."=".$sum."\n";
}

function SIGN($A)
{
	return $A > 0 ? 1 : -1;
}

function CalculateSame($X,$Y,$n)
{
	$sign = SIGN($X) * SIGN($Y);

	$X = abs($X);
	$Y = abs($Y);
	if ($X == 0 || $Y == 0)
		return 0;
	else if ($n == 1)
		return $sign * $X * $Y;
	else
	{
		$A = intval($X / pow(10, $n / 2));
		$B = intval($X % pow(10, $n / 2));
		$C = intval($Y / pow(10, $n / 2));
		$D = intval($Y % pow(10, $n / 2));

		//echo"sign=".$sign." pow=".pow(10, $n / 2)." X=".$X." Y=".$Y." A=".$A." B=".$B." C=".$C." D=".$D."\n";

		$AC = CalculateSame($A, $C, $n / 2);
		$BD = CalculateSame($B, $D, $n / 2);
		$ABCD = CalculateSame(($A - $B), ($D - $C), $n / 2) + $AC + $BD;
		
		//echo "sum=".( $AC * pow(10, $n) )." AC=".$AC." BD=".$BD." ABCD=".$ABCD."\n";

		return ($sign * ($AC * pow(10, $n) + $ABCD * pow(10, $n / 2) + $BD));
	}
}

function UnSameNumber()
{
	fwrite(STDOUT, "\n非理想状态！\n请输入两个大整数：\nX=");
	$X = trim(fgets(STDIN));
	fwrite(STDOUT, "Y=");
	$Y = trim(fgets(STDIN));
	fwrite(STDOUT, "请输入X的长度：xn=");
	$xn = trim(fgets(STDIN));
	fwrite(STDOUT, "请输入Y的长度：yn=");
	$yn = trim(fgets(STDIN));

	$sum = CalculateUnSame($X, $Y, $xn,$yn);

	echo "普通乘法 X*Y=".$X."*".$Y."=".$X*$Y."\n";
	echo "分治乘法 X*Y=".$X."*".$Y."=".$sum."\n";
}

function CalculateUnSame($X,$Y,$xn,$yn)
{
	if ($X == 0 || $Y == 0)
		return 0;
	else if (($xn == 1 && $yn == 1) || $xn == 1 || $yn == 1)
		return $X * $Y;
	else
	{
		$xn0 = intval($xn / 2);
		$yn0 = intval($yn / 2);
		$xn1 = $xn - $xn0;
		$yn1 = $yn - $yn0;

		$A = intval($X / pow(10, $xn0));
		$B = intval($X % pow(10, $xn0));
		$C = intval($Y / pow(10, $yn0));
		$D = intval($Y % pow(10, $yn0));

		echo"X=".$X." Y=".$Y." A=".$A." B=".$B." C=".$C." D=".$D."\n";

		$AC = CalculateUnSame($A, $C, $xn1, $yn1);
		$BD = CalculateUnSame($B, $D, $xn0, $yn0);
		$ABCD = CalculateUnSame(($A * pow(10, $xn0) - $B), ($D - $C * pow(10, $yn0)), $xn1, $yn1);

		//echo "sum=".( $AC * pow(10, $n) )." AC=".$AC." BD=".$BD." ABCD=".$ABCD."\n";

		return (2 * $AC * pow(10, ($xn0 + $yn0)) + $ABCD + 2 * $BD);
	}
}
?>
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-09-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除
编程算法
c#

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ，欢迎热爱写作的你一起参与！

编程算法
c#
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 分治法的经典问题——大整数相乘
    • 分治法的原理
      • 通过大整数相乘问题来了解分治法（理想状态下）
        • 算法分析
          • 理想状态下代码实现（部分）：
            • 大整数相乘算法非理想状态下
              • 非理想状态下代码实现（部分）：
                • 理想状态下与非理想状态下代码实现（完整）：
                  • c语言：
                    • c++语言：
                      • c#语言：
                        • Java语言：
                          • JavaScript语言：
                            • PHP语言：
                            领券

                            腾讯云开发者

                            扫码关注腾讯云开发者

                            扫码关注腾讯云开发者

                            领取腾讯云代金券

                            热门产品

                            热门推荐

                            更多推荐

                            Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

                            深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

                            腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

                            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

                            Copyright © 2013 - 2024 Tencent Cloud.

                            All Rights Reserved. 腾讯云 版权所有

                            登录 后参与评论