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
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
-
接続行列を使用してグラフを表現するC++プログラム
グラフの接続行列は、メモリに保存するグラフの別の表現です。この行列は正方行列ではありません。接続行列の次数はVxEです。ここで、Vは頂点の数、Eはグラフのエッジの数です。 この行列の各行に頂点を配置し、各列にエッジを配置します。エッジe{u、v}のこの表現では、列eの場所uとvに対して1でマークされます。 隣接行列表現の複雑さ 接続行列表現は、計算中にO（Vx E）のスペースを取ります。完全グラフの場合、エッジの数はV（V-1）/2になります。したがって、接続行列はメモリ内でより大きなスペースを取ります。 入力 出力 E0 E1 E2
-
隣接行列を使用してグラフを表現するC++プログラム
グラフの隣接行列は、サイズV x Vの正方行列です。Vは、グラフGの頂点の数です。この行列では、各辺にV個の頂点がマークされています。グラフにiからjの頂点までのエッジがある場合、i thの隣接行列に 行とjth 列は1（または加重グラフの場合はゼロ以外の値）になります。それ以外の場合、その場所は0を保持します。 隣接行列表現の複雑さ 隣接行列表現はO（V 2 ）計算中のスペースの量。グラフに最大数のエッジと最小数のエッジがある場合、どちらの場合も必要なスペースは同じになります。 入力 出力 0 1 2 3 4 5