Project Euler 99:Largest exponential 最大的幂

Largest exponential

Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187.

However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million digits.

Using base_exp.txt(right click and ‘Save Link/Target As…’), a 22K text file containing one thousand lines with a base/exponent pair on each line, determine which line number has the greatest numerical value.

NOTE: The first two lines in the file represent the numbers in the example given above.

---

最大的幂

比较两个如211和37这样写成幂的形式的数并不困难，任何计算器都能验证211 = 2048 < 37 = 2187。

然而，想要验证632382518061 > 519432525806就会变得非常困难，因为这两个数都包含有超过三百万位数字。

22K的文本文件base_exp.txt（右击并选择“目标另存为……”）有一千行，每一行有一对底数和指数，找出哪一行给出的幂的值最大。

注意：文件的前两行就是上述两个例子。

解题

指数运算太大了，取对数不就可以了

百度百科找的图片。

原函数和其反函数关于y=x对称，并且单调性一样。

JAVA

package Level3;

import java.io.BufferedReader;

import java.io.FileNotFoundException;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Set;

import java.util.TreeSet;

public class PE099{

    public static void run(){

        ArrayList<ArrayList<Integer>> base_exp = base_exp();

        int size = base_exp.size();

        double result[] = new double[size];

        double MAX = 1.0*Integer.MIN_VALUE;

        int index = 0;

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

            ArrayList<Integer> bp = base_exp.get(i);

            int base = bp.get(0);

            int exp = bp.get(1);

            result[i] = log10(base,exp);

//            System.out.println(result[i]);

            if(MAX < result[i]){

                MAX = result[i];

                index = i;

            }

        }

        // 要加一，你懂的

        index+=1;

        System.out.println(index);

    }

//    709

//    running time=0s22ms

    public static double log10(int base,int exp){

        double res = 0.0;

        res = exp*Math.log10(base);

        return res;

    }

    public static ArrayList<ArrayList<Integer>> base_exp(){

        String filename = "src/Level3/p099_base_exp.txt";

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

        try {

            BufferedReader input = new BufferedReader(new FileReader(filename));

            String str="";

            try {

                while((str=input.readLine())!=null){

                    String[] strArr = str.split(",");

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

                    num.add(Integer.parseInt(strArr[0]));

                    num.add(Integer.parseInt(strArr[1]));

                    base_exp.add(num);

                }

            } catch (IOException e) {

                // TODO Auto-generated catch block

                e.printStackTrace();

            }

        } catch (FileNotFoundException e) {

            // TODO Auto-generated catch block

            e.printStackTrace();

        }

        return base_exp;

    }

    public static void main(String[] args) throws IOException{

        long t0 = System.currentTimeMillis();

        run();

        long t1 = System.currentTimeMillis();

        long t = t1 - t0;

        System.out.println("running time="+t/1000+"s"+t%1000+"ms");

    }

}

Python

# coding=gbk

import time as time

import re

import math

def run():

    filename = 'E:/java/projecteuler/src/Level3/p099_base_exp.txt'

    file = open(filename)

    MAX = 0.0

    index = 0

    i = 0

    for row in file.readlines():

        row = row.strip('\n').split(",")

        res = int(row[1])*math.log(int(row[0]))

        i+=1

        if res>MAX:

            MAX = res

            index = i

    print index

#

# running time= 0.00400018692017 s

t0 = time.time()

run()

t1 = time.time()

print "running time=",(t1-t0),"s"