網格中的相鄰產品

我正在解決Project Euler的問題11。我已經想出了算法和我需要做的事情。網格被保存在一個文件grid.txt和它的內容是 -網格中的相鄰產品

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

的問題是 - 什麼是四個相鄰數的最大產品在任何方向（上，下，左，右，或對角）在20x20網格？

我知道算法正常工作，因爲我已經嘗試使用cout輸出數字，並且它們以正確的順序出現。雖然它給了我一個不正確的答案，但是可能是錯誤？

void problem11() 
{ 
    vector<vector<int>> grid; 

    ifstream stream("grid.txt"); 
    string line; 

    char *tok; 

    if (stream.is_open()) 
    { 
     while(stream.good()) 
     { 
      getline(stream, line); 

      tok = strtok((char *)line.c_str(), " "); 

      vector<int> row; 

      while (tok != NULL) 
      { 
       int field; 
       stringstream ss; 
       ss << tok; 
       ss >> field; 
       row.push_back(field); 

       tok = strtok(NULL, " "); 
      } 
      grid.push_back(row); 
     } 
     stream.close(); 
    } 

    unsigned long highest = 0; 

    /// LEFT TO RIGHT 
    for (int i=0; i < 20; i++) // i'th row 
    { 
     vector<int> row = grid.at(i); 

     for (int c=0; c < 20-3; c++) // -3 to accomodate for last 
     { 
      unsigned long prod = row.at(c) * row.at(c+1) * row.at(c+2) * row.at(c+3); // four consecutive 
      //cout << row.at(c) << " " << row.at(c+1) << " " << row.at(c+2) << " " << row.at(c+3) << endl; 
      if (prod > highest) 
       highest = prod; 
     } 
    } 

    /// TOP TO DOWN 
    /// This moves from left to right, then top to botom 
    /// 
    for (int i=0; i < 20-3; i++) // subtract last 3 
    { 
     vector<int> row1, row2, row3, row4; 

     row1 = grid.at(i); 
     row2 = grid.at(i+1); 
     row3 = grid.at(i+2); 
     row4 = grid.at(i+3); 

     for (int c=0; c < 20; c++) 
     { 
      unsigned long prod = row1.at(c) * row2.at(c) * row3.at(c) * row4.at(c); 
      //cout << row1.at(c) << " " << row2.at(c) << " " << row3.at(c) << " " << row4.at(c) << endl; 
      if (prod > highest) 
       highest = prod; 
     } 
    } 

    /// DOWN DIAGONAL 
    /// This moves diagonally from left to right, top to bottom 
    for (int i=0; i < 20-3; i++) // subtract last 3 
    { 
     vector<int> row1, row2, row3, row4; 

     row1 = grid.at(i); 
     row2 = grid.at(i+1); 
     row3 = grid.at(i+2); 
     row4 = grid.at(i+3); 

     for (int c=0; c < 20-3; c++) // omit last 3 
     { 
      unsigned long prod = row1.at(c) * row2.at(c+1) * row3.at(c+2) * row4.at(c+3); 
      //cout << row1.at(c) << " " << row2.at(c+1) << " " << row3.at(c+2) << " " << row4.at(c+3) << endl; 
      if (prod > highest) 
       highest = prod; 
     } 
    } 

    /// UP DIAGONAL 
    /// This moves diagonally from left to right, bottom to top 
    for (int i=3; i < 20; i++) // start from 3, skipping first four 
    { 
     vector<int> row1, row2, row3, row4; 

     row4 = grid.at(i); 
     row3 = grid.at(i-1); 
     row2 = grid.at(i-2); 
     row1 = grid.at(i-3); 

     for (int c=0; c < 20-3; c++) // omit last 3 
     { 
      unsigned long prod = row4.at(c) * row3.at(c+1) * row3.at(c+2) * row4.at(c+3); 
      //cout << row4.at(c) << " " << row3.at(c+1) << " " << row2.at(c+2) << " " << row1.at(c+3) << endl; 
      if (prod > highest) 
       highest = prod; 
     } 
    } 

    cout << "Required: " << highest; 

}

來源

2011-06-08 Ishbir

您是否試過在調試器中逐步調試程序？或者打印出中間變量？或者先運行一個簡單的數據集？你是否確定了四個循環中的哪一個（上下，左 - 右，向上，向下）是不正確的？ – 2011-06-08 10:50:40

你怎麼知道答案不正確？你會得到什麼答案而不是正確答案？ – 2011-06-08 11:05:56

我不打算回答這個問題（並且破壞了它的樂趣），但我建議將它分解成（至少）四個單獨的函數並獨立地測試它們。 – Johnsyweb 2011-06-08 11:16:21

在破壞自己尋找答案的樂趣的風險...

不要打印出來的對角線。目視檢查它們是否符合您的預期。

作爲旁註：並且不要創建表格行的副本，而是同樣訪問它們：vector[rowindex][column]。

編輯 -

好了，現在我要破壞它。在NxN的矩陣中，你有多少對角線路徑？你有多少條路徑？（通過採用2x2矩陣進行交叉檢查，該矩陣在每個方向上具有3條對角線路徑）

PS。如果您認真編程，遇到錯誤時，請首先驗證您的假設。

來源

2011-06-08 10:56:06 xtofl

我試圖打印對角線，他們出來是正確的，正如我所提到的。 – Ishbir 2011-06-08 12:27:05

對不起，您對「2x2網格的每個方向上的三個對角線」究竟意味着什麼？我認爲這個問題只是要考慮對角相鄰的數字。根據我的理解，在任何NxN網格的任何位置只能有4組對角相鄰的數字。那就是在每個（x，y）：（x + d，y + d），（xd，yd），（x + d，yd）和（xd，y + d）其中d的範圍從0到3。我誤解了這裏的問題嗎？ – rineez 2014-11-16 08:10:56

請嘗試以下輸入：

0 0 0 1 0 0 ... 
0 0 1 0 0 0 ... 
0 1 0 0 0 0 ... 
1 0 0 0 0 0 ... 
0 0 0 0 0 0 ... 
.....

，做什麼又建議xtofl你。

一般來說，如果您想顛倒某些操作的邏輯，那麼只需執行一次即可。（或者一般情況下，奇數次）。謹防a<=b被b>=a或left to right and top to bottom取代right to left and bottom to top或類似的東西。

來源

2011-06-08 12:53:23 xofon

-2

這是我寫的代碼。給出正確的答案。我希望這可以幫助....

#include <iostream> 
#include <vector> 
using namespace std; 



void main() 
{ 

int num_container[20][20] = { 
          { 8,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91, 8}, 
          {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00}, 
          {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65}, 
          {52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91}, 
          {22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80}, 
          {24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50}, 
          {32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70}, 
          {67,26,20,68,02,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21}, 
          {24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72}, 
          {21,36,23, 9,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95}, 
          {78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14, 9,53,56,92}, 
          {16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57}, 
          {86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58}, 
          {19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40}, 
          {04,52, 8,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66}, 
          {88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69}, 
          {04,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36}, 
          {20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16}, 
          {20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54}, 
          {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48}, 
                         }; 


int test = num_container[6][8] * num_container[7][9] * num_container[8][10] * num_container[9][11]; 
cout<<test<<endl; 
system("pause"); 

int start = 0; 
int end = 3; 
long long mul_result = 1; 

vector<long long>final_results; 

/////////////////////UP/DOWN///////////////////// 
for(int k=0; k<20; k++) 
{ 
    for(int i=0; i<=16; i++) 
    { 
     for(int j=start; j<=end; j++) 
     { 
      mul_result = mul_result * num_container[k][j]; 
      if (j == end) 
       final_results.push_back(mul_result); 
     } 
     mul_result = 1; 
     start++; 
     end++; 
    } 
    start = 0; 
    end = 3; 

    for(int i=0; i<=16; i++) 
    { 
     for(int j=start; j<=end; j++) 
     { 
      mul_result = mul_result * num_container[j][k]; 
      if (j == end) 
       final_results.push_back(mul_result); 
     } 
     mul_result = 1; 
     start++; 
     end++; 
    } 
    start = 0; 
    end = 3; 

} 
/////////////////////UP/DOWN Ends here////////////////////// 



///////////////////Both Ways Diagonal Starts here////////////////////// 
int current_row = 0; 

for(int i=0; i<=16; i++) 
{ 
    for(int j=0; j<=16; j++) 
    { 
     current_row = i; 
     for(int k=start; k<=end; k++) 
     { 
      mul_result = mul_result * num_container[current_row][k]; 
      current_row++; 
      if (k==end) 
       final_results.push_back(mul_result); 
     } 
     mul_result = 1; 
     start++; 
     end++;   
    } 
    start = 0; 
    end = 3; 

    for(int j=0; j<=16; j++) 
    { 
     current_row = i+3; 
     for(int k=start; k<=end; k++) 
     { 
      mul_result = mul_result * num_container[current_row][k]; 
      current_row--; 
      if (k==end) 
       final_results.push_back(mul_result); 
     } 
     mul_result = 1; 
     start++; 
     end++;   
    } 
    start = 0; 
    end = 3; 
} 
/////////////////////Both Ways diagonal ends here/////////////////// 


////////////////////Compare Thning Starts here////////////////////// 

long long the_big_one = 0; 
for(int i=0; i<final_results.size(); i++) 
{ 
    if (final_results[i] > the_big_one) 
     the_big_one = final_results[i]; 
} 





cout<<endl<<endl<<"The big one is: "<<the_big_one<<endl; 

system("pause"); 
}

來源

2011-07-10 18:53:16 Rafay

本網站不鼓勵在歐拉問題上發佈解決方案。 – 2011-08-21 11:21:07

這兩個和[使用系統（「暫停」）是_bad_]（http://stackoverflow.com/questions/1107705/systempause-why-is-it-wrong） – Chiffa 2013-12-19 21:28:34

我必須同意Konrad ...它是對於積極的編程挑戰提供完整的答案，味道很差。 – Beska 2015-11-05 14:17:02

我用Javascript來解決這個問題。如果您有任何疑問，請讓我知道。

<html> 
    <head> 
    </head> 
    <body> 
    <input type="button" value="Click Me" onClick="onPress()"></input>        
    </body> 
    <script> 
    function onPress() 
    { 
     var arr=[ 
      [8,2,22,97,38,15,0,40,0,75 4, 5, 7, 78, 52, 12, 50, 77,91, 8] 
      [49,49,99, 40,17,81, 18, 57, 60, 87,17,40,98,43,69,48,4,56, 62,0], 
      [81,49,31,73,55,79,14,29,93,71,40,67,53, 88, 30,3,49,13,36,65], 
      [52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71, 37, 2, 36, 91], 
      [22,31,16,71,51,67,63,89,41,92,36, 54,22,40,40,28,66, 33, 13,80], 
      [24,47,32,60,99,3,45,2,44,75,33,53,78,36,84, 20, 35,17,12,50], 
      [32,98,81,28,64,23,67,10,26,38,40, 67, 59, 54, 70, 66,18,38,64,70], 
      [67,26,20,68,2,62,12,20,95,63,94,39,63,8,40, 91, 66, 49, 94, 21], 
      [24,55,58,5,66,73,99,26,97,17,78,78,96,83,14, 88, 34, 89, 63, 72], 
      [21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95], 
      [78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56, 92], 
      [16,39,5,42,96,35,31,47,55, 58, 88, 24, 0, 17, 54,24,36,29,85,57], 
      [86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51, 54, 17, 58], 
      [19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89, 55, 40], 
      [4,52,8,83,97,35,99,16,7,97,57,32,16,26,26, 79, 33, 27, 98, 66], 
      [88,36,68,87,57,62,20,72,3,46,33,67,46, 55, 12, 32, 63, 93, 53, 69], 
      [4,42,16,73,38,25,39,11,24,94,72,18,8,46,29, 32, 40, 62, 76, 36], 
      [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36, 16], 
      [20,73,35,29,78,31,90,1,74,31,49,71,48,86, 81, 16, 23, 57,5, 54], 
      [1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1, 89, 19, 67, 48] 
     ]; 
     var i, j, product=0, arr2=[], max; 
     /* Horizontal 4 digit multiplication*/ 
     for(i=0; i<arr.length; i++) 
     { 
      for(j=0; j<17;j++) 
      { 
       product= arr[i][j]* arr[i][j+1] *arr[i][j+2] * arr[i][j+3] 
       arr2.push(product); 
      } 
     } 
     /* Vertical 4 digit multiplication*/ 
     for(var j=0; j<arr.length; j++) 
     { 
      for(var i=0; i<17; i++) 
      { 
       product= arr[i][j] * arr[i+1][j] * arr[i+2][j] * arr[i+3][j]; 
       arr2.push(product); 
      } 
     } 
     /* left to right diagonal*/ 
     for(var j=0 ; j<17; j++) 
     { 
      for(var i=0; i<17; i++) 
      { 
       product= arr[i][j]* arr[i+1][j+1]*arr[i+2][j+2]*arr[i+3][j+3]; 
       arr2.push(product) 
      } 
     } 
     /* right to left diagonal*/ 
     for(var i=0; i<17; i++) 
     { 
      for(var j=19; j>=3; j--) 
      { 
       product= arr[i][j]*arr[i+1][j-1]*arr[i+2][j-2]*arr[i+3][j-3] 
       arr2.push(product); 
      } 
     } 
     max= Math.max.apply(Math, arr2); 
     console.log(max) 
    } 
    </script> 
</html>

來源

2016-06-05 11:22:51

網格中的相鄰產品

回答

相關問題