C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C ++で余分なスペースを使用せずに、行列を90度回転します


マトリックスパターンを形成するために使用される2次元配列が与えられます。タスクは、最初の行が1番目の列、2番目の行が2番目の列、3番目の行が3番目の列になるように、マトリックスを反時計回りに90度回転することです。課題は、余分なものを使用する必要がないことです。スペース。

このためのさまざまな入出力シナリオを見てみましょう-

入力

int arr[row_col_size][row_col_size] = { { 5, 1, 4},
   { 9, 16, 12 },
   { 2, 8, 9}}

出力

Rotation of a matrix by 90 degree without using any extra space is:
4 12 9
1 16 8
5 9  2

説明 −整数型の2次元配列が与えられます。次に、マトリックスを時計回りに90度回転させます。

Before rotation-:
{ { 5, 1, 4},
{ 9, 16, 12 },
{ 2, 8, 9}}
After rotation-:
2 12 9
1 16 8
5 9  2

入力

int arr[row_col_size][row_col_size] = { { 2, 1, 9},
   { 11, 6, 32 },
   { 3, 7, 5}}

出力

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
9 32 5
1 6  7
2 7  3
説明 −整数型の2次元配列が与えられます。次に、マトリックスを時計回りに90度回転させます。

Before rotation-:
{ { 2, 1, 9},
{ 11, 6, 32 },
{ 3, 7, 5}}
After rotation-:
9 32 5
1 6  7
2 7  3

以下のプログラムで使用されているアプローチは次のとおりです

1。素朴なアプローチ

  • row_col_sizeの行列として扱われる2次元整数配列を入力します。

  • データを関数Rotate_ClockWise(arr)に渡します。

  • 関数Rotate_ClockWise(arr)

    の内部
    • iからrow_col_size/2未満になるまでループFORを開始します。

    • ループ内で、jから0までの別のループFORを開始し、jがrow_col_size--i-1未満になるまで

    • ループ内で、ptrをarr [i] [j]に、arr[i][j]をarr[row_col_size--1 --j] [i]に、arr [row_col_size -1--j][i]をarr[row_col_sizeに設定します。 --1- i] [row_col_size --1 --j]、arr [row_col_size --1 --i] [row_col_size --1 --j] to arr [j] [row_col_size --1--i]およびarr[j][row_col_size --1- i]からptr。

  • iからrow_col_size未満になるまでループFORを開始します。ループ内で、jがrow_col_size未満になるまで、jから0までの別のループFORを開始します。 j++とprintarr[i][j]。

2。効率的なアプローチ

  • row_col_sizeの行列として扱われる2次元整数配列を入力します。

  • データを関数Rotate_ClockWise(arr)に渡します。

  • 関数Rotate_ClockWise(arr)

    の内部
    • iからrow_col_size未満になるまでループFORを開始します。

    • ループ内で、jがrow_col_size-iより小さくなるまでjから0までの別のループFORを開始します。

    • ループ内で、ptrをarr [i] [j]に、arr[i][j]をarr[row_col_size--1 --j] arr [row_col_size -1 --i]に、[row_col_size-1-j]をarr[に設定します。 j] [row_col_size--1-i]からptr。

    • iからiまでrow_col_size/2未満になるまでループFORを開始します。ループ内で、jからjまでrow_col_size未満になるまで別のループFORを開始します。ループ内で、ptrをarr [i] [j]に、arr[i][j]をarr[row_col_size--1 --i] [j]に、arr [row_col_size -1--i][j]をptr

  • iからrow_col_size未満になるまでループFORを開始します。ループ内で、jがrow_col_size未満になるまで、jから0までの別のループFORを開始します。 j++とprintarr[i][j]。

素朴なアプローチ

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
   for(int i = 0; i < row_col_size / 2; i++){
      for(int j = i; j < row_col_size - i - 1; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - j][i];
         arr[row_col_size - 1 - j][i] = arr[row_col_size - 1 - i][row_col_size - 1 - j];
         arr[row_col_size - 1 - i][row_col_size - 1 - j] = arr[j][row_col_size - 1 - i];
         arr[j][row_col_size - 1 - i] = ptr;
      }
   }
}
int main(){
   int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
   Rotate_ClockWise(arr);
   cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size; j++){
         cout << arr[i][j] << " ";
      }
      cout << '\n';
   }
   return 0;
}
出力

上記のコードを実行すると、次の出力が生成されます

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
2 9  5
8 16 1
9 12 4
効率的なアプローチ

#include <bits/stdc++.h>
using namespace std;
#define row_col_size 3
void Rotate_ClockWise(int arr[row_col_size][row_col_size]){
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size - i; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - j][row_col_size - 1 - i];
         arr[row_col_size - 1 - j][row_col_size - 1 - i] = ptr;
      }
   }
   for(int i = 0; i < row_col_size / 2; i++){
      for(int j = 0; j < row_col_size; j++){
         int ptr = arr[i][j];
         arr[i][j] = arr[row_col_size - 1 - i][j];
         arr[row_col_size - 1 - i][j] = ptr;
      }
   }
}
int main(){
   int arr[row_col_size][row_col_size] = { { 5, 1, 4},{ 9, 16, 12 },{ 2, 8, 9}};
   Rotate_ClockWise(arr);
   cout<<"Rotation of a matrix by 90 degree in clockwise direction without using any extra space is: \n";
   for(int i = 0; i < row_col_size; i++){
      for(int j = 0; j < row_col_size; j++){
         cout << arr[i][j] << " ";
      }
      cout << '\n';
   }
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Rotation of a matrix by 90 degree in clockwise direction without using any extra space is:
2 9  5
8 16 1
9 12 4

  1. 接続行列を使用してグラフを表現するC++プログラム

    グラフの接続行列は、メモリに保存するグラフの別の表現です。この行列は正方行列ではありません。接続行列の次数はVxEです。ここで、Vは頂点の数、Eはグラフのエッジの数です。 この行列の各行に頂点を配置し、各列にエッジを配置します。エッジe{u、v}のこの表現では、列eの場所uとvに対して1でマークされます。 隣接行列表現の複雑さ 接続行列表現は、計算中にO(Vx E)のスペースを取ります。完全グラフの場合、エッジの数はV(V-1)/2になります。したがって、接続行列はメモリ内でより大きなスペースを取ります。 入力 出力 E0 E1 E2

  2. 隣接行列を使用してグラフを表現するC++プログラム

    グラフの隣接行列は、サイズV x Vの正方行列です。Vは、グラフGの頂点の数です。この行列では、各辺にV個の頂点がマークされています。グラフにiからjの頂点までのエッジがある場合、i thの隣接行列に 行とjth 列は1(または加重グラフの場合はゼロ以外の値)になります。それ以外の場合、その場所は0を保持します。 隣接行列表現の複雑さ 隣接行列表現はO(V 2 )計算中のスペースの量。グラフに最大数のエッジと最小数のエッジがある場合、どちらの場合も必要なスペースは同じになります。 入力 出力 0 1 2 3 4 5