source: esimerkit/2015k/live/live20/SuurinPolku/SuurinPolku.cs @ 1483

Revision 1097, 2.1 KB checked in by anlakane, 3 years ago (diff)
Line 
1using System;
2using System.Text;
3using System.Linq;
4using System.Collections.Generic;
5using System.IO;
6
7/// @author Antti-Jussi Lakanen
8/// @version 18.3.2015
9///
10/// <summary>
11/// Puun "suurimman" reitin summa.
12/// </summary>
13public class SuurinPolku
14{
15    /// <summary>
16    /// Luetaan tiedosto ja tehdään kutsut.
17    /// </summary>
18    public static void Main()
19    {
20        const string POLKU = @"tree_simple.txt";
21        string[] luetutRivit = File.ReadAllLines(POLKU);
22        int[,] arvot = new int[luetutRivit.Length, luetutRivit.Length];
23        for (int i = 0; i < luetutRivit.Length; i++)
24        {
25            string[] rivi = luetutRivit[i].Split(' ');
26            for (int j = 0; j < rivi.Length; j++)
27            {
28                arvot[i, j] = int.Parse(rivi[j]);
29            }
30        }
31
32        long solutions = 0;
33
34        int maksimi = Maksimi(arvot, 0, 0, ref solutions);
35
36    }
37
38    /// <summary>
39    /// Antaa parhaan reitin summan.
40    /// Laskee rekursiivisesti kaikki ratkaisut.
41    /// </summary>
42    /// <param name="arvot">Luvut</param>
43    /// <param name="rivi">Rivi</param>
44    /// <param name="sarake">Sarake</param>
45    /// <param name="solutions">Tähän asti käsiteltyjen ratkaisujen määrä.</param>
46    /// <returns></returns>
47    /// <example>
48    /// <pre name="test">
49    /// int[,] values = {        {89,  0,  0,  0,  0},
50    ///                         {70,  2,  0,  0,  0},
51    ///                       {39, 49, 87,  0,  0},
52    ///                     {43, 93, 68, 64,  0},
53    ///                   {87, 75, 69, 18, 44}};
54    /// int a =0;                       
55    /// SuurinPolku.Maksimi(values, 0, 0, ref a) === 376;
56    /// </pre>
57    /// </example>
58    public static int Maksimi(int[,] arvot, int rivi, int sarake, ref long solutions)
59    {
60        solutions++;
61
62        if (rivi == arvot.GetLength(0) - 1) return arvot[rivi, sarake];
63
64        return arvot[rivi, sarake] +
65            Math.Max(
66            Maksimi(arvot, rivi + 1, sarake, ref solutions),
67            Maksimi(arvot, rivi + 1, sarake + 1, ref solutions));
68
69        // return maksimi;
70    }
71}
Note: See TracBrowser for help on using the repository browser.