Tiodor
offline
Опыт:
76,834Активность: |
Задача: упорядочить
Вот собственно...
мы задаем число N. затем создается двумерный массив а(n,n) нам нужно сделать вот такую перестановку числа рандомные хз как надо это сделать =\ |
30.03.2012, 14:35 | #1
+1/−1
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J64_
offline
Опыт:
4,724Активность: |
для таких задач сначала пишем по порядку какие индексы будут использоваться, анализируем, делаем решение для любого N.
иногда решения бывают разными при четном n и нечетном. -> проверяем обе, желательно при больших n. (с) Кэп
для 4x4
3 3, 2 3 x-1
3 2, 3 3 y+1 1 2, 3 2 x+2 1 4, 1 2 y-2 4 4, 1 4 x-3 4 1, 4 4 y+3 1 1, 4 1
для 5x5
3 3, 2 3 x-1
2 3, 2 4 y+1 2 4, 4 4 x+2 4 4, 4 2 y-2 4 2, 1 2 x-3 1 2, 1 5 y+3 1 5, 5 5 x+4 5 5, 5 1 y-4 1 1, 5 1
Как мы видим, разница индексов с каждым разом увеличивается на один, и каждый раз меняется знак операции(плюс, минус). Если смотреть попарно, то количество действий будет равна: 2 * (n - 1) + 1.
Решение на паскале
|
30.03.2012, 17:26 | #2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
ScorpioT1000
Работаем
offline
Опыт: отключен
|
Вот еще логическое решение, если надо:
Тока там косяк - он заменяет соседнюю ячейку при переходе на новый виток =\ потом доделаю) если надо...
» Весь код
|
30.03.2012, 17:44 | #3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
x := n div 2 + 1;
как это в бейсике ввести, чет я туплю =\ Tiodor добавил:
уже нашел Judycaster64, сверху созданная матрица
внизу упорядоченная =\ |
30.03.2012, 18:02 | #4
+1/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J64_
offline
Опыт:
4,724Активность: |
Tiodor, это задание №2, или это моих рук дело? |
30.03.2012, 18:26 | #5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
п.с. это по твоему коду |
30.03.2012, 18:26 | #6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J64_
offline
Опыт:
4,724Активность: |
Tiodor, хз что там ты у себя в бэйсике наделал, но код выше, при нечетных n, работает как часы, а при четном n неправильно работал. Исправил
|
30.03.2012, 19:25 | #7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
Judycaster64, хз, все писал как у тебя
попробую вечером этот код Tiodor добавил:
все равно не работает, я хз или ты понял как оно должно работать =\ что оно делает? =\ оно меняет левый нижний элемент на первый элемент Tiodor добавил: да и некоторые элементы оно меняет в другую сторону... ну то есть должно по часовой стрелке, а оно меняет против |
30.03.2012, 22:49 | #8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
WaterMan
J.R.R.
offline
Опыт:
17,019Активность: |
Самое простое и очевидное решение (не рациональное вроде, хз, ты максимум не указал) на паскале:
» жми
Прилагаю также в скомпилированном виде (в input.txt вводишь размерность массива и элементы, output.txt выведет тебе элементы по порядку). Упорядочивание сделаешь сам, как надо, тут обход только и вывод для наглядности. Если непонятен где-то код - пиши сюда или в аську, разберемся. Попозже выложу описание алгоритма. В целом, вроде работает нормально, хз насколько отличается от предыдущих решений, особо не заморачивался над придумыванием кода. |
31.03.2012, 17:21 | #9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
у меня пока нет возможности искать значения функций, но что значит maxlongint fillchar continue; |
31.03.2012, 18:55 | #10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
WaterMan
J.R.R.
offline
Опыт:
17,019Активность: |
Tiodor, maxlongint - не функция. Это я так, чтобы зациклить цикл (извиняюсь за тавтологию). Maxlongint - максимальное значение, которое может принимать переменная типа longint (2*10^9), можно вместо нее просто большое число, за пределами максимального размера массива (10^6 мб, хз, как у тебя там максимальные данные в задаче)
fillchar - заполнить массив определенным числом, символом (в данном случае, false'ами). Вообще, это не обязательно зависит от компилятора. Мой компилятор (free pascal) присваивает всем переменным типа boolean (логический, булев тип) по умолчанию false. Но на всякий случай я всегда пишу fillchar. continue - переход к следующему шагу цикла. То есть, в данном случае он просто возвращается к началу цикла. Это сделано для того, чтобы он следом нижние условия не читал, а вернулся на начало. WaterMan добавил: Tiodor, а вообще, ты в алгоритме разобрался и расписать надо? |
31.03.2012, 19:29 | #11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
WaterMan, лучше распиши и я себе перепишу... потому, что бейсик канешн с паскалем чем-то похож... но все же я скорее запутаюсь |
31.03.2012, 20:59 | #12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
WaterMan
J.R.R.
offline
Опыт:
17,019Активность: |
Tiodor, примерно так: Создаем массив логического (булев) типа, который будет хранить номера ячеек, которые мы уже посетили (если мы уже прошли ячейку a[3,4], то в массиве b[3,4] будет храниться true). Заводим переменные c и d, которые хранят в себе смещение для координат массива (c для i, d для j, c=0, d=1, так как сначала пойдем вправо). Делаем бесконечный цикл, который не завершится пока мы его не прервем. В начале цикла проверяем, если из ячейки, в которой мы сейчас находимся нельзя пройти ни влево, ни вправо, ни вверх, ни вниз (то есть, ячейки вокруг были посещены), то цикл завершается. Если же нет, делаем ячейку, в которой мы сейчас находимся посещенной (b[i,j]:=true). Далее меняем координаты текущей ячейки на координаты плюс смещение (i:=i+c, j:=j+d, c и d мы завели вначале). Далее идем в указанном направлении, пока не наткнемся на уже посещенную ячейку либо не выйдем за пределы массива. Как только наткнемся либо выйдем, меняем направление (присваивая переменным c и d новые значения, в коде я укзал, как. Думаю, тут должно быть понятно, если шли вправо, идем вниз, если вниз, идем влево и т.д.). Таким образом, мы дойдем до центра массива, параллельно в цикле можно его упорядочивать или выводить, как угодно, цикл проходит массив именно в нужном порядке. Все понятно? |
31.03.2012, 21:15 | #13
+1/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J64_
offline
Опыт:
4,724Активность: |
Tiodor, наверное я не совсем понял тебя, судя по рисунку, тебе ведь нужно чтобы циферка из конца стрелки была впереди?
т.е. вместо -1 будет 52, вместо 7 -1, вместо 60 7 и так далее... короче высылаю программу - стандартная, input.txt, output.txt. в первой строке - n, начиная со второй - элементы массива. |
01.04.2012, 07:10 | #14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
вот что происходит... покажи свой скрин, как оно у тебя
тем более a[n, 1] := a[1, 1];
это команда просто абсурдная зачем заменять это число? Tiodor добавил:
сверху изначальная матрица, внизу упорядоченная
а вот так должно быть
|
||||||||||||||||||||||||||||||||||||||||||||||||||
01.04.2012, 15:34 | #15
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Tiodor
offline
Опыт:
76,834Активность: |
Вот собственно решение
((код
Option Base 1 Sub Zadacha() Dim A() As Double Dim i, j, l, h, n, s, m, n2, m2, p2, q2, nom, nom1, k As Integer Dim indeks, indeks1, indeks2, indeks3 As Integer n = InputBox("n") ReDim A(n, n) l = InputBox("max") h = InputBox("min") For i = 1 To n For j = 1 To n A(i, j) = Int((h - l + 1) * Rnd + l) Cells(i, j).Value = A(i, j) Next j Next i indeks = 1 indeks1 = n indeks2 = n indeks3 = 1 n2 = n m2 = 1 p2 = n q2 = 2 nom = 0 nom1 = 0 For k = 1 To 2 * n - 1 If k Mod 2 <> 0 Then nom = nom + 1 If nom Mod 2 <> 0 Then If q2 > 2 Then s = A(indeks, n2) A(indeks, n2) = m n2 = n2 - 1 indeks = indeks + 1 Else s = A(indeks, n2) A(indeks, n2) = A(indeks, 1) n2 = n2 - 1 indeks = indeks + 1 End If Else s = A(indeks1, m2) A(indeks1, m2) = m m2 = m2 + 1 indeks1 = indeks1 - 1 End If Else nom1 = nom1 + 1 If nom1 Mod 2 <> 0 Then m = A(p2, indeks2) A(p2, indeks2) = s p2 = p2 - 1 indeks2 = indeks2 - 1 Else m = A(q2, indeks3) A(q2, indeks3) = s q2 = q2 + 1 indeks3 = indeks3 + 1 End If End If Next k For i = 1 To n For j = 1 To n Cells(i, j + n + 2).Value = A(i, j) Next j Next i End Sub )) Отредактировано Tiodor, 02.04.2012 в 19:22. |
02.04.2012, 19:16 | #16
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J64_
offline
Опыт:
4,724Активность: |
Tiodor, ты хоть проверял?
input.txt
5 29 -47 -62 38 -17 -56 -36 71 52 34 -25 18 21 25 -13 52 -11 14 -1 -1 44 5 25 -54 13 output.txt
29 -47 -62 38 29 44 -36 71 -56 34 -25 -11 18 25 -13 52 -1 14 52 -1 13 5 25 -54 -17 где у меня неверно?
потому что если попарно смотреть, то только эта замена остается(см. в 2 посте). В самую правую ячейку самой верхней строки записывает значение самой левой ячейки самой верхней строки.
и кстати ты упорядоченную таблицу как-то неверно сделал, ну там -56 потерял и т.п. :) |
04.04.2012, 14:14 | #17
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|