Задача №29

[@BENZIN]

О_о

[@dohlik]

не думаю, что метод перебора известных Вам чисел быстро приведет к правильному решению: D

ЗЫ.

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

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

[@shai_xylyd]

a, b — целые. ошибся.

[@dohlik]

a, b — целые. ошибся.

Кто из нас? :)

[@shai_xylyd]

Я.

[@dohlik]

я так полагаю, просто составить программу и получить от нее итоговое количество элементов не покатит? :)

[@shai_xylyd]

Прокатит, просто есть нюансы.

[@xyz]

А где остальные 28 заданий?

[@dohlik]

это просто самое легкое — для разминки

[@shai_xylyd]

Только что его решил просто.

Я буду, если хабру, интересна эта тема переводить, решать и публиковать решения здесь. Надеюсь к этому блогу присоединяться люди, которые будут заниматься тем — же.

[@Barttos]

9801 так?

[@maximd]

Во загнул

[@elfiki]

После написания простенькой программки получилось, что всего 9801 число, из которых разные — всего 9183

[@shai_xylyd]

Опубликуй код проги в этом блоге — интересно почитать. А вообще верно.

[@Wizard87]

что за проект такой? Я например вручную считал. Тока Exel поюзал

[@shai_xylyd]

Я постарался написать о нем в описании этого коллективного блога.

[@elfiki]

Вот он:

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

:)

[@shai_xylyd]

Добавь время работы, теги project_euler_php, project_euler_29, ссылку на задание и запости его не как комментарий. А пока чую, что мой tcl быстрее будет

[@elfiki]

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

[@shai_xylyd]

ОК, замечательно, я рад. Я тоже не гонюсь за скоростью, мои рамки — меньше минуты на КПК. Просто иногда интересно что-то решать не в лоб. Уверен, что у данной задачи есть решение, которое легко посчатать и без компьютера.

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

[@dohlik]

…
$num = pow($i,$j);
$arr[$num] = $num;
…
В этом случае в массиве уже будут уникальные и упорядоченные элементы ;)

[@elfiki]

Хм, и вправду :)

[@elfiki]

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

[@dohlik]

0.263562 -> 0.011582 секунды

Нехило получилось o_0

[@elfiki]

Сортировка и уникальность много жрут :(

[@vorbiz]

9800

[@SkAZi]

Думаю 9800

[@SkAZi]

А теперь подумав — 9183

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

[@shai_xylyd]

Сколько работает, на какой машине? Python?

[@SkAZi]

Уф 3.7 сек, за 100 итераций… Да, пайтон. AMD 4400 что ли, два ядра, 2 Гб RAM… Ну вообще это замер средней температуры по больнице, эта информация Вам ни о чем не скажет. Надо тестировать на одной машине.

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

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

[@SkAZi]

* конечно операция, а не итерация, совсем к вечеру заговорился

[@shai_xylyd]

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

А так же мне эта информация скажет о выразительности языка, при решении той же задачи, которую я уже решал.

[@LoneCat]

Я вообще в математике не силен, но имхо есть такая закономерность:
x = (max — min) * max
соот-но в первом примере это:
x = (5 — 2) * 5 = 3 * 5 = 15
а во втором:
x = (100 — 2) * 100 = 98 * 100 = 9800

[@Wizard87]

В первом случае не так. 4 степени * 4 числа = 16. Одно число (а именно 16) совпадает. В итоге 15. Логику во втором отписал ниже

[@Wizard87]

9183 получается Всего 9801 число. и 617 совпадают. такие как степени 2, 3, 4 и т.д. чисел меньше 100

[@Twin]

Вот самое простое решение, пожалуй. И без компьютера, отлично )

Но, всё таки, мне кажется, что главный смысл задачи заключается в построении такого алгоритма, который даёт сразу число уникальных чисел в ряде. Т.е. умеет исключать повторяющиеся числа.

[@kolesnikov_evgeny]

9786

[@DrunkenMaster]

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 с.

[@naething]

Быстрое решение на C++: clipie.org/view.php? key=WKZ9L4SRIVYU7A5BDNX2
Брутфорс на Руби:

a = {}
(2..100).each{ |i| (2..100).each { |j| a[i ** j] = 1 } }
puts a.length

[@Nakilon]

омг… зачем же хэш? можно ещё тупей 8)
p (2..100).map{|a|(2..100).map{|b|a**b}}.flatten.uniq.size

[@shai_xylyd]

Круто, быстро. Интересно расшифровывать код в поиске алгоритма, а потом приятно обнаружить, что он то же, который ты сам реализовал, то есть, что кто-то думает так же, как и ты.

[@Nakilon]

Друг на лиспе написал.

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

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