1. Java / Говнокод #10324

    +74

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    public static boolean isBouncy(long n) {
	boolean isBouncy = false;
	String num = Long.toString(n);
	String[] seperateDigits = new String[num.length()+1];
	for (int i=1; i <= num.length(); i++) {
		seperateDigits[i] = num.substring(i-1,i);
	}
	int firstDig = Integer.parseInt(num.substring(0,1));
	int cDig;
	int iDeg = 0;
	int cDeg = 0;
	int dig0;
	int dig1;
	for (int i = 2; i <= seperateDigits.length-1; i++) {
		if (!isBouncy) {
			dig0 = Integer.parseInt(seperateDigits[i-1]);
			dig1 = Integer.parseInt(seperateDigits[i]);
			if (i == 2) iDeg = getDegree(dig0, dig1);
			else {
				cDeg = getDegree(dig0,dig1);
				if (iDeg == 0) iDeg = cDeg;
				else if (cDeg == -iDeg) isBouncy = true;
			}
		}
	}
	if (iDeg == 0) isBouncy = false;
	return isBouncy;
}

    http://projecteuler.net/problem=112
    http://projecteuler.net/thread=112&page=6#63821

    >Nothing intuitive about it at all

    Запостил: TheHamstertamer, 19 Мая 2012

    Комментарии (20) RSS

    • ava bormand 19.05.2012 12:47 # +3

      Омг, заставьте меня это развидеть! Разбиение числа на цифры через toString() и parseInt()...
      Ответить

      • ava bormand 19.05.2012 13:28 # 0

        Раскопал свое (довольно тупое) решение этой задачки:
        http://ideone.com/fC4g9
        Ответить

      • ava wvxvw 19.05.2012 14:39 # 0

        Это как бы не так уж и страшно (хотя, канеш, плохо). Из цикла, который числа сравнивает однозначно можно выйти как только обнаруживается, что числа не упорядочены. Т.е.:
        12123456
        --^
        дальше уже не нужно ничего проверять.
        Ответить

        • ava bormand 19.05.2012 14:55 # 0

          Ну да, вместо isBouncy = true можно было сразу поставить return true. Кстати только сейчас заметил, что автор нумерует элементы массива с единицы.
          Ответить

          • ava wvxvw 19.05.2012 15:23 # 0

            Хз, я сейчас прочитал описание задачи - чет вообще не понятно... а числа состоящие из всех одинаковых цифр - они в какую категорию попадают?
            Ответить

          • ava wvxvw 19.05.2012 15:35 # 0 

            (defun euler-112 (percent)
  (labels ((bouncingp (x)
             (do ((i (mod x 10) (mod x 10)) (j 10)
                  (decreasing) (increasing))
                 (nil)
               (cond
                 ((= j 10))
                 ((< i j) (setf increasing t))
                 ((> i j) (setf decreasing t)))
               (cond
                 ((zerop x) (return))
                 ((and increasing decreasing) (return t)))
               (setf j i x (floor x 10)))))
    (do ((i 100 (1+ i)) (bouncing 0))
        ((= percent (floor bouncing (/ i 100)))
         (return (1- i)))
      (when (bouncingp i) (incf bouncing)))))

(euler-112 50) ; 539
(euler-112 90) ; 21789

            Т.е. в принципе, с точки зрения рассчетов тут все правильно, но результат немного отличается. Х.з. тоже как они проценты считали - в какую сторону округлять?
            Ответить

            • ava bormand 19.05.2012 16:20 # 0

              Результат отличается т.к. вы проверяете условие выхода до инкремента bouncing при текущем i. Надо или перенести инкремент bouncing до проверки, или делить на (- i 1). Тогда все ок.
              Ответить

              • ava wvxvw 19.05.2012 16:23 # 0

                А, я думаю понял на счет переноса.

                Да, и на счет перебора не всех чисел - в принципе можно было бы, но становится очень сложно изза того, что если перебирать числа не последовательно, а "скачками":
                101->109 bouncy
                110->119 not bouncy
                120->121 bouncy
                и т.д. то потом становится очень заморочливо найти процент. Нужно придумыватьс сложную эвристику - когда остановиться перед тем, как считать по одному числу вместо блоками... Вобщем, согласен с комментарием, не интуитивно! :)
                Ответить

                • ava bormand 19.05.2012 16:24 # 0

                  (- i 1) кстати помогает.
                  Ответить

                • ava bormand 19.05.2012 16:30 # 0

                  http://ideone.com/fWCVc
                  Ответить

                  • ava wvxvw 19.05.2012 16:44 # 0

                    Угу, только это все равно не хорошо, т.как можно просчитать на сколько увеличить счетчик цикла, а не перебирать последовательно все подряд. И, в принципе, можно так же на основе этого просчитать, а нужно ли перебирать все подряд, чтобы не "перепрыгнуть" заданный процент - но получается сложно.
                    Ответить

                  • ava wvxvw 19.05.2012 23:20 # +1 

                    http://pastebin.com/4B8BhdVk

                    Но можно было еще и не прыгающих заоптимизировать :)
                    Ответить

    • ava JavaGovno 19.05.2012 21:20 # +4

      Do you want to come back to my place, bouncy bouncy?
      Ответить

    • ava lucidfoxGovno 20.05.2012 19:45 # +3

      А что, если проверять упорядоченность первых производных от периодической функции F(x, i) = kx+T_i, где i - номер десятичного знака?
      Ответить

    • ava unu-foja 21.05.2012 17:59 # 0

      Вроде по биномиальным коэффициентам можно построить табличку, в зависимости от длины числа и вида "префикса" (== / <= / >= / bouncy). Не нужно будет перебирать варианты, а только разряды.
      Ответить

    Добавить комментарий