Интересные задачки для реализации

[Кликермен]

Наткнулся на сайт, с  задачами для программистов.  около 500 различных головоломок,   без привязки к конкретному языку  программирования. очень понравилось. Хочу поделиться, только он на испанском
[spoiler]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 - уходит  примерно минута на обработку.

Code: (clickermann) [Select]

$_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.

[Vint]

Задача №1

Твой код выполнился у меня за

Code: [Select]

10:34:42 Затрачено 47.432 секунд, сумма:39
После оптимизации у меня стало уходить

Code: [Select]

10:53:49 Затрачено 32.619 секунд, сумма:39
[spoiler]

Code: (clickermann) [Select]

$_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]

[Vint]

Задача 2, посложнее

Если перечислить все натуральные числа меньше 10, кратные 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих чисел равна 23.
Необходимо найти сумму всех натуральных чисел до 1000, кратных 3 или 5.

  смеёшься? Что здесь сложного?
Вот 2 варианта

Code: [Select]

11:49:40 1 Затрачено 0.351 секунд, сумма:233168
11:49:41 2 Затрачено 1.478 секунд, сумма:233168
[spoiler]

Code: (clickermann) [Select]

$_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]

[Vint]

Вот была интересная задача.
В уме быстро посчитать сумму всех чисел от 1 до 100 включительно.

Догадался сразу как делать. А вы? Без интернета само собой.

[Луций]

ну допустим ты помнишь формулу суммы прогрессии с школы, но блин это 7й вроде бы класс, в жизни тебе это вряд ли пригодится (а тем более для кликера), может будем рассматривать задачи прикладные и реальные, вроде обхода блокировки лупы в привязке сменой браузера или установкой виндосовского флеша разных модификаций?

[Vint]

Ладно, ладно. Это я погорячился.
Но там никакой формулы не нужно, там нужна внимательность и способность к алгоритмам.

Для кликера пригодится всё. Это в принципе оптимизация вычислений. И т.к. вычисления у нас тормознутые нужно уметь их оптимизировать.

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]

Code: (clickermann) [Select]

$_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]
Винт, зацени)

Code: (clickermann) [Select]

0:00:53 Затрачено 6.596 секунд, сумма:32переделал алгоритм,  теперь пашет шустрее. и баг поправил -раньше выдавало ошибочный результат 39) кстати, утром считал 10 тысяч - ушло полтора часа, а сейчас

Code: (clickermann) [Select]

0:08:01 Затрачено 117.794 секунд, сумма:51

[Vint]

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

[Кликермен]

я заметил, что проверка if тоже очень замедляет работу.. добавил три если, чтобы ускориться, но  наоборот - в 3 раза медленнее.
Можно пример на костыль из строк? массив удобен,  аррсайз, аррпоп.. а как со строкой такое сделать?

[Vint]

Как раньше делали до появления массивов. Соединяли в строку через разделитель. Длина - количество разделителей (или кол-во + 1 если строка не закрыта разделителем)
Потом STRPOS STRCUT вычленяем нужные элементы.
Да морока это, неудабно. На коротких массивах ещё куда не шло. А большие...

[Кликермен]

3. Задача о максимальном произведении трех чисел массива

Задача, которую предлагали на собеседованиях в Apple: у вас есть массив с целыми числами, в том числе и отрицательными, вам нужно найти самое большое произведение 3 чисел из этого массива.

Например: у вас есть массив list_of_ints, содержащий числа -10, -10, 1, 3, 2. Функция, которая обрабатывает этот массив, должна вернуть 300, так как -10 * -10 * 3 = 300. Задание нужно выполнить максимально эффективно, не забывая про отрицательные числа.

[Vint]

Чёт никто не решает. Это же интересно. Не пиксел искать в тысячный раз.

Если чисто по задаче, то вот:
[spoiler]

Code: (clickermann) [Select]

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 что ещё лучше.
Вот даже попробую сделать тоже самое на питоне, чтобы посмотреть насколько делать удобней и лучше выглядит.