俄罗斯农民乘法 代码

/***********
描述：俄罗斯农民乘法
   基本公式：如果n是偶数，n*m=n/2*2*m;
   如果n是奇数,n*m=(n-1)/2*(2*m)+m
时间 2007.06.20
作者 lee
*******************/

 

#include<iostream>
using namespace std;
int G(int n,int m){
 int g=0,tmp=0;
 while(n>=1){
  if(n%2==0){//n为偶数情况
   n=n/2;
   m=m*2;
   }
  else {//n为奇数情况
   tmp=tmp+m;//tmp用于记录额外加数的总和
   n=n/2;
   m=m*2;
   } 
 
 }
 return g=m*n+tmp;
 }

 

void main(){
  cout<<G(50,60);
 }

 

 

注：此程序还可以写成这样，注意蓝色字体部分，一个有等号一个没有

 

#include<iostream>
using namespace std;
int G(int n,int m){
 int g=0,tmp=0;
 while(n>1){
  if(n%2==0){//n为偶数情况
   n=n/2;
   m=m*2;
   }
  else {//n为奇数情况
   tmp=tmp+m;//tmp用于记录额外加数的总和
   n=n/2;
   m=m*2;
   } 
 
 }
 return g=m*n+tmp;
 }

 

void main(){
  cout<<G(50,60);
 }