首页 > 试题广场 >

进制均值

[编程题]进制均值
  • 热度指数：16197 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
尽管是一个CS专业的学生，小B的数学基础很好并对数值计算有着特别的兴趣，喜欢用计算机程序来解决数学问题，现在，她正在玩一个数值变换的游戏。她发现计算机中经常用不同的进制表示一个数，如十进制数 123 表达为 16 进制时只包含两位数 7、11（B），用八进制表示为三位数 1、7、3，按不同进制表达时，各个位数的和也不同，如上述例子中十六进制和八进制中各位数的和分别是 18 和 11 。 小B感兴趣的是，一个数 A 如果按 2 到 A-1 进制表达时，各个位数之和的均值是多少？她希望你能帮她解决这个问题？ 所有的计算均基于十进制进行，结果也用十进制表示为不可约简的分数形式。

数据范围：

输入描述:
输入中有多组测试数据，每组测试数据为一个整数A


输出描述:
对每组测试数据，在单独的行中以X/Y的形式输出结果。
示例1

输入

5
3

输出

7/3
2/1
算法知识视频讲解
添加回答
Java
黄小斜头像 黄小斜 
在进制转换过程中累加每位的和，进制转换从2进制一直到A-1进制。
然后求sum和A-2的最大公约数，分别除以最大公约数，即可得不可约的分数
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            System.out.println(sumAndAve(n));
        }
    }

    public static String sumAndAve(int n) {
        int sum = 0;
        for (int i = 2;i < n;i ++) {
            sum += convert(n, i, 0);
        }
        int gcd = gcd(sum, n - 2);
        return sum/gcd + "/" + (n - 2)/gcd;
    }

//    // 2-16进制表示的位数
//    public String[] arr = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
//            "A", "B", "C", "D", "E", "F"};

    /**
     * @param number 要转换的十进制数
     * @param system 转换的进制位
     */
    public static int convert(int number, int system, int sum) {
        sum = number % system + sum;

        if(number/system == 0) return sum;

        return convert(number/system, system, sum);
    }

    public static int gcd(int x, int y){ // 这个是运用辗转相除法求 两个数的 最大公约数  看不懂可以百度                                                        //    下
        if(y == 0)
            return x;
        else
            return gcd(y,x%y);
    }
}

发表于 2018-06-06 23:08:32 回复(0)
更多回答
那年夏天宁静的海00头像 那年夏天宁静的海00
//还是上一题难 ！！！ 求最大公约数 +数字位求和
import java.util.*;
public class test2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int num = sc.nextInt();
deal(num);
}
}
public static void deal(int num){
int sum=0;
int kind =num-2;
for(int i=2;i<num;i++){
sum+=fun2(num,i);
}
int con =fun(sum,kind);
System.out.println(sum/con+"/"+kind/con);
}
//一个数字按不同进制的各个位加和
public static int fun2(int num,int x){
int res=0;
while(num!=0){
res+=num%x;
num/=x;
}
return res;
}
//求出最大公约数
public static int fun(int a, int b){
while(a%b!=0){
int c =a%b;
a=b;
b=c;
}
return b;
}
}
发表于 2017-07-24 16:38:09 回复(0)
菜鸟四号头像 菜鸟四号 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while(~scanf("%d",&n)) {
        int sum=0;
        for(int i=2; i<n; i++) {
            int m=n;
            while(m) {
                sum+=(m%i);
                m/=i;
            }
        }
        int val=__gcd(sum,n-2);
        printf("%d/%d\n",sum/val,(n-2)/val);
    }
    return 0;
}

发表于 2017-08-09 14:40:05 回复(3)
Asdil头像 Asdil 
# 不仅考察进制换算，还考察最大公约数
def f1(n): # 进制换算，计数
    ret = 0
    for i in range(2,n): # 一次除以2至n-1，相当于换算成2至n-1进制
        t = n
        while 1:
            ret += t % i # 将结果加入返回值
            t = t // i
            if t == 0:
                break
    return ret
def f2(n, m): # 求最大公约数
    ret = 1
    while m > 0:
        t = n % m
        n = m
        m = t
    ret = n
    return ret
if __name__ == '__main__':
    while 1:
        try:
            n = int(raw_input())
        except:
            break
        r = f1(n) # r是总的进制换算相加的数
        l = len(range(2, n)) # 被除数2 至（n-1）
        s = f2(r, l) # 最大公约数
        r , l = r//s, l//s # 结果除以最大公约数
        print str(r) + '/' + str(l)

编辑于 2017-07-06 20:00:02 回复(0)
牛客吴彦祖QAQ头像 牛客吴彦祖QAQ 
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int m;
    vector<int> v;
    cin >> m;
    for(int i = 2; i < m; i++)//i进制求和
    {
        int n = m;
        while(n != 0)
        {
            int tmp = n % i;
            v.push_back(tmp);
            n = n / i;
        }
    }
    int sum = 0;
    for(int i = 0; i < v.size(); i++)
      sum = sum + v[i];
    int num = m - 2;
    for(int i = m - 2; i > 1; i--)//约分
    {
        if((sum % i == 0) && ((num) % i == 0))
        {
            sum = sum / i;
            num = num / i;
        }
    }
    cout << sum << "/" << num << endl;
}
发表于 2018-09-17 21:55:24 回复(0)
Python
华科平凡头像 华科平凡

python解法：

在化简的时候先求分子和分母的最大公约数，再将这两个数同时除以最大公约数即可。

from math import gcd

def calcSumOfANumber(number):
    total = 0
    for i in range(2, number):
        res, num = 0, number
        while num:
            res += num % i
            num = num // i
        total += res
    return total

while True:
    try:
        a = int(input())
        b = calcSumOfANumber(a)
        gcdRes = gcd(b, a - 2)
        print(str(b // gcdRes) + "/" + str((a - 2) // gcdRes))
    except:
        break
发表于 2018-04-13 17:13:19 回复(0)
Tonedoony头像 Tonedoony
#include<iostream>

using namespace std;

int main(){
    int x;
    int sum = 0;
    cin>>x;
    int count = x-2;
//求每各位数的和
    for(int i=2;i<x;i++){
        int temp = x/i; 
        sum += x %i;
        while(temp !=0){
            sum += temp %i;
            temp = temp/i;
        }
    }
//求最大公约数
    int a = count,b = sum;
    int flag = count % sum;
    while(flag !=0){
        a = b;
        b = flag;
        flag = a % b;
    }
    sum = sum / b;
    count = count / b;
    cout<<sum<<'/'<<count;
    return 0;
}
发表于 2017-09-08 15:40:10 回复(0)
早起的小虫儿头像 早起的小虫儿 
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNextInt()){
			int num = scanner.nextInt();
			int sum = 0;
			for(int i = 2; i <= num - 1; i++){
				sum += hexSum(num, i);
			}
			int gcd = gcd(sum, num - 2);
			System.out.println(sum / gcd + "/" + (num - 2) / gcd);
		}
		scanner.close();
	}
	
	public static int gcd(int one, int two){
		return two == 0 ? one : gcd(two, one % two);
	}
	
	public static int hexSum(int num, int base){
		int sum = 0;
		while(num != 0){
			sum += num % base;
			num = num / base;
		}
		return sum;
	}
}

发表于 2017-08-28 20:30:27 回复(1)
Java
指offer的剑在哪？头像 指offer的剑在哪？
n的i进制数，对i反复进行求余累加知道n为0；
求最大公约数，使用辗转相除法，直到为0则其前一个数为最大公约数 
import java.util.Scanner;
public class StringUtil{
		
	//禁止均值
	public static void main(String[] args){
		
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			int sum = 0;
			for(int i=2; i<=n-1; i++){
				sum += jzh(n,i);
			}
			int gys = gy(sum, n-2);
			System.out.println(sum/gys + "/" +(n-2)/gys);
		}
		
	}
	
	//求最大公约数
	public static int gy(int a, int b){
	
		if(a > b){
			a = a+b;
			b = a-b;
			a = a-b;
		}
		while(a != 0){
			int c = b%a;
			b = a;
			a = c;
		}
		return b;
	}
	
	//求进制和
	public static int jzh(int n,int m){
		
		int sum = 0;
		while(n != 0){
			sum += n%m;
			n /= m;
		}
		return sum;
	}
}

发表于 2017-09-07 10:32:12 回复(0)
pein531头像 pein531 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int val = scanner.nextInt();
            int totalSum = 0;
            // 遍历不同进制
            for (int i = 2; i <= val - 1; i++)
                totalSum += sum(val, i);      // 求val在i进制下各位数的和
            int k = val - 2;                  // 可以转化为几种进制
            int commondiv = commonDiv(totalSum, k);
            // 约分输出
            System.out.println(totalSum / commondiv + "/" + k / commondiv);
        }
        scanner.close();
    }

    public static int sum(int val, int factor){
        int sum = 0;
        while(val > 0){
            sum += val % factor;
            val /= factor;
        }
        return sum;
    }
    // 求最大公约数,使用辗转相除法
    public static int commonDiv(int a,int b){
        if(a < b){    // a中存较大的那个值
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
        }
        while (a % b != 0) {
            int leave = a % b;        // 求余数
            a = b;
            b = leave;
        }
        return b;
    }
}

发表于 2020-10-15 23:07:20 回复(0)
C/C++
海问香12138头像 海问香12138

其他语言永远也体会不到C语言的快乐（尤其是C++） 
#include <stdio.h>

int n,sum;

int gcd(int a,int b);

int main()
{
	int i,t;
	while(scanf("%d",&n)!=EOF)
	{
		sum = 0;
		for(i=2;i^n;i++)
			for(t=n;t;t/=i)
				sum += t % i;
		n -= 2;
		t = gcd(sum,n);
		printf("%d/%d\n",sum/t,n/t);
	}
	return 0;
}

int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}

发表于 2019-08-18 21:03:53 回复(0)
一匹努力的千里马头像 一匹努力的千里马
这个题目的意思是：
输入5
那么在 2进制所有数和为A,
3进制所有数和为B,
4进制所有数和为C,
那么最后的平均值为（A+B+C)/3，就是最后结果

 
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = 0;
        for(int i = 2;i< n;i++) {
            count += function(n,i);
        }
        int maxcommon = common(count,n-2);
        System.out.println(count/maxcommon+"/"+(n-2)/maxcommon);
    }
    private static int common(int x,int y) {
        int res = y;
        while(y!=0) {
            int temp = x;
            x = y;
            y = temp % y;
        }
        return x;
    }
    
    private static int function(int x,int radis) {
        int count= 0;
        int tmp = x;
        while(tmp != 0) {
            count+=tmp%radis;
            tmp/=radis;
        }
        return count;
    }
}

编辑于 2018-05-10 16:55:21 回复(0)
C/C++
stubsx头像 stubsx 

	#include <iostream>





	using namespace std;





	int convert(int A, int B)//A在B进制下的各位数之和





	{





	    int after=0;





	    while(A!=0)





	    {





	        int temp=A%B;





	        after=after+temp;





	        A=A/B;





	    }





	    return after;





	}





	int main(int argc, const char * argv[]) {





	    int A;





	    cin>>A;





	    int sum=0;





	    for(int i=2;i<=A-1;i++)//求和





	    {





	        sum=sum+convert(A, i);





	    }





	    int div=A-2;





	    for(int i=2;i<=div;)//化简





	    {





	        if(sum%i==0&&div%i==0)





	           {





	               sum/=i;





	               div/=i;





	               continue;





	           }





	        i++;





	    }





	    cout<<sum<<"/"<<div<<endl;





	    return 0;





	}

发表于 2018-02-02 11:19:27 回复(0)
C/C++
nbgao头像 nbgao 
#include <iostream> 
using namespace std;

int Sum(int n, int m)
{     int sum = 0;     while(n)     {         sum += n%m;         n /= m;     }     return sum;
}

int gcd(int a, int b)
{     int t = a%b;      while(t)     {         a = b;         b = t;         t = a%b;     }     return b;
}

int main()
{     int A, sum;     while(cin>>A)     {         sum = 0;         for(int i=2;i<=A-1;i++)             sum += Sum(A,i);         int u = gcd(sum, A-2);         cout<<sum/u<<"/"<<(A-2)/u<<endl;     }      return 0;
}

发表于 2018-01-11 01:16:00 回复(0)
元气の悟空头像 元气の悟空 
#include<stdio.h>
#include<math.h>
int getSum(int,int);
int gcd(int,int);
int main(){
    int A,i;
    while(scanf("%d",&A)!=EOF){
        int len=A-2,sum=0;
        for(i=2;i<A;i++) sum+=getSum(A,i);
        printf("%d/%d\n",sum/gcd(sum,len),len/gcd(sum,len));
    }
}
int getSum(int x,int y){
    int sum=0;
    while(x) sum+=x%y,x/=y;
    return sum;
}
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

发表于 2017-10-29 10:27:28 回复(0)
咸鱼吧，后浪！头像 咸鱼吧，后浪！ 
// 万能c++头文件，包含c++所有头文件
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    // "~"符号不可缺失
    while(~scanf("%d",&n)) {
        int sum=0;
        for(int i=2; i<n; i++) {
            int m=n;
            while(m) {
                sum+=(m%i);
                m/=i;
            }
        }
        // 库函数__***()，用于求最大公约数
        // 要是觉得不手写搁着难受，可用欧几里德算法手撸一个：
        // 思想很简单：被除数%除数，如果余数为零，那么最大公约数***为除数
        // 如果余数不为零，将除数赋给被除数，余数赋给除数，继续上述过程
        // int x = sum,y = n-2;
        // int z = x % y;      
        // while(z){
        //     x = y;
        //    y = z;
        //    z = x % y;
        // }
        int val = __***(sum,n-2);
        printf("%d/%d\n",sum/val,(n-2)/val);
    }
    return 0;
}
发表于 2017-09-09 10:54:29 回复(0)
明月醉清风头像 明月醉清风
var nums = [];
while((line = readline())) {
    nums.push(line);
}
average(nums);
function average (nums) {
    for(var i = 0; i < nums.length; i++) {
        var sum = 0;
        for(var j = 2; j < nums[i]; j++) {
            var A = nums[i];
 
            while(Math.floor(A / j) != 0) {
                sum += A % j;
                A = Math.floor(A / j);
            }
            sum += A % j;
        };
        var k = format(sum, nums[i] - 2);
        //console.log(sum / k + '\/' + (nums[i] - 2) / k + '\n');
        print(sum / k + "/"+ (nums[i] - 2) / k)
    };
    //寻找最大公约数
    function format (num1, num2) {
        var l = num1 >= num2 ? num2 : num1;
 
        for(var i = l; i >= 2; i--) {
            if(num1 % i == 0&& num2 % i == 0) {
                break;
            }
        };
        returni;
    }
}
发表于 2017-09-03 18:13:54 回复(0)
niutor头像 niutor 
#include <iostream>

int main() {
	int A = 0;
	int sum = 0;
	while (std::cin >> A) {
		if (A == 1) {
			std::cout << "1" << "\n";
			continue;
		}
		if (A == 2) {
			std::cout << "1/2" << "\n";
			continue;
		}
		for (int i = 2; i <= A-1; ++i) {
			int temp = A;
			while (temp != 0) {
				sum += temp % i;
				temp = temp / i;
			}
		}
		int count = A-2;
		int t = sum > count ? sum : count;
		for (int i = 2; i <= t; ++i) {
			while (sum % i == 0 && count % i == 0) {
				sum = sum / i;
				count = count / i;
			}
		}
		std::cout << sum  << "/" << count << "\n";
		sum = 0;
	}
}
发表于 2017-08-30 11:44:36 回复(0)
@曼彻斯特罗比头像 @曼彻斯特罗比
A = int(input(''))
num = int(0)
order = int(0)
B = A
T=int(0)
fori in range(2, A):
    whileB != 0:
        T = B%i
        B = B//i
        num = num + T
        T = int(0)
    order = order + 1
    B = A
forq in range(2,order+1):
    whilenum%q ==0and order%q ==0:
        num = num/q
        order = order/q 
print('{0}/{1}'.format(int(num),int(order)))

第一个for i in range(2, A):循环进制数,例如15%3 = 0 ,5%3 = 2, 3/3 = 1,则15转化为3进制为120。
在循环中num累加每一位的数值，order统计进制的种数。
然后for q in range(2,order+1): 寻找num和order的公约数并除掉。
最后以分子形式输出。
发表于 2017-08-24 21:59:09 回复(0)
蓝魔4头像 蓝魔4 
#include<iostream>
#include<cmath>
using namespace std;
int Getsum(int num,int bit)
{
    int res=0;
    while(num)
    {
        int lei=num%bit;
        res=res+lei;
        num/=bit;
    }
    return res;
}
int gcd(int num1,int num2)
{
    int p=min(num1,num2);
    int maxVal=1;
	if(num1%num2==0)
		return num2;
    for(int i=2;i<=sqrt(double(p));i++)
    {
        if(num1%i==0&&num2%i==0)
        {
            maxVal=max(i,maxVal);
        }
    }
    return maxVal;
}
int main()
{
    int num;
    while(cin>>num)
    {
        int sum=0;
        for(int i=2;i<=num-1;i++)
        {
            sum+=Getsum(num,i);
        }
        int r=gcd(sum,num-2);
        cout<<sum/r<<"/"<<(num-2)/r<<endl;
    }
    return 0;
}

发表于 2017-08-20 19:14:27 回复(0)
提交观点

问题信息

2017 C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 模拟 京东 Java工程师
难度：
145条回答 16031浏览

热门推荐

通过挑战的用户

查看代码

相关试题

进制均值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号