Си диез / Говнокод #11013 Ссылка на оригинал

0

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  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
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
private static BigInteger result = 0;
        static BigInteger F1 = 1;
        static BigInteger F2 = 1;
        static BigInteger provv;
        static BigInteger provv2;

        static void Main(string[] args)
        {
            for (BigInteger number = 3; result == 0; number++)
            {
                provv2 = F2;
                F2 = F2 + F1;
                F1 = provv2; ;
                if (HasProperty(F2.ToString()))
                    result = number;
            }
        }

        private static bool HasProperty(string number)
        {
            if (number.Length < 9)
                return false;
            if (IsPandigital(number.Substring(0, 9)))
                if (IsPandigital(number.Substring(number.Length - 9, 9)))
                    return true;
            return false;
        }

        private static bool IsPandigital(string result)
        {
            int repetitions;
            for (int count = 0; count < 9; count++)
            {
                repetitions = 0;
                for (int count2 = 0; count2 < 9; count2++)
                {
                    if (result.ElementAt(count).ToString() == "0")
                        return false;
                    if (result.ElementAt(count).ToString() == result.ElementAt(count2).ToString())
                    {
                        repetitions++;
                        if (repetitions == 2)
                            return false;
                    }
                }
            }
            return true;
        }

http://projecteuler.net/problem=104
http://projecteuler.net/thread=104;page=6


>brute force approach,solved aproximately in 24 hours
>solved aproximately in 24 hours
>24 hours
>24
>hours

Терпеливый, сука!

Запостил: TheHamstertamer TheHamstertamer, (Updated )

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

    • ava quest # Ссылка на оригинал 0 ⇈

      Не теряешь ли ты пандигитальность первых 9 цифр, когда берёшь остаток по модулю 10^9 вместо самого числа?
      Ответить

      • ava bormand # Ссылка на оригинал 0 ⇈

        А тут 2 уровня проверки - quick and dirty проверка последних 9 цифр (считаются по модулю 10^9), и только если они пандигитальны - заставляю gmp вычислить число полностью, и смотрю в нем первые 9 цифр.
        Ответить

        • ava quest # Ссылка на оригинал 0 ⇈

          Так если тебе всё равно приходится считать 100500е число Фибоначчи по-честному, то не лучше ли делать это сразу? Причём изначально храня его в строке в 10ичном виде.
          Ответить

            • ava quest # Ссылка на оригинал 0 ⇈

              Не очень понял - есь возможность честно посчитать 100500е число Фибоначчи, не посчитав 100499е, 100498е, 100497е итд?
              Я в курсе про формулу для общего члена, но неужели она применима для длинных чисел?
              Ответить

              • ava bormand # Ссылка на оригинал 0 ⇈

                Есть вот такая вот формулка с матрицей:
                | 1 1 | ^ (n-1) = | f(n)   f(n-1) |
| 1 0 |           | f(n-1) f(n-2) |

                Если возводить ее по-тупому - получаем все числа фибоначчи по порядку. Если же воспользоваться быстрым возведением в степень (например через битовое разложение n) - то можно быстро найти нужное нам число за О(log(n)) умножений...

                В gmp используется похожая формулка.
                Ответить

                • ava quest # Ссылка на оригинал 0 ⇈

                  Хм, понятненько.
                  А нельзя ли попробовать воспользоваться формулой Ф^n? Точности первых 9 знаков как раз хватит.
                  Ответить

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

Переведи на "PHP", guest!

    А не использовать ли нам bbcode?

    ↑
    8
    ↓