How to become an author
Search
Write a publication
Pull to refresh

Comments 57

Уф, второй раз смотрю на ваш код на Тикле, второй раз бросает в дрожь… Плюс вам за то что не страшно таких мустангов объезжать! Я бы егойных копыт побоялся, честно =))
Rating is hidden
Приятно кстати — такой грамотный код на тикле пишете, не нубский =)
Rating is hidden
Вот. Быдлокодинг, конечно, но все таки.

<?
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

Правильно?
Rating is hidden
Да, похоже на то, у меня тоже получилось 45228, алгоритм только корявый, выкладывать пока не буду, ещё покумекаю.
Rating is hidden
таки да, я немного ошибся… у меня тоже после коррекции допущений получилось это число.
Rating is hidden
Скорость, осмелюсь предположить, после этого тоже немного cкорректировалась ;)
Rating is hidden
<?
$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
Rating is hidden
Банальное решение с банальным отсечением занимает 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
Rating is hidden
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
Rating is hidden
Если считать простом, как доска, перебором, то получается вот так:

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
Rating is hidden
проверьте, что в сумме вы учли их один раз.

У вас тоже 45228 :)
Rating is hidden
Я уже понял. Невнимательно прочитал, так что ошибочка вышла, ага :(
Rating is hidden
>>> 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
Rating is hidden
Ну, разбавлю поток скриптовых решений :) Вот, немного хакерское решение (на CeleronM 540@1.8ГГц с 512DDR@266МГц работает за 0,013 секунд. Работает быстро, потому как использует битовые маски для определения «правильности» числа + небольшой отсев.
#include <stdio.h>
#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;
}
Как видно, numtomask тоже можно ускорить.
Rating is hidden
UFO landed and left these words here
Я своему преподу покажу. В своё время мне нравилось познавать JS именно на решение различных математических задач, а не как юзабили или вёрстку дизайна. Реально очень интересно. Слежу за каждым выпуском.
Rating is hidden
Ну наконец то! Давно жду, когда же появится решение на статическом, компилируемом языке. Да, конечно по скорости нам не тягаться, оптимизация моего решения при помощи ваших масок дала прирост всего в 1-2 секунды на 100 итераций, тут уж се ля ви даже не в масках дело. =)

Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
Rating is hidden
> Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
Верно. Еще можно перебирать в [2, sq) а не в [sq,1]. 

  int sq, i, d1=numtomask(a);
  if (bitcount(d1) != 4)
   continue; // coz it isn't abcd-number
  sq=(int)sqrt(float(a));
  for (i=2; i<sq && !find; i++)
Rating is hidden
Да, точно, помню что 2 тонкости заметил, но пока пост писал вылетело.
Rating is hidden
Незначительное ускорение даст тот факт, что a не оканчивается на 5.
Rating is hidden
UFO landed and left these words here
Думаю, что нет. По сути, все алгоритмы, которые здесь представленны — брут форс. Если замутить генерацию перестановок, то можно выиграть на проверках, но это тоже перебор и не учитывает специфику задачи. Это задание, как школьные задания вида: ABC+ZA=SDF, где все разные буквы это разные цифры, а от сюда следует, что (C+A)%10 == F и область перебора сужается:)
Rating is hidden
Я начал от перестановок, но полез явно не в ту сторону, верное решение я нашёл сразу (и оно было гарантировано верным, т.к. перебирал я там вообще все варианты перестановок от этих 9-ти цифр =)), но вот со скоростью и расходом памяти там был полный швах, по-этому я отбросил эту идею и написал то, что написал выше. Надо будет ещё покусать…
А вообще там, да, явно нужно больше математики, верно выбранное математическое обоснование даст огромный прирост по скорости.
Rating is hidden
Я тоже вначале думал о перестановках и математике, но быстро понял, что генерация подходящих вариантов будет занимать значительно больше времени чем простой перебор. Имхо лучше одно умножение чем одно условие (ошибка предсказателя переходов при ветвлении в процессоре сбрасывает весь конвеер, что замедляет работу).
P.S.
Код на Java. 0.156 сек. E8400 3ГГц.
Rating is hidden
Отталкивался от следующего:
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
Rating is hidden
UFO landed and left these words here
UFO landed and left these words here
msec можно трактовать по разному милли и микро, в данном случае милли.
Rating is hidden
UFO landed and left these words here
UFO landed and left these words here
UFO landed and left these words here
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… Интересный вариант ;)
Rating is hidden
UFO landed and left these words here
А сейчас я покажу вам немного магии, кодерской магии:
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


Так и быть, раскажу «секрет» фокуса :) Фишка в том, что с теми переменными вы саначала перебирали («странным») образом «делители» и только потом само число. Если число перебирать на внешмен уровне рекурсии, то перейти к следующему, пропустив остальные делители не составляет труда. Такие дела :)
Rating is hidden
UFO landed and left these words here
UFO landed and left these words here
UFO landed and left these words here
UFO landed and left these words here
UFO landed and left these words here
UFO landed and left these words here
А ещё можно математичненько так (и читаемо, заодно):
# 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.
Rating is hidden
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']
Rating is hidden
Python, Haskell, TCL, C, PHP, C# — круто, чувствую скоро рабисты подтянуться=)
Rating is hidden
… и будут дальше упражняться в повышении компактности брутфорса разной степени тормознутости :)
Rating is hidden
Ну так дайте же его нам! Красивое и быстрое решение без брутфорса =)
Rating is hidden
Скучная задача, раз простым перебором решается)
Тем не менее, код на С++: clipie.org/view.php? key=E1ZLSOPRG7M4UCK30FIT
Rating is hidden
Простите за кривую сслыку, в предпросмотре показывалась нормально. Что за издевательство, почему нельзя по-человечески вставить ссылку?
Rating is hidden
ну вот вам и самый простой брут на руби (диапазоны в уме подбирал)

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+
Rating is hidden
о! в руби 1.9 есть #permutation типа как в STL
Rating is hidden
Sign up to leave a comment.

Articles

Your account

Sections

Information

Services

Support
© 2006–2025, Habr