Найдите целое число n> 0, которое содержит следующие три условия:

Некоторое определение для стартеров: flip (n) - это поворот на 180 градусов семисегментного номера шрифта дисплея, поэтому шрифт из 2-х семи сегментов будет перевернут на 2. 0,1,2,5,8 будет сопоставлены с самим собой. 6 → 9, 9 → 6 и 3,4,7 не определены. Поэтому любое число, содержащее 3,4,7, не будет гибким. Дополнительные примеры: flip (112) = 211, flip (168) = 891, flip (3112) = не определено.

(Кстати, я вполне уверен, что flip (1) должен быть undefined, но домашнее задание говорит, что flip (168) = 891, поэтому в отношении этого назначения определяется flip (1))

Оригинальная задача: Найти целое число n > 0, которое содержит следующие три условия:

  • Определяется flip (n) и flip (n) = n
  • Определяется флип (n * n)
  • n делится на 2011 год → n %2011 == 0

Наше решение, которое вы можете найти ниже, похоже, работает, но оно не находит ответа хотя бы не на 2011 год. Если я использую 1991 вместо этого (я искал какой-то "базовый" номер, для которого проблема могла быть решена) Я получаю довольно быстрый ответ, говорящий о 1515151. Таким образом, основная концепция, похоже, работает, но не для данной "базы" в домашнем задании. Я что-то пропустил?

Решение, написанное в псевдокоде (у нас есть реализация в Small Basic, и я сделал многопоточность в Java):

for (i = 1; i < Integer.MaxValue; i++) {
  n = i * 2011;
  f = flip(n, true);
  if (f != null && flip(n*n, false) != null) {
    print n + " is the number";
    return;
  }
}


flip(n, symmetry) {
  l = n.length;
  l2 = (symmetry) ? ceil(l/2) : l;
  f = "";

  for (i = 0; i < l2; i++) {
    s = n.substr(i,1);
    switch(s) {
      case 0,1,2,5,8:
        r = s; break;
      case 6:
        r = 9; break;
      case 9:
        r = 6; break;
      default:
        r = "";
    }
    if (r == "") {
      print n + " is not flippable";
      return -1;
    } elseif (symmetry && r != n.substr(l-i-1,1)) {
      print n + " is not flip(n)";
      return -1;
    }
    f = r + f;
  }
  return (symmetry) ? n : f;
}

Ответы

Ответ 1

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

Я начну с списка всех чисел, которые удовлетворяют 2 критериям (число и его отражение будут одинаковыми, т.е. легкомысленно симметричными и что оно кратно 2011), менее 10 ^ 11:

192555261 611000119 862956298 988659886 2091001602 2220550222 2589226852 6510550159 8585115858 10282828201 12102220121 18065559081 18551215581 19299066261 20866099802 22582528522 25288188252 25510001552 25862529852 28018181082 28568189582 28806090882 50669869905 51905850615 52218581225 55666299955 58609860985 59226192265 60912021609 68651515989 68828282889 69018081069 69568089569 85065859058 85551515558 89285158268 91081118016 92529862526 92852225826 95189068156 95625052956 96056895096 96592826596 98661119986 98882128886 98986298686

Здесь имеется 46 номеров, все легкомысленно симметричные в соответствии с определением и кратные 2011, под 10 ^ 11. Похоже, что кратные 2011 года, которые удовлетворяют этому условию, станут более слабыми, потому что по мере увеличения количества цифр меньшее количество кратных будет статистически палиндромами.

т.е. для любого заданного диапазона, скажем, [1, 10 ^ 11] (как и выше), было 46. Для смежного диапазона равной ширины: [10 ^ 11 + 1, 2 * 10 ^ 11], можно предположить, 46 или около того. Но по мере того как мы продолжаем с интервалами с одинаковой шириной в более высоких степенях 10, число чисел одинаково (потому что мы анализируем интервалы с равной шириной), хотя состояние палиндрома теперь падает на большее число цифр, поскольку число цифр увеличивается. Таким образом, приближаясь к бесконечности, мы ожидаем, что число палиндромов на любом фиксированном интервале будет приближаться к 0. Или, более формально (но без доказательства) для каждого положительного значения N, с вероятностью 0, данный интервал (заданной ширины) будет иметь больше N кратных 2011 года, которые являются палиндромами.

Таким образом, количество палиндромов, которое мы можем найти, будет уменьшаться по мере продолжения исчерпывающего поиска. В соответствии с вероятностью того, что для любого найденного палиндрома квадрат будет гибким, мы предполагаем равномерное распределение квадратов палиндромов (поскольку у нас нет анализа, чтобы сказать нам иначе, и нет оснований полагать иначе), а затем вероятность того, что любой заданный квадрат из d цифр длины будет гибким является (7/10) ^ d.

Начнем с наименьшего такого квадрата. Мы нашли

192555261 ^ 2 = 37077528538778121

который уже имеет 17 цифр, что дает вероятность около 0,002 (приблизительно 1/430), которую он легко определить. Но уже к тому времени, когда мы достигли последнего в списке:

98986298686 ^ 2 = 9798287327554005326596

длина которого составляет 24 цифры, и имеет вероятность того, что менее 1/5000 будет определено с легкостью.

Так как поиск продолжается в более высоких числах, количество палиндромов уменьшается, а вероятность того, что любой найденный палиндромный квадрат является гибким, также уменьшается - клинок с двойной кромкой.

Осталось найти какое-то соотношение плотностей и, соответственно, увидеть, насколько невероятным найти решение является... Хотя интуитивно понятно, что поиск решения становится менее вероятным вероятностно (что ни в коем случае не исключает того, что один или существует даже большое количество решений (возможно, бесконечное число?)).

Удачи! Надеюсь, кто-то решит это. Как и во многих проблемах, решения часто не так просты, как запуск алгоритма на более быстрой машине или с большим количеством parallelism или в течение более длительного периода времени или еще много чего, но с более сложной техникой или более изобретательными методами атаки на проблему, которые сами по себе являются полем. Ответ, число, имеет гораздо меньший интерес (обычно), чем метод, используемый для его получения.

Ответ 2

Вы просматриваете все числа, делящиеся на 2011 год, а затем проверяете, являются ли они переворотом самих себя. Но после того, как вы достигли 7-значных чисел, условие, что это будет переворот самого себя, является более ограничительным, чем условие того, что оно будет делиться к 2011 году. Поэтому я предлагаю вам вместо этого перебирать все числа, которые могут быть построены без цифры 3, 4, 7, а затем построить число, которое переворачивается само по себе заранее, возможно, скрещивая среднюю цифру, если средние цифры составляют 11, 22, 55 или 88. Затем проверьте на делимость к 2011 году, затем проверьте, n*n является гибким.

Быть очень, очень осознавая возможность того, что n*n попадет в цельное переполнение. Когда вы достигнете 5-значного числа для базы, ваш n будет длиной 9 или 10 цифр, а n*n будет длиной 18-21.

Ответ 3

Не обязательно полное решение, больше похожее на мыслительный процесс, который может помочь вам в этом.

  • n = flip (n) = > n - палиндром (поворот на 180 ° в flip()), n состоит только из чисел, которые отображаются в себя в flip(), то есть: 0, 1, 2, 5, 8
  • flip (n * n). Таким образом, n * n может не содержать 3, 4, 7
  • n %2011 = 0.
  • n > 0.