时间戳

首页 > 解决方案 > 在矩阵中找到所有可能的和

c++ - 在矩阵中找到所有可能的和

问题描述

我正在尝试编写一个代码来查找二维矩阵中所有可能数字的总和。但问题是您必须从一行中选择一个元素。

#include <algorithm>
#include <iostream>
#include <vector>
#include <climits>
#include <math.h>
using namespace std;
int main() { 
    int n;
    cin>>n;
    int array[n][n]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>array[i][j];
        }
    }
    int power=pow(n,n);
    int sum[power]={0};
    for(int i=0;i<power;i++){
        for(int j=0;j<n;j++){
            for(int l=0;l<n;l++){
                sum[i]=sum[i]+array[j][l];
            }
        }
    }
    for(int i=0;i<power;i++){
        cout<<sum[i]<<" ";
    }
    return 0;
}

此代码仅显示二维数组中所有元素的总和。所以我需要帮助试图找到所有可能的总和，给定每行中的一个元素是为每个总和选择的。

2
1 1
1 2

2, 3, 2, 3

这应该是输出，但它只给出 5

标签： c++math

解决方案

你的核心循环全错了。如果要sum[i]包含给定路径的值，则需要将其i视为穿过矩阵的路径。

通常，将i其视为以 n 为底的数字（例如，= 2）。这意味着

i = idx_1 * n^(n-1) + idx_2 * n^(n-2) + ... + idx_n

您可以通过重复除以 n 并取余数来恢复各种索引：

for(uint64_t i=0;i<power;i++){
   sum[i] = 0;
   uint64_t encoded_index = i;
   for (size_t j = 0; j < n; j++) {
       uint64_t index_j = encoded_index % n;
       encoded_index /= n;
       sum[i] += hist[j][index_j];
   }
}

当然，这个技巧只有在 n*n < 2**64 时才有效（因为 uint64_t 是 64 位）。有关更一般的方法，请参阅我对您的其他问题的回答。

推荐阅读