資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中二進位制矩陣的最大十進位制值路徑
給定任務是從給定方形二進位制陣列的左上角元素到右下角元素遍歷路徑時獲得的最大整數值，即從索引[0][0]到索引[n-1][n-1]。
在遍歷路徑時，我們只能向右移動([i][j+1])或向下移動([i+1][j])
整數值將使用遍歷路徑的位進行計算。
讓我們用一個例子來理解我們必須做什麼：
輸入
m = {
{1, 1, 1, 1},
{0, 0, 1, 0},
{1, 0, 1, 1},
{0, 1, 1, 1}
}輸出
127
解釋
我們選擇的路徑是：[0, 0] →[0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] →[3, 3]
因此，十進位制值變為 = 1*(20) + 1*(21) + 1*(22) + 1*(23) + 1*(24) + 1*(25) + 1*(26)
= 1 + 2 + 4 + 8 + 16 + 32 + 64
= 127
輸入
m = {
{1, 0, 1, 1},
{0, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 1, 1}
}輸出
109
下面程式中使用的方案如下
首先使用#define定義方形矩陣邊的尺寸。
在main()函式中建立一個二維陣列int m[][4]來儲存矩陣，並呼叫Max(m, 0, 0, 0)
在max()函式中，首先檢查(i >= side || j >= side)。如果是，則意味著我們超出了矩陣邊界，返回0。
建立一個新的變數int ans，並設定ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1))。
然後檢查(m[i][j] == 1)。如果是，則返回pow(2, pw) + ans。
否則，只返回ans。
示例
#include<bits/stdc++.h>
using namespace std;
#define side 4
// pw is power of 2
int Max(int m[][side], int i, int j, int pw){
// Out of boundary
if (i >= side || j >= side )
return 0;
int ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1));
if (m[i][j] == 1)
return pow(2, pw) + ans;
else
return ans;
}
//main function
int main(){
int m[][4] = {{1, 1, 1, 1},{0, 0, 1, 0},{1, 0, 1, 1},{0, 1, 1, 1}};
cout << Max(m, 0, 0, 0);
return 0;
}輸出
127
更新於：2020年8月4日
104 次瀏覽
廣告