当前位置:首页 » Project Euler » 详细页

Largest exponential 题号:99 难度: 10 中英对照

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.

Solution

该题求一系列指数中的哪一个值最大,开始想到可以用直接用指数函数求每个指数的值,然后取最大值,但是性能非常低,一个数就要计算2分钟左右。 实际上,该题只要求得到哪一个值最大,可以利用对数将指数运算转化为乘法运算: $$log_a (x^y) =y log_a(x)$$ 特别的,取$~a=10~$,这样我们只要比较对数值即可得到原指数值的大小。

Code

using System;
using System.Diagnostics;
using System.IO;
namespace euler
{
	class Problem099
	{
		public static void Main(string[] args)
		{
			Stopwatch clock = Stopwatch.StartNew();
			var result = Run();
			clock.Stop();
			Console.WriteLine(result);
			Console.WriteLine("Solution took {0} ms", clock.Elapsed.TotalMilliseconds);
			Console.Read();
		}

		public static int Run()
		{
			int maxline = 0;
			double maxnum = 0;
			string filename = Environment.GetFolderPath(Environment.SpecialFolder.DesktopDirectory) + "\\p099_base_exp.txt";
			string[] lines = File.ReadAllLines(filename);
            for (int i = 0; i<lines.Length; i++) {
                string[] line = lines[i].Split(',');
				double basenum = Math.Log(Convert.ToInt32(line[0]));
				int exponent = Convert.ToInt32(line[1]);
				double number = basenum * exponent;
                if (number > maxnum) {                    
                    maxline = i+1;
                    maxnum = number;                        
                }
            }
			return maxline;
		}
	}
}
709
Solution took 92.3869 ms
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.List;

public class p99 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        long result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    public static long run() {
        int maxline = 0; 
        double maxnum = 0;
        Path path = Paths.get("C:/temp/p099_base_exp.txt");
        try{
            List<String> lines = Files.readAllLines(path);
            for (int i = 0; i<lines.size(); i++) {
                String[] line = lines.get(i).split(",");
                double basenum = Math.log(Integer.parseInt(line[0]));
                int exponent = Integer.parseInt(line[1]);
                double number = basenum * exponent;
                if (number > maxnum) {                    
                    maxline = i+1;
                    maxnum = number;                        
                }
            }
            return maxline;
        } catch (IOException | NumberFormatException e) {  
        }
        return 0;
    }
}
709
30ms