3

だから、これは学校の毎週のプロジェクトで、私はそれを完全に機能させましたが、私がやった方法はおそらくそれを行うための最良の方法の1つではないように感じます(または良い方法でさえありません)。皆さんがそれを最適化するのを手伝ってくれたり、より良い解決策を提供してくれることを願っていました. 私はすでにこのバージョンを提出しましたが、問題に対するより最適な解決策を知りたいです。

というわけで、まずは問題です...

もうすぐハロウィン。ライナスは大かぼちゃを待つために庭に出かけます。残念なことに、今年は庭に他のひょうたんがたくさんあるので、カボチャのパッチがいくつあり、どれくらいの大きさかを伝えるプログラムを作成する必要があります。

このプログラムへの入力は、さまざまな庭園の数になります。各庭の入力の最初の行は庭の寸法、r は庭の行数、c は列数で、0 ≤ r ≤ 40 および 0 ≤ c ≤ 40 です。次元は、各行に c 文字を含む r 行になります。これらの各文字は、正方形で栽培されているひょうたんの種類を表す小文字になります。小文字の「p」はカボチャを表します。行数または列数が 0 の庭は、入力の終わりを示しており、処理されるべきではありません。

入力例:

10 10
pzzzzzzzzp
pyypzzzzzy
ppppssssyy
ssspssssyy
ssssppssyy
ssssppsspy
zzzzzzsspy
zzzzzzsspy
yyyypzsspy
yyyypppppy
3 4
pppp
pppp
pppp
1 7
zzzzzzz
0 0

庭ごとに、庭の数 (最初の入力セットは庭 1)、庭のカボチャ畑の数、カボチャ畑のサイズを最小から最大の順に出力します。特定のサイズのパッチが複数ある場合は、そのサイズを何度でも印刷します。次の形式を使用します。

出力例:

Garden # 1: 4 patches, sizes: 1 4 8 10 
Garden # 2: 1 patches, sizes: 12
Garden # 3: 0 patches, sizes:

注: 問題はファイルから入力するように言っていますが、教授はキーボードから入力するように言いました。

これに対する私のアプローチは、庭をxの境界線で囲まれた2次元配列に入れることでした。次に、関数を使用してカボチャのパッチを見つけます (そしてその座標を返します)。次に、カボチャが上、下、左、右に接続されているかどうかを再帰的に検出し、カボチャ パッチのサイズを返す別の関数を使用します。また、この関数は、カボチャが見つかったときに、各カボチャを「x」に置き換えて「削除」します。これにより、カボチャを何度も見つけることを心配する必要がなくなりました。

これが私のコードです。かなりよくコメントされているので、私がやろうとしていることを理解していただければ幸いです。

#include <iostream>
#include <fstream> 

using namespace std; 

const int MAX_ROW = 41; 
const int MAX_COL = 41; 

char input (); 

int checkForPatchSize ( char arr[][MAX_COL], int numOne, int numTwo ); 

bool findPatch ( char arr[][MAX_COL], int &row, int&col ); 

void sort ( int arr[], int size);

int main () 
    {
    int inputNumOne = -1;  // Defaulted to -1, First number for Patch Size
    int inputNumTwo = -1;  // Defaulted to -1, Second number for Patch Size
    int i, j;      // i, j are indexes for loops, number
    int numArr[MAX_ROW][MAX_COL]; // Array for storing Data
    int indexGarden = 0;  
    int index = 1; 

    while ( inputNumOne != 0 ) 
        {
        cin >> inputNumOne;       // User inputs Dimension
        cin >> inputNumTwo;       // Of Garden...
        if ( inputNumOne != 0 and inputNumTwo != 0 )   // End case is that both are 0. 
            { 
            char pumpkinPatch[MAX_ROW][MAX_COL];   // Array for storing pumpkin patch info. 
            for ( i = 0; i < inputNumOne+2; i++ )   
                {
                for ( j = 0; j < inputNumTwo+2; j++ ) 
                     {
                    // This if statement surrounds the garden in X's so that I have a border (allows me to not have to worry about test cases. 
                    if ( i == 0 or j == 0 or i == inputNumOne + 1 or j == inputNumTwo + 1 ) 
                        {
                        pumpkinPatch[i][j] = 'x'; 
                        }
                    else   // This is the input of the garden into a 2d array.
                        {
                        pumpkinPatch[i][j] = input(); 
                        }
                    }

                }




            int row, col, size, numberOfPatches = 0; 
            bool foundPatch = true; 
            index = 1; 

            while ( foundPatch == true )
                {
                row = inputNumOne+2;  // Because I added a border to the garden
                col = inputNumTwo+2;  // the size is +2 of what the user input. 
                foundPatch = findPatch ( pumpkinPatch, row, col );  // Finds the start of a pumpkin patch, and returns the coordinates ( as row and col ). 
                if ( foundPatch == true ) // If a patch is found....
                    {
                    numberOfPatches++;  // Increase number of patches 
                    size = checkForPatchSize ( pumpkinPatch, row, col); // find size of particular patch
                    numArr[indexGarden][index] = size; // put size into data arr (to be printed to screen later). 
                    index++;  


                    }

                }
                numArr[indexGarden][0] = numberOfPatches; // Put number of patches as first item in each column of data arr. 
                indexGarden++; 


            }

        }

    for ( index = 0; index < indexGarden; index++ ) // Print out Garden Info
        {
        cout << "Garden # " << index + 1 <<": " << numArr[index][0] << " patches, sizes: "; 
        int temp = numArr[index][0]; // temp is the number of patches in particular garden. 
        int tempArr[temp];   // temp array to be used for sorting
        int indexTwo; 
        for ( indexTwo = 0; indexTwo < temp; indexTwo++ ) 
            {
            tempArr[indexTwo] = numArr[index][indexTwo+1];   // Transfer sizes into a temp array so that they can be sorted.    

            }
        sort (tempArr, temp);  // Sort ( Sorts arr from smalles to larges ) 

        for ( indexTwo = 0; indexTwo < temp; indexTwo++ )  // Output sorted array to screen.  
            {
            cout << tempArr[indexTwo] << " "; 
            }

        cout << endl; 
       }
     

     



    }

char input()
   {
    char letter; 
    cin >> letter; 
    return letter; 
    } 
/////////////// findPatch /////////////////////////////////////////////////
// Requirements: a 2D array of garden, and the size of it (row and col). //
// Returns a bool, true if patch is found, false if no patches found.    //
// row and col are returned by reference to be the coordinates of one    //
//  of the pumpkins in the patch.                                    //
/////////////////////////////////////////////////////////////////////////// 
bool findPatch ( char arr[][MAX_COL], int &row, int&col ) 
    {
    int rowIndex = 0; 
int colIndex = 0; 

while ( arr[rowIndex][colIndex] != 'p' and rowIndex < row ) 
    {
    colIndex = 0; 
    while ( arr[rowIndex][colIndex] != 'p' and colIndex < col ) 
        {
        colIndex++;
        }
    if ( arr[rowIndex][colIndex] != 'p' )       
        {
        rowIndex++;
        }
    }

if ( arr[rowIndex][colIndex] != 'p' ) 
    {
    return false; 
    }
row = rowIndex;
col = colIndex; 
return true; 

}

/////////////// checkForPatchSize /////////////////////////////////////////
// Requirements: a 2D array of garden, and the coordinates of the start  //
//                 of a patch.  (Gotten from findPatch)                  //
// Returns an int, which is the size of the patch found                  //
// All p's or pumpkins are changed to x's so that they are not used      // 
//  multiple times.                                                  //
/////////////////////////////////////////////////////////////////////////// 
int checkForPatchSize ( char arr[][MAX_COL], int numOne, int numTwo ) 
{
int index = 0;  


if ( arr[numOne][numTwo] == 'p' ) 
    {
    index++; 
    arr[numOne][numTwo] = '0';

        // Check Above
        index += checkForPatchSize ( arr, numOne - 1, numTwo );

        // Check to Left
        index += checkForPatchSize ( arr, numOne, numTwo - 1 ); 

        // Check Below
        index += checkForPatchSize ( arr, numOne + 1, numTwo ); 

        // Check to Right 
        index += checkForPatchSize ( arr, numOne, numTwo + 1 ); 

    return index; 
    }

return 0;


    


}
/////////////// sort //////////////////////////////////////////////////////
// Requirements: an integer array, and the size of it (amount of         //
//               numbers in it).                                         //
//                                                                       //
// Sorts an array from smalles to largest numbers                        //
/////////////////////////////////////////////////////////////////////////// 
void sort ( int arr[], int size ) 
{
int index = 0; 
bool changeMade = true; 
    
while ( changeMade == true ) 
    {
    changeMade = false;
    for ( index = 0; index < size - 1; index++ ) 
        {
        if ( arr[index] > arr[index+1] ) 
            {
            int temp = arr[index]; 
            arr[index] = arr[index+1];
            arr[index+1] = temp;
            changeMade = true; 
            } 
        }

    }
}
4

1 に答える 1

0

あなたのコードを読んだ後、私はあなたのアプローチを見ます。一般的に、私は視覚的な観点からこれに取り組みます。このままでは、コードは問題なく動作するはずであり、非常に洗練されたソリューションです。アルゴリズムの唯一の弱点は、移動するたびに同じパッチを反復するという事実です。たとえば、上に移動すると、下にチェックされます。冗長性を回避することは、アルゴリズムが最適であることの最も確実な兆候ですが、アルゴリズムを展開する規模が小さいという点では、必ずしも最適である必要はありません。

ある意味で、コードの再帰的な性質は非常に美しいものです。なぜなら、それは消える小さな火花のようにパンプキン パッチを通過するからです。私はそれが本当に好きです。再帰は、主に再帰的に考えないため、気にすることはあまりありませんが、少し時間をかけてアルゴリズムについて頭を悩ませた後、このような場合にその価値が本当にわかります。動的なビジュアルでアルゴリズムが動作するのを見てみたいです。

あなたのアルゴリズムの精度に関しては、アルゴリズムが繰り返される選択されたカボチャの周りに小さな波を作ることによって機能するため、カボチャを正しく数えることが何らかの方法で失敗するとは想像できません。すべてカウントされます。私が言ったように、あなたのアルゴリズムの唯一の欠点は、何らかの方法でカボチャを見つかったとしてマークしないと、無限ループに陥ることです (呼び出し元の位置をチェックします)。それを超えて、私はあなたが優れた解決策を提案し、あなたの疑問はほとんど完全に見当違いであるとしか言いようがありません. 再帰アルゴリズムを使用することは、「カウント」するためにケースの長いリストを必要としないため、この点で優れた選択でした。隣接する位置にジャンプし、フルカウントで自分自身に戻ります。

于 2013-09-25T03:02:49.983 に答える