今天在看《Java编程思想》的时候遇到求“吸血鬼数字”的问题。
吸血鬼数字是指位数为偶数的数字,可以由一对数字相乘而得到,这对数字各包含乘积的一半的数字,例如:1260=21*60,1827=21*87……,1260、1827这样的数字就叫做吸血鬼数字。以两个0结尾的数字不是吸血鬼数字。
我在网上看到了一个比较高效的算法(http://topic.csdn.net/u/20090123/10/8dc0c939-20ae-41f1-a7c1-d05b897b27c7.html):
import java.util.Arrays;
public class Vampire {
public static void main(String[] args) {
int count = 0;//4位的吸血鬼数字的个数
int product;//乘积
char[] pArray;//乘积的字符数组
char[] nArray;//数字的字符数组
int num = 0;//内层循环体的执行次数
for(int i = 11;i < 100;i++)
for(int j = 1000 / i + 1 > i ? 1000 / i + 1 : i;j < 100;j++) {//关键代码1
product = i * j;
if(product % 100 == 0 || (product - i - j) % 9 != 0) //关键代码2
continue;
num++;
pArray = String.valueOf(product).toCharArray();
nArray = (String.valueOf(i) + String.valueOf(j)).toCharArray();
Arrays.sort(pArray);
Arrays.sort(nArray);
if(Arrays.equals(pArray,nArray)) {
System.out.println(i + "*" + j + "=" + product);
count++;
}
}
System.out.println("共找到" + count + "组吸血鬼数字");
System.out.println("内层循环共执行" + num + "次");
}
}
代码解释:
关键代码1:j的初始值的设定。注意到i和j都是两位数,为避免重复,可设定j不小于i,又因为i和j的乘积大于1000,因此j应取1000/i + 1 与 i中的较大者。如此一来,相比直接设定i = 11,j = i要减少很多内层循环次数。
关键代码2:根据吸血鬼数字的定义,以两个0结尾的数字不是吸血鬼数字,因此如果乘积能被100整除,就被pass了,另外,假定任意一个4位数字A表示成1000*a + 100*b + 10*c + d的形式,那么如果这个数是吸血鬼数的话,那么它可以表示成两个两位数x,y的乘积的形式,即A = x * y。其中x、y可以表示成x = 10*a + b,y = 10*c + d或x = 10*a + c,y = 10*b + d……之类的形式。
以x = 10*a + b,y = 10*c + d为例,A - x - y = 990*a + 99*b = 9*(110*a + 11*b),能被9整除
x、y的其他形式也同样能被9整除。
程序的执行结果如下:
15*93=1395
21*60=1260
21*87=1827
27*81=2187
30*51=1530
35*41=1435
80*86=6880
共找到7组吸血鬼数字
内层循环共执行243次
如果去掉关键代码2处的判断,则内层循环将会执行3337次,程序效率的提升非常显著。不过这一点非常不容易想到,特做此笔记,加深记忆。
分享到:
相关推荐
4位吸血鬼数字java原码
吸血鬼数字是指位数为偶数的数字,可以由一对数字相乘而得到,而这对数字各包含乘积的一半位数的数字,其中从最初的数字中选取的数字可以任意排序。以两个0结尾的数字是不允许的,例如,下列数字都是“吸血鬼”数字...
Java实现吸血鬼数字的3种算法,3种算法的效率各自的比较
只修改main 的for就可以得到一下结果,运行时间有点长,应该稍微优化一下 配合我发送的 http://download.csdn.net/source/530288 修改使用 public static void main(String[] args){ for(int x=1;...
吸血鬼数字是指位数为偶数的数字,可以由一对数字相乘得到,而这对数字各包含乘积的一半位数的数字,其中从最初的数字中选取的数字可以任意排序。以2个0结尾的数字是不允许的,例如,下列数字都是吸血鬼数字: 1260 ...
THINK IN JAVA上的课后题,只是寻找4位数的。
今天小编就为大家分享一篇关于4位吸血鬼数字的java实现思路与实例讲解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
可爱的吸血鬼数。可爱的吸血鬼数。可爱的吸血鬼数。可爱的吸血鬼数。
关于吸血鬼数字算法问题,我也是读《java编程思想》中遇到的,觉得很有意思。于是,就去做了做。但因为我的粗心,读题的时候忽略了点问题,所以导致我的思路出现了岔口!(当时的思路就是想着把一个4位数拆分成两个2...
赫尔辛一个POSIX吸血鬼数字生成器,内置了heapsort。该项目的重点是性能,代码可读性和可移植性。 在helsing / configuration.h中,您可以轻松设置线程数,选择算法实现并进行调整,调整详细程度并启用从检查点恢复...
##挑战:给定一个数字,检测并显示介于0和该给定数字之间的所有吸血鬼数字吸血鬼编号-Fang1 * Fang2 规则1:吸血鬼编号必须为偶数位数规则2:每个毒牙的位数必须是吸血鬼数的一半规则3:吸血鬼编号中的所有数字必须...
有多种关于吸血鬼数字的算法 ! 输出结果为: 1260 = 21 * 60 1395 = 15 * 93 1435 = 41 * 35 1530 = 51 * 30 1827 = 87 * 21 2187 = 27 * 81 6880 = 86 * 80 6880 = 80 * 86 以上仅供参考:
自己用java写的一个吸血鬼算法,希望大家给点意见!
本程序用java实现了吸血鬼数字的功能,欢迎大家下载
C#数字图像处理算法典型实例源代码
控制项行动钥匙移动W A S D ,箭头键或数字键盘2 4 6 8 (按住Shift键可将其转到适当的位置) 相互作用E , Z或数字键盘5 退出游戏Esc键静音中号切换调试覆盖\学分我自己创建了该项目中使用的大多数资产。...
Q1:该新型数字控制技术具体优势是什么? A1:优势主要是看用在什么功率上。如果是在低功率上,优势主要是在它是用数字方式来实现... A3:因其耗能特性而被我们称之为“能源吸血鬼”的线性电源,使用了与当前创新
学习JS :check_mark_button: 学习JS ... 与吸血鬼主题颜色相同 :books: IMC项目 国际货币基金组织 :books: 项目DateArraySwitch 日期(小时()) :books: 项目节点列表 Altera CSS de cada