首页 > 代码库 > 1、对一个正整数算到1需要的最少操作次数
1、对一个正整数算到1需要的最少操作次数
题1:实现一个函数,对一个正整数n,算得到1需要的最少操作次数。操作规则为:如果n为偶数,将其除以2;如果n为奇数,可以加1或减1;一直处理下去;
例子:
func(7) = 4,可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求:实现函数(实现尽可能高效) int func(unsign int n);n为输入,返回最小的运算次数。给出思路(文字描述),完成代码,并分析你算法的时间复杂度。
java源程序:
package bfgy.lab.work; import java.util.Scanner; import java.lang.Integer; public class first {/*** 820lab*/ public static void main(String[] args) { int n,m=0; Scanner sc=new Scanner(System.in); n=sc.nextInt(); function(n,m); System.out.println(function(n,m)); } public static int function(int n,int m){ while(n!=0){ if(n==1){ return 0;} else if(n%2==0) {return 1+function(n/2,m+1); } int x=function(n+1,m+1); int y=function(n-1,m+1); if(x>y) {return y+1;}else{return x+1;}} return m; } }
1、对一个正整数算到1需要的最少操作次数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。