Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 57
У меня получилось за 0.7 секунды на P4 3Ггц на языке TCL.
clipie.org/view.php? key=5ZPF4SCV7Q1M32UJ6GE8
clipie.org/view.php? key=5ZPF4SCV7Q1M32UJ6GE8
Вот. Быдлокодинг, конечно, но все таки.
Ответ:
28 * 157 = 4396
18 * 297 = 5346
12 * 483 = 5796
4 * 1738 = 6952
39 * 186 = 7254
48 * 159 = 7632
4 * 1963 = 7852
45228
Правильно?
<?
set_time_limit(0);
$n = 0;
for ($i = 999; $i < 9999; $i++) {
for ($a = 1; $a <= $i; $a++) {
$good = false;
$b = $i / $a;
if (round($b) == $b) {
$s = "$a$b$i";
if (strlen($s) == 9) {
$good = true;
for ($x = 1; $x < 10; $x++) {
if (strpos($s, "$x") === false) {
$good = false;
break;
}
}
if ($good) {
$n += $i;
print "$a * $b = $i
";
break;
}
}
}
}
}
print $n;
?>
Ответ:
28 * 157 = 4396
18 * 297 = 5346
12 * 483 = 5796
4 * 1738 = 6952
39 * 186 = 7254
48 * 159 = 7632
4 * 1963 = 7852
45228
Правильно?
30424
<?
$found = array();
for($i=11; $i<=99; $i++){
if($i{1} != '0'){
for($j=111; $j<=999; $j++){
if(($j{1} != '0') && ($j{2} != '0')){
$n = $i*$j;
if($n <= 9999){
$cnt = count(array_flip(preg_split('//', "0".$n.$i.$j, -1, PREG_SPLIT_NO_EMPTY)));
if($cnt == 10){
$found[$n]++;
}
}
}
}
}
}
echo array_sum(array_keys($found));
?>
0.2c на P4 core2Duo 2.4GHz
Банальное решение с банальным отсечением занимает 0.4 с на AMD Turion 64 X2 2.0 GHz.
s = {}
check = lambda i, j: i*j < 10000 and i*j > 1000 and \
"".join(sorted(str(i)+str(j)+str(i*j))) == "123456789"
for i in xrange(1, 9):
for j in xrange(1, 9999):
if check(i, j):
s[i*j] = i, j
for i in xrange(11, 99):
for j in xrange(11, 999):
if check(i, j):
s[i*j] = i, j
print "\n".join(["%i x %i = %i" % (s[a][0], s[a][1], a) for a in s])
print "Total:", sum(s.keys())
27 x 198 = 5346 42 x 138 = 5796 4 x 1738 = 6952 28 x 157 = 4396 4 x 1963 = 7852 48 x 159 = 7632 39 x 186 = 7254 Total: 45228
14.8 за 100 итераций на Intel E6550. Расход памяти только для хранения суммы. =)
from math import sqrt
base, summ = set("123456789"), 0
for i in xrange(1234, 9877):
if len( set( str(i) ) ) == 4:
for j in xrange(2, int(sqrt( i ))):
if i % j == 0 and set("%s%s%s" % (i ,j, i/j)) == base:
summ += i
break
print summ
Если считать простом, как доска, перебором, то получается вот так:
4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
summ: 56370
53844 ms
4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
summ: 56370
53844 ms
>>> def do():
prods = []
for n in range(1, 10000):
if len(str(n))==len(set(str(n))):
for k in range(2, n**.5+1):
if len(str(k))==len(set(str(k))) and n%k==0 and len(set(''.join(map(str,(n,k,n/k))).replace('0','')))==9:
print k,'*',n/k,'=',n
prods.append(n)
print sum(set(prods))
>>> do()
28 * 157 = 4396
18 * 297 = 5346
27 * 198 = 5346
12 * 483 = 5796
42 * 138 = 5796
4 * 1738 = 6952
39 * 186 = 7254
48 * 159 = 7632
4 * 1963 = 7852
45228
Ну, разбавлю поток скриптовых решений :) Вот, немного хакерское решение (на CeleronM 540@1.8ГГц с 512DDR@266МГц работает за 0,013 секунд. Работает быстро, потому как использует битовые маски для определения «правильности» числа + небольшой отсев.
#include <stdio.h>Как видно, numtomask тоже можно ускорить.
#include <math.h>
#include <time.h>
int numtomask(int n)
{
int ans=0;
{
while(n)
{
ans+=1<<(n%10);
n/=10;
}
}
return ans;
}
int bitcount(int n) {
/* MIT HAKMEM Count
works for 32-bit numbers only
fix last line for 64-bit numbers */
int tmp;
tmp = n — ((n >> 1) & 033333333333)
— ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
int main ()
{
int magic_number=0;
clock_t start, finish;
start=clock();
for (int a=1234; a<=9876; a++)
{
bool find=false;
int i=(int)sqrt(float(a)), d1=numtomask(a);
if (bitcount(d1) != 4)
continue; // coz it isn't abcd-number
for (; i>=1 &&! find; i--)
if (a%i==0)
{
int d4 = d1 ^ numtomask(a/i) ^ numtomask(i);
if (1022 == d4) // ..1111111110 in bin
{
magic_number+=a;
find=true;
}
}
}
finish=clock();
printf(«%i\n», magic_number);
printf( «%2.7f seconds\n», (double)(finish — start) / CLOCKS_PER_SEC);
return 0;
}
для пятизначного результата
Ну наконец то! Давно жду, когда же появится решение на статическом, компилируемом языке. Да, конечно по скорости нам не тягаться, оптимизация моего решения при помощи ваших масок дала прирост всего в 1-2 секунды на 100 итераций, тут уж се ля ви даже не в масках дело. =)
Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
Незначительное ускорение даст тот факт, что a не оканчивается на 5.
Думаю, что нет. По сути, все алгоритмы, которые здесь представленны — брут форс. Если замутить генерацию перестановок, то можно выиграть на проверках, но это тоже перебор и не учитывает специфику задачи. Это задание, как школьные задания вида: ABC+ZA=SDF, где все разные буквы это разные цифры, а от сюда следует, что (C+A)%10 == F и область перебора сужается:)
Я начал от перестановок, но полез явно не в ту сторону, верное решение я нашёл сразу (и оно было гарантировано верным, т.к. перебирал я там вообще все варианты перестановок от этих 9-ти цифр =)), но вот со скоростью и расходом памяти там был полный швах, по-этому я отбросил эту идею и написал то, что написал выше. Надо будет ещё покусать…
А вообще там, да, явно нужно больше математики, верно выбранное математическое обоснование даст огромный прирост по скорости.
А вообще там, да, явно нужно больше математики, верно выбранное математическое обоснование даст огромный прирост по скорости.
Я тоже вначале думал о перестановках и математике, но быстро понял, что генерация подходящих вариантов будет занимать значительно больше времени чем простой перебор. Имхо лучше одно умножение чем одно условие (ошибка предсказателя переходов при ветвлении в процессоре сбрасывает весь конвеер, что замедляет работу).
P.S.
Код на Java. 0.156 сек. E8400 3ГГц.
P.S.
Код на Java. 0.156 сек. E8400 3ГГц.
Отталкивался от следующего:
abc*de=khgf равноценно
(a*100+b*10+c)*(d*10+e)=k*1000+h*100+g*10+f, то есть
1000*a*d+100*(a*e+d*b)+(e*b+c*d)*10+c*e=k*1000+h*100+g*10+f
а далее смотрю на остатки при делении и того 0.03 на TCL, почти догнал брут форс на C=)
clipie.org/view.php? key=B9K47FLMVSP03EDUJIX5
abc*de=khgf равноценно
(a*100+b*10+c)*(d*10+e)=k*1000+h*100+g*10+f, то есть
1000*a*d+100*(a*e+d*b)+(e*b+c*d)*10+c*e=k*1000+h*100+g*10+f
а далее смотрю на остатки при делении и того 0.03 на TCL, почти догнал брут форс на C=)
clipie.org/view.php? key=B9K47FLMVSP03EDUJIX5
msec можно трактовать по разному милли и микро, в данном случае милли.
if (a * b == c) {
nums[c] = true; // имеет смысл заменить на sum += n;
} else {
a = n1*10 + n2;
b = n3*100 + n4*10 + n5;
if (a*b==c) {
nums[c] = true; // sum += n;
}
}Этот цикл дальше по коду, ого-го время кушает (и массив булей убрать, он не нужен):
for (int n = 1000; n < 10000; n++) {
if (nums[n]) {
sum += n;
}
}Еще можно сузить перебор переменных n1, n2, n3… Интересный вариант ;)
А сейчас я покажу вам немного магии, кодерской магии:
Так и быть, раскажу «секрет» фокуса :) Фишка в том, что с теми переменными вы саначала перебирали («странным») образом «делители» и только потом само число. Если число перебирать на внешмен уровне рекурсии, то перейти к следующему, пропустив остальные делители не составляет труда. Такие дела :)
bool flags[10], magic=false;
memset(flags,false,sizeof(flags));
int sum=0; //дальше без изменений
for (int n1 = 1; n1 < 10; n1++) {
flags[n1] = true; //...первые три без изменений
for (int n4 = 1; n4 < 10; n4++) if (!flags[n4]) {
for (int n5 = 1; n5 < 10 && !magic; n5++) //... с n5 до n9 добавляется новое уловие
for (int n9 = 1; n9 < 10 && !magic; n9++){ //..
int c = n1 * 1000 + n2 * 100 + n3 * 10 + n4; // особая магия
int a = n5; // у-у-у
int b = n7 * 1000 + n8 * 100 + n9 * 10 + n6; // бу-у-у
if (a * b == c) {
sum+=c; magic=true;
} else {
a = n5*10 + n7; // ву-у-у
b = n8*100 + n9*10 + n6; // а-а-а
if (a*b==c) {
sum+=c; magic=true;
}
}
} //тут закрываются циклы с n9 по n5
magic=false;
} //end for n4Так и быть, раскажу «секрет» фокуса :) Фишка в том, что с теми переменными вы саначала перебирали («странным») образом «делители» и только потом само число. Если число перебирать на внешмен уровне рекурсии, то перейти к следующему, пропустив остальные делители не составляет труда. Такие дела :)
А ещё можно математичненько так (и читаемо, заодно):
На моей машине выдаёт «Done 10 times in 2.11714696884 sec.», т.е. считает за 0.2 секунды. Похоже, неплохо, учитывая рекурсивный генератор, сортировку и set.
# Python
import timeit
def gen_positional_combinations(seq, n):
# Генерируем сочетания по n элементов, только позиционные.
# Не помню, как это называется в комбинаторике.
if n==1:
for e in seq:
yield e
else:
for i in range(len(seq)):
for tail in gen_positional_combinations(seq[:i]+seq[i+1:], n-1):
yield seq[i]+tail
def work():
result_set=set()
for perm in gen_positional_combinations('123456789', 5):
for i in (1,2):
x, y = int(perm[:i]), int(perm[i:])
xy = x*y
if ''.join(sorted(perm+str(xy)))=='123456789':
print x, y, x*y
result_set.add(x*y)
return sum(list(result_set))
t = timeit.Timer('print euler32.work()', 'import euler32')
print "Done 10 times in %s sec."%t.timeit(10)
На моей машине выдаёт «Done 10 times in 2.11714696884 sec.», т.е. считает за 0.2 секунды. Похоже, неплохо, учитывая рекурсивный генератор, сортировку и set.
Haskell:
import Data.List (sort, nub)
main = print $ sum $ nub [i | i <- [1234..9876], j <- [2..iSqrt i], let (d,m) = i `divMod` j, m == 0, allDigits i j d]
where
iSqrt = round . sqrt . fromIntegral
allDigits x y z = sort (show x ++ show y ++ show z) == ['1'..'9']
Python, Haskell, TCL, C, PHP, C# — круто, чувствую скоро рабисты подтянуться=)
Скучная задача, раз простым перебором решается)
Тем не менее, код на С++: clipie.org/view.php? key=E1ZLSOPRG7M4UCK30FIT
Тем не менее, код на С++: clipie.org/view.php? key=E1ZLSOPRG7M4UCK30FIT
ну вот вам и самый простой брут на руби (диапазоны в уме подбирал)
c=[]
for a in 2..98
for b in 123..4897
s=a.to_s+b.to_s+(a*b).to_s
c.push a*b if s.size==9 &&! s['0'] && s.split(//).uniq.size==9
end
end
p c.uniq.inject{|s, i|s+i}
3.7сек на AM2 4200+
c=[]
for a in 2..98
for b in 123..4897
s=a.to_s+b.to_s+(a*b).to_s
c.push a*b if s.size==9 &&! s['0'] && s.split(//).uniq.size==9
end
end
p c.uniq.inject{|s, i|s+i}
3.7сек на AM2 4200+
Java
3.6 секунд на Intel Q6600
3.6 секунд на Intel Q6600
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача №32