溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這個問題來源于Java編程思想一書，所謂“吸血鬼數(shù)字”就是指位數(shù)為偶數(shù)的數(shù)字，可以由一對數(shù)字相乘而得到，而這對數(shù)字各包含乘積的一半位數(shù)字，其中從偶數(shù)位數(shù)字中選取的數(shù)字可以任意排列。例如：
1260=21*60，1827=21*87，2187=27*81……
先列出結果：
一共7個：
1260=21*60，1395=15*93，1435=41*35，1530=51*30，1827=87*21，2187=27*81，6880=86*80
第一種思路對所有的4位數(shù)進行窮舉，假設這個4位數(shù)是abcd，可以表示為1000a+100b+10c+d。那么由這個4位數(shù)中抽出的2位數(shù)的組合有如下12種（abcd分別為0-9的數(shù)字，能作為X、Y的十位上的數(shù)字必為1-9）：
這12種組合中，有沒有可能其中某些情況是不可能滿足1000a+100b+10c+d=X*Y的？如果能直接去掉就能減少不必要的計算。
假設①可能找出匹配的吸血鬼數(shù)字，那么存在等式：(10*a + b)*(10*c + d) = 1000a+100b+10c+d = 100*(10*a + b) + 10*c + d
<=>(10*a + b)*(10*c + d - 100) = 10*c + d
因為左邊(10*c + d - 100)是負數(shù)，而右邊為正數(shù)，不可能相等；又因為在上式中c/d具有互換性，故不可能通過①②找到吸血鬼數(shù)。
假設③可能找出匹配的吸血鬼數(shù)字，那么存在等式：(10*a + c)*(10*b + d) = 1000a+100b+10c+d
<=>100*a*b + 10*(a*d+b*c) + cd = 100*a*b - 100*a*b + 1000*a + 100*b + 10*c +d = 100*a*b + 10*[10*a*(10-b) + 10*b] + 10*c +d
<=>10*(a*d+b*c) + cd = 10*[10*a*(10-b) + 10*b] + 10*c +d
因為兩邊的子項都有a*d<10*a*(10-b)，b*c<10*b，cd<10*c +d，所以右邊恒大于左邊；又因為在上式中b/d具有互換性，故不可能通過③④找到吸血鬼數(shù)。
假設10*b + c的組合⑤能找到吸血鬼數(shù)字，那么存在等式：(10*a + d)*(10*b + c) = 1000*a + 10*(10*b + c) + d
<=>(10*b + c)*(10*a + d - 10) = 1000*a + d = 100*(10a + d/100)
因為左邊(10*b + c)<100，(10*a + d - 10)<(10a + d/100)，所以右邊恒大于左邊；又因為在上式中a/d具有互換性，故不可能通過⑤⑨找到吸血鬼數(shù)。
另外4位數(shù)中包含兩個及以上0的是不可能為吸血鬼數(shù)字，原因：假如包含2個零，則只能拆出10*a和10*b形式，乘積的結果后兩位必為ZZ00的形式；于是等式就退化為a*b =10*a + b，變換為b=10*a/(a-1) >10,而b不可能大于10。
實現(xiàn)代碼如下：
/**
* VampireNumbers<br />
* 求所有的4位吸血鬼數(shù)
* @author South Park
*/
public final class VampireNumbers {
private static final StringBuilder outputStr = new StringBuilder(14);
private static final String equalSign = " = ";
private static final String multiSign = " * ";
/**
* 如果這兩個2位數(shù)的乘積等于原來的數(shù)則成功，打印該數(shù)字
* @param i 4位數(shù)的值
* @param m 其中一個2位數(shù)
* @param n 另外一個2位數(shù)
*/
private static final void productTest (final int i, final int m, final int n) {
// 如果滿足條件，就輸出
if(m * n == i) {
outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);
System.out.println(outputStr.toString());
outputStr.delete(0, 14);
}
}
/**
* 從1011開始到9998，循環(huán)嘗試每個4位數(shù)的各種分拆組合
* @param args
*/
public static void main(String[] args) {
int count = 0;// 計數(shù)循環(huán)次數(shù)
long startTime = System.nanoTime();
// 分別表示千百十各位
int a,b,c,d;
// 4位數(shù)中含零的個數(shù)
int zeroCount = 0;
for(short i = 1011; i < 9999; i++) {
zeroCount = 0;
String value = ""+i;
// 獲取各位中的值(0-9)
a = value.charAt(0) - 48;//千位
b = value.charAt(1) - 48;//百位
c = value.charAt(2) - 48;//十位
d = value.charAt(3) - 48;//個位
if (b == 0)
zeroCount++;
if (c == 0)
zeroCount++;
if (d == 0)
zeroCount++;
// 數(shù)字中含有2個以上的零排除
if (zeroCount >= 2) {
continue;
}
count++;
//productTest(i, 10*a + b, 10*c + d);
//productTest(i, 10*a + b, 10*d + c);
//productTest(i, 10*a + c, 10*b + d);
//productTest(i, 10*a + c, 10*d + b);
//productTest(i, 10*a + d, 10*b + c);
productTest(i, 10*a + d, 10*c + b);
productTest(i, 10*b + a, 10*c + d);
productTest(i, 10*b + a, 10*d + c);
//productTest(i, 10*b + c, 10*d + a);
productTest(i, 10*b + d, 10*c + a);
productTest(i, 10*c + a, 10*d + b);
productTest(i, 10*c + b, 10*d + a);
}
System.out.println(System.nanoTime() - startTime);
// 輸出循環(huán)次數(shù)
System.out.println("loop count:" + count);
}
}
輸出結果：
1260 = 21 * 60
1395 = 15 * 93
1435 = 41 * 35
1530 = 51 * 30
1827 = 87 * 21
2187 = 27 * 81
6880 = 86 * 80
6880 = 80 * 86
12360961
loop count:8747
第二種方式是對分解后的一對XY入手，從10到99進行雙重循環(huán)窮舉，由于乘積結果必須是4位數(shù)，也就是范圍為1000到9999，故可對第二層循環(huán)進行范圍限定，減少循環(huán)次數(shù)。從結果來看，第二種方式的循環(huán)次數(shù)較少，時間也更少。
對于4位吸血鬼數(shù)，必有X*Y-X-Y為9的倍數(shù)，因為X*Y-X-Y只有下列6種結果：
代碼實現(xiàn)：
import java.util.Arrays;
/**
* VampireNumbers2<br />
* 求所有的4位吸血鬼數(shù)
* @author South Park
*/
public final class VampireNumbers2 {
private static final StringBuilder outputStr = new StringBuilder(14);
private static final String equalSign = " = ";
private static final String multiSign = " * ";
/**
* 如果這兩個2位數(shù)的乘積等于原來的數(shù)則成功，打印該數(shù)字
* @param i 4位數(shù)的值
* @param m 其中一個2位數(shù)
* @param n 另外一個2位數(shù)
*/
private static final void printVN (final int i, final int m, final int n) {
outputStr.append(i).append(equalSign).append(m).append(multiSign).append(n);
System.out.println(outputStr.toString());
outputStr.delete(0, 14);
}
/**
* 從11開始到99，雙重循環(huán)嘗試每種組合的4位數(shù)乘積結果是否剛好包含原來兩個2位數(shù)的數(shù)字
* @param args
*/
public static void main(String[] arg) {
int count = 0;// 計數(shù)循環(huán)次數(shù)
long startTime = System.nanoTime();
String vnValueStr = "";
String multiValueStr = "";
char[] vnValueArr = new char[4];
char[] multiValueArr = new char[4];
int from;
int to;
int vampireNumbers;
// 雙重循環(huán)窮舉
for (int i = 11; i < 100; i++) {
// 通過對from和to的計算，縮小第二重循環(huán)的次數(shù)；j=i+1避免重復
from = Math.max(1000 / i + 1, i + 1);
to = Math.min(10000 / i, 100);
for (int j = from; j < to; j++) {
count++;
vampireNumbers = i * j;
// 過濾掉非吸血鬼數(shù)
if ((vampireNumbers - i - j) % 9 != 0) {
continue;
}
vnValueStr = "" + vampireNumbers;
vnValueArr[0] = vnValueStr.charAt(0);
vnValueArr[1] = vnValueStr.charAt(1);
vnValueArr[2] = vnValueStr.charAt(2);
vnValueArr[3] = vnValueStr.charAt(3);
multiValueStr = "" + i + j;
multiValueArr[0] = multiValueStr.charAt(0);
multiValueArr[1] = multiValueStr.charAt(1);
multiValueArr[2] = multiValueStr.charAt(2);
multiValueArr[3] = multiValueStr.charAt(3);
Arrays.sort(vnValueArr);
Arrays.sort(multiValueArr);
if (Arrays.equals(vnValueArr, multiValueArr)) {// 排序后比較,為真則找到一個吸血鬼數(shù)
printVN(vampireNumbers, i, j);
}
}
}
System.out.println(System.nanoTime() - startTime);
// 輸出循環(huán)次數(shù)
System.out.println(count);
}
}
輸出結果：
1395 = 15 * 93
1260 = 21 * 60
1827 = 21 * 87
2187 = 27 * 81
1530 = 30 * 51
1435 = 35 * 41
6880 = 80 * 86
3024115
3269
由于沒有找到吸血鬼數(shù)的產(chǎn)生機理，所以只好用窮舉法。在這里提高性能的方法主要是減少循環(huán)次數(shù)，減少不必要的計算。
總結
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對億速云的支持。如果你想了解更多相關內(nèi)容請查看下面相關鏈接
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內(nèi)容。
