算法——俄式乘法

共计 419 个字符，预计需要花费 2 分钟才能阅读完成。

两个正整数相乘的非主流算法

假设 n 和 m 是两个正整数，计算 n *m，现在用 n 的输入作为实例规模的度量标准。

假设 n 是偶数，一个规模为原来一半的实例必须要对 n / 2 进行处理，n*m=n/2 * 2m

假设 n 是奇数，只需要对公式进行简单调整，n*m=（n-1）/2 * 2m

并且使用 1 *m= m 作为终止条件。

我们写下来一个例子就会发现：所有当前 n 的值是奇数时候，只需要相加对应的 m 值即可得到 n * m 的乘积。

例如：50*65=25*130=12*260（+130）=6*520=3*1040=1*2080===2080+1040+130=3250

下面我们就开始下代码实现：
#include
using namespace std;

int main()
{
int n,m,mul=0;
cin>>n>>m;
for(int i=n>>1;i>=1;i=i>>1)
{
m=m

阿里云 2 核 2G 服务器 3M 带宽 61 元 1 年，有高配

腾讯云新客低至 82 元 / 年，老客户 99 元 / 年

代金券：在阿里云专用满减优惠券