Pull to refresh

Comments 43

UFO landed and left these words here
не думаю, что метод перебора известных Вам чисел быстро приведет к правильному решению: D

ЗЫ.
Рассмотрим все целые числа, порожденные формулой ab, где 2 ≤ a ≤ 5 и 2 ≤ b ≤ 5:

Т.е. не a и b — целые числа, а полученное число?
a, b — целые. ошибся.

Кто из нас? :)
я так полагаю, просто составить программу и получить от нее итоговое количество элементов не покатит? :)
это просто самое легкое — для разминки
Только что его решил просто.

Я буду, если хабру, интересна эта тема переводить, решать и публиковать решения здесь. Надеюсь к этому блогу присоединяться люди, которые будут заниматься тем — же.
После написания простенькой программки получилось, что всего 9801 число, из которых разные — всего 9183
Опубликуй код проги в этом блоге — интересно почитать. А вообще верно.
что за проект такой? Я например вручную считал. Тока Exel поюзал
Я постарался написать о нем в описании этого коллективного блога.
Вот он:

<? php
for ($i=2;$i<=100;$i++){
for ($j=2;$j<=100;$j++){
$arr[]=pow($i,$j);
}
}
$array=array_unique($arr);
sort($array);
print count($array);
?>

:)
Добавь время работы, теги project_euler_php, project_euler_29, ссылку на задание и запости его не как комментарий. А пока чую, что мой tcl быстрее будет
Я не ставил перед собой цель сделать наиболее быстрое решение. Считать, что это способ написания решения на ПХП — так же не правильно, ибо данный алгоритм работает и в других языках.
Времени на работу скрипта потрачено 0.263562 секунды (AMD Athlon 64 X2 6000+)
ОК, замечательно, я рад. Я тоже не гонюсь за скоростью, мои рамки — меньше минуты на КПК. Просто иногда интересно что-то решать не в лоб. Уверен, что у данной задачи есть решение, которое легко посчатать и без компьютера.

А указывать для любого алгоритма время его работы интересно тем, что можно сравнить языки и машины. Например, P4 работает в среднем на подобных задачах в 20 раз быстрее PDA Acer n311 если кодить на TCL. Если будет больше данных, то можно будет собрать статистику по интересней.

$num = pow($i,$j);
$arr[$num] = $num;

В этом случае в массиве уже будут уникальные и упорядоченные элементы ;)
<? php
for ($i=2;$i<=100;$i++){
for ($j=2;$j<=100;$j++){
$num = pow($i,$j);
$arr[$num] = $num;
}
}
print count($array);
?>
0.011582 секунды (AMD Athlon 64 X2 6000+)
С подсказки пользователя dohlik
0.263562 -> 0.011582 секунды

Нехило получилось o_0
Сортировка и уникальность много жрут :(
А теперь подумав — 9183

print len( set([ a**b for a in range(2,101) for b in range(2,101) ]) )
Сколько работает, на какой машине? Python?
Уф 3.7 сек, за 100 итераций… Да, пайтон. AMD 4400 что ли, два ядра, 2 Гб RAM… Ну вообще это замер средней температуры по больнице, эта информация Вам ни о чем не скажет. Надо тестировать на одной машине.

И ещё там лишняя итерация в коде — вот так лучше:

print len( set( a**b for a in range(2,101) for b in range(2,101) ) )

* конечно операция, а не итерация, совсем к вечеру заговорился
Если в гододе много больниц, а больных часто перевозят из одной в другую, то при некоторых условиях обладая средней температурой в каждой больнице можно померить температуру в точности до одного больного=)

А так же мне эта информация скажет о выразительности языка, при решении той же задачи, которую я уже решал.
Я вообще в математике не силен, но имхо есть такая закономерность:
x = (max — min) * max
соот-но в первом примере это:
x = (5 — 2) * 5 = 3 * 5 = 15
а во втором:
x = (100 — 2) * 100 = 98 * 100 = 9800

В первом случае не так. 4 степени * 4 числа = 16. Одно число (а именно 16) совпадает. В итоге 15. Логику во втором отписал ниже
9183 получается Всего 9801 число. и 617 совпадают. такие как степени 2, 3, 4 и т.д. чисел меньше 100
Вот самое простое решение, пожалуй. И без компьютера, отлично )

Но, всё таки, мне кажется, что главный смысл задачи заключается в построении такого алгоритма, который даёт сразу число уникальных чисел в ряде. Т.е. умеет исключать повторяющиеся числа.
PowerShell
$a = 2..100; $h = @{}; foreach ($i in $a) {foreach ($j in $a) {$h[$p] = $p = [Math]::Pow($i, $j)}}; $h.Count;

На P4 3 ГГц ~1,7 с.
Быстрое решение на C++: clipie.org/view.php? key=WKZ9L4SRIVYU7A5BDNX2
Брутфорс на Руби:

a = {}
(2..100).each{ |i| (2..100).each { |j| a[i ** j] = 1 } }
puts a.length
омг… зачем же хэш? можно ещё тупей 8)
p (2..100).map{|a|(2..100).map{|b|a**b}}.flatten.uniq.size
Круто, быстро. Интересно расшифровывать код в поиске алгоритма, а потом приятно обнаружить, что он то же, который ты сам реализовал, то есть, что кто-то думает так же, как и ты.
Друг на лиспе написал.

(print
(length
(remove-duplicates
(loop for i from 2 to 100
append (loop for j from 2 to 100
collect (expt i j)))))

Он хотел бы сам запостить, да не зареган, а на инвайт у меня сил маловато ..)
Sign up to leave a comment.

Articles