Java实现 蓝桥杯 算法训练 乘法次数

乘法次数

资源限制

时间限制：1.0s 内存限制：999.4MB

问题描述

　　给你一个非零整数，让你求这个数的n次方，每次相乘的结果可以在后面使用，求至少需要多少次乘。如24：22=22（第一次乘），2222=24（第二次乘），所以最少共2次；

输入格式

　　第一行m表示有m(1<=m<=100)组测试数据；

　　每一组测试数据有一整数n（0<n<=100000000）;

输出格式

　　输出每组测试数据所需次数s;

样例输入

3

2

3

4

样例输出

1

2

2

PS：

二分法

import java.util.ArrayList;

import java.util.Scanner;

public class 乘法次数 {

	public static void main(String[] args) {

		ArrayList<Integer> input = new ArrayList<Integer>();

		ArrayList<Integer> result = new ArrayList<Integer>();

		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		for (int i = 0; i <n; i++) {

			input.add(sc.nextInt());

		}

		for(int i:input){

			int temp=0;

			while(i!=1){

				if(i%2==0){

					temp+=1;

				}

				else{

					temp+=2;

				}

				i/=2;

			}

			result.add(temp);

		}

		for (int i:result) {

			System.out.println(i);

		}

	}

}