アルゴリズム-吸血鬼アルゴリズムの詳細
ヴァンパイアのアルゴリズムタイトル吸血鬼数字とは、偶数の桁数の数字で、数字の山から乗じたいと思って得ることができます.このペアの数字には、積の半分の桁数を含む数字があり、最初の数字から選択した数字は任意にソートできます.2つの0で終わる数字は許されません.例えば、以下の数字はすべて「吸血鬼」の数字です.1260=21*60 1827=21*87 2187=27*81はプログラムを書いて、4桁のすべての吸血鬼の数字 を見つけます.考え方 個人の考え方 は、2桁のループを用いて乗算4桁の を得る.は、2つの2桁と4桁をそれぞれ1文字に分解し、Listに 保存する. Listのequalsメソッドを用いて に等しいか否かを判定する.
公式構想 すべての4桁の を巡回は4桁を分割してそれぞれ2つの2桁に組み合わせて、全部で12種類の組み合わせ方式 があります.それぞれの組み合わせは と判断する.
のメリット 個人の考え方は半分近くの遍歴回数を減らすことができ、約3000回の
実装 個人の考え方 公式構想
package ten;
import java.util.*;
public class VampireNumberImp {
static int VampireJudgeImp(){
List VampireArray = new ArrayList();
List ikList = new ArrayList();
List sumList = new ArrayList();
int point = 0;
for (int i = 11 ; i < 100 ; i++ ){
for (int k = i ; k < 100 ; k++){
int sum = i * k;
// ,
if ( sum < 1000 || sum > 9999 || sum % 100 == 0 || VampireArray.contains(sum)){
continue;
}
point++;
//
// list
ikList.add((char) (i / 10));
ikList.add((char) (i % 10));
ikList.add((char) (k / 10));
ikList.add((char) (k % 10));
sumList.add((char) (sum / 1000));
sumList.add((char) (sum % 1000 / 100));
sumList.add((char) (sum % 1000 % 100 / 10));
sumList.add((char) (sum % 10));
//
Collections.sort(ikList);
Collections.sort(sumList);
//
if (ikList.equals(sumList)){
VampireArray.add(sum);
System.out.println(sum);
}
ikList.clear();
sumList.clear();
}
}
return point;
}
public static void main(String[] args) {
long startTime=System.currentTimeMillis();
int point = VampireJudgeImp();
//
long endTime=System.currentTimeMillis();
System.out.println(" : "+(endTime - startTime)+"ms");
System.out.println(" : "+point+" ");
}
}/* output
1395
1260
1827
2187
1530
1435
6880
: 19ms
: 3210
*/
package ten;
public class VampireNumberOfficial {
static int a(int i) {
return i/1000;
}
static int b(int i) {
return (i%1000)/100;
}
static int c(int i) {
return ((i%1000)%100)/10;
}
static int d(int i) {
return ((i%1000)%100)%10;
}
static int com(int i, int j) {
return (i * 10) + j;
}
static void productTest (int i, int m, int n) {
if(m * n == i) System.out.println(i + " = " + m + " * " + n);
}
public static void main(String[] args) {
long startTime=System.currentTimeMillis();
for(int i = 1001; i < 9999; i++) {
productTest(i, com(a(i), b(i)), com(c(i), d(i)));
productTest(i, com(a(i), b(i)), com(d(i), c(i)));
productTest(i, com(a(i), c(i)), com(b(i), d(i)));
productTest(i, com(a(i), c(i)), com(d(i), b(i)));
productTest(i, com(a(i), d(i)), com(b(i), c(i)));
productTest(i, com(a(i), d(i)), com(c(i), b(i)));
productTest(i, com(b(i), a(i)), com(c(i), d(i)));
productTest(i, com(b(i), a(i)), com(d(i), c(i)));
productTest(i, com(b(i), c(i)), com(d(i), a(i)));
productTest(i, com(b(i), d(i)), com(c(i), a(i)));
productTest(i, com(c(i), a(i)), com(d(i), b(i)));
productTest(i, com(c(i), b(i)), com(d(i), a(i)));
}
long endTime=System.currentTimeMillis();
System.out.println(" : "+(endTime - startTime)+"ms");
}
}/*output
1260 = 21 * 60
1395 = 15 * 93
1435 = 41 * 35
1530 = 51 * 30
1827 = 87 * 21
2187 = 27 * 81
6880 = 86 * 80
6880 = 80 * 86
: 54ms
*/