首页 > 代码库 > 算法笔记_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)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。