資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中統計幻方個數
給定一個數字矩陣，目標是找到該矩陣中存在的幻方數量。
幻方，如果作為一個矩陣，是一個3x3的矩陣，其中包含從1到9的元素，就像數獨中的網格一樣。屬性如下：
- 所有數字都恰好出現一次。
- 矩陣中所有9個單元格的總和為45。
- 每行3個數字的和為15。
- 每列3個數字的和為15。
- 對角線3個數字的和為15。
- 為了得到這樣的和，5總是位於兩個對角線的中間。
輸入
int arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };輸出
Magic Squares present: 0
說明 − 建立矩陣形式以便理解 −
| 1 | 2 | 3 | 0 |
| 4 | 5 | 6 | 1 |
| 7 | 8 | 9 | 0 |
所有元素都在1到9之間且唯一。但是，
1+2+3=6 != 4+5+6=15 != 7+8+9=23
對角線之和也不等於15。
輸入
arr[][]= { { 1,2,3,0 }, { 4,5,6,1 }, { 7,8,9,0 } };輸出
Magic Squares present : 1
說明 − 建立矩陣形式以便理解 −
| 1 | 6 | 8 | 4 |
| 8 | 1 | 6 | 0 |
| 3 | 5 | 7 | 1 |
| 4 | 9 | 2 | 0 |
所有數字都是唯一的，並且在1到9的範圍內。
行和，8+1+6=3+5+7=4+9+2=15
列和，8+3+4=1+5+9=6+7+2=15
對角線和，8+5+2=4+5+6=15
此外，將1到9相加得到45，而5位於兩個對角線的中間。
下面程式中使用的演算法如下
整數陣列Grid[][]儲存數字，row和col儲存其維度。
函式magicSquare(int a, int b……int i) 將所有9個元素作為輸入，並檢查它是否構成幻方。如果是幻方，則返回1；否則返回0。
在這裡，我們將使用陣列arr[9]來儲存所有引數，並透過檢查它們是否佔據陣列中的唯一單元格來檢查它們是否唯一。如果一個單元格的計數count<1，則表示該數字不在1到9的範圍內，或者如果count>1，則表示該數字不唯一。將flag設定為0。
如果flag為1，我們將檢查行、列、對角線之和是否為15。如果為真，則它是一個幻方。返回1，否則返回0。
函式countSquares(int G[3][4],int R, int C) 將網格、其行和列作為輸入，並計算其中存在的幻方數量。
Count用於儲存此類正方形的數量。
從第一個元素開始遍歷到row-2, col-2 (3x3矩陣)
如果對角線的中間元素G[i+1][j+1]不是5，則不可能形成幻方，跳過當前迭代。
否則，透過將其傳遞給magicSquare(int a到i)來檢查所有9個元素。
所有9個元素包括G[i][j]、G[i+1][j]、G[i+2][j]、G[i+1][j+1]、G[i][j+1]、G[i][j+2]、G[i+2][j+2]、G[i+2][j+1]、G[i+1][j+2]
如果返回1，則計數加1。
最後返回計數作為期望的結果。
示例
#include <bits/stdc++.h>
using namespace std;
// to check is subgrid is Magic Square
int magicSquare(int a, int b, int c, int d, int e,
int f, int g, int h, int i){
int flag=1; // to mark all numbers are unique and between 1 to 9
int arr[9]={0};
arr[a-1]++;
arr[b-1]++;
arr[c-1]++;
arr[d-1]++;
arr[e-1]++;
arr[f-1]++;
arr[g-1]++;
arr[h-1]++;
arr[i-1]++;
for(int i=0;i<9;i++)
if(arr[i]>1 || arr[i]<1) //every number occurs exactly once{
flag=0;
break;
}
// checking all sums as 15
if (flag==1 && (a + b + c) == 15 && (d + e + f) == 15 && (g + h + i) == 15 && (a + d + g) == 15 &&(b + e + h) == 15 && (c + f + i) == 15 &&(a + e + i) == 15 && (c + e + g) == 15)
return 1;
return 0;
}
int countSquares(int G[3][4],int R, int C){
int count = 0;
for (int i = 0; i < R - 2; i++)
for (int j = 0; j < C - 2; j++) {
if (G[i + 1][j + 1] != 5)
continue;
int ismagic=magicSquare(G[i][j], G[i][j + 1], G[i][j + 2], G[i + 1][j], G[i + 1][j + 1],
G[i + 1][j + 2], G[i + 2][j], G[i + 2][j + 1], G[i + 2][j + 2]);
// check for magic square subgrid
if (ismagic==1)
count++;
}
return count;
}
int main(){
int Grid[3][4] = { { 4, 3, 8, 4 },{ 9, 5, 1, 9 },{ 2, 7, 6, 2 } };
int row=3;
int col=4;
cout <<"Count of Magic Squares in Grid: "<<countSquares(Grid,row,col);
return 0;
}輸出
Count of Magic Squares in Grid: 1
242 次檢視
