2017京東校招筆試験プログラミング問題:進数変換、転々と相殺

1844 ワード

タイトルの説明
時間制限:C/C++言語1000 MSその他言語:3000 MS
メモリ制限:C/C++言語65536 KBその他言語:589824 KB
テーマの内容:CSの専门の学生ですけれども、小さいBの数学の基础はとても良くてそして数値の计算に対して特别な兴味を持って、コンピュータのプログラムで数学の问题を解决することが好きです.今、彼女は数値変換のゲームをしています.彼女はコンピュータの中でよく異なる進数で同じ数を表すことを発見して、例えば十進数123が16進数で表現する時2桁の7、11(B)だけを含んで、8進数で表す時3桁の1、7、3です.異なる進数で表現する場合、各ビット数の和も異なり、上記の例では16進数と8進数の和がそれぞれ18と11である.Bさんが興味を持っているのは、1つの数Aが2からA-1進数で表現された場合、各桁数の和の平均値はいくらですか.彼女はあなたがこの問題を解決してくれることを望んでいます.すべての計算は10進法に基づいて行われ、結果も10進法で簡略化できない点数形式として表される.
入力:入力に複数のテストデータがあります.各試験データのセットは、整数>A(1<=A<=5000)である.
出力:テストデータのセットごとに、結果を個別の行にX/Yで出力します.
サンプル入力:
5
3
サンプル出力:
7/3
2/1
コード実装(Java)
テーマは相対的に簡単で、主に2つの関数を実現して、1つは10進数から任意進数の間の変換です;もう1つは2つの数の最大公約数を解くことです.ダイレクトコード:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {    
    //10        ,        list ,        
    public static int transForm(int num, int n){
        List list = new ArrayList<>();
        int sum = 0; 
        while(num != 0){
            int remainder = num%n;
            num = num/n;
            list.add(remainder);
        }
        for(int i = 0; i < list.size(); i++){
            sum += list.get(i);
        } 
       return sum;
    } 

   //    ,           
    public static int gcd(int m, int n){
        int r = m % n;
        while (r != 0){
            m = n; 
            n = r;
            r = m % n;
        }
        return n;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int sum = 0, div;
        div = m - 2;    //   

        for(int i = 2; i < m; i++){
            sum += transForm(m, i);
        }
        System.out.println(sum/gcd(sum, div) + "/" + div/gcd(sum, div));
    }
}