首页 > 代码库 > 算法笔记_027:俄式乘法(Java)

算法笔记_027:俄式乘法(Java)

1 问题描述

首先,了解一下何为俄式乘法?此处,借用《算法设计与分析基础》第三版上一段文字介绍:

 技术分享

技术分享

 

 


2 解决方案

具体编码如下:

package com.liuzhen.chapter4;

public class RussianPeasant {
    //方法1:递归求解
    public void recursionRussian(int m,int n,int result){
        if(m < 1)
            return;
        if(m == 1)
            System.out.println("使用递归求取m*n结果: "+(result+n));
        if(m % 2 == 0){
            m = m/2;
            n = n*2;
            recursionRussian(m,n,result);
        }
        else{
            result += n;
            m = (m-1)/2;
            n = n*2;
            recursionRussian(m,n,result);
        }
    }
    
    //方法2:迭代求解
    public int iterationRussian(int m,int n){
        int result = 0;
        while(m > 0){
            if(m % 2 == 0){
                m = m/2;
                n = n*2;
            }
            else{
                result += n;
                m = (m-1)/2;
                n = n*2;
            }
        }
        return result;
    }
    
    public static void main(String[] args){
        RussianPeasant test = new RussianPeasant();
        test.recursionRussian(50, 65, 0);
        System.out.println("使用迭代求取m*n结果:"+test.iterationRussian(50, 65));
    }
}

运行结果:

使用递归求取m*n结果: 3250
使用迭代求取m*n结果:3250

 

算法笔记_027:俄式乘法(Java)