Определить, где будет находиться робот, который движется по спирали, через N шагов

@catauggie · Регистрация: 20.09.2018

Студворк — интернет-сервис помощи студентам

Робот расположен в точке (0,0). Робот движется по спирали в следующем порядке: (0,0). (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1). (1,0), (1,1). (1,2),..

Определить, где будет находиться робот, который движется по спирали, через N шагов

Определить, где будет находиться робот через N шагов.
Формат ввода:
Единственная строка входного файла содержит одно целое неотрицательное число N (Q < N < 1012) - количество сделанных шагов.
Формат вывода:
Выведите два числа - координаты клетки, в которой окажется робот через N шагов.
Я начал делать так, но не совсем понимаю, как разобраться с алгоритмом определения координат:

Python
1
2
3
4
5
import math
n = int(input('число шагов: '))
for i in range(n):
    ''''if q=(n)**(1/2)>2:
        x=''''

Если вам не трудно, подскажите, пожалуйста, алгоритм действий. Заранее большое спасибо.

@catauggie · 05.05.2019, 20:35 **[ТС]**

Робот перейдет на 2ой квадрат через 9 шагов, на 3-ий - через 25 шагов и т.д.

Можно сравнить движение робота со спиралью Архимеда https://ru.wikipedia.org/wiki/... 0%BB%D1%8C
где наши значения шагов 16 ,25... - наподобие периода [0+2pi*k,2pi+2pi*k]. Однако как это реализовать в питоне мне не понятно.

@Viktorrus · 05.05.2019, 20:40

catauggie, Алгоритма я вижу два.
1) В цикле двигаться по одному шагу, определяя когда меняется направление движения (на углах квадрата).
2) В движении по спирали есть определенная зависимость получающихся квадратов, используя которую можно сразу вычислить точку с наибольшими координатами (x,y). То есть для заданного N можно сразу вычислить, какая из точек (1,1), (2,2), (3,3), ... , которые проходит робот, станет максимальной, и затем будет осуществлено еще какое то небольшое количество шагов, не превышающее полный квадрат.

Добавлено через 5 минут
catauggie, Вы немного ошиблись, зависимость от квадрата к квадрату по количеству шагов будет несколько иная.
0, 8, 16, 24, 32, 50, ... что можно записать формулой n*8

@catauggie · 05.05.2019, 20:45 **[ТС]**

возможно. но как реализовать алгоритм?

@Viktorrus · 05.05.2019, 20:46

В питоне деление N//8 даст вам наибольшее значение координат.
Например для числа 42 , 42//8 равно 5 и остаток 2. Отсюда точка с максимальными координатами (5, 5). И еще два шага влево. Получаем ответ в виде координат (3, 5).

@catauggie · 05.05.2019, 20:47 **[ТС]**

вроде на полный период не похоже

@Viktorrus · 05.05.2019, 20:49

После получение точки с максимальными координатами, мошно пойти по кругу в цикле, а можно использовать зависимость сторон квадратов, что бы вычислить длину стороны и использовать ее для получения ответа.

@catauggie · 05.05.2019, 20:51 **[ТС]**

Допустим:

Python
1
2
3
4
import math
n = int(input('число шагов: '))
if n mod 8 = 0:
    print(x, y)

@Viktorrus · 05.05.2019, 20:51

catauggie, Вы 2 точки не дорисовали, должен быть полный квадрат

@catauggie · 05.05.2019, 20:52 **[ТС]**

Хотя следует добавить еще зависимость типа q = n mod 8 и тогда x=q, y=q

@Viktorrus · 05.05.2019, 20:53

Когда робот идет он же не оставляет пропусков. Каждый новый квадрат, это полный квадрат.

@catauggie · 05.05.2019, 20:54 **[ТС]**

Так больше похоже на правду?

@Viktorrus · 05.05.2019, 21:02

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

Добавлено через 31 секунду
catauggie, Последний рисунок правильный

Добавлено через 4 минуты
Поэтому делите на 8 с усечением и получаете максимальную точку в верхнем правом углу Для начального ресунка, который в условии. А для последнего рисунка это будет минимальная точка в нижнем левом углу, если добавить координатам минусы. Но лучше оперировать с рисунком, который дан в условии. Когда первый шаг вверх.

@catauggie · 05.05.2019, 21:02 **[ТС]**

А если так:

@catauggie · 05.05.2019, 21:04 **[ТС]**

не там условие поменялось. теперь первый шаг вниз

Добавлено через 44 секунды
просто не знаю как заменить картинку в описании темы

@Viktorrus · 05.05.2019, 21:08

Когда вниз, то немного усложняется. Тогда квадрат будет заканчиваться внизу слева и координаты будут наименьшими отрицательными.

Добавлено через 50 секунд
На последнем рисунке все правильно

Добавлено через 58 секунд
Назначте значение для N и вычислим для него координаты.

@catauggie · 05.05.2019, 21:12 **[ТС]**

Ок. Мы определились с рисунком и условием. Я начну реализовывать код так:

Python
1
2
3
4
5
6
7
import math
n = int(input('число шагов: '))
if n mod 8 = 0:
    q=n/8
    x=-q*h
    y=-q*h
...........

При этом h - это это номер квадрата

Добавлено через 34 секунды
однако непонятно, как искать h

@Viktorrus · 05.05.2019, 21:39

Предположим N равно 35. Тогда 35//8 будет 4 и остаток 3. Значит наименьшая точка (-4, -4). Дальше
(-4, -5) -> (-3, -5) -> (-2, -5)
Ответ, на шаге 35, будет в координате (-2, -5).

Добавлено через 8 минут
Сначала делите используя оператор N//8 . Он усечет до целого числа и получите чему равны x и y. Затем ищете остаток (оставшиеся шаги). N%8, получаете остаток. Дальше или идете по шагам в цикле или используете зависимость длин сторон у квадратов.

Добавлено через 1 минуту
Длина стороны каждого следующего квадрата увеличивается на 2.

@catauggie · 05.05.2019, 21:40 **[ТС]**

Но нам следует еще записать зависимость наименьшей координаты от промежутка шагов

@Viktorrus · 05.05.2019, 21:58

Номер квадрата умножить на 2 даст количество шагов в стороне квадрата.
N//8 *2 дает количество шагов в стороне последнего квадрата.

Добавлено через 4 минуты
Если l = N//8 *2 , то разделив остаток на l получим сколько у нас в остатке полных сторон квадрата и на какой стороне искать нужную точку. И в зависимости от того, что это за сторона, прибавляем или отнимаем от координать несколько оставшихся шагов.

Добавлено через 6 минут
Кстати, зачем Вы импортируете модуль math? Для тех вычислений которые здесь, он не нужен.

Добавлено через 2 минуты
И еще одно замечание. Деление по модулю в питоне осуществляется оператором % .

Новые блоги и статьи Все статьи Все блоги /
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 20:35 [ТС]
	Робот перейдет на 2ой квадрат через 9 шагов, на 3-ий - через 25 шагов и т.д. Можно сравнить движение робота со спиралью Архимеда https://ru.wikipedia.org/wiki/... 0%BB%D1%8C где наши значения шагов 16 ,25... - наподобие периода [0+2pik,2pi+2pik]. Однако как это реализовать в питоне мне не понятно. 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 20:40
	catauggie, Алгоритма я вижу два. 1) В цикле двигаться по одному шагу, определяя когда меняется направление движения (на углах квадрата). 2) В движении по спирали есть определенная зависимость получающихся квадратов, используя которую можно сразу вычислить точку с наибольшими координатами (x,y). То есть для заданного N можно сразу вычислить, какая из точек (1,1), (2,2), (3,3), ... , которые проходит робот, станет максимальной, и затем будет осуществлено еще какое то небольшое количество шагов, не превышающее полный квадрат. Добавлено через 5 минут catauggie, Вы немного ошиблись, зависимость от квадрата к квадрату по количеству шагов будет несколько иная. 0, 8, 16, 24, 32, 50, ... что можно записать формулой n*8 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 20:45 [ТС]
	возможно. но как реализовать алгоритм? 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 20:46
	В питоне деление N//8 даст вам наибольшее значение координат. Например для числа 42 , 42//8 равно 5 и остаток 2. Отсюда точка с максимальными координатами (5, 5). И еще два шага влево. Получаем ответ в виде координат (3, 5). 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 20:47 [ТС]
	вроде на полный период не похоже 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 20:49
	После получение точки с максимальными координатами, мошно пойти по кругу в цикле, а можно использовать зависимость сторон квадратов, что бы вычислить длину стороны и использовать ее для получения ответа. 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 20:51
	catauggie, Вы 2 точки не дорисовали, должен быть полный квадрат 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 20:52 [ТС]
	Хотя следует добавить еще зависимость типа q = n mod 8 и тогда x=q, y=q 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 20:53
	Когда робот идет он же не оставляет пропусков. Каждый новый квадрат, это полный квадрат. 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 20:54 [ТС]
	Так больше похоже на правду? 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 21:02
	Предыдущий квадрат заканчивается, только когда он переходит на новый квадрат. А у Вас робот пройдет еще две точки по старому квадрату. Добавлено через 31 секунду catauggie, Последний рисунок правильный Добавлено через 4 минуты Поэтому делите на 8 с усечением и получаете максимальную точку в верхнем правом углу Для начального ресунка, который в условии. А для последнего рисунка это будет минимальная точка в нижнем левом углу, если добавить координатам минусы. Но лучше оперировать с рисунком, который дан в условии. Когда первый шаг вверх. 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 21:02 [ТС]
	А если так: 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 21:04 [ТС]
	не там условие поменялось. теперь первый шаг вниз Добавлено через 44 секунды просто не знаю как заменить картинку в описании темы 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 21:08
	Когда вниз, то немного усложняется. Тогда квадрат будет заканчиваться внизу слева и координаты будут наименьшими отрицательными. Добавлено через 50 секунд На последнем рисунке все правильно Добавлено через 58 секунд Назначте значение для N и вычислим для него координаты. 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 21:39
	Предположим N равно 35. Тогда 35//8 будет 4 и остаток 3. Значит наименьшая точка (-4, -4). Дальше (-4, -5) -> (-3, -5) -> (-2, -5) Ответ, на шаге 35, будет в координате (-2, -5). Добавлено через 8 минут Сначала делите используя оператор N//8 . Он усечет до целого числа и получите чему равны x и y. Затем ищете остаток (оставшиеся шаги). N%8, получаете остаток. Дальше или идете по шагам в цикле или используете зависимость длин сторон у квадратов. Добавлено через 1 минуту Длина стороны каждого следующего квадрата увеличивается на 2. 0

@catauggie 24 / 5 / 0 Регистрация: 20.09.2018 Сообщений: 310
	05.05.2019, 21:40 [ТС]
	Но нам следует еще записать зависимость наименьшей координаты от промежутка шагов 0

@Viktorrus 1732 / 970 / 199 Регистрация: 22.02.2018 Сообщений: 2,693 Записей в блоге: 6
	05.05.2019, 21:58
	Номер квадрата умножить на 2 даст количество шагов в стороне квадрата. N//8 2 дает количество шагов в стороне последнего квадрата. Добавлено через 4 минуты* Если l = N//8 2 , то разделив остаток на l получим сколько у нас в остатке полных сторон квадрата и на какой стороне искать нужную точку. И в зависимости от того, что это за сторона, прибавляем или отнимаем от координать несколько оставшихся шагов. Добавлено через 6 минут* Кстати, зачем Вы импортируете модуль math? Для тех вычислений которые здесь, он не нужен. Добавлено через 2 минуты И еще одно замечание. Деление по модулю в питоне осуществляется оператором % . 0