问题:
求一个数A如果按2到A-1进制表达时, 各个位数之和的均值是多少?
输入:
输入中有多组测试数据, 每组测试数据为一个整数(A在[1, 5000]内)
输出:
对每组测试数据, 在单独的行中以X/Y的形式表达.
样例输入
5
3
样例输出
7/3
2/1
分析:
均值即平均值, 数字5在二进制下, 变为101, 3进制下为12, 4进制下为11, 故结果为7/3.
e.g.
255(10), n是数字, a是进制数, 255%10为个位数5, 即通过取余和移位的方法, 可以求得该数字在几进制下的所有位数之和, 再通过循环取得从2到A-1进制下的总和即可.
代码示例以及注释:
package nowcoder.a1_Jingdong;
import java.util.Scanner;
/**
* 进制均值
*
* @Author menglanyingfei
* @Created on 2017.11.29 15:24
*/
public class T1_hexSum {
public static void main(String[] args) {
int A;
Scanner sc = new Scanner(System.in);
while ((A = sc.nextInt()) != 0) {
int sum = 0;
for (int i = 2; i <= A - 1; i++) {
sum += hexSum(A, i);
}
int r = gcd(sum, A-2);
System.out.println((sum / r) + "/" + (A-2) / r);
}
}
// 求一个进制数的所有位数之和, n是数字, a是进制数
public static int hexSum(int n, int a) {
int sum = 0;
while (n != 0) {
sum += (n % a);
n = n / a;
}
return sum;
}
/*
实现gcd比较好用的是辗转相除法
比如：49和91
a b temp
49 % 91 = 49
91 % 49 = 42
49 % 42 = 7
42 % 7 = 0
所以最大公约数就是7.
(看懂这, 下面的代码, 你肯定懂的!)
*/
// 求最大公约数(辗转相除法)
private static int gcd(int sum, int i) {
while (i != 0) {
int temp = sum % i;
sum = i;
i = temp;
}
return sum;
}
}
