decadence

個人のメモ帳

Project Euler 24

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目

  • 使ってない数字がn個の時はfact(n)通りの並べ方がある
  • 残った数字のリストと今何番目であるかを引数に再帰を行う

こんな感じでやりましてん
1000000-1の1が気がつかなくて一つずれてたりあうあう
再帰とか苦手なんですけど答え出たからおっけーでしょう
リストへの初期値への代入の仕方が地味にわからなくて探したり云々

...
for10個繋いだ解答があったけど...いや確かに出るけどさ...

import java.util.*;

class Sample{
	static String answer = "";
	public static void main(String[] args){
		List<String> num = Arrays.asList("0","1","2","3","4","5","6","7","8","9");
		ArrayList<String> n = new ArrayList<String>(num);
		check(n,1000000-1);
	}

	private static void check(ArrayList<String> num,int count) {
		int factCount = fact(num.size()-1);
		int number = count/factCount;
		System.out.println(count);
		if(num.isEmpty()) System.exit(0);
		answer += num.get(number);
		num.remove(number);
		System.out.println("answer : "+answer);
		check(num, count - number*factCount);
	}

	private static int fact(int n){
		int result = n;
		if(n == 0) return 1;
		for(int i = 1; i < n; ++i){
			result *= i;
		}
		return result;
	}
}