C++ ProjectEuler＃11

我正試圖解決ProjectEuler.net上的第11個問題。這個問題的目標是在任何方向（上，下，右，左，對角線）上找到4個相鄰數字的20x20網格中的最大產品。C++ ProjectEuler＃11

我使用BigInteger庫，因爲我不知道數字有多大，我不想溢出 - 但我認爲這可能是問題所在。每次我重新啓動程序，我都會得到不同的答案。：/我也嘗試使用unsigned long long int來看看會發生什麼 - 答案保持不變。

這是代碼（沒有什麼複雜的;我只是測試網格中的每個元素，看它是否有任何方向上有3個相鄰的數字，計算產品並將其設置爲新的最大值，如果它大於前一個。最後我打印最大的產品。）：

//NO.11 
#include <iostream> 
#include <BigIntegerLibrary.hh> 
#include <windows.h> 

int main() 
{ 
    int grid[20][20] = 
    { 
     { 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, 01, 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, 03, 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, 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, 4, 89, 55, 40}, 
     { 4, 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, 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, 04, 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} 
    }; 

    BigInteger biggestProduct = 0; 
    //unsigned long long int biggestProduct = 0; 

    for (int row = 0; row < 20; row++) 
    { 
     for (int col = 0; col < 20; col++) 
     { 
      BigInteger product; 
      //unsigned long long int product; 

      //std::cout << grid[row][col] << ":" << std::endl; system("pause>nul"); 

      //UP 
      if ((row-1 >= 0) && (row-2 >= 0) && (row-3 >= 0)) 
      { 
       product = grid[row][col] * grid[row-1][col] * grid[row-2][col] * grid[row-3][col]; 
       //std::cout << " U: " << grid[row][col] << "*" << grid[row-1][col] << "*" << grid[row-2][col] << "*" << grid[row-3][col] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 
      //DOWN 
      if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0)) 
      { 
       product = grid[row][col] * grid[row+1][col] * grid[row+2][col] * grid[row+3][col]; 
       //std::cout << " D: " << grid[row][col] << "*" << grid[row+1][col] << "*" << grid[row+2][col] << "*" << grid[row+3][col] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 
      //RIGHT 
      if ((col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0)) 
      { 
       product = grid[row][col] * grid[row][col+1] * grid[row][col+2] * grid[row][col+3]; 
       //std::cout << " R: " << grid[row][col] << "*" << grid[row][col+1] << "*" << grid[row][col+2] << "*" << grid[row][col+3] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 
      //LEFT 
      if ((col-1 >= 0) && (col-2 >= 0) && (col-3 >= 0)) 
      { 
       product = grid[row][col] * grid[row][col-1] * grid[row][col-2] * grid[row][col-3]; 
       //std::cout << " L: " << grid[row][col] << "*" << grid[row][col-1] << "*" << grid[row][col-2] << "*" << grid[row][col-3] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 

      //UP-RIGHT 
      if ((row-1 >= 0) && (row-2 >= 0) && (row-3 >= 0) && (col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0)) 
      { 
       product = grid[row][col] * grid[row-1][col+1] * grid[row-2][col+2] * grid[row-3][col+3]; 
       //std::cout << " U-R: " << grid[row][col] << "*" << grid[row-1][col+1] << "*" << grid[row-2][col+2] << "*" << grid[row-3][col+3] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 

      //DOWN-RIGHT 
      if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0) && (col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0)) 
      { 
       product = grid[row][col] * grid[row+1][col+1] * grid[row+2][col+2] * grid[row+3][col+3]; 
       //std::cout << " D-R: " << grid[row][col] << "*" << grid[row+1][col+1] << "*" << grid[row+2][col+2] << "*" << grid[row+3][col+3] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 

      //DOWN-LEFT 
      if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0) && (col-1 >= 0) && (col-2 >= 0) && (col-3 >= 0)) 
      { 
       product = grid[row][col] * grid[row+1][col-1] * grid[row+2][col-2] * grid[row+3][col-3]; 
       //std::cout << " D-L: " << grid[row][col] << "*" << grid[row+1][col-1] << "*" << grid[row+2][col-2] << "*" << grid[row+3][col-3] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 

      //UP-LEFT 
      if ((row-1 >= 0) && (row-2 >= 0) && (row-3 >= 0) && (col-1 >= 0) && (col-2 >= 0) && (col-3 >= 0)) 
      { 
       product = grid[row][col] * grid[row-1][col-1] * grid[row-2][col-2] * grid[row-3][col-3]; 
       //std::cout << " U-L: " << grid[row][col] << "*" << grid[row-1][col-1] << "*" << grid[row-2][col-2] << "*" << grid[row-3][col-3] << "= \t" << product << std::endl; system("pause>nul"); 
       if (product > biggestProduct) 
        biggestProduct = product; 
      } 
     } 
    } 

    std::cout << biggestProduct; 

    return 0; 
}

有誰知道什麼是錯的？

謝謝， Tuntuni。

來源

2012-07-03 Tuntuni

你絕對不需要一個BigInteger庫。 4個兩位數字的最大可能的產品只有'99^4'或96059601. – Blastfurnace

哦，傻我！我沒有想到這個！ – Tuntuni

你的問題是你的範圍檢查：

例如：

// DOWN 
if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0))

應該是：

// DOWN 
//if ((row+1 < 20) && (row+2 < 20) && (row+3 < 20)) 
//which still contains redundant comparisons (as pointed out by Blastfurnace), 
//and thus can be can be simplified to : 
if(row + 3 < 20)

如果您在程序的每次運行中都有隨機結果，並且不使用併發性，則隨機數字生成器或類似的東西，最有可能的是，我的隨機性是由未定義的行爲造成的，例如讀取未分配的內存或使用未初始化的變量讀取。

來源

2012-07-03 14:49:18 smerlin

這些複合測試正在做冗餘工作。例如，DOWN測試可以簡化爲'if（row <17）'。 – Blastfurnace

@Blastfurnace：你顯然是對的。雖然我更喜歡'row + 3 <20'。這樣可以更容易地用search + replace替換爲常量變量20），並且無論如何它都會得到優化。 – smerlin

我想我現在明白了。我會嘗試修改我的程序，看看我得到了什麼。謝謝！我稍後再回來看看。 – Tuntuni

看起來你正在閱讀過的底部和右側邊緣：

if ((row+1 >= 0) && (row+2 >= 0) && (row+3 >= 0)) 
if ((col+1 >= 0) && (col+2 >= 0) && (col+3 >= 0))

，並與對角線相同的測試。

你應該檢查該指數未達到20

來源

2012-07-03 14:49:15

訪問此鏈接代碼 http://codingloverlavi.blogspot.in/2013/06/project-euler-solution-11.html

#include<stdio.h> 
#include<conio.h> 
#include<stdlib.h> 

long find_max(int **); 

int main() 
{ 
       FILE *f; 
       int **arr,i=0,j; 
       arr=(int **)malloc(sizeof(int*)*20); 
       for(i=0;i<20;i++) 
           arr[i]=(int *)malloc(sizeof(int)*20); 

       f=fopen("D:/b.txt","r"); 
       if(f) 
           for(i=0;i<20;i++) 
               for(j=0;j<20;j++) 
                   fscanf(f,"%d",&arr[i][j]);    
       else 
           printf("file operation not successful\n"); 

       printf("Answer = %ld\n",find_max(arr)); 

       system("pause"); 
} 


long find_max(int **arr) 
{ 
       int i,j,k; 
       long product,max=0; 
       for(i=0;i<20;i++) 
           for(j=0;j<20;j++) 
           { 
               /*checking for horizontal sequence*/ 
               product=1; 
               for(k=0;k<4;k++) 
               { 
                   if(j+k<20) 
                   { 
                       product*=arr[i][j+k]; 
                   } 
               } 
               if(product>max) 
                   max=product; 

               /*checking for vertical sequence*/ 
               product=1; 
               for(k=0;k<4;k++) 
               { 
                   if(i+k<20) 
                   { 
                       product*=arr[i+k][j]; 
                   } 
               } 
               if(product>max) 
                   max=product; 

               product=1; 
               for(k=0;k<4;k++) 
               { 
                   if((i+k<20) && (j+k<20)) 
                   { 
                       product*=arr[i+k][j+k]; 
                   } 
               } 
               if(product>max) 
                   max=product; 

               product=1; 
               for(k=0;k<4;k++) 
               { 
                   if((i+k<20) && (j-k>0)) 
                   { 
                       product*=arr[i+k][j-k]; 
                   } 
               } 
               if(product>max) 
                   max=product; 


           } 
           return max; 
}

來源

2014-02-19 08:45:21

C++ ProjectEuler＃11

回答

相關問題