كيف يمكنك تدوير الأبعاد اثنين المصفوفة ؟
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
مستوحاة من ريمون تشن بعد, نقول لديك 4x4 ثنائية الأبعاد مجموعة ، كتابة الوظيفة التي تدور 90 درجة.ريمون وصلات إلى حل في البرمجية الزائفة ، ولكن أود أن أرى بعض العالم الحقيقي الأشياء.
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
يصبح:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
التحديث:نيك الجواب هو الأكثر وضوحا ، ولكن هل هناك طريقة للقيام بذلك أفضل من ن^2?ماذا لو المصفوفة 10000x10000?
المحلول
هنا هو في C#
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
نصائح أخرى
O(n^2) الوقت O(1) مساحة الخوارزمية ( دون أي الحلول و دجل الاشياء!)
تدوير +90:
- تبديل
- عكس كل صف
تدوير قبل -90:
الأسلوب 1 :
- تبديل
- عكس كل عمود
الطريقة 2 :
- عكس كل صف
- تبديل
تدوير +180:
الأسلوب 1:تدوير +90 مرتين
الطريقة 2:عكس كل صف ثم عكس كل عمود (تبديل)
تدوير قبل -180:
الأسلوب 1:تدوير قبل -90 مرتين
الطريقة 2:عكس كل عمود ثم عكس كل صف
طريقة 3:تدوير +180 لأنها هي نفسها
أود أن أضيف أكثر من ذلك بقليل من التفصيل.في هذا الجواب ، مفاهيم أساسية تتكرر, وتيرة بطيئة عمدا المتكررة.الحل المقدمة هنا ليست الأكثر نحويا المدمجة ، بيد أنه المقصود بالنسبة لأولئك الذين يرغبون في معرفة ما مصفوفة الدوران الناتج التنفيذ.
أولا, ما هي المصفوفة ؟ لأغراض هذا الجواب ، مصفوفة هو مجرد الشبكة حيث العرض والارتفاع هي نفسها.ملاحظة العرض والارتفاع من مصفوفة يمكن أن تكون مختلفة ولكن البساطة, هذا البرنامج التعليمي ترى فقط المصفوفات على قدم المساواة مع العرض والارتفاع (مربع المصفوفات).و نعم ، المصفوفات هو الجمع من المصفوفة.
مثال على المصفوفات هي:2×2 و 3×3 أو 5×5.أو أكثر عموما ، ن×ن2×2 مصفوفة سوف يكون 4 مربعات لأن 2×2=4.5×5 مصفوفة سوف يكون 25 الساحات لأن 5×5=25.كل مربع يسمى عنصر أو الدخول.سوف تمثل كل عنصر مع فترة (.) في الرسوم البيانية أدناه:
2×2 مصفوفة
. .
. .
3×3 مصفوفة
. . .
. . .
. . .
4×4 مصفوفة
. . . .
. . . .
. . . .
. . . .
لذا ، ما يعني أن تدوير المصفوفة ؟ دعونا نأخذ 2×2 مصفوفة وضع بعض الأرقام في كل عنصر حتى دوران يمكن ملاحظتها:
0 1
2 3
يدور هذا بنسبة 90 درجة يعطينا:
2 0
3 1
نحن حرفيا تحولت كلها مصفوفة مرة واحدة إلى اليمين مثل تحول عجلة القيادة في سيارة.فإنه قد يساعد على التفكير في "البقشيش" ماتريكس على الجانب الأيمن.نريد أن نكتب وظيفة في بيثون ، التي تأخذ مصفوفة تدور في مرة واحدة إلى اليمين.وظيفة التوقيع سوف يكون:
def rotate(matrix):
# Algorithm goes here.
المصفوفة سيتم تحديدها باستخدام صفيف ثنائي الأبعاد:
matrix = [
[0,1],
[2,3]
]
ولذلك أول مؤشر موقف يصل إلى الصف.الثاني مؤشر موقف يصل إلى العمود:
matrix[row][column]
ونحن سوف تحدد وظيفة الأداة طباعة مصفوفة.
def print_matrix(matrix):
for row in matrix:
print row
أسلوب واحد من الدورية مصفوفة هو أن تفعل ذلك طبقة في كل مرة.ولكن ما هو طبقة?أعتقد من البصل.تماما مثل طبقات البصل ، حيث أن كل طبقة إزالتها ، ونحن نتحرك نحو المركز.غيرها من القياس هو دمية ماتريوشكا أو لعبة تمرير--الطرود.
العرض والارتفاع من مصفوفة إملاء عدد من الطبقات في هذه المصفوفة.دعونا استخدام رموز مختلفة على كل طبقة:
2×2 مصفوفة 1 طبقة
. .
. .
3×3 مصفوفة 2 طبقات
. . .
. x .
. . .
4×4 مصفوفة 2 طبقات
. . . .
. x x .
. x x .
. . . .
5×5 مصفوفة 3 طبقات
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
6×6 مصفوفة 3 طبقات
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
7×7 مصفوفة 4 طبقات
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
قد تلاحظ أن تزايد العرض والارتفاع من مصفوفة من جانب واحد ، لا دائما زيادة عدد الطبقات.أخذ فوق المصفوفات وجدولة طبقات الأبعاد ، ونحن نرى عدد طبقات يزيد مرة واحدة لكل اثنين من الزيادات من العرض والارتفاع:
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
ومع ذلك ، ليس كل طبقات تحتاج الدورية.1×1 مصفوفة هو نفسه قبل وبعد دوران.المركزية 1×1 طبقة هو نفسه دائما قبل وبعد دوران بغض النظر عن كيفية كبيرة الشاملة مصفوفة:
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
نظرا N×N مصفوفة, كيف يمكن برمجيا تحديد عدد طبقات نحن بحاجة إلى تدوير?إذا كان لنا أن تقسيم العرض أو الارتفاع من قبل اثنين من وتجاهل بقية نحصل على النتائج التالية.
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
لاحظ كيف N/2 المباريات عدد من الطبقات التي تحتاج إلى أن تكون استدارة?في بعض الأحيان عدد من للتدوير طبقات هي واحدة أقل عدد من الطبقات في المصفوفة.يحدث هذا عند الطبقة الأعمق يتكون من عنصر واحد فقط (أي1×1 مصفوفة) و لذلك لا تحتاج إلى أن تكون استدارة.فإنه يحصل ببساطة تجاهلها.
نحن بلا شك بحاجة إلى هذه المعلومات في وظيفة تدوير مصفوفة, لذلك دعونا إضافة الآن:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
الآن نحن نعرف ما هي الطبقات وكيفية تحديد عدد الطبقات التي تحتاج في الواقع الدورية ، كيف يمكننا عزل طبقة واحدة حتى نتمكن من تدوير ؟ أولا: فحص مصفوفة من الطبقة الخارجية, إلى الداخل, إلى الطبقة الأعمق.5×5 مصفوفة ثلاث طبقات في مجموع طبقتين التي تحتاج الدورية:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
دعونا ننظر في الأعمدة الأولى.موقف الأعمدة تحديد الطبقة الخارجية ، على افتراض أننا العد من 0 ، 0 ، 4:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 و 4 هي أيضا مواقف صفوف الطبقة الخارجية.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
هذا سوف يكون الحال دائما منذ العرض والارتفاع هي نفسها.لذلك يمكن أن نحدد العمود و الصف مواقف طبقة مع اثنين فقط من القيم (بدلا من أربعة).
تتحرك للداخل إلى الطبقة الثانية ، والموقف من الأعمدة هي 1 و 3.و, نعم, هل تفكر في ذلك, نفس الأمر بالنسبة الصفوف.من المهم أن نفهم نحن أن كل زيادة و إنقاص الصف و العمود المواقف عندما تتحرك للداخل إلى الطبقة التالية.
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
إذن بتفتيش كل طبقة ، نريد حلقة مع كل زيادة وخفض العدادات التي تمثل تتحرك إلى الداخل ، بدءا من الطبقة الخارجية.سوف نسمي هذه 'طبقة حلقة'.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
رمز أعلاه الحلقات من خلال (صف و عمود) مواقف من أي الطبقات التي تحتاج الدورية.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
لدينا الآن حلقة توفير مواقف الصفوف والأعمدة من كل طبقة.المتغيرات first و last تحديد مؤشر موقف أول و آخر الصفوف والأعمدة.مشيرا إلى الصف و العمود الجداول:
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
حتى نتمكن من التنقل عبر طبقات من مصفوفة.الآن نحن بحاجة إلى وسيلة التنقل داخل طبقة حتى نتمكن من التحرك حول عناصر هذه الطبقة.ملاحظة العناصر أبدا 'تقفز' من طبقة إلى أخرى ، ولكنها تتحرك في كل الطبقات.
تناوب كل عنصر في طبقة تدور طبقة كاملة.تناوب كل الطبقات في مصفوفة تدور كامل المصفوفة.هذه الجملة مهمة جدا ، لذا يرجى محاولة الخاص بك أفضل أن نفهم ذلك قبل الانتقال.
الآن نحن بحاجة إلى وسيلة تتحرك في الواقع العناصر ، أيتدوير كل عنصر ، ثم طبقة ، وفي نهاية المطاف المصفوفة.عن البساطة ، سوف تعود إلى مصفوفة 3x3 — التي لديها واحد للتدوير طبقة.
0 1 2
3 4 5
6 7 8
لدينا طبقة حلقة يوفر مؤشرات الأول والأخير الأعمدة ، وكذلك الصفوف الأول والأخير:
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
لأن المصفوفات هي دائما مربع ، نحن بحاجة فقط اثنين من المتغيرات ، first و last, لأن مؤشر المواقف هي نفسها بالنسبة الصفوف والأعمدة.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
المتغيرات الأول والأخير يمكن بسهولة أن تستخدم للإشارة إلى الزوايا الأربع من مصفوفة.وذلك لأن زوايا أنفسهم يمكن تعريفها باستخدام صيغ مختلفة first و last (لا والطرح والجمع أو إزاحة تلك المتغيرات):
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
لهذا السبب فنحن نبدأ الدوران الخارجي في أربع زوايا — سوف تدوير تلك الأولى.دعونا تسليط الضوء عليها مع *.
* 1 *
3 4 5
* 7 *
نريد مبادلة كل * مع * إلى اليمين منه.لذلك دعونا نمضي قدما طباعة من زوايا محددة فقط باستخدام صيغ مختلفة first و last:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
يجب أن يكون الإخراج:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
الآن يمكننا بسهولة مبادلة كل من الزوايا من داخل طبقة حلقة:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
مصفوفة قبل تدوير زوايا:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
مصفوفة بعد تدوير الزوايا:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
كبيرة!لدينا بنجاح استدارة كل ركن من المصفوفة.ولكن لم تدوير العناصر في منتصف كل طبقة.من الواضح أننا بحاجة إلى وسيلة بالتكرار ضمن الطبقة.
المشكلة هي إلا حلقة في وظيفة حتى الآن (لدينا طبقة حلقة) ، ينتقل إلى الطبقة التالية على كل التكرار.منذ لدينا مصفوفة واحدة فقط للتدوير الطبقة طبقة حلقة المخارج بعد تدوير فقط الزوايا.دعونا ننظر إلى ما يحدث مع أكبر 5×5 مصفوفة (حيث طبقتين تحتاج الدورية).رمز وظيفة تم حذفها ولكن فإنه لا يزال هو نفسه على النحو الوارد أعلاه:
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
الناتج هو:
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
فإنه لا ينبغي أن يكون مفاجأة أن زوايا الطبقة الخارجية تم تدويرها ، ولكن قد تلاحظ أيضا زوايا الطبقة التالية (الداخل) تم تدويرها.وهذا يجعل الشعور.لقد كتبت رمز للتنقل من خلال طبقات أيضا إلى تدوير الزوايا من كل طبقة.هذا يبدو وكأنه التقدم ، ولكن للأسف يجب علينا أن نأخذ خطوة إلى الوراء.انها مجرد ليست جيدة الانتقال إلى الطبقة التالية حتى السابق (الخارجي) طبقة بالكامل استدارة.حتى كل عنصر في طبقة وقد تناوب.الدورية فقط زوايا لن تفعل!
تأخذ نفسا عميقا.نحن بحاجة إلى حلقة أخرى.حلقة متداخلة ولا أقل.الجديد, حلقة متداخلة ، first و last المتغيرات بالإضافة إلى إزاحة للتنقل داخل طبقة.ندعو هذا حلقة جديدة لدينا 'عنصر حلقة'.عنصر حلقة زيارة كل عنصر على طول الصف العلوي ، كل عنصر أسفل الجانب الأيمن ، كل عنصر على طول الصف السفلي و كل عنصر حتى الجانب الأيسر.
- تتحرك إلى الأمام على طول الصف العلوي يتطلب العمود مؤشر أن تكون زيادة.
- تتحرك إلى أسفل الجانب الأيمن يتطلب الصف مؤشر إلى أن زيادة.
- تتحرك إلى الخلف على طول الجزء السفلي يتطلب العمود مؤشر إلى أن decremented.
- تتحرك صعودا الجانب الأيسر يتطلب الصف مؤشر إلى أن decremented.
هذا يبدو معقدة لكنها سهلة لأن عدد مرات ونحن زيادة و إنقاص لتحقيق أعلاه لا يزال هو نفسه على جميع الجوانب الأربعة من المصفوفة.على سبيل المثال:
- الخطوة 1 عنصر في أعلى الصف.
- الخطوة 1 عنصر أسفل الجانب الأيمن.
- الخطوة 1 عنصر إلى الوراء على طول الصف السفلي.
- الخطوة 1 عنصر في أعلى الجانب الأيسر.
هذا يعني أننا يمكن استخدام متغير واحد في تركيبة مع first و last المتغيرات للتحرك داخل الطبقة.فإنه قد يساعد على ملاحظة أن تتحرك عبر أعلى صف أسفل الجانب الأيمن على حد سواء تتطلب تزايد.بينما تتحرك إلى الوراء على طول القاع و حتى الجانب الأيسر على حد سواء تتطلب decrementing.
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_element = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
الآن نحن ببساطة بحاجة إلى تعيين أعلى إلى الجانب الأيمن والجانب الأيمن إلى أسفل ، أسفل إلى الجانب الأيسر والجانب الأيسر إلى الأعلى.وضع كل هذا معا نحصل على:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
نظرا مصفوفة:
0, 1, 2
3, 4, 5
6, 7, 8
لدينا rotate وظيفة النتائج في:
6, 3, 0
7, 4, 1
8, 5, 2
بايثون:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
رخيصة أعلم.
و عكس اتجاه عقارب الساعة:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
كيف يعمل هذا: (طلب التعليقات)
zip(*original) سوف مبادلة محاور صفائف 2d عن طريق التراص المقابلة العناصر من القوائم في قوائم جديدة.(إن * مشغل يحكي وظيفة توزيع الواردة في قوائم الحجج)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
على [::-1] بيان عكس عناصر مجموعة (يرجى الاطلاع تمديد شرائح).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
أخيرا, الجمع بين اثنين سوف يؤدي إلى دوران التحول.
التغيير في وضع [::-1] عكس القوائم في مستويات مختلفة من المصفوفة.
هنا هو واحد التي لا دوران في المكان بدلا من استخدام جديد تماما مجموعة عقد النتيجة.لقد تركته تهيئة مجموعة والطباعة بها.هذا يعمل فقط على ساحة المصفوفات ولكن يمكن أن يكون من أي حجم.الذاكرة العلوية يساوي حجم عنصر واحد من مجموعة حتى تتمكن من القيام دوران كبيرة صفيف كما تريد.
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
هناك طن من كود جيدة هنا لكن أريد فقط أن تظهر ما يجري هندسيا حتى تتمكن من فهم رمز المنطق أفضل قليلا.هنا هو كيف سيكون هذا النهج.
أولا لا تخلط بين هذا مع تبديل والتي من السهل جدا..
على basica فكرة هو التعامل معها على أنها طبقات ونحن تدوير طبقة واحدة في وقت واحد..
أقول لدينا 4x4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
بعد تدوير في اتجاه عقارب الساعة بنسبة 90 نحصل على
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
لذلك دعونا تتحلل هذا أولا نحن تدوير زوايا 4 أساسا
1 4
13 16
ثم نحن تدوير التالية الماس الذي هو نوع من منحرف
2
8
9
15
ثم 2 منحرفة الماس
3
5
12
14
بحيث يأخذ الرعاية من الحافة الخارجية أساسا حتى نفعل ذلك قذيفة واحدة في كل مرة حتى
وأخيرا ساحة الأوسط (أو إذا كان الغريب فقط العنصر الأخير الذي لا يتحرك)
6 7
10 11
حتى الآن دعونا معرفة المؤشرات من كل طبقة ، نفترض نحن نعمل دائما مع الطبقة الخارجية ، نقوم به
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
جرا وهلم جرا حتى نحن في منتصف الحافة
في ذلك العام النمط
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
كما قلت في مشاركتي السابقة, وهنا بعض التعليمات البرمجية في C# التي تطبق O(1) مصفوفة الدوران لأي حجم المصفوفة.الإيجاز و القراءة لا يوجد خطأ تدقيق أو فحص النطاق.رمز:
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
حسنا سأضع يدي, أنها لا تفعل في الواقع أي تعديلات على المصفوفة الأصلية عندما الدورية.ولكن في OO النظام هذا لا يهم طالما أن الهدف يبدو أنه كان استدارة إلى عملاء من الدرجة.في هذه اللحظة, مصفوفة من الدرجة يستخدم المراجع الأصلية مجموعة البيانات حتى تغيير أي قيمة m1 سوف تتغير أيضا m2 و m3.تغيير طفيف إلى منشئ لإنشاء مجموعة جديدة ونسخ القيم إلى أنه سيتم فرز ذلك.
في حين تناوب البيانات في مكان قد يكون ضروريا (ربما لتحديث جسديا المخزنة التمثيل) ، يصبح أكثر بساطة وربما أكثر performant لإضافة طبقة من المراوغة على مجموعة الوصول ، وربما واجهة:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
إذا كان الخاص بك Matrix بالفعل بتنفيذ هذه الواجهة ، ثم أنها يمكن أن تكون استدارة عن طريق الديكور فئة مثل هذا:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
الدورية +90/-90/180 درجة التقليب أفقيا/رأسيا وتوسيع يمكن تحقيقه في هذه الموضة أيضا.
الأداء يحتاج إلى أن يقاس في سيناريو معين.ومع ذلك O(n^2) عملية تم الآن استبدال O(1) الدعوة.انها الظاهري استدعاء الأسلوب الذي هو أبطأ من مباشرة مجموعة الوصول ، حيث أنه يعتمد على مدى تكرار تناوب مجموعة يستخدم بعد دوران.إذا انها تستخدم مرة واحدة ، ثم هذا النهج بالتأكيد الفوز.إذا كان استدارة ثم المستخدمة في نظام تشغيل لعدة أيام ، ثم في مكان التناوب قد أداء أفضل.كما يعتمد ما إذا كنت يمكن أن تقبل مقدما التكلفة.
كما هو الحال مع جميع مسائل الأداء, قياس, قياس, قياس!
هذه نسخة أفضل من ذلك في جاوة:لقد جعلت على مصفوفة مع العرض والارتفاع
- ح هنا ارتفاع المصفوفة بعد تدوير
- w هو هنا عرض المصفوفة بعد تدوير
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
هذا الرمز هو على أساس نيك بيراردي بعد.
روبي-الطريقة: .transpose.map &:reverse
هناك الكثير من الإجابات بالفعل ، لقد وجدت اثنين من يدعي O(1) الوقت التعقيد.على الحقيقي س(1) الخوارزمية هو ترك مجموعة التخزين يمسها ، و تغيير كيفية مؤشر عناصرها.الهدف هنا هو أنه لا تستهلك ذاكرة إضافية ولا تتطلب وقتا إضافيا تكرار البيانات.
تناوب 90 -90 180 درجة بسيطة التحولات التي يمكن أن يؤديها طالما كنت تعرف كيفية العديد من الصفوف والأعمدة في 2D array ، لتدوير أي ناقلات بنسبة 90 درجة ، مبادلة محاور ينفي محور Y.بالنسبة -90 درجة مبادلة محاور ينفي المحور X.لمدة 180 درجة ، ينفي المحورين دون مبادلة.
المزيد من التحولات المحتملة ، مثل النسخ المتطابق أفقيا أو عموديا من خلال إلغاء المحاور بشكل مستقل.
ويمكن أن يتم ذلك من خلال مثلاوهو أسلوب استرجاع قيمة الأسلوب.الأمثلة التالية هي وظائف JavaScript, ولكن المفاهيم تنطبق على جميع اللغات.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);هذا القانون يفترض مجموعة من الصفائف المتداخلة ، حيث كل داخلي صف هو صف.
الأسلوب يسمح لك قراءة (أو كتابة) العناصر (حتى في ترتيب عشوائي) كما لو كان مجموعة تم تدويرها أو تحويلها.الآن فقط اختيار الحق في وظيفة الدعوة ، ربما عن طريق الإشارة ، وتذهب بعيدا!
مفهوم يمكن أن تمتد إلى تطبيق التحولات additively (و غير المدمر) من خلال أسلوب استرجاع القيمة الأساليب.بما في ذلك زاوية التعسفي التناوب التحجيم.
زوجين من الناس بالفعل طرح الأمثلة التي تنطوي على صنع مجموعة جديدة.
عدد قليل من الأشياء الأخرى إلى النظر في:
(أ) بدلا من الواقع نقل البيانات ببساطة اجتياز "استدارة" مجموعة بشكل مختلف.
(ب) القيام دوران في نفس المكان يمكن أن يكون أصعب قليلا.سوف تحتاج قليلا من الصفر مكان (ربما يساوي تقريبا صف واحد أو عمود في الحجم).هناك قديمة ACM ورقة عن القيام في مكان ينقل (http://doi.acm.org/10.1145/355719.355729) ، ولكن على سبيل المثال رمز سيئة غوتو لادن FORTRAN.
إضافة:
http://doi.acm.org/10.1145/355611.355612 آخر يفترض متفوقة في مكان تبديل الخوارزمية.
نيك الجواب أن العمل NxM مجموعة جدا مع تعديل بسيط (بدلا من NxN).
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
طريقة واحدة للتفكير في ذلك هو أن كنت قد انتقلت مركز المحور (0,0) من أعلى الزاوية اليسرى إلى الزاوية اليمنى العليا.أنت ببساطة نقل من واحدة إلى أخرى.
الوقت - O(N), مساحة - O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
هنا هو بلدي روبي نسخة (ملاحظة القيم لا يتم عرض نفس, لكنها لا تزال تدور كما هو موضح).
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
الإخراج:
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
وهنا في الفضاء تدوير طريقة, عن طريق جافا فقط مربع.غير مربع 2d array, سيكون لديك لإنشاء مجموعة جديدة على أية حال.
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
رمز تدوير أي حجم 2d array من خلال إنشاء مجموعة جديدة:
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
تنفيذ الدمل هو +90 شبة الكود (مثلا ، تبديل ثم عكس كل صف) في جافا سكريبت:
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
يمكنك القيام بذلك في 3 خطوات سهلة:
1)لنفترض أن لدينا مصفوفة
1 2 3
4 5 6
7 8 9
2)اتخاذ منقول المصفوفة
1 4 7
2 5 8
3 6 9
3)تبادل الصفوف للحصول على استدارة مصفوفة
3 6 9
2 5 8
1 4 7
جافا التعليمات البرمجية المصدر لهذا:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
الإخراج:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP:
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
هذا هو بلدي ، ج ، س(1) الذاكرة التعقيد في مكان تناوب 90 درجة في اتجاه عقارب الساعة:
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
هنا هو نسخة جافا:
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
الطريقة الأولى تدوير mostouter طبقة ، ثم الانتقال إلى الطبقة الداخلية squentially.
من الخطية وجهة النظر المصفوفات:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
إن تبديل
1 4 7
A' = 2 5 8
3 6 9
والنظر في العمل من أ على ب ، أو ب على'.
على التوالي:
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
هذا هو للتوسيع لأي n x n مصفوفة.وتطبيق هذا المفهوم بسرعة في التعليمات البرمجية:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
C# كود لتدوير [n,m] صفائف 2D 90 درجة الحق
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
النتيجة:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X هو حجم المصفوفة الرسم هو في.
#تبديل هو الطريقة القياسية روبي مجموعة الفئة بالتالي:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
التنفيذ هو n^2 تبديل وظيفة كتابية في C.يمكنك أن ترى هنا:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose عن طريق اختيار "انقر فوق تبديل مصدر" بجوار "تبديل".
أذكر أفضل من O(n^2) الحلول ، ولكن فقط من أجل شيدت خصيصا المصفوفات (مثل متفرق المصفوفات)
ج رمز مصفوفة الدوران 90 درجة في اتجاه عقارب الساعة في مكان لأي M*N مصفوفة
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
هنا هو بلدي في مكان التنفيذ في ج
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
هنا هو بلدي محاولة مصفوفة 90 درجة التناوب الذي هو الخطوة 2 الحل في C.أول تبديل في مصفوفة في المكان ومن ثم مبادلة cols.
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
@dagorym:يا رجل.لقد كانت معلقة على هذا النحو الجيد "أنا أشعر بالملل ، ماذا يمكنني أن يتأمل" اللغز.لقد جاء مع بلدي في مكان تبديل رمز ، ولكن هنا تجد لك متطابقة الى حد كبير لي...آه ، حسنا.هنا هو في روبي.
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
بسيطة C++ طريقة ثو سيكون هناك ذاكرة كبيرة النفقات العامة في مجموعة كبيرة.
