- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在尝试拆分一个大整数的数字。让我更具体一点。我正在使用斐波那契数列生成一个大整数,现在使用此算法我需要循环直到找到一个 BigInteger,其中前 9 位数字和后 9 位数字是泛数字。唯一的问题是我必须循环的数量是 300K(现在 BigInteger 将变得如此巨大)。
我试过将 BigInteger 转换成字符串,然后使用“substring(begin, end)”。但是,那太慢了,仅仅做 100K 个索引就花了将近 28 分钟。
对此有一个数学解决方案,但我不完全确定它是什么,如果有人能引导我朝着正确的方向前进,我将不胜感激。注意:我不是直接要求答案,只是朝着找到正确答案迈出的一步。
这是我的代码,以防你想知道:
import java.math.BigInteger;
public class Main {
public static void main(String...strings)
{
long timeStart = System.currentTimeMillis();
fib(300_000);
long timeEnd = System.currentTimeMillis();
System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
}
public static BigInteger fib(int n)
{
BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);
for (int i = 0; i < n; i++)
{
BigInteger savePrev1 = prev1;
prev1 = prev2;
prev2 = savePrev1.add(prev2);
}
return prev1;
}
static BigInteger[] pows = new BigInteger[16];
static {
for (int i = 0; i < 16; i++) {
pows[i] = BigInteger.TEN.pow(i);
}
}
static boolean isPanDigital(BigInteger n) {
if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
return false;
}
boolean[] foundDigits = new boolean[9];
boolean isPanDigital = true;
for (int i = 1; i <= 9; i++) {
BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
for (int j = 0; j < foundDigits.length; j++) {
if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
foundDigits[j] = true;
}
}
}
for (int i = 0; i < 9; i++) {
isPanDigital = isPanDigital && foundDigits[i];
}
return isPanDigital;
}
}
已更新,设法弄清楚如何生成前 9 位数字(而且它似乎并不太慢)。但是,我在生成最后 9 位数字时遇到了问题。
import java.math.BigInteger;
public class Main {
public static void main(String...strings)
{
long timeStart = System.currentTimeMillis();
fib(300_000);
long timeEnd = System.currentTimeMillis();
System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
}
public static BigInteger fib(int n)
{
BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);
for (int i = 0; i < n; i++)
{
if (prev1.toString().length() > 19)
{
String leading9Digits = leading9Digits(prev1);
if (isPanDigital(BigInteger.valueOf(Integer.valueOf(leading9Digits))))
{
System.out.println("Solved at index: " + i);
break;
}
}
BigInteger savePrev1 = prev1;
prev1 = prev2;
prev2 = savePrev1.add(prev2);
}
return prev1;
}
public static String leading9Digits(BigInteger x) {
int log10 = (x.bitLength() - 1) * 3 / 10;
x = x.divide(BigInteger.TEN.pow(Math.max(log10 + 1 - 9, 0)));
return x.toString().substring(0, 9);
}
static BigInteger[] pows = new BigInteger[16];
static {
for (int i = 0; i < 16; i++) {
pows[i] = BigInteger.TEN.pow(i);
}
}
static boolean isPanDigital(BigInteger n) {
if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
return false;
}
boolean[] foundDigits = new boolean[9];
boolean isPanDigital = true;
for (int i = 1; i <= 9; i++) {
BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
for (int j = 0; j < foundDigits.length; j++) {
if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
foundDigits[j] = true;
}
}
}
for (int i = 0; i < 9; i++) {
isPanDigital = isPanDigital && foundDigits[i];
}
return isPanDigital;
}
}
最佳答案
好的,我对你的代码做了一些优化。
leading9Digits
方法不应返回String
,而应返回一个数字。如果愿意,允许代码的其他部分将其转换为字符串。BigInteger.pow()
是一种浪费。您可以预先计算所有这些 10 的幂并将它们存储在一个数组中。boolean
数组中的单元格递增两次,那么它就不是 pandigital。此外,您可以在 0
时提前退出。 trailing9digits
使用 mod 1000000000 很容易请注意,我尝试使用 String
而不是余数,结果结果大致相同。我将两者都包含在您的代码中。
最后,正确答案不在前 300,000 个中;大约是329,000。在我的机器上运行大约需要 29 秒。
import java.math.BigInteger;
public class Main {
private static final BigInteger NINE = BigInteger.valueOf(9);
private static final BigInteger BILLION = BigInteger.valueOf(1000000000);
private static final double log10_2 = Math.log10(2);
private static final double CORRECTION = 9d;
private static final int ARRAY_SIZE = 131072;
static BigInteger[] pows = new BigInteger[ARRAY_SIZE];
static {
pows[0] = BigInteger.ONE;
for (int i = 1; i < ARRAY_SIZE; i++) {
pows[i] = pows[i - 1].multiply(BigInteger.TEN);
}
}
public static void main(String... strings) {
long timeStart = System.currentTimeMillis();
fib(500_000);
long timeEnd = System.currentTimeMillis();
System.out.println("Finished processing, time: "
+ (timeEnd - timeStart) + " milliseconds.");
}
public static BigInteger fib(int n) {
BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);
for (int i = 0; i < n; i++) {
if (prev1.bitLength() > 30) {
if (isDualPanDigital(prev1)) {
System.out.println("Solved at index: " + i);
break;
}
}
BigInteger savePrev1 = prev1;
prev1 = prev2;
prev2 = savePrev1.add(prev2);
}
return prev1;
}
public static BigInteger leading9Digits(BigInteger x) {
int dividePower = (int) (x.bitLength() * log10_2 - CORRECTION);
BigInteger y = x.divide(pows[dividePower]);
if (y.compareTo(BILLION) != -1) y = y.divide(BigInteger.TEN);
return y;
}
public static BigInteger trailing9Digits(BigInteger x) {
return x.mod(BILLION);
}
static boolean isDualPanDigital(BigInteger n) {
boolean leading = isPanDigital(leading9Digits(n));
boolean trailing = isPanDigital(trailing9Digits(n));
if (leading && trailing) {
System.out.format("leadingDigits: %s, trailingDigits: %s%n",
leading9Digits(n), trailing9Digits(n));
}
return leading && trailing;
}
static boolean isPanDigital(BigInteger n) {
if (!n.remainder(NINE).equals(BigInteger.ZERO)) {
return false;
}
return isPanDigitalString(n);
}
private static boolean isPanDigitalMath(BigInteger n) {
boolean[] foundDigits = new boolean[10];
for (int i = 1; i <= 9; i++) {
int digit = n.remainder(pows[i]).divide(pows[i - 1]).intValue();
if (digit == 0)
return false;
if (foundDigits[digit - 1])
return false;
else
foundDigits[digit - 1] = true;
}
return true;
}
private static boolean isPanDigitalString(BigInteger n) {
boolean[] foundDigits = new boolean[9];
String s = n.toString();
if (s.length() < 9) {
return false;
}
for (int i = 0; i < 9; i++) {
int digit = s.charAt(i) - '1';
if (digit == -1 || foundDigits[digit])
return false;
foundDigits[digit] = true;
}
return true;
}
}
关于java - 拆分 BigIntegers 数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15216777/
fiddle :http://jsfiddle.net/rtucgv74/ 我正在尝试将第一个字符与 3 位数字匹配。所以下面的代码应该提醒f234。但反而返回 null ? 源代码: var reg
复制代码 代码如下: Dim strOk,strNo strOk = "12312321$12
我想找 {a number} / { a number } / {a string}模式。我可以得到number / number工作,但是当我添加 / string它不是。 我试图找到的例子: 15
我,我正在做一个模式正则表达式来检查字符串是否是: 数字.数字.数字,如下所示: 1.1.1 0.20.2 58.55541.5221 在java中我使用这个: private static Patt
我有一个字符串,我需要检查它是否在字符串的末尾包含一个数字/数字,并且需要将该数字/数字递增到字符串末尾 +1 我会得到下面的字符串 string2 = suppose_name_1 string3
我正在寻找一个正则表达式 (数字/数字),如(1/2) 数字必须是 1-3 位数字。我使用 Java。 我认为我的问题比正则表达式更深。我无法让这个工作 String s ="(1/15)";
谁能帮我理解为什么我在使用以下代码时会出现类型错误: function sumOfTwoNumbersInArray(a: [number, number]) { return a[0] +
我看到有些人过去也遇到过类似的问题,但他们似乎只是不同,所以解决方案也有所不同。所以这里是: 我正在尝试在 Google Apps 脚本中返回工作表的已知尺寸范围,如下所示: var myRange
我试图了解python中的正则表达式模块。我试图让我的程序从用户输入的一行文本中匹配以下模式: 8-13 之间的数字“/” 0-15 之间的数字 例如:8/2、11/13、10/9 等。 我想出的模式
简单地说,我当前正在开发的程序要求我拆分扫描仪输入(例如:2 个火腿和奶酪 5.5)。它应该读取杂货订单并将其分成三个数组。我应该使用 string.split 并能够将此输入分成三部分,而不管中间字
(number) & (-number) 是什么意思?我已经搜索过了,但无法找到含义 我想在 for 循环中使用 i & (-i),例如: for (i = 0; i 110000 .对于i没有高于
需要将图像ID设置为数字 var number = $(this).attr('rel'); number = parseInt(number); $('#carousel .slid
我有一个函数,我想确保它接受一个字符串,后跟一个数字。并且可选地,更多的字符串数字对。就像一个元组,但“无限”次: const fn = (...args: [string, number] | [s
我想复制“可用”输入数字的更改并将其添加或减去到“总计”中 如果此人将“可用”更改为“3”,则“总计”将变为“9”。 如果用户将“可用”更改为“5”,则“总计”将变为“11”。 $('#id1').b
我有一个与 R 中的断线相关的简单问题。 我正在尝试粘贴,但在获取(字符/数字)之间的断线时遇到问题。请注意,这些值包含在向量中(V1=81,V2=55,V3=25)我已经尝试过这段代码: cat(p
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的,无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它,visit the help center 。 已关
我在 Typescript 中收到以下错误: Argument of type 'number[]' is not assignable to parameter of type 'number' 我
在本教程中,您将通过示例了解JavaScript 数字。 在JavaScript中,数字是基本数据类型。例如, const a = 3; const b = 3.13; 与其他一些编程语言不同
我在 MDN Reintroduction to JavaScript 上阅读JavaScript 数字只是浮点精度类型,JavaScript 中没有整数。然而 JavaScript 有两个函数,pa
我们在 Excel 中管理库存。我知道这有点过时,但我们正在发展商业公司,我们所有的钱都被困在业务上,没有钱投资 IT。 所以我想知道我可以用Excel自动完成产品编号的方式进行编程吗? 这是一个产品
我是一名优秀的程序员,十分优秀!