View Single Post
Old 20-08-2008, 08:55   #94
gugoXX
Senior Member
 
L'Avatar di gugoXX
 
Iscritto dal: May 2004
Cittā: Londra (Torino)
Messaggi: 3692
Riduzione codice e tempi.
Toglo Eratostene, tolgo molti if e aggiusto output.
Mi sa che se non riesco a passare a qualche greedy decente finisco qui.

Codice:
Coordinate: 94,60   - Dimensione 56   - Somma 3185
Time: 297ms
Test: 3185
Codice:
class Program
{
    static void Main(string[] args)
    {
        Matrix mat = new Matrix("Matrix2.txt");
        Stopwatch sw = new Stopwatch();
        sw.Start();
        var toprint = mat.Ex7();
        sw.Stop();

        int x = toprint.Coords.x;
        int y = toprint.Coords.y;
        int z = toprint.Coords.z;

        Console.WriteLine("Coordinate: {0},{1}   - Dimensione {2}   - Somma {3}", x, y, z, toprint.val);
        Console.WriteLine("Time: {0}ms", sw.ElapsedMilliseconds);
       
        int test = mat.Test(x, y, z);
        Console.WriteLine("Test: {0}", test);

        Console.ReadKey();
    }
}

public class Matrix
{
    public int Dim;
    public int[,] Mat;

    public void Save(string fname)
    {
        StreamWriter sw = new StreamWriter(@"C:\temp\" + fname);            
        sw.WriteLine("--{0}--", Dim);
        for (int y = 0; y < Dim; y++)
        {
            for (int x = 0; x < Dim; x++)
            {
                sw.Write("{0} ", Mat[x, y].ToString());
            }
            sw.WriteLine();
        }
        sw.Close();
    }

    public Matrix(string fname)
    {
        Load(fname);
    }

    public Matrix(int[,] vals)
    {
        Mat = vals;
        Dim = vals.GetLength(0);
    }

    public void Load(string fname)
    {
        StreamReader sr = new StreamReader(@"C:\temp\" + fname);                        
        string fline = sr.ReadLine();            
        string mds = fline.Substring(2, fline.Length - 4);
        Dim = int.Parse(mds);
        Mat = new int[Dim, Dim];
        for (int y = 0; y < Dim; y++)
        {
            string line = sr.ReadLine();
            string[] valss = line.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            var valis = valss.Select(t => int.Parse(t)).ToArray();
            Enumerable.Range(0, Dim).ForAll(x => Mat[x, y] = valis[x]);
        }
        sr.Close();            
    }        

    public struct CoordsStruct
    {
        public int x;
        public int y;
        public int z;
        public CoordsStruct(int ix, int iy, int iz)
        {
            x = ix;
            y = iy;
            z = iz;
        }
    }

    public struct Ex2Result
    {                        
        public CoordsStruct Coords;
        public int val;

        public Ex2Result(CoordsStruct ics,int ival)
        {
            Coords = ics;
            val = ival;
        }
    }

    public int Test(int x, int y, int d)
    {
        var dom = from ty in Enumerable.Range(y, d)
                  from tx in Enumerable.Range(x, d)
                  select Mat[tx, ty];
        return dom.Sum();                        
    }                        

    public Ex2Result Ex7()
    {
        int[,][] Compl = new int[Dim, Dim][];   
        for (int y = 0; y < Dim; y++)
        {
            for (int x = 0; x < Dim; x++)
            {
                int mxy = (Dim+1) - ((x > y) ? x : y);
                int[] st = Compl[x, y] = new int[mxy];
                st[1] = Mat[x, y];
                if (mxy > 2) st[2] = Mat[x, y] + Mat[x, y + 1] + Mat[x + 1, y] + Mat[x + 1, y + 1];
                if (mxy > 3) st[3] = st[2] + Mat[x, y + 2] + Mat[x + 1, y + 2] + Mat[x + 2, y + 2] + Mat[x + 2, y + 1] + Mat[x + 2, y];
            }
        }

        Ex2Result rer = new Ex2Result();
        int rerval = int.MinValue;
        for (int z = 4; z <= Dim; z++)
        {
            int mda = (z >> 1);
            int ze1 = z & 1;
            int md = mda + ze1;
            bool ze1u1 = ze1 == 1;
            int dimmz = Dim - z;
            for (int y = 0; y < dimmz; y++)
            {
                for (int x = 0; x < dimmz; x++)
                {
                    int xmda = x + mda;
                    int ymda = y + mda;

                    int cur = Compl[x, y][md]
                               + Compl[x, y + md][mda] 
                               + Compl[x + md, y][mda] 
                               + Compl[xmda, ymda][md];
                    
                    if (ze1u1)
                    {
                        cur -= Mat[xmda, ymda];
                    }                            

                    Compl[x, y][z] = cur;                            
                    if (cur > rerval)
                    {
                        rer = new Ex2Result(new CoordsStruct(x, y, z), cur);
                        rerval = cur;
                    }                        
                }
            }
        }
        return rer;
    }}
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto.
E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test.

Ultima modifica di gugoXX : 20-08-2008 alle 08:59.
gugoXX č offline   Rispondi citando il messaggio o parte di esso