|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
03.12.2011, 14:32 | #1 |
Форумчанин
Регистрация: 02.04.2011
Сообщений: 136
|
Посчитать число изломов (углов) у линии, проходящей спиралью по массиву
Здравствуйте!
Помогите с задачей, идею подкиньте! ничего путного не лезет в голову суть в том что дана матрица NxM (любые числа)! сказано что линия начинается в верхнем левом углу (А[1,1]) идёт вдоль первой строки до конца, затем идёт в низ (тоесть по правому крайнему столбику донизу), затем поворачивает влево и идет по самой нижней строке и так она колесит по матрице (получается спираль) и доходит доконца! Нужно определить сколько углов образует эта прямая(красный цвет), угла (синие) |
03.12.2011, 14:54 | #2 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Как-то вот так..
Код:
Предпочитаю на "ты".
|
03.12.2011, 17:38 | #3 |
Форумчанин
Регистрация: 02.04.2011
Сообщений: 136
|
Непомешали бы!
p.s. если не трудно!) |
03.12.2011, 22:09 | #4 |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Сорри, я ошибся чуток.. Меня поправили ).
И тот человек сам объяснит тогда p.s. если не трудно )) Юля, тебе +1, и сиб!
Предпочитаю на "ты".
|
03.12.2011, 22:14 | #5 |
Регистрация: 10.11.2009
Сообщений: 5
|
Код:
|
04.12.2011, 22:23 | #6 |
Форумчанин
Регистрация: 02.04.2011
Сообщений: 136
|
Не объясните почему оно именно так?????
|
05.12.2011, 22:59 | #7 |
Форумчанин
Регистрация: 02.04.2011
Сообщений: 136
|
что никто не поможет разобраться??? вроде код простой а смысл в чём???
|
06.12.2011, 12:16 | #8 | |
Форумчанин
Регистрация: 05.09.2011
Сообщений: 869
|
Цитата:
Сначала рассмотрим горизонтальную матрицу (то есть столбцов больше, чем строк). Нарисуй ее, как ты рисовал, и проведи спираль, отметив повороты. Потом заметь, что в середине несколько столбцов не содержат ни поворотов, ни начальных или конечных точек. Следовательно, их можно удалить из матрицы, не изменив икомого кол-ва поворотов. Удалишь и увидишь, что матрица стала квадратной. Причем сторона этого квадрата равная количеству строк. Теперь, если добавлять к этой квадратной матрице один столбец (слева) и одну строку (снизу) и продолжить спираль, а также одновременно повернуть ее на 180 градусов (чтоб начало спирали снова было вверху слева), то мы увидим, что добавилось 2 поворота. Отсюда нетрудно вывести формулу для этого случая. В этот момент может показаться, что этот ответ будет верен для всех матриц (то есть и для вертикальных тоже), потому что вся картина представляется симметричной. Именно такую ошибку я и сделал, и Юля меня поправила (сиб еще раз!)). Картина на самом деле не совсем симметрична, поскольку есть ДВА параметра, связанных с центральным углом: направление И начало спирали (перед большой строной или перед малой). Но чтобы разобраться нужно проделать то же самое. Рисуешь вертикальную матрицу и удаляешь все "лишние" строки. Но теперь оказывается, что если не удалять точку окончания спирали, то матрица не дотягивает до квадратной, остается кособокой (строк на 1 больше, чем столбцов). Конечно, окончание спирали - это не поворот, и кажется, что эту строку тоже можно удалить.. Но при попытке это сделать сразу видно, что раз удаляется звено спирали, то исчезает и поворот, так что это делать нельзя. Так что оставляем как есть и считаем повороты, и их оказывается на 1 больше, чем в горизонтальной матрице такого же размера. Дальше все точно так же как - добавляем по одному столбцу и строке и вертим матрицу. Формула та же самая, но плюс 1. По сути, удаление центральных столбцов и строк не обязательно. Можно просто начать с самой маленькой матрицы (2xN или Mx2) и наращивать ее по одному слою (тем же способом). Кому что удобнее )). Просто удаление центральных строк/столбцов сразу бросается в глаза, и очень хочется его приткнуть )).
Предпочитаю на "ты".
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Посчитать число сочетаний (Cnk) | pollypolly | Visual C++ | 0 | 07.11.2011 21:30 |
Дано целое число Х. Посчитать количество бит равных 1 | Preidman | Общие вопросы C/C++ | 2 | 29.03.2011 18:01 |
Посчитать число одинаковых букв | ValdisZ | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 21.12.2010 20:07 |
Посчитать большое число | Dimbur | Помощь студентам | 2 | 08.05.2010 18:40 |
Посчитать число цифр в тексте и их сумму | Иван 883 | Помощь студентам | 3 | 17.04.2009 13:38 |