Автокликер Clickermann :: Форум
Основной раздел => Общие вопросы => Topic started by: Кликермен on February 05, 2016, 05:10:17 AM
-
Наткнулся на сайт, с задачами для программистов. около 500 различных головоломок, без привязки к конкретному языку программирования. очень понравилось. Хочу поделиться, только он на испанском :D
[spoiler]projecteuler.net (http://projecteuler.net)
Шучу, на английском)[/spoiler]
Буду дублировать интересные задачи, с моей реализацией(или без, если не додумаюсь). Подключайтесь, очень много реально интересного.
Задача №1(там она 35, ну да ладно)
Число 197 - круговое простое , потому что все круговые перестановки цифр: 197, 971, и 719, образуют только простые числа.
Есть тринадцать таких простых чисел меньше 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, и 97.
Сколько всего круговых простых чисел до миллиона?
-
Решение задачи №1
Пока решал - освоил азы обработки строк)) раньше вообще не хотелось изучать их. задача решена идеально, в начале нужно выбрать диапазон чисел. на 1000 - уходит примерно минута на обработку.
$_ms1=$_ms
FOR($a=0,$a<1000) // повторяем 3 раза
for($i=1, $i<$a+1)
if (strpos($a/$i, ".")=0)
$light=$light+1
if (($light=3)|($light>3))
$i=$a+1
end_if
end_if
END_CYC
if (($light<3)&($a>1))
arrpush($arr, $a)
end_if
$light=0
END_CYC
FOR($a=0,$a<ARRSIZE($arr)) // повторяем 3 раза
FOR($p=1,$p<(strlen($arr[$a])))
if ($m=0)
$m=$arr[$a]
end_if
$m=STRCONCAT(strcut($m,2,strlen($m)-1), strcut($m,1,1))
while (strpos($m,"0")=1)
$m=STRCONCAT(strcut($m,2,strlen($m)-1))
end_cyc
FOR($l=0,$l<ARRSIZE($arr))
if ($m=$arr[$l])
$yes=$yes+1
$l=ARRSIZE($arr)
end_if
END_CYC
if ($yes=(strlen($m)-1))
print("простоЕ!" , $arr[$a])
$summa=$summa+1
end_if
END_CYC
if (strlen($arr[$a])<2)
print("простоЕ!" , $arr[$a])
$summa=$summa+1
end_if
$yes=0
$m=0
END_CYC
print("Затрачено ", ($_ms-$_ms1)/1000, " секунд, сумма:", $summa)
halt
-
Задача 2, посложнее
Если перечислить все натуральные числа меньше 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих чисел равна 23.
Необходимо найти сумму всех натуральных чисел до 1000, кратных 3 или 5.
-
Задача №1
Твой код выполнился у меня за
10:34:42 Затрачено 47.432 секунд, сумма:39
После оптимизации у меня стало уходить
10:53:49 Затрачено 32.619 секунд, сумма:39
[spoiler]$_ms1 = $_ms
arrpush($arr, 2)
FOR($a=3, $a < 1000)
FOR($i=2, $i < $a)
//IF(($a/$i) - INT($a/$i) = 0)
IF(strpos($a/$i, ".") = 0)
$i = $a + 10
END_IF
END_CYC
IF($i-1 ! ($a + 10))
arrpush($arr, $a)
END_IF
END_CYC
$size = ARRSIZE($arr)
FOR($a=0, $a < $size)
$m = 0
$yes = 0
FOR($p=1, $p < (strlen($arr[$a])))
IF($m = 0)
$m = $arr[$a]
END_IF
$m = INT(STRCONCAT(strcut($m, 2, strlen($m)-1), strcut($m, 1, 1)))
FOR($l=0, $l < $size)
IF($m = $arr[$l])
$yes = $yes + 1
$l = $size
END_IF
END_CYC
IF($yes = (strlen($m) - 1))
print("простое!", $arr[$a])
$summa = $summa + 1
END_IF
END_CYC
IF(strlen($arr[$a]) < 2)
print("простое!" , $arr[$a])
$summa = $summa + 1
END_IF
END_CYC
print("Затрачено ", ($_ms-$_ms1)/1000, " секунд, сумма:", $summa)
HALT[/spoiler]
-
Задача 2, посложнее
Если перечислить все натуральные числа меньше 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих чисел равна 23.
Необходимо найти сумму всех натуральных чисел до 1000, кратных 3 или 5.
:D ;D смеёшься? Что здесь сложного?
Вот 2 варианта
11:49:40 1 Затрачено 0.351 секунд, сумма:233168
11:49:41 2 Затрачено 1.478 секунд, сумма:233168
[spoiler]$_ms1 = $_ms
$summa = 0
FOR($a=1, $a < 1000)
IF((strpos($a/3, ".") = 0) | (strpos($a/5, ".") = 0))
$summa = $summa + $a
END_IF
END_CYC
print("1 Затрачено ", ($_ms-$_ms1)/1000, " секунд, сумма:", $summa)
$_ms1 = $_ms
$summa = 0
FOR($a=1, $a < 1000)
$endn = STRCUT($a, STRLEN($a), 1)
IF(STRPOS ("05", $endn) > 0)
//print("Кратно 5 ", $a, " ", $endn)
$summa = $summa + $a
ELSE
$sum = 0
FOR($i=1, $i < STRLEN($a)+1)
$sum = $sum + INT(STRCUT($a, $i, 1))
END_CYC
IF(strpos($sum/3, ".") = 0)
$summa = $summa + $a
END_IF
END_IF
END_CYC
print("2 Затрачено ", ($_ms-$_ms1)/1000, " секунд, сумма:", $summa)
HALT[/spoiler]
-
Вот была интересная задача.
В уме быстро посчитать сумму всех чисел от 1 до 100 включительно.
Догадался сразу как делать. А вы? Без интернета само собой.
-
ну допустим ты помнишь формулу суммы прогрессии с школы, но блин это 7й вроде бы класс, в жизни тебе это вряд ли пригодится (а тем более для кликера), может будем рассматривать задачи прикладные и реальные, вроде обхода блокировки лупы в привязке сменой браузера или установкой виндосовского флеша разных модификаций?
-
Ладно, ладно. Это я погорячился.
Но там никакой формулы не нужно, там нужна внимательность и способность к алгоритмам.
Для кликера пригодится всё. Это в принципе оптимизация вычислений. И т.к. вычисления у нас тормознутые нужно уметь их оптимизировать.
P.S. А с привязкой я вообще завязал. И раньше не любил её капризность, а теперь у меня во всех браузерах при привязке-смещение. В мозиле влево на 4 px - величину рамки окна. В опере влево 4 px и вверх 25 px - высота заголовка. Хром вообще мёртв.
И что я могу решить? Слишком всё индивидуально. Как слышу "привязка" так сразу теперь отказываюсь от кода. Нах, нах, нервы не железные.
Если бы джонни решил это на уровне кликера, а не мы на уровне десятка параметров с неизвестным результатом, тогда другое дело.
-
Вот была интересная задача.
В уме быстро посчитать сумму всех чисел от 1 до 100 включительно.
Догадался сразу как делать. А вы? Без интернета само собой.
Я недавно искал инфу по нетривиальному программированию( такое определение кликера на главной) и наткнулся на Эйлера, как он во 2 классе открыл, что первый+предпоследний член = последнему
у эйлера было нетравиальное мышление. будучи учеником младших классов, он быстро выполнял все задания и досаждал учителю разными вопросами. как-то учитель решил дать ему задание, которое надо, по его мнению, решать весь урок. задание такое: найти сумму всех чисел от 1 до 100. эйлер справился с заданием за 5 минут, заодно переоткрыл формулу суммы арифметической прогрессии. 1+99=100, 2+98=100, 3+97=100 ...49+51=100, т. е. 49 раз по 100 и еще 100+50, итого 5050. ученик с травиальным мышлением суммировал бы на прямую 1+2=3, 3+3=6, 6+4=10 и т. д. всего 100 операций сложения, если на каждую затрачивать 25с, то нахождение всей суммы займет 41мин.
Вот тогда я понял, что абсолютно не помню школьную математику.
Винт, вот решение(из головы, я его недавно повторно вывел, когда писал для кликера алгоритм)
[spoiler](1+100)*100/2=5050[/spoiler]
-
[spoiler]
$_ms1=$_ms
print("простоЕ!" , 2)
$summa=$summa+1
FOR($a=3,$a<1001) // повторяем
if ($a<100)
$b=10
else
$b=int(SQRT($a))+1
end_if
for($i=2, $i<$b)
if ((strpos($a/$i, ".")=0)&($a!$i))
$light=1
$i=$a+1
end_if
// if (strlen($a)>1)
// if (strcut($a, strlen($a), 1)="0")
// $light=1
// $i=$a+1
// end_if
// if ((strcut($a, strlen($a), 1)=5))
// $light=1
// $i=$a+1
// end_if
// if (strcut($a, strlen($a), 1)/2=int(strcut($a, strlen($a), 1)/2))
// $light=1
// $i=$a+1
// end_if
// end_if
END_CYC
if ($light!1)
if ($m=0)
$m=$a
end_if
FOR($p=1,$p<(strlen($a)))
$m=STRCONCAT(strcut($m,2,strlen($m)-1), strcut($m,1,1))
while (strpos($m,"0")=1) //чистим первые нули, получаемые перестановкой
$m=STRCONCAT(strcut($m,2,strlen($m)-1))
end_cyc
if ($a<100)
$bb=10
else
$bb=int(SQRT($a))+1
end_if
for($i=2, $i<$bb)
if (strpos($m/$i, ".")=0)
$yes=1
$i2=$a+1
end_if
// if (strlen($m)>1)
// if (strcut($m, strlen($m), 1)="0")
// $yes=1
// $i2=$a+1
// end_if
// if ((strcut($m, strlen($m), 1)=5))
// $yes=1
// $i2=$a+1
// end_if
// if (strcut($m, strlen($m), 1)/2=int(strcut($m, strlen($m), 1)/2))
// $yes=1
// $i2=$a+1
// end_if
// end_if
END_CYC
END_CYC
if (($yes=0)&(strlen($a)>1))
print("простоЕ!" , $a)
$summa=$summa+1
end_if
if (strlen($a)<2)
print("простоЕ!" , $a)
$summa=$summa+1
end_if
end_if
$light=0
$yes=0
$m=0
END_CYC
print("Затрачено ", ($_ms-$_ms1)/1000, " секунд, сумма:", $summa)
halt[/spoiler]
Винт, зацени)
0:00:53 Затрачено 6.596 секунд, сумма:32переделал алгоритм, теперь пашет шустрее. и баг поправил -раньше выдавало ошибочный результат 39) кстати, утром считал 10 тысяч - ушло полтора часа, а сейчас
0:08:01 Затрачено 117.794 секунд, сумма:51
-
Меня одно печалит. Что в кликере массивы работают так медленно. Убрав простое складывание в массив ускоряет скрипт в разы.
Я в начале думал что массивы работают быстро. Потом оказалось, что костыли из строк намного быстрей массивов. Погоревал, погоревал, но использовать продолжаю. Удобней.
-
я заметил, что проверка if тоже очень замедляет работу.. добавил три если, чтобы ускориться, но наоборот - в 3 раза медленнее.
Можно пример на костыль из строк? массив удобен, аррсайз, аррпоп.. а как со строкой такое сделать?
-
Как раньше делали до появления массивов. Соединяли в строку через разделитель. Длина - количество разделителей (или кол-во + 1 если строка не закрыта разделителем)
Потом STRPOS STRCUT вычленяем нужные элементы.
Да морока это, неудабно. На коротких массивах ещё куда не шло. А большие...
-
3. Задача о максимальном произведении трех чисел массива
Задача, которую предлагали на собеседованиях в Apple: у вас есть массив с целыми числами, в том числе и отрицательными, вам нужно найти самое большое произведение 3 чисел из этого массива.
Например: у вас есть массив list_of_ints, содержащий числа -10, -10, 1, 3, 2. Функция, которая обрабатывает этот массив, должна вернуть 300, так как -10 * -10 * 3 = 300. Задание нужно выполнить максимально эффективно, не забывая про отрицательные числа.
-
Чёт никто не решает. Это же интересно. Не пиксел искать в тысячный раз.
Если чисто по задаче, то вот:
[spoiler]SUB(multi_3_max) //=============================================================
$result = 1
$len = ARRSIZE($list_of_ints)
IF($len = 0)
$result = 0
ELSE
IF($len < 4)
FOR($i=0, $i < $len)
$result = $result * $list_of_ints[$i]
END_CYC
ELSE
FOR($i=0, $i < $len)
$num = INT($list_of_ints[$i])
IF($num > 0)
ARRPUSH($pos, $num)
FOR($p=(ARRSIZE($pos)-2), $p > -1, -1)
IF($pos[$p+1] > $pos[$p])
$temp = $pos[$p+1]
$pos[$p+1] = $pos[$p]
$pos[$p] = $temp
ELSE
$p = -1
END_IF
END_CYC
IF(ARRSIZE($pos) > 3)
$pass = ARRPOP($pos)
END_IF
ELSE
ARRPUSH($neg, $num)
FOR($n=(ARRSIZE($neg)-2), $n > -1, -1)
IF($neg[$n+1] < $neg[$n])
$temp = $neg[$n+1]
$neg[$n+1] = $neg[$n]
$neg[$n] = $temp
ELSE
$n = -1
END_IF
END_CYC
END_IF
END_CYC
SWITCH(ARRSIZE($pos))
CASE(0)
$nl = ARRSIZE($neg)
LOGWRITE ("перемножаемые ", $neg[$nl-1], " * ", $neg[$nl-2], " * ", $neg[$nl-3])
$result = $neg[$nl-1] * $neg[$nl-2] * $neg[$nl-3]
CASE(1)
LOGWRITE ("перемножаемые ", $pos[0], " * ", $neg[0], " * ", $neg[1])
$result = $pos[0] * $neg[0] * $neg[1]
CASE(2)
IF(ARRSIZE($neg) > 1)
LOGWRITE ("перемножаемые ", $pos[0], " * ", $neg[0], " * ", $neg[1])
$result = $pos[0] * $neg[0] * $neg[1]
ELSE
$result = 0
END_IF
DEFAULT
IF(ARRSIZE($neg) > 1)
$r1 = $pos[0] * $pos[1] * $pos[2]
$r2 = $pos[0] * $neg[0] * $neg[1]
IF($r1 > $r2)
LOGWRITE ("перемножаемые ", $pos[0], " * ", $pos[1], " * ", $pos[2])
$result = $r1
ELSE
LOGWRITE ("перемножаемые ", $pos[0], " * ", $neg[0], " * ", $neg[1])
$result = $r2
END_IF
ELSE
LOGWRITE ("перемножаемые ", $pos[0], " * ", $pos[1], " * ", $pos[2])
$result = $pos[0] * $pos[1] * $pos[2]
END_IF
END_SWITCH
END_IF
END_IF
END_SUB
//==============================================================================
LOGCLEAR
// задан массив
STRSEPARATE("3,-2,4,0", ",", $list_of_ints) # "3,-2,4,0" "5,3,-2,0,0"
$t=$_ms
multi_3_max()
LOGWRITE ("Результат: ", $result)
print("за ",$_ms-$t,"ms")
HALT
[/spoiler]
Сильно заметно, что код на кликере не такой изящный как можно сделать на других языках. Не хватает мелочей. Все эти многоэтажные вложенные условия выглядят не очень хорошо.
Хорошо бы ещё была встроенная функция сортировки массивов прямая и обратная. Понятно, что на всё это давно сделаны подпрограммы, но вот скорость. Делфи бы их сортировал в 1000 раз быстрее.
Ещё бы не помешал вариант свитча с произвольными условиями в CASE или в варианте ELIF что ещё лучше.
Вот даже попробую сделать тоже самое на питоне, чтобы посмотреть насколько делать удобней и лучше выглядит.
-
хехе, я вчера часа 4 потратил на эту задачу. получил простенький вариант с сортировкой массива, но длительный, на сортировку много уходит сил.
второй вариант мега сложный, но быстрый.
SUB(fast) //быстрый но сложный способ
IF(ARRSIZE($arr)>3) //проверка, чтоб в массиве было более трех элементов
FOR($a=0,$a<ARRSIZE($arr)) //делим на отрицательные и положительные (0 пусть будет положительным)
IF($arr[$a]<0)
arrpush($minus,$arr[$a])
else
arrpush($plus,$arr[$a])
END_IF
END_CYC
IF(ARRSIZE($plus)=0) //если положительных чисел нету
print("положительных чисел нету")
$minus_max=$minus[0]
$i=0
FOR($a=1,$a<ARRSIZE($minus))
IF($minus[$a]>$minus_max)
$minus_max=$minus[$a]
$i=$a
END_IF
END_CYC
$minus[$i]=1
//print($minus_max)
IF($i=0)
$minus_2 = $minus[1]*$minus_max
else
$minus_2 = $minus[0]*$minus_max
END_IF
$i=0
FOR($a=0,$a<ARRSIZE($minus)) //наименьшее произведение двух отрицательных
IF((($minus[$a]*$minus_max) < $minus_2)&($minus[$a]<0))
$minus_2=$minus[$a]*$minus_max
$i=$a
END_IF
END_CYC
$minus[$i]=1
//print($minus_2)
IF($minus[0]<0)
$finish = $minus[0]*$minus_2
else
IF($minus[1]<0)
$finish = $minus[1]*$minus_2
else
$finish = $minus[2]*$minus_2
END_IF
END_IF
FOR($a=0,$a<ARRSIZE($minus)) //наименьшее произведение трех отрицательных
IF((($minus[$a]*$minus_2) > $finish)&($minus[$a]<0))
$finish=$minus[$a]*$minus_2
END_IF
END_CYC
print($finish)
else
IF(ARRSIZE($minus)>1) //проверяем, чтоб отрицательных было 2 и более
$i=0
FOR($a=0,$a<ARRSIZE($minus))
IF($minus[$a]<$minus_min)
$minus_min=$minus[$a]
$i=$a
END_IF
END_CYC
//print($minus_min)
$minus[$i]=0 //убираем наименьший элемент
FOR($a=0,$a<ARRSIZE($minus)) //наибольшее произведение двух отрицательных
IF(($minus[$a]*$minus_min) > $minus_2)
$minus_2=$minus[$a]*$minus_min
END_IF
END_CYC
END_IF
//print($minus_2)
IF(ARRSIZE($plus)=1)) //если положительное одно
$finish=$plus[0]*$minus_2
print($finish)
else
IF(ARRSIZE($plus)=2)) //если положительных 2
IF($plus[0] > $plus[1])
$finish=$plus[0]*$minus_2
print($finish)
else
$finish=$plus[1]*$minus_2
print($finish)
END_IF
else //если положительных 3 и более
$i=0
FOR($a=0,$a<ARRSIZE($plus)) //находим максимум
IF($plus[$a]>$plus_max)
$plus_max=$plus[$a]
$i=$a
END_IF
END_CYC
$plus[$i]=0
//print($plus_max)
$i=0
FOR($a=0,$a<ARRSIZE($plus)) //максимум при умножении на себеподобные
IF(($plus[$a]*$plus_max)>$plus_2)
$plus_2=$plus[$a]*$plus_max
$i=$a
END_IF
END_CYC
$plus[$i]=0
//print($plus_2)
FOR($a=0,$a<ARRSIZE($plus)) // максимум при умножении трех положительных
IF(($plus[$a]*$plus_2)>$plus_3)
$plus_3=$plus[$a]*$plus_2
END_IF
END_CYC
//print($plus_3)
IF($plus_3 > ($minus_2*$plus_max)) //сравниваем, что больше - 2 отрицательных и одно положительное, или 3 положительных.
$finish = $plus_3
print($finish)
else
$finish = $minus_2*$plus_max
print($finish)
END_IF
END_IF
END_IF
END_IF
else
IF(ARRSIZE($arr)=3) // если всего три элемента
$finish=$arr[0]*$arr[1]*$arr[2]
print($finish)
else
print("в массиве меньше трех элементов")
halt
END_IF
END_IF
END_SUB
//==========================================================
SUB(low) //медленный но простой способ
$siz = ARRSIZE($arr)
$srtcheck = 0
$srt = 0
FOR($a=$siz-1,($a>0)&($srt=0),-1)
FOR($b=0,$b<$a)
IF($arr[$b] > $arr[$b+1])
$srtcheck = 1
$tmp = $arr[$b]
$arr[$b] = $arr[$b+1]
$arr[$b+1] = $tmp
END_IF
END_CYC
IF($srtcheck = 0)
$srt = 1
END_IF
END_CYC
IF(($arr[0]*$arr[1]*$arr[ARRSIZE($arr)-1])<($arr[ARRSIZE($arr)-1]*$arr[ARRSIZE($arr)-2]*$arr[ARRSIZE($arr)-3]))
$finish=$arr[ARRSIZE($arr)-1]*$arr[ARRSIZE($arr)-2]*$arr[ARRSIZE($arr)-3]
else
$finish=$arr[0]*$arr[1]*$arr[ARRSIZE($arr)-1]
END_IF
print($finish)
END_SUB
//==========================================================
//==========================================================
//==========================================================
//==========================================================
//==========================================================
//==========================================================
STRSEPARATE("-5,-2,-3,2,3,1,0,-1",",",$arr)
//FOR($a=0,$a<ARRSIZE($arr))
// print($arr[$a])
//END_CYC
wait(1)
$t=$_ms
fast()
print("за ",$_ms-$t,"ms")
wait(1)
$t=$_ms
low()
print("за ",$_ms-$t,"ms")
halt
-
Вот на питоне:
[spoiler]#!/usr/bin/env python
# -*- coding: utf-8 -*-
def multi_3_max(list_of_ints):
if not list_of_ints: return 0, ''
if len(list_of_ints) < 4:
res = list_of_ints
else:
res = [0]
list_of_ints.sort(reverse=True)
pos = list_of_ints[:3]
pos = [i for i in pos if i > 0]
list_of_ints.sort()
neg = [i for i in list_of_ints if i <= 0]
if not len(pos):
res = [neg[-1], neg[-2], neg[-3]]
elif len(pos) == 1:
res = [pos[0], neg[0], neg[1]]
elif len(pos) == 2:
if len(neg) > 1:
res = [pos[0], neg[0], neg[1]]
else:
if len(neg) < 2:
res = [pos[0], pos[1], pos[2]]
elif pos[0]*pos[1]*pos[2] > pos[0]*neg[0]*neg[1]:
res = [pos[0], pos[1], pos[2]]
else:
res = [pos[0], neg[0], neg[1]]
op = ''
result = 1
for i in res:
result *= i
if op: op += u' * '
op += str(i)
return result, op
# list_of_ints = [-10, -10, 1, 3, 2]
# print u'Результат: %d операнды %s' % multi_3_max(list_of_ints)
print u'Результат: %d операнды %s' % multi_3_max([-10, 3, 2])
print u'Результат: %d операнды %s' % multi_3_max([-10, -10, 0, 1, 3, 2])
print u'Результат: %d операнды %s' % multi_3_max([-10, 0, 3, 2])
print u'Результат: %d операнды %s' % multi_3_max([-10, 0, 3, 2, -2])
print u'Результат: %d операнды %s' % multi_3_max([-10, 7, 3, 2])
print u'Результат: %d операнды %s' % multi_3_max([-10, 7, 3, 2, -5])
print u'Результат: %d операнды %s' % multi_3_max([-10, -7, -5, -2])
print u'Результат: %d операнды %s' % multi_3_max([-5,-2,-3,2,3,1,0,-1])
print u'Результат: %d операнды %s' % multi_3_max([4,3,-2,0,0])[/spoiler]
Результат: -60 операнды -10 * 3 * 2
Результат: 300 операнды 3 * -10 * -10
Результат: 0 операнды 3 * -10 * 0
Результат: 60 операнды 3 * -10 * -2
Результат: 42 операнды 7 * 3 * 2
Результат: 350 операнды 7 * -10 * -5
Результат: -70 операнды -2 * -5 * -7
Результат: 45 операнды 3 * -5 * -3
Результат: 0 операнды 4 * -2 * 0
[-10, -10, 0, 1, 3, 2]
1000 раз за 0.00521407050337 мс
-
А нафига там декомпилятор? pyc в py переводить?
-
Так зачем? Какая-то конкретная большая прога выложена без файлов py?
Обычно так никто не делает. Ну я раз делал, чтобы скрыть код. Но всё нужное можно найти в нормальных файлах. В крайнем случае самому написать.
Мне вот ни разу не потребовалось pyc декомпилировать.