Блог пользователя Ram_iL

Автор Ram_iL, 12 лет назад, По-русски

Здравствуйте!

Не так давно столкнулся с двумя задачками, связанными с перестановками. Решить их у меня не получилось, но мне бы хотелось разобраться, как решать задачи такого типа за полиномиальное время. Прошу помощи.

1) Условие: Дано число n и массив b — некая перестановка чисел от 1 до n. Нужно найти какую-нибудь перестановку a (также из n элементов), чтобы для каждого i (1  ≤  i  ≤  n) выполнялось равенство b[a[a[i]]] = i. К примеру, если нам дана перестановка b = (3, 4, 1, 2), то в качестве ответа можно вывести перестановку a = (2, 3, 4, 1). Если искомой перестановки a не существует, вывести "0".

2) Условие: Из заданной перестановки нужно извлечь квадратный корень. Здесь можно прочесть полное условие этой задачи (задача P).

Заранее всем спасибо!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

Автор Ram_iL, 12 лет назад, По-русски

Здравствуйте)

Недавно наткнулся на одну занимательную, на мой взгляд, задачу. Несколько дней думал, но в итоге решить полностью так и не удалось. Интересно узнать, как она все-таки решается. Буду рад любым идеям.

Условие таково: доказать, что для любого натурального n ≥ 12 найдется такая перестановка чисел от 1 до n {π1, π2, π3, ..., πn}, что πi + i является полным квадратом для любого 1 ≤ i ≤ n .

P.S. Заранее прошу прощения, если задача широко известна и где-то уже обсуждалась. Я не нашел.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится