4桁のヴァンパイア番号をすべて見つける問題を解いています。
吸血鬼の数v=x*y は、「n/2」桁の数字のペアを乗算することによって形成される「n」桁の偶数を持つ数字として定義されます (数字は元の数字から任意の順序で取得されます)xそして一緒に。v がヴァンパイア ナンバーの場合、x&y と はその「牙」と呼ばれます。
ヴァンパイア番号の例は次のとおりです。
1. 1260=21*60
2. 1395=15*93
3. 1530=30*51
私はブルート フォース アルゴリズムを試して、与えられた数字の異なる数字を結合し、それらを掛け合わせました。しかし、この方法は非常に非効率的で、多くの時間がかかります。
この問題に対するより効率的なアルゴリズムの解決策はありますか?
可能性のあるすべての牙 (100 x 100 = 10000 の可能性) を反復処理し、それらの製品が牙と同じ数字を持っているかどうかを確認します。
起動する無料のバブルソートを備えた、さらに別のブルートフォース（C）バージョン...
#include <stdio.h>
static inline void bubsort(int *p)
{ while (1)
{ int s = 0;
for (int i = 0; i < 3; ++i)
if (p[i] > p[i + 1])
{ s = 1;
int t = p[i]; p[i] = p[i + 1]; p[i + 1] = t;
}
if (!s) break;
}
}
int main()
{ for (int i = 10; i < 100; ++i)
for (int j = i; j < 100; ++j)
{ int p = i * j;
if (p < 1000) continue;
int xd[4];
xd[0] = i % 10;
xd[1] = i / 10;
xd[2] = j % 10;
xd[3] = j / 10;
bubsort(xd);
int x = xd[0] + xd[1] * 10 + xd[2] * 100 + xd[3] * 1000;
int yd[4];
yd[0] = p % 10;
yd[1] = (p / 10) % 10;
yd[2] = (p / 100) % 10;
yd[3] = (p / 1000);
bubsort(yd);
int y = yd[0] + yd[1] * 10 + yd[2] * 100 + yd[3] * 1000;
if (x == y)
printf("%2d * %2d = %4d\n", i, j, p);
}
return 0;
}
ほとんど瞬時に実行されます。変数名はあまり説明的ではありませんが、かなり明白なはずです...
基本的な考え方は、2 つの潜在的な牙から始めて、それらを数字に分解し、簡単に比較できるように数字を並べ替えることです。次に、積についても同じことを行います - 数字に分解して並べ替えます。次に、並べ替えられた数字から 2 つの整数を再構成し、それらが等しい場合は一致します。
考えられる改善点: 1)実行する必要を避ける代わりにから開始jする、2) バブル ソートの代わりに挿入ソートを使用する (しかし、これら 2 つの余分なスワップに誰が気付くでしょうか?)、3) 実際の実装を使用する、4) 配列を直接比較するそれらから合成整数を構築するのではなく。ただし、コモドール64などで実行しない限り、これらのいずれかが測定可能な違いをもたらすかどうかはわかりません...1000 / iiif (p < 1000) ...swap()
編集: 好奇心から、私はこのバージョンを採用し、4 桁、6 桁、8 桁のケースで動作するようにもう少し一般化しました。大幅な最適化を行わなくても、8 桁の吸血鬼の番号をすべて 10 秒未満で見つけることができます.. .
これは醜いハック (ブルート フォース、順列の手動チェック、安全でないバッファ操作、複製の生成など) ですが、仕事はします。あなたの新しい練習はそれを改善することです:P
ウィキペディアによると、吸血鬼には 4 桁の数字が 7 つあります。完全なコードはそれらすべてを検出し、一部の重複も検出しました。
編集2： これは、を使用して結果を一意にする（したがって、重複を回避する）C++バージョンstd::mapです（特定の吸血鬼番号の最後の発生をその要因とともに保存します）。また、因数の少なくとも 1 つが で終わってはならないという基準も満たしています0。このテストは 6 桁の吸血鬼の番号を探し、ウィキペディアの記述によると、正確に 148 個を検出します。
元のコード:
#include <stdio.h>
void getdigits(char buf[], int n)
{
while (n) {
*buf++ = n % 10;
n /= 10;
}
}
int is_vampire(const char n[4], const char i[2], const char j[2])
{
/* maybe a bit faster if unrolled manually */
if (i[0] == n[0]
&& i[1] == n[1]
&& j[0] == n[2]
&& j[1] == n[3])
return 1;
if (i[0] == n[1]
&& i[1] == n[0]
&& j[0] == n[2]
&& j[1] == n[3])
return 1;
if (i[0] == n[0]
&& i[1] == n[1]
&& j[0] == n[3]
&& j[1] == n[2])
return 1;
if (i[0] == n[1]
&& i[1] == n[0]
&& j[0] == n[3]
&& j[1] == n[2])
return 1;
// et cetera, the following 20 repetitions are redacted for clarity
// (this really should be a loop, shouldn't it?)
return 0;
}
int main()
{
for (int i = 10; i < 100; i++) {
for (int j = 10; j < 100; j++) {
int n = i * j;
if (n < 1000)
continue;
char ndigits[4];
getdigits(ndigits, n);
char idigits[2];
char jdigits[2];
getdigits(idigits, i);
getdigits(jdigits, j);
if (is_vampire(ndigits, idigits, jdigits))
printf("%d * %d = %d\n", i, j, n);
}
}
return 0;
}
力ずくでそう簡単に諦めたりはしなかったでしょう。実行しなければならない 1000 から 9999 までの一連の数字があります。セットをいくつかのサブセットに分割し、スレッドを起動して各サブセットを処理します。
各数値のさまざまな組み合わせを考え出す作業をさらに分割することができます。IIRC 私の個別の数学では、試行する数値ごとに 4*3*2 または 24 の組み合わせがあります。
生産者/消費者のアプローチは価値があるかもしれません。
すべての値を見つけるためにこれを一度だけ行う必要があり、後でそれらをキャッシュすることができるので、反復は私にはうまくいくようです。約 1.5 秒かかる Python (3) バージョン:
# just some setup
from itertools import product, permutations
dtoi = lambda *digits: int(''.join(str(digit) for digit in digits))
gen = ((dtoi(*digits), digits) for digits in product(range(10), repeat=4) if digits[0] != 0)
l = []
for val, digits in gen:
for check1, check2 in ((dtoi(*order[:2]), dtoi(*order[2:])) for order in permutations(digits) if order[0] > 0 and order[2] > 0):
if check1 * check2 == val:
l.append(val)
break
print(l)
どちらがあなたに与えるでしょう[1260, 1395, 1435, 1530, 1827, 2187, 6880]
1260 1395 1435 1530 1827 2187 6880 はヴァンパイア
私はプログラミングは初めてです...しかし、4桁の吸血鬼の数字をすべて見つけるには、12の組み合わせしかありません。私の悪い答えは次のとおりです。
public class VampNo {
public static void main(String[] args) {
for(int i = 1000; i < 10000; i++) {
int a = i/1000;
int b = i/100%10;
int c = i/10%10;
int d = i%10;
if((a * 10 + b) * (c * 10 + d) == i || (b * 10 + a) * (d * 10 + c) == i ||
(a * 10 + d) * (b * 10 + c) == i || (d * 10 + a) * (c * 10 + b) == i ||
(a * 10 + c) * (b * 10 + d) == i || (c * 10 + a) * (d * 10 + b) == i ||
(a * 10 + b) * (d * 10 + c) == i || (b * 10 + a) * (c * 10 + d) == i ||
(b * 10 + c) * (d * 10 + a) == i || (c * 10 + b) * (a * 10 + d) == i ||
(a * 10 + c) * (d * 10 + b) == i || (c * 10 + a) * (b * 10 + d) == i)
System.out.println(i + " is vampire");
}
}
}
ここでの主なタスクは、If() ブロックのブール式を単純化することです
この python コードは非常に高速に実行されます (O(n2))
result = []
for i in range(10,100):
for j in range(10, 100):
list1 = []
list2 = []
k = i * j
if k < 1000 or k > 10000:
continue
else:
for item in str(i):
list1.append(item)
for item in str(j):
list1.append(item)
for item in str(k):
list2.append(item)
flag = 1
for each in list1:
if each not in list2:
flag = 0
else:
list2.remove(each)
for each in list2:
if each not in list1:
flag = 0
if flag == 1:
if k not in result:
result.append(k)
for each in result:
print(each)
特に抽象的な洞察に頼らずに可能な限り少ないテストを実行するには、おそらく牙を繰り返して、明らかに無意味な候補を選別する必要があるようです。
たとえば、x*y == y*x検索スペースの約半分は、y > x. 最大の 2 桁の牙が 99 である場合、4 桁の数を作成できる最小の牙は 11 であるため、11 未満で開始しないでください。
編集：
OK、私が考えたすべてをミックスに投入します (主要なソリューションに対してはばかげているように見えますが)。
for (x = 11; x < 100; x++)
{
/* start y either at x, or if x is too small then 1000 / x */
for (y = (x * x < 1000 ? 1000 / x : x); y < 100; y++)
{
int p = x * y;
/* if sum of digits in product is != sum of digits in x+y, then skip */
if ((p - (x + y)) % 9 != 0)
continue;
if (is_vampire(p, x, y))
printf("%d\n", p);
}
}
誰もヒストグラムを使用していないので、テストはまだ:
int is_vampire(int p, int x, int y)
{
int h[10] = { 0 };
int i;
for (i = 0; i < 4; i++)
{
h[p % 10]++;
p /= 10;
}
for (i = 0; i < 2; i++)
{
h[x % 10]--;
h[y % 10]--;
x /= 10;
y /= 10;
}
for (i = 0; i < 10; i++)
if (h[i] != 0)
return 0;
return 1;
}
私が試みるアプローチは、[1000, 9999] の各数値をループし、その数字の順列 (途中で分割) を乗算してそれを作成するかどうかをテストすることです。
これには (9999 - 1000) * 24 = 215,976 のテストが必要であり、最新のマシンでは許容できる速さで実行されるはずです。
私は間違いなく数字を別々に保存するので、単一の整数から数字を抽出するために一連の除算のようなことをする必要がなくなります。
整数の加算と乗算 (および場合によってはキャリーする除算) のみを行うようにコードを作成すると、かなり高速になるはずです。「明らかに」機能しない 2 桁のペアをスキップすることで、速度をさらに向上させることができます。たとえば、先頭にゼロが付いているペア (1 桁の数字と 2 桁の数字で生成できる最大の積は 9 * 99、または 891)。
また、このアプローチは非常に並列であることに注意してください ( http://en.wikipedia.org/wiki/Embarrassingly_parallel )。そのため、さらに高速化する必要がある場合は、別のスレッドで数値をテストすることを検討する必要があります。
<?php
for ($i = 10; $i <= 99; $j++) {
// Extract digits
$digits = str_split($i);
// Loop through 2nd number
for ($j = 10; $j <= 99; $j++) {
// Extract digits
$j_digits = str_split($j);
$digits[2] = $j_digits[0];
$digits[3] = $j_digits[1];
$product = $i * $j;
$product_digits = str_split($product);
// check if fangs
$inc = 0;
while (in_array($digits[$inc], $product_digits)) {
// Remove digit from product table
/// So AAAA -> doesnt match ABCD
unset($product_digits[$array_serach($digits[$inc], $product_digits)]);
$inc++;
// If reached 4 -> vampire number
if ($inc == 4) {
$vampire[] = $product;
break;
}
}
}
}
// Print results
print_r($vampire);
?>
PHP では 1 秒もかかりませんでした。8,100 回の計算を実行する必要があることさえわかりませんでした... コンピューターは高速です!
結果：
4桁すべてに加えて、一部が繰り返されます。データをさらに処理し、重複を削除できます。